Explain, thoroughly, at a high level, how wildcard flushing is supposed to work.

subscribing

The logic was just optimized, and I added comments inline in the process. It should be easier to follow along with the logic now.

We track wildcard flushes by incrementing a simple counter named for the table and cid being flushed, and update a global object tracking for each table the lengths of each cid that has been wildcard flushed. As memcache is a hashtable, we can't efficiently find all matching items.

Then, at get time we check for matching wildcard flushes. Say we're doing a cache_get on 'foo' from the 'bar' table. If someone flushed 'f*', 'fo*', or 'foo*' since our item was cached, then we know our cached object is stale. We check the global object to determine which cid lengths we even need to bother looking up, skipping those that couldn't possible have been flushed, and doing a getMulti on the rest.

We also check for matching wildcard flushes when storing an item. We simply take a sum total of all matching wildcard flushes, and store that within the cache object. This is how we know the difference between old wildcard flushes and flushes that have happened since we stored out item.

Subscribing, I've spent a fair bit of time with this now. Jeremy's explanation is good.

Subscribing.

I started a handbook section for memcache to make the main project page a bit tidier - http://drupal.org/node/1131458

That would be a good place to add this.

Note we are still tweaking this a bit, so there might be some slight changes to the implementation.

Also I am starting a push to remove wildcard prefix clears in Drupal 8 and replace it with a 'tags' system at #636454: Cache tag support - the current wildcard logic should adapt really well to tags, but that's even more of a reason to document it.