CAS operation

[Dustin Sallings]

On Sep 8, 2007, at 0:38, dormando wrote:

> Sorry.. Could I perhaps get an example (to the list is fine) of a  
> condition this fixes? Having a hard time thinking it through.

	Yeah, I almost wrote more, but I've been typing too much lately.

	In the earlier question about how to track recent users on a site,  
one could imagine a list of active users in a form like:

	uid1,uid2,uid3,uid4,uid5,...

	To ensure the current user is in the list, you could do something  
like this:

	get(s) the current value for the uid list
	check to see if you're in it.  If so, you're done.
	If not, adjust the list appropriately and cas in the new list

	There are three points for failure:

	1)  gets fails -- add || try again
	2)  cas fails (not found) -- add || try again
	3)  cas fails (exists) -- try again

	The CAS provides the ``only replace this object iff I know the  
value'' functionality that prevents race conditions for arbitrary  
mutations.

	You could, for example, implement a client-side incr with a CAS if  
the server-functionality didn't exist.  Obviously, it's two (or more  
depending on contention) round trips instead of one, but it seems  
like a pretty good building block.

> Thanks,
> -Dormando
>
> Dustin Sallings wrote:
>>     I just prototyped a pair of operations for implementing CAS in  
>> memcached.  This provides atomic updates of arbitrary objects  
>> without having to rely on locks.
>>     The idea is that every object will have some unique 64-bit  
>> value that can be retrieved with a new command (I called it  
>> ``gets'' for some reason).  This value needs to be unique and  
>> consistent for a given value within memcached.  It can be a  
>> counter or memory address or whatever.
>>     After doing a ``gets'' for a key and getting a response, the  
>> client can manipulate the data structure as fit, and use a ``cas''  
>> operation to put it back iff it has the same value as retrieved  
>> (based on the identifier).  It returns a ``NOT FOUND'' error when  
>> there's no value for the key (and then you can try it with an  
>> ``add''), or ``EXISTS'' when the identifier does not match (and  
>> then you can try again from the ``gets'').
>>     Opinions?
>
>

-- 
Dustin Sallings