\svnInfo $Id$  

There is a large and varied body of work on improving the performance
of database-driven web applications. This work generally falls into
two extremes: database replication or caching schemes that help
alleviate database bottlenecks and offer transactional consistency,
but are fairly heavy-weight; or light-weight application level caches
that reduce load on the database and application servers, but do not
provide transactional consistency. \txcache also builds on previous
work in relaxed freshness and multiversioned concurrency.

%database stuff on relaxed consistency, i.e. snapshot isolation
%relaxed consistency distributed systems i.e. dynamo sinfonia
%relaxed consistency replication, database, or otherwise
%replicating the database, with consistency, generally doesn't work
%very well

%dynamic page caching, most have no consistency semantics

%mid tier caches
%application caches

\subsection{Database Replication}
\label{sec:relwork:replication}

Database replication or a middle-tier caching can effectively reduce
the load on the database. There are a wide range of database
replication schemes. Some guarantee transactional
consistency~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat,
  kemme00:_dont_be_lazy_be_consis, kemme00:_new_approac_to_devel_and},
but are difficult to scale to large numbers of replicas or require the
developer to know the access pattern beforehand~\cite{amza03:_distr} or
statically partition the data~\cite{cecchet04:_c_jdbc}. Others offer
some form of weakened consistency~\cite{downing90:_oscar,
  petersen97:_flexib_updat_propag_for_weakl_consis_replic}, but these
schemes are often difficult to reason about and use correctly.

Transparent query caches or middle-tier caches like
TimesTen~\cite{timesten} and others~\cite{dbcache, csql,
  garrod08:_scalab_query_resul_cachin_for_web_applic, mtcache}, sit
between the application and the database, and cache query
results. These caches strive to be transparent to the application, so
they usually offer the same consistency guarantees as the database
(although some do
not~\cite{guo05:_cachin_with_good_enoug_curren}). Transparent query
caches must replicate much of the functionality of the database, so
they are have similar drawbacks.
 
Several systems have explored the use of stale data for replicated
databases and middle-tier caches~\cite{plattner04:_ganym,
  rhm_fas:freshness-sensitive_2002,
  bernstein06:_relax}. Fundamentally, the algorithms used by these
systems differ from \txcache's because each replica in a replicated
database has a full snapshot at a particular point in time. Thus, in a
replicated database with $n$ replicas, a read-only transaction can
only be run at one of $n$ points in time. Both
Ganymed~\cite{plattner04:_ganym} and
FAS~\cite{rhm_fas:freshness-sensitive_2002} assign the read-only
transaction the timestamp of the least-loaded replica that is within
the freshness requirement for the transaction. Once the replica is
chosen at the beginning of the transaction, all queries in that
transaction must continue to run on the chosen replica.
%For
%transactions with more than one query, this decision is suboptimal
%because the chosen replica could become heavily loaded after the
%transaction starts.

The key difference between \txcache's application-level cache and
database replicas is that \txcache's cache nodes have only a partial
set of the values that might be requested. Whereas a database replica
can be kept complete and up to date by shipping all updates to it, it
is infeasible to maintain a complete set of application-level values
because this would require recomputing all relevant function results
each time data is updated. \txcache's cache nodes contain only the
values recently computed by the application. Moreover, these values
are valid at several, different points in time.  Thus, choosing an
optimal timestamp for the transaction is difficult without knowing in
advance what the transaction will read. \txcache uses an adaptive
algorithm to lazily choose the optimal timestamp for the transaction,
so that the transaction can make the best use of the cache.

\subsection{Application-Level Caching}
\label{sec:relwork:applevel}

Application-level caches can improve the performance of both the
application servers and database, and can be used with a replicated
database to further improve throughput. These caches are easier to
scale than replicated databases because each cache node does not store
a complete copy of the database. Application level caches are also
very easy to add to existing systems and cost-effective. However, none
of the current application level caches offer transactional
consistency.

Dynamic web caches~\cite{candan01:_enabl_dynam_conten_cachin_for,
  challenger99:_scalab_system_for_consis_cachin,
  yu99:_scalab_web_cache_consis_archit,
  zhu01:_class_based_cache_manag_for} store entire web pages produced
by the web application. The disadvantage of these caches is that the
web application must regenerate whole pages when any data used the
generate the page changes. Application object
caches~\cite{oracl_web_cache,bakalova04:_websp_dynam_cache,memcached}
are more effective than dynamic web caches because they allow the
application to choose what to store, including query results,
arbitrary application data, and fragments of or whole web
pages. Application object caches are generally very simple and do not
offer transactional semantics, but scale well. Applications are
responsible for either explicitly invalidating stale data or setting
up some sort of policy for invalidation.

\txcache's cache server design is similar to
\memcached~\cite{memcached}, a popular application object cache. Its
largest user, Facebook has a dedicated cluster of \memcached nodes
with over 28 terabytes of
memory~\cite{saab08:_scalin_memcac_at_faceb}. The goal of \memcached
is to respond to requests as quickly as possible, by guaranteeing that
data is never swapped to disk and requests never block. \memcached
gives the application a put/get/invalidate interface and has no notion
of transactions. \txcache caches the same sort of application data,
while also offering strict consistency semantics and a simpler
programming model.

% Like middle-tier caches, \txcache maintains the same semantics as the
% database, but allows applications to cache arbitrary data like
% application-level caches.

\subsection{Relaxing Freshness}
\label{sec:relwork:concurrency}

\txcache builds on a long history of previous work on multiversion
concurrency control. Many different approaches to using multiple
versions to ensure isolation
exist~\cite{reed78:_namin_and_synch_in_decen_comput_system,
  adya95:_effic_optim_concur_contr_using,
  berenson95:_critiq_of_ansi_sql_isolat_level,
  bernstein81:_concur_contr_in_distr_datab_system}, the most prevalent
such approach in production systems being snapshot
isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}.  In
snapshot isolation, all data read by a transaction comes from a
snapshot of the database taken at the time the transaction started.
Snapshot isolation permits some anomalies that make it an isolation
level less than true serializability. However, these anomalies only
occur with read-write transactions; \txcache avoids them because it
does not attempt to optimize read-write transactions at all.

Unlike snapshot isolation, where transactions use a snapshot current
as of the time they started, \txcache can assign transactions a
snapshot slightly earlier than their actual start time. Similar
approaches have also been proposed in a distributed environment, for
both transactional file
systems~\cite{liskov04:_trans_file_system_can_be_fast} and distributed
databases~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat}. These
proposals improve cache performance in an environment where each
client has its own local cache; \txcache has a different model
consisting of a single shared cache.

Bernstein~et~al.\ defined a notion of relaxed-currency
serializability~\cite{bernstein06:_relax} that encompasses \txcache's
use of stale data (as well as several other types of currency
constraints). The algorithms presented in this work rely on a similar
notion of validity intervals. They assume a model similar to that of
the replicated database systems discussed previously. In such a model,
validity intervals of data are more readily available. Our
contributions include a technique for easily generating validity
intervals using existing database concurrency control mechanisms, and
using them to generate validity information for application-level
objects.

As we argued in Section~\ref{sec:stale:anomalies}, assigning
transactions an earlier timestamp is safe as long as it does not
permit any causality anomalies. Other systems also allow operations to
be reordered when there are no causal dependencies. Lamport introduced
the happens-before relation, wherein transactions are considered
current if they do not depend on each
other~\cite{lamport78:_time_clock_and_order_of}. This idea was notably
used in the ISIS
system~\cite{birman87:_exploit_virtual_synch_in_distr_system}, whose
virtual synchrony communication model enforced ordering constraints
only on causally-dependent messages.

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

% LocalWords:  multiversion serializability timestamp Lamport