Atomic replace and append operations

[Richard Cameron]

I'm making some good progress on this. I've added support for "append" 
which was fairly straightforward and seems to work, as well as partial 
support for "areplace" which still needs some more effort. I've also 
patched libmemcache to let it speak these two commands.

Aside from a few minor bits and pieces I need to do before releasing a 
patch, the biggest issue I've got at the moment is that I can take a 
clean, unhacked copy of memcached, run it up, and say:

[set x "hello"]
[delete x]

very quickly followed by

[add x "world"]

I get a "NOT_STORED" error back. This is not what I'd expect to happen. 
On the other hand, if I give it a few seconds between the "delete" and 
the "add", it seems quite happy. There's obviously some issue with 
objects living in a zombie "deleted" state but not being freed causing 
confusion. There are a few odd bits of code which look like they might 
be covering up a more fundamental problem, for example:

         if (old_it && (old_it->it_flags & ITEM_DELETED) && (comm == 
NREAD_REPLACE || comm == NREAD_ADD)) {
             out_string(c, "NOT_STORED");
             break;
         }

Unfortunately doing the semi-obvious thing with that doesn't seem to 
solve the problem. Can anyone give me any pointers on what I need to do 
here?

Richard.


On 18 Mar 2005, at 14:40, Gregory Block wrote:

> I'd second these additions - I've been waiting with a similar kind of 
> need for some time, and would be very happy to see this added.
>
> On 18 Mar 2005, at 13:55, Richard Cameron wrote:
>
>>
>> I'm interested in implementing two extra storage commands "areplace" 
>> and "append" for memcached. The former would behave exactly like 
>> "replace", but would return the object's value before it performs the 
>> replace operation; the latter would simply string append the new 
>> value onto the old one.
>>
>> The motivation is not purely to add extra bloat to memcached but 
>> rather to provide the minimal extra operations I'd need to be able to 
>> keep track of dependency trees in the cached data.
>>
>> For instance, if I want to cache objects A and B (the results of two 
>> SQL query, say) which depends on some "thing" in the database (like a 
>> particular user U's account), I'd like to be able keep track of my 
>> dependencies like this:
>>
>> U -> A,B
>>
>> Memcached itself seems like a good choice to store this list. So, 
>> when user U does something to his account, I'll want to delete the 
>> newly defunct objects from the cache. I think the best I can do at 
>> the moment is:
>>
>> my_deps := [get U]
>> foreach dep $my_deps:
>> 	[delete $dep]
>> [set U ""]
>>
>> Also, if I perform another cacheable operation C which depends on U, 
>> I'd like to be able to add this dependency to my list. The existing 
>> protocol lets me say:
>>
>> old_deps := "get U"
>> new_deps := append(old_deps, C)
>> [set U $new_deps]
>>
>> The trouble, of course, is that there are race conditions in both 
>> cases where multi-threaded code could execute in a way which would 
>> corrupt the dependency list.
>>
>> On a single machine, I can simply guard the critical section in the 
>> client code with a mutex, but this won't work on a distributed server 
>> farm. It would be possible to use memcached's existing "incr" and 
>> "decr" operations to produce a "global" mutex, but this is a) not 
>> terribly efficient, and b) dangerous if one server incr's the 
>> semaphore on entry to the critical section but crashes before it 
>> exists - this would break things such that no machine could 
>> subsequently update the dependency and we'd be stuck in that state 
>> for good.
>>
>> So, my proposed solution is to implement an "areplace" (atomic 
>> replace) operation which looks like this:
>>
>> my_deps = [areplace U ""]
>>
>> and and append operation which looks like this:
>>
>> [append U " C"]
>>
>> I could then keep most of the bloat in the client library, not the 
>> server. This approach also has the advantage of being able to track 
>> dependencies over multiple memcached instances.
>>
>> This is probably bending memcached's intended use slightly, but I 
>> think it still adheres to the basic principle that it's a cache: all 
>> the data can be regenerated from the database if required. The 
>> advantage is that I can immediately tell when data should be marked 
>> as being invalid, which means I can use much longer cache times 
>> which, in turn, means that the cached items in the "long tail" 
>> (object which get accessed infrequently but are expensive to compute) 
>> can have much higher hit rates.
>>
>> Seem at all sensible? I'd be interested in any comments before I go 
>> away and code this up.
>>
>> Richard.
>>
>