\svnInfo $Id$  

Typical application data caches do not support transactional
consistency, forcing application developers to choose between the
performance benefit of caching and the consistency guarantees of the
underlying database. We provide an alternative with \txcache, an
application-level cache that ensures all data seen by an application
during a transaction is consistent, regardless of whether it comes
from the cache or database. \txcache guarantees consistency by
modifying the database server to return validity intervals that
describe the range of time over which the result was valid, tagging
data in the cache with these intervals, and then only retrieving
values from the cache that were valid at a single point in time.

\txcache allows transactions to run on consistent but slightly stale
snapshots of the database, when this is allowed by the application's
causality requirements. This approach provides several
benefits. First, it allows read-only transactions to execute without
blocking or aborting even in the presence of concurrent
modifications. Second, it allows the application to better utilize the
cache, taking advantage of cached data that was valid at recent points
in time. Finally, it allows the cache to operate without
invalidations: rather than track what data is currently valid, it
instead tracks when data has been valid in the past. Avoiding
invalidations frees the programmer from having to reason globally
about when cached values change, enabling \txcache to make caching as
effortless as simply deciding what functions should be cached.

It is in some respects surprising that it is possible to build a cache
that maintains consistency despite the fact that the cache is never
informed when cached values change. The price to pay for this is that
transactions may see slightly stale data, and the amount of staleness
permitted determines how much cached data can be used.  Even so, our
results show that \txcache is effective: in our web application
benchmark, it increased peak throughput by 77\%, while
ensuring that all data is current to within 30 seconds.

We are currently investigating two approaches to combine these
techniques with invalidations to allow cached data that does not
change to remain useful longer. One approach is to allow the
programmer to explicitly, but optionally, provide invalidations for
certain data items where it is convenient to do so, falling back on
our current scheme when no invalidations are available. Alternative,
we could modify the database to automatically generate invalidations
and send them to the cache.

%%% Local Variables: 
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: "paper.tex"
%%% End: 

% LocalWords:  timestamp invalidations