[ZODB-Dev] Memcache or ZEO cache (Re: ZEO and relstporage performance)

[Shane Hathaway]

Shane Hathaway wrote:
> RelStorage currently uses memcached in a very simple way: it puts (tid, 
> state) in the cache for each oid.  When RelStorage reads from the cache, 
> if it gets a state for a different transaction than the transaction ID 
> last polled by the storage instance, RelStorage discards the state from 
> the cache and falls back to the database.  That means most of the cache 
> needs to be revalidated after every commit. :-(  The strategy should 
> work well for databases that change rarely, but will only add overhead 
> for databases that change often.  There is an attempt to improve the 
> situation with backpointers, but I doubt they actually help.

FWIW, not long after I sent this message, I finally found a more optimal 
way to use memcached.  I have implemented the new strategy on the 
RelStorage trunk.  I'll try to explain it briefly, but since the 
algorithm is new to me, I am only beginning to learn how to explain it.

The new strategy caches object state by oid and tid, so key 
":state:123:456" holds the tid and state of object 456 as it should be 
seen by transaction 123.  The tid in the cache value does not 
necessarily match the tid in the cache key.  (This part of the algorithm 
is obvious.)

Additionally, each storage instance now holds on to a pair of 
checkpoints.  (This is the new part of the algorithm.)  The checkpoints 
are transaction IDs.  Each storage instance maintains a snapshot of the 
checkpoints, the delta between the checkpoints, and the delta since the 
latest checkpoint.  Each delta is a simple dictionary that maps oid to 
tid.  When a storage instance looks for a cached value, if the object it 
is looking for is in one of the delta maps, it looks at the 
corresponding cache key.  If the storage instance doesn't know the tid, 
then the object has presumably not changed recently, so the storage 
instance looks for the object in the cache at both checkpoints (using a 
single lookup).  If no cached value is found there, then the storage 
instance gets the object state from the database and caches it at the 
most recent checkpoint.

Storage instances choose the checkpoints and make an effort to keep 
their checkpoints in sync with each other, to maximize cache sharing. 
The current checkpoints are stored in the key ":checkpoints" in 
memcached.  There are lots of conditions where the checkpoints fall out 
of sync, and clients might even contend over what the checkpoints should 
be, but in theory, checkpoint disagreement will only lead to cache 
misses, not stale data.

This strategy relies only on the most basic guarantees that memcached 
provides, so I expect it to be reliable.  I also expect it to provide an 
excellent cache hit rate, unless the checkpoints move too often.

I've written more notes here:

http://svn.zope.org/relstorage/trunk/notes/caching.txt?view=markup

The entire implementation is here:

http://svn.zope.org/relstorage/trunk/relstorage/cache.py?rev=105167&view=markup

I just thought you'd like to know.  I think the algorithm might be 
applicable elsewhere.  I invite anyone to steal it if they can. :-)

Shane