Tag Archives: Computer Science

A Distributed Reentrant Read-Write Lock Using a Hazelcast Data Grid

Most Java programmers are familiar with the java.util.concurrent package and some of the handy things in it like ReentrantReadWriteLock. To recap, a ReadWriteLock solves the “Readers-Writers Problem” in computer science.

A read-write lock allows for a greater level of concurrency in accessing shared data than that permitted by a mutual exclusion lock. It exploits the fact that while only a single thread at a time (a writer thread) can modify the shared data, in many cases any number of threads can concurrently read the data (hence reader threads). In theory, the increase in concurrency permitted by the use of a read-write lock will lead to performance improvements over the use of a mutual exclusion lock. – JavaDocs, JSE 7

Additionally, a ReentrantReadWriteLock, allows any thread to acquire the same lock more than once.

This lock allows both readers and writers to reacquire read or write locks in the style of a ReentrantLock. Non-reentrant readers are not allowed until all write locks held by the writing thread have been released.

Additionally, a writer can acquire the read lock, but not vice-versa. Among other applications, reentrancy can be useful when write locks are held during calls or callbacks to methods that perform reads under read locks. If a reader tries to acquire the write lock it will never succeed.- JavaDocs, JSE 7

It would be nice to have the same semantics available to control concurrent access to resources in a distributed application, but the only implementations I’m aware of are heavy-weight (.e.g. Apache Zookeeper Shared Reentrant Read Write Lock Recipe.)

Hazelcast’s distributed in-memory data grid, on the other hand, is lightweight and easy to use. Drop a jar file into your application and off you go. Hazelcast includes distributed implementations of Maps, Lists, Queues, etc. as well as Semaphores, Locks and AtomicLongs. It seems we should be able to implement the synchronization we want using some of these distributed collections and concurrency primitives.

This blog post provides a good starting point for how to implement a ReadWrite lock using two semaphores. Though it explains the concept simply, it has two deficiencies. First, writers may starve while readers hog the lock. Second, it isn’t re-entrant. The first problem can be solved, as the blog author notes, using a third semaphore. This article (PDF) illustrates how to solve the “writers-preference” problem using a third semaphore. To make it work, though, we’ll have to replace those counters with distributed AtomicLongs.

That’s great for a non-reentrant ReadWrite lock, but what about a reentrant one? An algorithm to prevent deadlock and allow strongly reentrant usage (writers can acquire nested read locks) is explained in “Reentrant Readers-Writers” (PDF). It requires the use of a monitor–which in Java means a Lock and associated Condition–and involves keeping a per-thread count of nested locks. For the latter, I stash the count in a ThreadLocal. There are a couple of other niggly bits involving a distributed counter and a distributed boolean (which we’ll fake with an AtomicLong.)

The end result is two types of distributed locks, implemented using Hazelcast’s ISemaphore, ILock, ICondition and IAtomicLong. The only further complication is the desire to abstract the grid implementation being used (mostly useful for testing, since I know of no other grid technology that provides the data structures required here.) I use a DistributedDataStructureFactory and a DistributedLockFactory to solve those problems, as well as some helper interfaces and wrapper classes to compensate for the fact that in java.util.concurrent, Semaphore and AtomicLong are concrete classes.

Assuming you have a HazelcastInstance, usage is identical to usage of java.util.concurrent.locks.ReentrantReadWriteLock, with the exception of creation of a new lock instance.

// This can be a singleton, but additional instances aren't a problem.
DistributedLockFactory lockFactory =
    new DistributedLockFactory(new HazelcastDataStructureFactory(hazelcastInstance));
 
ReadWriteLock lock = lockFactory.getReentrantReadWriteLock("myLock");
lock.readLock().lock();
try {
    // do some stuff
}
finally {
    lock.readLock.unlock();
}

The full package, with both types of locks, helper classes, unit and integration tests has been released under the Apache 2.0 license by kind permission of my employer ThoughtWire Corporation. You can find it on GitHub here: https://github.com/ThoughtWire/hazelcast-locks

 
Update: June 13, 2014.
Shortly after releasing the first version of this package, I discovered an additional wrinkle, namely that each lock operation must deal very carefully with thread interruption so as not to leave any data structures in a state which could lead to deadlock of other threads or nodes. Specifically, all operations that call blocking methods (such as Semaphore.acquire() or Condition.await()) must catch any thrown InterruptedException and restore the lock’s original state before setting the thread’s interrupted status and returning. In practice, this is quite messy to do (!) and a worthy improvement would be to find a way to tidy it up. For the gory details on proper handling of task cancellation, see Goetz et al, “Java Concurrency in Practice, 2nd edition” (specifically, Chapter 7.)