Feature request: Atomically check and delete a specific value

[Sophos-Elias-Vasylenko]

Proposal for a cache.Unset(key, value) operation that atomically deletes a cache item only if it matches the given value.

Often an entry in a cache becomes invalidated for some external reason and needs to be cleared. When this happens we call Delete(key).

But when we call this we don't actually know whether we're deleting the right thing. If there are multiple consumers all trying to call delete this is racy, someone may have recreated the cache item with a fresh value in the meantime.

// say this is a high-load service, there are many concurrent callers to this function
token := cache.Get(key, withLoader(loader)) // the token is present in the cache but it is bad!
result, err := fetchFromApi(token.Value()) // this is a slow call, so lots of in-flight requests using the bad cached token
if err != nil {
  cache.Delete(key) // the first request to get here deletes the bad token from the cache. In the meantime, lots more requests are arriving, and lots more failed requests are reaching this point, so we can get a stampede where the cached token is repeatedly refreshed and deleted a hundred times.
}

The above is just the naive approach. It's obviously possible to mitigate the problem by doing another get before the delete to make sure the cache value is still what we expect. Or to eliminate the bug entirely by manually synchronising around deletes/gets. But the cache already has a mutex, I'd rather not waste energy reproducing that functionality on top of the cache.

I feel like 90% of the time that you're calling Delete, you really ought to know what it is that you're deleting, and you don't want to just kill whatever happens to be there at the time. Really it's something like cache.Unset(key, value) that you should be doing instead. Even the built-in GetAndDelete is broken because it doesn't do this.

There is also #72 which would solve this more generally, but I don't know the appetite for resolving that ticket. And if that's not on the roadmap I'd argue that this deserves to be a primitive operation anyway.

[davseby]

Yeah, that is a great idea, I think in general this strategy is called 'Optimistic Locking'.

Since we assign a version attribute to all of our items, I'd suggest to operate on it instead of comparing the values. We should expand upon this idea and add a similar functionality to Set method as well. The new methods could be called something along the lines Versioned* or Optimistic* (e.g. VersionedDelete(k Key, version uint64) bool). @swithek what do you think?

It should be easy to implement and in some scenarios way less expensive than locking the whole cache as suggested in the #72.

[davseby]

@Sophos-Elias-Vasylenko

Would this implementation be of use to you? #170