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
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:
The entire implementation is here:
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. :-)
For more information about ZODB, see the ZODB Wiki:
ZODB-Dev mailing list - ZODB-Dev@zope.org