CAS operation

[Dustin Sallings]

[replying back on the list to try to keep the discussion open and  
hopefully avoid repeating myself]

On Sep 8, 2007, at 7:31, Jehiah Czebotar wrote:

> This sounds like the proposed "append" method which would allow
> memcache to handle lists on the server side... with one caviat, you
> want a conditional append which only appends if the value isn't
> already there.

	In this example usage...sort of.  One would also want to remove  
items from the list to keep it from growing out of control.

	There was another proposal to allow updating parts of a value by  
offset or other such things.  None of these things can work race-free  
without implementing advisory locks which, as already pointed out,  
may be subject to the LRU.

> If memcached were handling the lists, you wouldn't have to add all
> that conditional logic and "replace if it's still the same" stuff
> which won't work in high concurrency situations anyway.

	Well, it's not entirely fair to say it doesn't work in high  
concurrency situations.  The operation is always atomic, but it may  
need to be retried.  This is a common strategy in concurrent  
programming for creating lock-free concurrent data structures.  If a  
particular key is too hot, though, you could potentially split it  
into multiple keys to reduce retries in practice.  In the current  
example, you could have a series of current_login keys hashed by  
uid.  Your contention is reduced by the number of keys.  There's  
never a case where you blindly overwrite values, though.

	Adding an add-this-to-a-list-if-it-does-not-exist-and-remove- 
something-else-to-keep-the-list-to-n-elements would be an  
unreasonable operation to add.  The only reasonable way to do  
something like this would be to add server-side scripting and then  
effectively write the exact operations you need so that they may be  
performed atomically.

	Are there enough potential server-side operations to really justify  
a scripting interface?  When it's been brought up in meetings, the  
response has varied from interest, to a warning about crossing  
streams or something.

	Both a CAS and a scripting interface provide a foundation for  
building atomic data structure manipulation without having to define  
all of the data structures and all of the operations at the protocol  
level.  Each has downside.  With CAS, you may have to retry a few  
times under contention and this would be amplified by the latency.   
With scripting, you may easily slow down the whole server, and you  
have to deal with how parameters are passed in and results are  
returned -- and this would mean very different things by protocol.

-- 
Dustin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.danga.com/pipermail/memcached/attachments/20070908/cd92bcee/attachment.html