\svnInfo $Id$  

%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

There is a large and varied body of work on scaling databases to keep
up with the demanding workload of web applications. Replication is the
primary method for directly scaling databases. Some database
replication schemes guarantee transactional
consistency~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat,
  kemme00:_dont_be_lazy_be_consis,
  kemme00:_new_approac_to_devel_and}, but these
schemes become increasingly complex for large numbers of
replicas. Instead, many replication schemes offer some form of
weakened consistency
~\cite{downing90:_oscar,
  petersen97:_flexib_updat_propag_for_weakl_consis_replic},
but these systems are often very difficult to
reason about and use correctly.

% There are a number of other distributed storage solutions that are
% used in web applications that offer better scalability, such as
% Dynamo~\cite{decandia07:_dynam},
% TACT~\cite{yu02:_desig_and_evaluat_of_conit}. However, these systems
% have no transactional consistency, making them difficult to use in
% many applications.

To avoid the complexity and cost of database replication, web
applications often use caching instead to reduce the load on the
database. Caches that are external to the database are most popular
because they are easy to add to an existing system, cost-effective,
and can scale as
necessary to improve performance.

Transparent query caches or mid-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
generally strive to be transparent to the application, so they often
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,
making them complex and difficult to scale. % In fact, an
% approach taken by DBCache~\cite{dbcache} and MTCache~\cite{mtcache} is
% to run a small database on each application server as a
% cache. Mid-tier caches cannot help alleviate overload on applications
% servers.

In contrast, 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} cache pages produced by the
web application, reducing the load on the application server and the
database. These caches are essentially web caches with support for
invalidating changing data. However, these systems do not offer
transactional consistency and the web application must regenerate
whole pages when any data used the generate the page changes, reducing
the effectiveness of these caches.

Application object
caches~\cite{oracl_web_cache,bakalova04:_websp_dynam_cache,memcached}
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.

\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.

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