\svnInfo $Id$  

\txcache is designed for systems consisting of one or more application
servers that interact with a database server. These application
servers could be web servers running embedded scripts (\eg{with
  \texttt{mod\_php}}), or dedicated application servers, as with Sun's
Enterprise Java Beans. The database server is a standard relational
database; for simplicity, we assume the application uses a single
database to store all of its persistent state.

\begin{figure}[tp]
  \centering
  \includegraphics{arch3.pdf}
  \caption{Key components in a \txcache deployment. The system
    consists of a single database, a set of cache nodes, and a set of
    application servers. \txcache also introduces a application
    library, which handles all interactions with the cache server.}
  \label{fig:architecture}
\end{figure}

\txcache introduces two new components, as shown in
Figure~\ref{fig:architecture}: a cache and an application-side cache
library, as well as some modifications to the database server. The
cache is partitioned across a set of cache nodes, which may run on
dedicated hardware or share it with other servers. The application
never interacts with the cache servers; the \txcache library
transparently translates an application's cacheable functions into
cache accesses.

\subsection{Programming Model}
\label{sec:model:programming}

Our goal is to make it effortless to incorporate caching into a new or
existing application. Towards this end, \txcache provides an
application library with a simple programming model, shown in
Figure~\ref{fig:library-api}, based on \emph{cacheable
  functions}. Applications developers can cache computations simply by
designating functions to be cached.
% XXX Library also provides consistency.

\begin{figure}[t]
  \newcommand{\cmdarg}[1]{\textit{#1}}
  \addtolength{\leftmargini}{1.5em}
  \begin{itemize}
  \itemindent=-1.5em   
  \item \command{begin-ro}(\cmdarg{staleness}) : Begin a read-only
    transaction. The transaction sees a consistent snapshot from
    within the past \cmdarg{staleness} seconds.
  \item \command{begin-rw}() : Begin a read/write transaction.
  \item \command{commit}() / \command{abort}() : End a transaction
  \end{itemize}
  \vspace{0.2em}

  \begin{itemize}
  \itemindent=-1.5em   
  \item \command{wrap}(\cmdarg{fn}) $\to$ \cmdarg{cached-fn} :
    Makes a function cacheable. \cmdarg{cached-fn} a new function that first
    checks the cache for the result of another call with the same
    arguments. If not found, executes \cmdarg{fn} and stores
    its result in the cache.
  \end{itemize}
  \vspace{0.2em}
  
  \begin{itemize}
  \itemindent=-1.5em
  \item \command{query}(\cmdarg{SQL}) $\to$ \cmdarg{result} :
    Sends a SQL query to the database server.
  \end{itemize}

  \caption{TxCache library API}
  \label{fig:library-api}
\end{figure}

Programs group their operations into transactions. \txcache requires
applications to specify whether their transactions are read-only or
read/write by using either the \command{begin-ro} or
\command{begin-rw} function. Transactions are ended by calling
\command{commit} or \command{abort}. Within a transaction block,
\txcache ensures that, regardless of whether the application gets it's
data from the database or the cache, it sees a view consistent with
the state of the database at a single point in time.

% through the
% \txcache library's \command{begin} and \command{commit}
% functions. When starting a transaction, the program declares whether
% it will be a read-only or read/write transaction. If read-only, the
% application can also specify any requirements for how fresh the data
% must be; Section~\ref{sec:stale:anomalies} discusses how applications
% can use these freshness requirements.  We focus on optimizing
% read-only transactions, as these are most common in most
% workloads.\edatnote{DRKP}{Citation for this?}  Read/write transactions
% do not take advantage of caching; \txcache's library forwards them
% directly to the database, so they execute exactly as they would on an
% unmodified system.

Within a transaction, operations can be grouped into \emph{cacheable
  functions}. These are actual functions in the program's code,
annotated to indicate that their results can be be cached.  A
cacheable function can consist of database queries and computation,
and can also make calls to other cacheable functions. To
be suitable for caching, these functions must be deterministic, not
have side effects, and depend only on their arguments and the database
state. For example, it would not make sense to cache a function that
returns the current time. % We believe it is reasonable
%for programmers to identify such cacheable functions.

Cacheable functions are essentially memoized. \txcache's library
provides a \command{wrap} function that takes an implementation of a
cacheable function and returns a wrapper function. When called, this
wrapper function first checks if the cache contains the result of a
previous call to the function with the same arguments that is
consistent with the current transaction's snapshot. If so, it returns
it. Otherwise, it invokes the implementation function and stores the
returned value in the cache.

A cacheable function interface is easier to use than the
\command{get}/\command{put} interface provided by existing caches like
\memcached. It does not require programmers to manually assign keys to
cached values and keep them up to date. We found that several
\memcached-related MediaWiki bugs stemmed from choosing insufficiently
descriptive keys, causing two different objects to overwrite each
other. This problem is not possible with \txcache.


\txcache's programming model has another significant benefit: it does
not require applications to explicitly invalidate cached results when
modifying the database, unlike other application data caches such as
\memcached. Adding explicit invalidations requires global reasoning
about the entire application, hindering modularity: adding caching for
an object requires knowing every place it could possibly change. For
example, consider placing a new bid on an item in an eBay-like auction
site. Clearly, any cached copies of the item's page must be
invalidated, because the price has changed. Some other objects that
must be invalidated are less obvious: the item's price also appears on
various search result pages, and the home pages of users who bid on
it. Finding all of these cached objects is not straightforward,
especially in applications so complex that no single developer is
aware of the whole of the application.

% \txcache instead tracks each application data object's dependencies on
% particular database state, and automatically generates invalidations
% when it is updated. To achieve this, the \txcache library interposes
% on an application's database queries, as noted in
% Figure~\ref{fig:library-api}. However, it does so only to receive
% metadata from the database server, as noted in
% Section~\ref{sec:library}. It does not attempt to parse or rewrite the
% SQL queries or results themselves.

\subsection{Consistency Model}
\label{sec:model:consistency}

\txcache provides \emph{transactional consistency}: all requests
within a transaction see a consistent view of the system as of a
specific timestamp. That is, requests see only the effects of other
transactions that committed prior to that timestamp. It is not
practical to simultaneously guarantee both transactional consistency
and \emph{freshness}, where the cache reflects the latest state of the
system. To do so would require a concurrency control scheme like
two-phase locking~\cite{gray77:_granul_of_locks_and_degrees} or
optimistic concurrency
control~\cite{kung81:_optim_method_for_concur_contr} Then, read-only
transactions, even ones that access only the cache, could be blocked
or force other transactions to block or retry, negating the benefits
of the cache.

In order to provide consistency without requiring transactions to
block, \txcache relaxes its freshness guarantee for read-only
transactions. It achieves this using a multiversion concurrency
control approach similar to snapshot isolation
databases~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}, where
read-only transactions are assigned a timestamp, and then are only
allowed to read values that are current as of that timestamp.

However, \txcache goes further by allowing applications to specify an
explicit \emph{staleness limit} to \command{begin-ro}, indicating that
they are willing to accept data up to a certain age. This is motivated
by the observation that many applications can tolerate a certain
amount of staleness, and using slightly stale cached data can improve
the cache's hit rate. \drkp{citations.}  Applications can specify
their staleness limit on a per-transaction basis, allowing them, for
example, to avoid anomalies by ensuring that a user always sees his
latest update. Regardless of the age of the snapshot, each
transaction always sees a consistent view.

Read/write transactions bypass the cache entirely, so \txcache does
not introduce new anomalies. The application can expect the same
guarantees (and anomalies) of the underlying database. For example, if
the underlying database uses snapshot isolation, the system will still
have the same anomalies as snapshot isolation, but \txcache will never
introduce snapshot isolation anomalies into a system that does not use
snapshot isolation.



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

% LocalWords:  versioned versioning php timestamp Cacheable cacheable memoized
% LocalWords:  invalidations
