Category Archives: Computer Science

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.)

New Direction: Computational Biology

After an absurdly long job search, I’ve finally found myself a comfortable place in a computational biology lab. I’ve been here a bit more than a month and thought I should mention something about what I’m doing.

I’m working for Dr. Michael Brudno in the Computational Biology Lab at the University of Toronto. At the moment, I’m developing an application for visualization and analysis of biological sequence and annotation data with a graduate student named Marc Fiume. (We just chose a name for our project today: SAVANT. I like it.) I’m also sitting in on a graduate seminar on analysis of high throughput sequencing data and attending the occasional presentation on related research at The Centre for Applied Genomics. I’ll be spending one day a week at Sick Kids hospital, in order to interact with biologists and bioinformaticians who are among the target users of SAVANT.

I’m having a great time.

This is all a huge change from the enterprise web development that is more or less what I’ve been doing since 1996. A huge change that I really needed. Sometimes you just need to start over, you know? It was getting to the point where I honestly couldn’t picture myself actually taking any of the jobs I was applying for. I couldn’t face the same-old, same-old any longer.

I’m not sure where this is all going to lead, but I’m kind of hoping to make a career in this relatively young field. I believe that my many years of experience in commercial software engineering will be useful here. I think I can have fun and make a difference. The territory is huge; the problem space practically inexhaustible. I can’t imagine getting bored any time soon. Heading off in a new direction feels exactly right. So work-wise right now, it’s all good. :)

Loosely-Coupled Actors: In Brief

Actors are a popular way to write concurrent & distributed programs. Immutable messages are passed between actors which do the required processing, avoiding the difficulties inherent in sharing data among threads/processes.

Tuplespaces (best exemplified in current times by JavaSpaces) are a way to decouple cooperating processes by using pattern-matching to share immutable and persistent data objects.

Many distributed algorithms can be modelled as a flow of objects between participants.

JavaSpaces(TM) Principles, Patterns, and Practice

Or, if you prefer, substitute “parallel” for “distributed” and “messages” for “objects”.

So what do you get if you combine the pattern-based communication of tuplespaces with the message processing paradigm of actors? Loosely-coupled actors.

Actually, as I see it, you get two things:

  • An easier way to write tuplespace programs: the actor DSL provides a formalism for describing reading, writing, and consuming of tuples and the behaviour associated with these operations.
  • Pattern-based communication between actors with no explicit reference to each other: actors are decoupled in both (address)space and time (since messages are persistent objects.)

In both cases, a (hopefully) better way to write concurrent programs.

To the best of my knowledge, no one has tried this yet.

Note: I wrote a longer piece on this topic yesterday with more explanation and references. For those wanting a little more…

Loosely-Coupled Actors

Recently the growing concern with effective use of multicore processors and the subsequent popularity of the actor model came together with my desire to do a project in Groovy. Adding to the mix, I had an in-JVM tuplespace library in Java I’d never released because it seemed thread co-ordination was just not enough of a big deal. Now, with the need to simplify and promote good multi-threaded programming practices, I thought it might be worth translating it into Groovy as a learning exercise (I’m new to Groovy) and releasing it as open source.

But the actor model and tuplespaces kept getting mixed up in my head. Like chocolate and peanut butter, I just wanted them both at the same time. What I really wanted was loosely-coupled actors.

Actors

The actor model uses the passing of immutable messages to avoid the problem of shared state in concurrent and parallel programs. This is a gross oversimplification, but a deeper discussion is beyond the scope of this post. If you want a better explanation, this two-part article (part 1, part2) by Alex Miller really helped me out. (Don’t let the Erlang stuff in Part 1 turn you off, he gets to Scala, Java, and Groovy eventually.)

Tuplespaces

In a tuplespace–again grossly simplified–there are no shared variables, but there is a shared data space filled with immutable objects. These objects are accessed not by address, but by their contents. A tuplespace is an associative shared data store. These objects, or tuples, can be thought of as messages. They are matched by templates inserted into the space by other components or processes, rather than delivered to a named end-point. A tuplespace is a realization of the “generative communication model” because messages are first-class, shared objects. But in this model communication is uncoupled rather than point-to-point.

Digression: Assembly by Diffusion

A passage in Manuel Delanda’s Intensive Science & Virtual Philosophy, does something to explain why I am so attracted to spaces as a communication mechanism. It’s not an exact analogy, by any means, but it gives a flavour of the “open combinatorial spaces” that the generative communication model creates. Here’s an excerpt:

[Biological assembly] permits the transport processes not to be rigidly channelled, using simple diffusion through a fluid medium to bring the different parts together. Components may float around and randomly collide, using a lock-and-key mechanism to find matching patterns without the need for exact positioning.

I think that’s a pretty fair description of “loose coupling”: no rigid channels; no exact positioning; parts brought together by pattern matching. Tuplespaces would seem to act like the aforementioned fluid medium, allowing components to work together in an almost organic manner.

ActorSpaces

Agha and Callsen describe the idea of an ActorSpace. Have I finally found what I’ve been looking for? Well… not quite. Agha and Callsen do recognize the importance of “pattern-based communication between processes which have no explicit reference to each other” for open distributed programming. However, they chose to base their pattern matching on attributes of actors themselves. This introduces a new element to the actor model–attributes–and it is not entirely clear what these attributes might be or how to use them to abstract communication. Interesting paper, but it doesn’t quite scratch my personal itch.

Tuplespaces + Actors

Many distributed algorithms can be modelled as a flow of objects between participants.

JavaSpaces(TM) Principles, Patterns, and Practice

We could as well substitute “parallel” for “distributed” and “messages” for “objects”.

Considering the quote above, the actor DSL provides a way to define the “participants”, describe their behaviour, and manage their lifecycle. The tuplespace operations provide the pattern-directed flow of messages.

The result is:

  • An easier way to write tuplespace programs: the actor DSL provides a formalism for describing reading, writing, and consuming of tuples and the behaviour associated with these operations.
  • Pattern-based communication between actors with no explicit reference to each other: actors are decoupled in both (address)space and time (since messages are persistent objects.)

In both cases, a (hopefully) better way to write parallel programs.

So the bottom line of all this is that my little Groovy tuplespace project is trying to grow into something more: using a tuplespace paradigm to provide pattern-matching based on messages and processing of these messages by actors: loosely-coupled actors.

Genetic Programming Example in JavaScript

While researching genetic programming as one possible way to discover near-optimal solutions to the Travelling Salesman Problem (TSP), I came across this cool interactive demonstration of genetic programming using JavaScript. I found myself playing with it for a good while, enjoying watching the solutions evolve and converge under different fitness constraints.

The page itself doesn’t provide much information on what’s going on, but you can get a quick overview of genetic programming here. For deeper investigation, try genetic-programming.org, a site maintained by John Koza, one of the major figures in genetic programming research. There are links to all sorts of resources including all of Koza’s publications, many of which are available online.

First Woman Turing Award Winner: Frances Allen

It only took 40 years, but a woman has finally been selected as the A.M. Turing Award Winner for “pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution.” Allen was also the first woman to be appointed an IBM fellow (1989). More info on Frances E. Allen…

Also discovered serendipitously: “The Invisible Women of Science and Technology”.

Grokking Duck Typing

To make a long story very short: I spent many years programming large systems in C. If I had declared every function like this:

void *foo(void *arg,...);

everyone would have thought I was nuts (not to mention a really terrible programmer.) This is the nutshell version of why I don’t think I will personally ever understand the appeal of duck typing.

Having said that, I will probably make one more attempt to learn Ruby. I liked some of Ruby’s structures, it was just the duck-typing thing I couldn’t grok. I’ll give it one more try and maybe I’ll see what all the fuss is about this time. If not, at least I can honestly say I tried…