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.