AppEngine Memcache atomic get-and-delete

Question 1

After sleeping on it for a night, I came up with a couple of approaches. Neither one of which is particularly elegant, but let me put them here as food for thought:

MemCache does offer (at least) 4 commands that atomically modify an entry in some way and return some information about its previous state (two of them were pointed out by @Moshe Shaham as well):

delete: deletes an entry and returns whether it existed
increment: increments an entry and returns its new value
put: puts an entry and returns whether it existed (if used with the right policy)
putIfUntouched: puts an entry if it still matches an expected state (returns whether it did)

Let me provide a possible implementation for each of them. The first 3 will be specific to integer keys and will require that the actual entries have a positive key (as they will use the corresponding negative key as a marker-entry).

Note: The examples given below are conceptual in nature. Some of them might still allow for race-conditions and I haven't actually tested any of them. So, take them with a grain of salt.

Here goes:

1. delete

When first storing the entry, store a marker along with it (with a derived corresponding key). Gate the get-and-delete based on the success of an attempt to delete this marker.

public void putForAtomicGnD(MemcacheService memcache, int key, Object value) {
    assert key>=0;
    memcache.put(key, value);    // Put entry
    memcache.put(-key-1, null);  // Put a marker
}

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (!memcache.delete(-key-1)) return null;  // Are we first to request it?
    Object result = memcache.get(key);          // Grab content
    memcache.delete(key);                       // Delete entry
    return result;
}

Possible race-condition: A putForAtomicGnD might overwrite a value that is in the process of being read. Can be avoided by using ADD_ONLY_IF_NOT_PRESENT policy for put and millisNoReAdd for delete.

Possible optimization: Use putAll.

2. increment

Have a read-counter associated with each entry that gates get-and-delete.

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (memcache.increment(-key-1, 1L, 0L) != 1L) return null; // Are we 1st?
    Object result = memcache.get(key);                         // Grab content
    memcache.delete(key);                                      // Delete entry
    return result;
}

Note: As shown here, this code only allows every key to be used once. To re-use, corresponding marker needs to be deleted, which leads to race-condition (again resolvable via millisNoReAdd).

3. put

Have a read-flag (non-existence of marker entry) associated with each entry that gates get-and-delete. Essentially the inverse of approach "1. delete".

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (!memcache.put(-key-1, null, null, SetPolicy.ADD_ONLY_IF_NOT_PRESENT))
        return null;                    // Are we 1st?
    Object result = memcache.get(key);  // Grab content
    memcache.delete(key);               // Delete entry
    memcache.delete(-key-1, 10000);     // Delete marker with millisNoReAdd
    return result;
}

Possible race-condition: Another put might overwrite a value that is in the process of being read. Again, resolvable with use of millisNoReAdd.

Possible optimization: Use deleteAll.

4. putIfUntouched

My current favorite: Try to get an entry and set it to null in a simulated transaction and use success of that to gate delete.

public Object atomicGetAndDelete(MemcacheService memcache, Object key) {
    IdentifiableValue result = memcache.getIdentifiable(key);
    if (result==null) return null;                     // Entry didn't exist
    if (result.getValue()==null) return null;          // Someone else got it
    if (!memcache.putIfUntouched(key, result, null)) return null;  // Still 1st?
    memcache.delete(key);                              // Delete entry
    return result.getValue();
}

Note: This approach is almost completely general (no restrictions on key-type) as it does not need to be able to derive a key for a marker object from the given one. The only restriction it has is that it does not support actual null-entries as this value is reserved to denote "entry already taken".

Possible race-conditions? I don't currently see any, but maybe I'm missing something?

Possible optimization: putIfUntouched with immediate Expiration (find out how here!) instead of delete.

Conclusion

There seem to be a bunch of ways to do this, but none of the ones I've come up with so far look particularly elegant. Please use the examples given here primarily as food for thought and let's see if we can come up with a cleaner solution, or at least convince ourselves that one of the ones above (putIfUntouched?) will actually work reliably.

Question 2

you have two mechanisms built into memcache in order to manage concurrency and race conditions:

increment: you can build a mechanism around this atomic increment function. simply increment a counter when you start working on a value, decrement when you finish, and don't allow any other thread to work while the counter is incremented.
putIfUntouched: this function won't allow you to change the memcache value if it was changed since you read it. it will return false in that case.