AppEngine Memcache atomic get-and-delete

Question

I would like to store authentication challenges in Google AppEngine's Memcache that I index by a random integer. So, for example I have entries like:

 5932 -> IUH#(*HKJSBOHFBAHV&EG*Y$#)*HF739r7fGA$74gflUSAB
11234 -> (*&YGy3g87gfGYJKY#GRO&Fta9p8yfdlhuH$UT#K&GAk&#G
-3944 -> 8yU#*&GfgKGF&Y@dy;0aU#(Y9fyhgyL$BVGAZD(O$fg($&G
   .
   :

If a client then tries to authenticate a request, it will send me the challenge ID (e.g. -3944) and the corresponding calculated response.

Now, my server needs to grab challenge number -3944 out of the list and mark it used or (better yet) delete it immediately to prevent replay attacks (a second request being authenticated with the same challenge). Then, the server calculates what the response should have been and accepts or rejects the authentication based on a (mis-)match.

For performance and quota reasons, I would like to avoid having to use the DataStore for the challenges. I will have a system in place that allows the client to request more challenges and retry the request, so that the rare cases where Memcache gets purged aren't going to be an issue either.

Is there a way to do an atomic get-and-delete operation in Memcache, that will return the entry for a given key exactly once and return null for any request for the same key after (unless it has been set again)? It should also return null for any keys that were never set.

PS: I'm using Java.

Answer 1

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

1. 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.

2. 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.

Answer 2

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):

1. delete:                 deletes an entry and returns whether it existed
2. increment:           increments an entry and returns its new value
3. put:                      puts an entry and returns whether it existed (if used with the right policy)
4. 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.