\svnInfo $Id$  

\txcache stores cached data in RAM on a number of cache servers. The
cache presents a hash table interface: it maps keys to associated
values. However, applications do not access the cache directly:
\txcache's application-side library handles everything relating to
retrieving
and updating cached values whenever cacheable functions are called,
including assigning the keys.

Data is partitioned among cache nodes using a consistent hashing
approach~\cite{karger97:_consis_hashin_and_random_trees}. Each cache
server has an ID, and the server responsible for storing a key is the
first one whose hashed server ID is greater than the hash of the key,
wrapping around if necessary. This computation can be performed by any
application server; it need only know the list of servers being
used. We assume that every application node has an identical,
up-to-date list of servers. This list can be maintained by hand in
small systems, or using a group membership
service~\cite{cowling09:_census,birman87:_exploit_virtual_synch_in_distr_system}
in larger or more dynamic environments.

The interface and partitioning of our cache are very similar to
peer-to-peer distributed hash tables, such as
Chord~\cite{stoica03:_chord}, Pastry~\cite{rowstron01:_pastr}, and
countless others. However, our system lacks many of their more
demanding requirements, and so avoids most of their complexity. In
particular, multi-hop routing is unnecessary at the scale of perhaps
hundreds of nodes in a data center. Data replication is also
unnecessary; if a cache node fails, attempts to access it can simply
be treated as cache misses until the node is repaired or removed from
the membership list.

\subsection{Versioning}
\label{sec:cache:versioning}

The most important difference between our cache and a distributed hash
table is that our cache is \emph{versioned}. In addition to its key,
each entry in the cache is tagged with its \emph{validity
  interval}, as shown in figure~\ref{fig:cache-intervals}. This
interval is the range of time at which the cached
value was current. Its lower bound is the commit time of the
transaction that caused it to become valid, and its upper bound is the
commit time of the first subsequent transaction to change the result,
making the cache entry invalid. Multiple cache entries with the same
key can be stored in the cache, as long as they have disjoint
validity intervals.

Whenever the \txcache library puts the result of a cacheable function
call into the cache, it includes the validity interval of that
result. The library automatically computes this validity
interval using information obtained from the database;
Sections~\ref{sec:database} and~\ref{sec:library} describe how this is
done.

\begin{figure}[tp]
  \centering
  \includegraphics[scale=0.4]{cache-intervals.pdf}
  \caption{An example of data in the cache over time. Each line shows
    which versions of the data are in the cache. For example, the
    cache has two version of the data associated with key 1: one
    version that became valid with commit 43 and invalid with commit
    46, and another version that became valid with commit 51 and
    invalid with commit 53. The cache does not contain any data that
    is valid now, but if a query was run slightly in the past at
    commit 51, all four values are available in the cache.}
  \label{fig:cache-intervals}
\end{figure}

To look up a result in the cache, the \txcache library sends both the
key it is interested in and a timestamp or range of acceptable
timestamps. The cache server returns a value consistent with the
library's request, \ie one whose validity interval intersects the
given range of acceptable timestamps, if any exists. The server
also returns the value's associated validity interval. If multiple
such values exist, the cache server returns the most recent one.
The reason the library might want to specify a range of
values is that, rather than assign a transaction's timestamp
immediately when it begins, it can choose the timestamp lazily based on
what data is in the cache; Section~\ref{sec:library} explains this
process in detail.

When a cache node runs out of memory, it evicts old cached values to
free up space for new ones. There are no restrictions on what can be
discarded, \ie{cache entries are never pinned}; if an evicted value is
later needed, it can be recomputed using the normal cache miss
procedure. A cache eviction policy can take into account both the
time since an entry was last looked up, and its staleness. Our cache
server uses a least-recently-used replacement policy, and also
discards any values older than a fixed global maximum staleness.


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

% LocalWords:  cacheable multi versioned invalidations timestamp