Distributed Mutex

Kyle R. Burton Kyle R. Burton" <mortis@voicenet.com
Tue, 10 Feb 2004 11:43:53 -0700

I've had my ear to the ground on the memcached list for a few months.
The project looks like it works extremely well for it's intended

I have an alternate, but possibly similar, need for functionality for
some of the distributed processing I'm currently working on.  I'm
performing a distributed, parallelized task that requires a
synchronization point on a specific key.  Currently we're using a
table lock in a database (Oracle) as the mutex.  This was a simpler
solution to code, but locks out a large amount of the potential
parallelism we could achieve.

The task involves processing work units and caching the results (into
a database currently).  Each result is assigned an unique result id
(currently from a sequence in the database).  The software's
requirements are such that if two workers produce the same result they
are to both produce output and the output must have the same result

After thinking about it, I remembered memcached.  What I'm looking for
in a distributed mutex may not be that much of an extension to what
memcached is already designed to do.  

There are two modes of mutex that I'd need.  The first is a simple
mutual exclusion based on a key specific to each work unit.  Which
corresponds to the above scenario.  The api for this could possibly be
as simple as:

	int mutex_lock( char* mutex_key, time_t duration );
	int mutex_unlock( char* mutex_key );
	int mutex_lock_nonblock( char *mutex_key, time_t duration );

Where mutex_lock could block until the lock is obtained, and
mutex_lock_nonblock would return an indicator of whether or not the
lock could be obtained.  The duration parameter is a maximum time that
the lock would be held, which could be short-circuited by calling
mutex_unlock before the duration expired.  The duration would be a
maximum expected lock time - so if a lock is obtained, but the worker
that obtained the lock never unlocked it, the lock would be released
and processing could otherwise continue.  This is basically to support
unreliable workers, which is a feature we need.

The second mode I'd be looking for would be for supporting distributed
'distincting' types of operations.  An unique list of all keys would
be built (stored in the server) as processing progressed, where
duplicate additions to the key list would be blocked.  This type of
api could be fairly simple as well, perhaps something like:

  int distinct_list_set_up( char *session, time_t duration );
  int distinct_list_insert( char *session, char *key );
  int distinct_list_tear_down( char *session );

Do you feel that either of these features might be useful extensions
to memcached?  Or are would they just add unnecessary complexity to
memcached and therefore be inappropriate additions?

I look forward to your feedback.

Kyle R. Burton


Wisdom and Compassion are inseparable.
        -- Christmas Humphreys
mortis@voicenet.com                            http://www.voicenet.com/~mortis