\svnInfo $Id$  

\newcommand{\pinstar}[0]{\ensuremath{\star}\xspace}
\newtheorem{invariant}{Invariant}

Applications interact with \txcache through its application-side
library, which keeps them blissfully unaware of the details of cache
servers, validity intervals, invalidation tags and the like. It is
responsible for assigning timestamps to read-only transactions,
retrieving values from the cache when cacheable functions are called,
storing results in the cache, and computing the validity intervals and
invalidation tags for anything it stores in the cache.

In this section, we describe the implementation of the \txcache
library. For clarity, we begin with a simplified version where
timestamps are chosen when a transaction begins and cacheable
functions do not call other cacheable functions. In
Section~\ref{sec:library:lazy}, we describe a technique for choosing
timestamps lazily to take better advantage of cached data.  In
Section~\ref{sec:library:nested}, we lift the restriction on nested
calls.

\subsection{Basic Functionality}
\label{sec:library:basic}

The \txcache library is divided into a language-independent library that
implements the core functionality, and a set of bindings that
implement language-specific interfaces. Currently, we have only
implemented bindings for PHP, but adding support for other languages
should be relatively straightforward.

Recall from Figure~\ref{fig:library-api} that the library's interface
is simple: it provides the standard transaction commands
(\command{begin}, \command{commit}, and \command{abort}) and a command
for making database queries (\command{query}). Functions are
designated as cacheable using a \command{wrap} function that takes a
function and returns a wrapped function that first checks for
available cached values\footnote{In languages such as PHP that lack
  higher-order functions, the syntax is slightly more complicated, but
the concept is the same.}.

When a transaction is started, the application specifies whether it is
read/write or read-only, and, if read-only, the staleness limit.  For
a read/write transaction, the \txcache library simply starts a
transaction on the database server, and passes all queries directly to
it.  At the beginning of a read-only transaction, the library contacts
the pincushion to request the list of pinned snapshots within the
staleness limit, then chooses one to run the transaction at.  If no
sufficiently recent snapshots exist, the library starts a new
transaction on the database and pins its snapshot.

The library can delay beginning an underlying read-only transaction on
the database (\ie{sending a \command{begin} SQL statement}) until it
actually needs to issue a query.  Thus, transactions whose requests
are all satisfied from the cache do not need to contact the database
at all.

When a cacheable function's wrapper is called, the library checks
whether its result is in the cache. To do so, it serializes the
function's name and arguments into a key, identifies the responsible
cache server using consistent hashing, and sends it a \command{lookup}
request. The request includes transaction's timestamp, which any
returned value must satisfy. If the cache returns a matching result,
the library returns it directly to the program.

In the event of a cache miss, the library calls the cacheable
function's implementation.  As the cacheable function issues queries
to the database, the library accumulates the validity intervals and
invalidation tags returned by these queries.  The final result of the
cacheable function is valid at all times in the intersection of the
accumulated validity intervals.  When the cacheable function returns,
the library serializes its result and inserts it into the cache,
tagged with the accumulated validity interval and any invalidation
tags.

\subsection{Choosing Timestamps Lazily}
\label{sec:library:lazy}

Above, we assumed that the library chooses a read-only transaction's
timestamp when the transaction starts. Although straightforward, this
approach requires the library to decide on a timestamp without any
knowledge of what data is in the cache or what data will be
accessed. Lacking this knowledge, it is not clear what policy would
provide the best hit rate.

However, the timestamp need not be chosen immediately. Instead, it can
be chosen lazily based on which cached results are available. This
takes advantage of the fact that each cached value is valid over a range
of timestamps: its validity interval.  For example, consider a
transaction that has observed a single cached result $x$.  This
transaction can still be serialized at \emph{any} timestamp in $x$'s
validity interval.  On the transaction's next call to a cacheable
function, any cached value whose validity interval overlaps $x$'s can
be chosen, as this still ensures there is at least one timestamp at
which the transaction can be serialized.  As the transaction proceeds,
the set of possible serialization points narrows each time the
transaction reads a cached value or a database query result.

Specifically, the algorithm proceeds as follows. When a transaction
begins, the library requests from the pincushion all pinned snapshot
IDs that satisfy its freshness requirement. It stores this set as its
\emph{pin set}. The pin set represents the set of timestamps at which
the current transaction can be serialized; it will be updated as the
cache and the database are accessed.  The pin set also initially
contains a special ID, denoted \pinstar, which indicates that the
transaction can also be run in the present, on some newly pinned
snapshot. The pin set only contains \pinstar until the first cacheable
function in the transaction executes. 

When the application invokes a cacheable function, the library sends a
\command{lookup} request for the appropriate key, but instead of
indicating a single timestamp, it indicates the \emph{bounds} of the
pin set (the lowest and highest timestamp, excluding \pinstar).  The
transaction can use any cached value whose validity interval overlaps
these bounds and still remain serializable at one or more timestamps.
%The cache node returns the most up-to-date value that overlaps the
%given bounds, though other policies are possible.
The library then reduces the transaction's pin set by eliminating all
timestamps that do not lie in the returned value's validity interval,
since observing a cached value means the transaction can no longer be
serialized outside its validity interval. This includes removing
\pinstar from the pinset because once the transaction has used cached
data, it cannot be run on a new, possibly inconsistent snapshot.

When the cache does not contain any entries that match both the key
and the requested interval, a cache miss occurs. In this case, the
library calls the cacheable function's implementation, as before.
When the transaction makes its first database query, the library is
finally forced to select a specific timestamp from the pin set and
\command{begin} a read-only transaction on the database at the chosen
timestamp. If a non-\pinstar timestamp is chosen, the transaction runs
on that timestamp's saved snapshot. If \pinstar is chosen,
the library starts a new transaction, pinning the latest snapshot and
reporting the pin to the pincushion. The pin set is then
\emph{reified}: \pinstar is replaced with the newly-created snapshot's
timestamp, replacing the abstract concept of ``the present time'' with
a concrete timestamp.

The library needs a policy to choose which pinned snapshot from the
pin set it should run at. Simply choosing \pinstar if available, or
the most recent timestamp otherwise, biases transactions towards
running on recent data, but results in a very large number of pinned
snapshots, which can ultimately slow the system down. To avoid the
overhead of creating many snapshots, we used the following policy: if
the most recent timestamp in the pin set is older than five seconds
and \pinstar is available, then the library chooses \pinstar in order
to produce a new pinned snapshot; otherwise it chooses the most recent
timestamp.

% This has
% the cumulative effect of producing a new pinned snapshot every five
% seconds, which avoids the overhead of large numbers of snapshots while
% giving other transactions a variety of timestamps to use when
% retrieving values from the cache.

% There are many imaginable policies for choosing which pinned snapshot
% to run at.  Simply choosing the latest pin that isn't \pinstar (or
% \pinstar if nothing else is available) results in the creation of a
% new pin every time some requested freshness requirement can't be
% satisfied.  This results in very few pins (for example, one every 30
% seconds if the freshness requirement is 30 seconds), but can cause
% thrashing every time a new pin is created.  Choosing \pinstar in
% preference to the latest pin produces a large variety of pins and
% evenly distributes the load on the cache and the database over time.
% However, this policy can result in \emph{too many} pinned snapshots,
% introducing large processing overheads.  Ultimately, we settled on a
% compromise between these policies: the latest pin is used, unless it
% is older than some small age (say, 5 seconds), in which case \pinstar
% is used.  This results in a new pin every 5 seconds, spreading out the
% load on the cache without introducing large processing overheads.

During the execution of a cacheable function, the validity intervals
of the queries that the function makes are accumulated, and their
intersection defines the validity interval of the cacheable result,
just as before. In addition, just like when a transaction observes
values from the cache, each time it observes query results from the
database, the transaction's pin set is reduced by eliminating all
timestamps outside the result's validity interval, as the transaction
can no longer be serialized at these points.  If the transaction's pin
set still contains \pinstar, \pinstar is removed.

The validity interval of the cacheable function and pin set of the
transaction are two distinct but related notions: the function's
validity interval is the set of timestamps at which its result is
valid, and the pin set is the set of timestamps at which the enclosing
transaction can be serialized. The pin set always lies within the
validity interval, but the two may differ whe a transaction calls
multiple cacheable functions in sequence, or performs ``bare''
database queries outside a cacheable function.

\subsubsection{Correctness}
\label{sec:library:lazy:correctness}

Lazy selection of timestamps is a complex algorithm, and its
correctness is not self-evident. The following two properties show
that it provides transactional consistency.

\begin{invariant}
  \label{inv:pin-serializability}
  All data seen by the application during a read-only transaction is
  consistent with the database state at every timestamp
  in the pin set, \ie{the transaction can be serialized at any
    timestamp in the pin set}.
\end{invariant}

Invariant~\ref{inv:pin-serializability} holds because any timestamps
\emph{in}consistent with data the application has seen are removed
from the pin set. The application sees two types of data: cached
values and database query results. Each is tagged with its validity
interval. The library removes from the pin set all timestamps that lie
outside either of these intervals.

\begin{invariant}
  \label{inv:pin-non-empty}
  The pin set is never empty, \ie{the transaction can always be
    serialized at some timestamp}.
\end{invariant}

The pin set is initially non-empty: it contains the timestamps of all
sufficiently-fresh pinned snapshots, if any, and always \pinstar. So
we must ensure that at least one timestamp remains every time the pin
set shrinks, \ie{when a result is obtained from the cache or
  database}.

When a value is fetched from the cache, its validity interval is
guaranteed to intersect the transaction's pin set at at least one
timestamp. The
cache will only return an entry with a non-empty intersection
between its validity interval and the bounds of the transaction's pin
set. This intersection contains the timestamp of at least one pinned
snapshot: if the result's validity interval lies partially within and
partially outside the bounds of the client's pin set, then either the
earliest or latest timestamp in the pin set lies in the
intersection. If the result's validity interval lies entirely within
the bounds of the transaction's pin set, then the pin set must
contain the timestamp of the pinned snapshot from which the cached
result was originally generated. Thus,
Invariant~\ref{inv:pin-non-empty} continues to hold even after
removing from the pin set any timestamps that do not lie within the
cached result's validity interval.

It is easier to see that when the database returns a query result, the
validity interval intersects the pin set at at least one
timestamp. The validity interval of the query result must contain the
timestamp of the pinned snapshot at which it was executed, by
definition. That pinned snapshot was chosen by the \txcache library
from the transaction's pin
set (or it chose \pinstar, obtained a new snapshot, and added it to
the pin set). Thus, at least that one timestamp will remain in the pin
set after intersecting it with the query's validity interval.

\subsection{Handling Nested Calls}
\label{sec:library:nested}

In the preceding sections, we assumed that cacheable functions never
call other cacheable functions. However, it is useful to be able to
nest calls to cacheable functions. For example, a user's home page at
an auction site might contain a list of items the user recently bid
on. We might want to cache the description and price for each
item as a function of the item ID (because they might appear on other
user's pages) in addition to the complete content of the user's page
(because he might access it again).

Handling nested calls does not require any fundamental changes to our
approach. However, we must keep track of a separate cumulative
validity interval and invalidation tag set for each cacheable function
in the call stack. When a cached value or database query result is
accessed, its validity interval is intersected with that of
\emph{each} function currently on the call stack. As a result, a
nested call to a cacheable function may have a wider validity interval
than its enclosing function, but not vice versa. This makes sense, as
the outer function might have seen more data than the functions it
calls (\eg{if it calls more than one cacheable function}). Similarly,
any invalidation tags from the database are attached to each function
on the call stack, as they now have a dependency on the data.

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

% LocalWords:  cacheable PHP timestamp lookup timestamp's reified