Distributed Mutex

[Kyle R. Burton]

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

Polling works, but is, as you have said, an undesirable solution.
Polling doesn't tend to scale with larger numbers of workers - the
'pings' will increase with the number of workers.  Though in most
scenarios, mutex/key collisions should be infrequent.  Also, the poll
frequency basically ends up being designed-in latency in the system,
which is also undesirable for cluster computing where those types of
delays start to add up.

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

That is very interesting, I was unaware of the GET_LOCK/RELEASE_LOCK
functions in MySQL.  They provide a very simple, easy to use arbitrary
mutex system.  Thank you for making me aware of them.  I suppose for
scaling you could do key hashing as the memcached client api does to
support multiple servers...though clients having to know the list of
all servers is also somewhat undesirable.

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

Yes, unique lists of items.  The process is analogous to a 'SELECT
DISTINCT' database operation.  In the cluster environment, basically
the first worker to start processing a given key marks it, then any
other workers that receive that same key as a unit of work should
discard it.  That way only the distinct set of unique (based on the
key) work units is processed.

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

For our purposes, we have a [large] set of work units to be processed.
Part of processing each individual work unit is generating a unique
key based on the content (it is expensive enough an operation that
performance is better if the key generation is farmed out), and then
other calculations are performed on the data.  Once both parts are
finished, the results are accumulated by a central process.

> 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"
> 
> Now:
> 
> "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?

For enumeration yes, but enumeration does not exactly meet my needs.


Thank you for your reply.


Kyle R. Burton

-- 

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