Suppose that a reader thread is trying to cache an object that it just
read, while a writer thread is trying to cache an object that it just
wrote. The writer thread definitionally has the latest version. The
reader thread may be out of date. While we previously took some care to
not replace a new version with an old version, this did not take into
account evictions, and so the following bug was possible:
READER WRITER
read object_by_id_cache (miss)
read dirty set (miss)
write to dirty
read db (old version)
write to cache (while holding dirty lock)
cache entry is evicted
write to cache
There is no way for the reader to tell that the value it is caching is
out of date, because the up to date entry is already gone from the
cache.
We fix this by requiring reader threads to obtain a ticket before they
read from the dirty set and/or db. Tickets are expired by writers. Then,
the above case looks like this:
READER WRITER
get ticket
read cache (miss)
read dirty (miss)
write dirty
read db (old version)
expire ticket
write cache (while holding dirty lock)
cache eviction
no write to cache (ticket expired)
Any interleaving of the above either results in the reader seeing a
recent version, or else having an expired ticket.