Distributed Semaphore (Lock) with memcached

Hi, today I want to show a simple technique how to build a synchronization primitive when you have compare-and-swap operation (in fact you can apply those technique to Mongo or Zokeeper and get the semaphore backed by Mongo or ZooKeeper, actually I really like ZK-based locks and semaphores since there is a built-in notification for value changes).
!!! Note, that the code I provide is just for demonstration purposes it's not production-ready. Please do not use these distributed semaphores as is.

Memcached samples

Before going exactly to distributed semaphore I'd like to show some samples on how to use memcached (check the tests directory).

There are several tests covering those areas:

• Storing primitives in memcached
• Retrieving and updating using (inc/decr, set)
• Appending and prepending of values to different types (String, numeric types)

There is another test I'd like to mention. Fibonacci service - I've implemented a recursive fibonacci to show how to cache returning values of method using Simple Spring Memcached. The class is automatically wrapped to a Proxy object using Spring AOP / Aspect J. And all the returning value of methods are cached to avoid further calculations with the same parameters. 

Note that there is no caching the method of the object is called recursively - that's why for method apply0(...) I'm caching values directly. It's only done for demonstration - while SSM annotations is a good approach, direct manipulations with cache withing the business logic code - the thing that's better to be avoided. 

Memcached-backed Semaphore

The idea behind all the semaphores is simple - you just try to aquire the resouce (countDown) if there are some available. To avoid race conditions the Compare-and-Swap operation should be used. 

Compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value (wikipedia). 

Memcached provides built-in support for CAS operations - that's why we are able to implement a semaphore: we are trying to CAS value until succeed. :)

I'm using SpyMemcached library to work with memcached server. The library provides it's own concept to work with CAS operations called Mutator/Mutations. Actually it's quite good, but it's unable to instruct to break the retries cycle, so I ought to throw an exception.  

I've implemented two versions of Semaphores which are compatible (they can be used together to work with the same memcached piece of memory): 

• Basic (that is based on memcached CAS primitive)
• Mutator-based (based on SpyMemcached concept of Mutator/Mutation)
• PriorityBasedWithParking (the order of execution is determined by threads priority, unlike previous 2 semaphores the aquire operation parks the thread and stops the execution until lock is acquired). 

So how do we aquire lock: 

1. Check that there is free room for you. Remember the space availabe(N).
2. Try to CAS the N-1, N
3. If 2 is unsuccessful: either park thread until notified and then go to 4 or go to 4 without parking
4. Retry step 1 without parking. 

I would like to talk a bit about PriorityBasedWithParking implementation. This semaphore parks the thread if it fails to acquire and then unparks it when a certain condition occurs (two other semaphores do not park at all and just return true or false).

There is a weak place here - stateChanged() method. In current implementation this method doesn't notify all the JVM's that are waiting for change notification. This means that the Semaphore is not shared (it is shared, but the waits might be long since notifications are not propogated to all the semaphores). In order to minimize the lock time and make the Semaphore truly shared, it's better to use notifications with JMS or Akka, or subscribe to value changes by replacing Memcached with CouchDB. 

That's all. Enjoy distrbuted locking with Memcached. :)