Perform atomic array modification in memcache

Question

Suppose you want to keep an list of the last 10 visitors to your site in memcache.

Every time that someone accesses your site, you want to push them onto an array and shift off the first visitor in the array.

Of course, a potential problem is that multiple visitors could be overwriting and reading this array at the same time, possibly tripping each other up. There isn't an atomic push/shift in memcache, of course.

Possible inconsistency scenario with 2 near-simultaneous user accesses:

1. User A gets array from memcache
2. User B gets array from memcache
3. User A modifies array (change will be lost)
4. User B modifies array
5. User A stores array in memcache
6. User B stores array in memcache (will overwrite A's change in step 3)

How can you accomplish something like this correctly using memcache?

Answer 1

Using CAS tokens. See: http://github.com/memcached/memcached/blob/master/doc/protocol.txt See for instance in the PHP implementation. It could be up to the 'losing' process' job to fetch the new data and determine what to do with the modification of the winning process.

Answer 2

We built CAS for this.

1. User A gets array
2. User B gets array
3. User A changes array
4. User B changes array
5. User A CASes in array -- wins
6. User B CASes in array -- loses
7. User B repeats from 2