Distributed Mutex

Brad Fitzpatrick brad@danga.com
Wed, 11 Feb 2004 20:19:09 -0800 (PST)

I've thought about the mutex case myself (wanting it for LJ) but each time
I realize memcached already provides enough primitives to build that API
on top of it.

(well, sort of)

The idea is you use the "add" command to set a key (mutex name) to some
value.  The add command returns "STORED" or "NOT_STORED", but it's atomic,
so two callers won't both pass.  Then your app can just poll (re-trying
the lock once a second) until it gets it.  And when it's done, die.

Now, this is lame for a couple reasons:

-- it polls.

-- the key/value pair in memcached you're using as your mutex state
   could be pushed out of memory.  there's no way to pin items
   inside memcached.  (that'd be easy to add, though)

-- if the client dies before unlocking the mutex, it's never unlocked.
   (except of course by time).

A better solution (if you need something quick) is run a bunch of MySQL
servers and use GET_LOCK() and RELEASE_LOCK() which have the semantics you
want already, and is Free.  (unlike Oracle)

I don't quite follow your second need, but it sounds like you're just
trying to build lists of items?  You can already do that with memcached as
well... no changes should be necessary.

You just want to build named sets you can enumerate?  (a set is a bag
with the constraint that items are unique)

Just use keys, say:

<set_name>_items = 2
<set_name>_item_1 = key_foo
<set_name>_item_2 = key_bar
<set_name>_key_foo = <ANY DUMMY VALUE, even 0 bytes>
<set_name>_key_bar = <ANY DUMMY VALUE, even 0 bytes>

Now, to add to a set:

"add set_name_key_baz 0 0 0 ... "

if it returns "NOT_STORED", the item is already in the set.  if it returns
"STORED", then do:

"add set_names_items = 0"  (initialize the item count)
"incr set_name_items"      (increment the item count)

Now, "incr" command returns the new value.  So say it returns "3"


"set set_name_item_3 = key_baz"

(pseudo protocol talk above)

So yeah, you can already do that.  The only concern, again, is items
falling out.  Maybe we need an attribute (or server-global setting) to not
dump items.

Would that be sufficient?

On Tue, 10 Feb 2004, Kyle R. Burton wrote:

> 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
> purpose.
> 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
> id.
> 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
> ------------------------------------------------------------------------------