\svnInfo $Id$  

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

Applications interact with \txcache through its application-side
library. Much of the complexity of the system lies in the library,
which 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 associated with everything it stores in the cache.

In this section, we describe the implementation of the \txcache
library. For clarity, we initially describe a simplified version in
which 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.
Section~\ref{sec:library:nested} describes how 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.

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}). There is also a way to designate a function as
cacheable, though the details depend on the language being used. In a
language that supports higher-order functions, this would be a
\command{wrap} function that takes a function and returns a wrapped
function that first checks for available cached values. In other
languages, such as PHP, the function needs to be called through a
\command{cacheable-call} procedure.

When a transaction is started, the programmer must specify whether the
transaction is read/write or read-only, and the freshness requirement,
if read-only. 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 that satisfy the freshness requirement, then chooses one to
run the transaction at.  If no sufficiently recent
snapshots exist, the library starts a new transaction on the database,
pins its snapshot, and notifies the pincushion of this new snapshot.

Note that 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 to the
database.  This can be a useful optimization, because a transaction
whose requests are all satisfied from the cache does not need to
contact the database at all.

When a cacheable function is called, the library checks whether its
result is in the cache. The library does so by serializing the
function's name and arguments to generate a key and using consistent
hashing to identify the cache server responsible for storing the
key. The library sends the cache node a \command{lookup} request,
indicating not only the key to look up but also the transaction's
timestamp, which any returned value must satisfy. If the cache returns
a matching result, the library deserializes this and 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
returned by these queries.  Ultimately, 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.

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

Above, we assumed that the \txcache library chooses a read-only
transaction's timestamp when the transaction starts. Although
straightforward, this approach may not be able to take the most
advantage of cached data. When assigning timestamps eagerly, the
library must decide on a timestamp without any knowledge of what data
is in the cache or what data will be accessed. Indeed, lacking this
knowledge, it is not at all clear what policy would provide the most
benefit.

However, the timestamp need not be chosen at transaction-start
time. Instead, the timestamp can be chosen lazily based on which
cached results are available. This takes advantage of the fact that
each cached value is valid at a range of timestamps (over 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 without affecting the
transaction's result.  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 that the transaction can be
serialized at at least one timestamp.  As the transaction proceeds,
the set of snapshots at which the transaction can be serialized
narrows each time the transaction uses a cached value or a result
obtained from the database.

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 validity interval of the returned value, since
observing this cached value means the transaction can no longer be
serialized at timestamps outside of this interval. This includes
removing \pinstar from the pinset because once the transaction has
used cached data, the transaction can no longer be run in the present.

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 using some policy and \command{begin} a read-only transaction on
the database at the chosen timestamp. If a non-\pinstar timestamp is
chosen, the transaction is started using that timestamp's saved
snapshot. If \pinstar is chosen, the library starts a new transaction
that runs in the present, pinning its snapshot and reporting the pin
to the pincushion. The pin set is then \emph{reified}: \pinstar is
replaced with the timestamp of the newly-created snapshot, replacing
the abstract concept of ``the present time'' with a concrete
timestamp.

There are many imaginable policies for choosing which pinned snapshot
to 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.  Instead, we settled on a
slightly subtler 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 not contained in the validity interval of the query
results.  Like with cache values, the transaction can no longer be
serialized outside of this validity interval.  If the transaction's
pin set still contains \pinstar, \pinstar is removed because the
transaction can no longer run on a newly pinned snapshot.

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 transaction's pin set is the set of timestamps at which
it can be serialized. The two may differ if a transaction calls
multiple cacheable functions, or performs ``bare'' database queries
outside a cacheable function.

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

Lazy selection of timestamps is a somewhat 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 results seen by the application during a read-only transaction
  are consistent with the state of the database at all of the
  timestamps 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 the data the application has seen are removed
from
the pin set. The application sees two types of data: values obtained
from the cache, and query results from the database. Cached values are
tagged with their validity interval, and the database reports validity
intervals for query results. 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 can only return an entry that has 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 must 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 for simplicity 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 current
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 do need to keep track of a separate cumulative
validity
interval for each cacheable function in the call stack. Each time a
result is fetched from the cache or a query is performed on the
database, its validity interval is intersected with that of each
functions currently on the call stack. As a result, these validity
intervals have
an interesting property: a nested call to a cacheable function may
have a wider validity interval than its enclosing function, but not
vice versa. This makes sense, because the outer function might have
seen more data than the functions it calls (\eg{if it calls more than
  one cacheable function}).


%%% 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