\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

\txcache builds on previous work in multi-version concurrency control 
\begin{ednote}{IZ}
  Paragraph on MVCC and snapshot isolation work
\end{ednote}

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{kemme00:_dont_be_lazy_be_consis,
  kemme00:_new_approac_to_devel_and,
  elnikety05:_datab_replic_using_gener_snaps_isolat}, but these
schemes become increasingly complex for large numbers of
replicas. Instead, many replication schemes offer some form of
weakened consistency
~\cite{petersen97:_flexib_updat_propag_for_weakl_consis_replic,
  downing90:_oscar}, 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 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 and can scale as
necessary to improve performance.

Transparent query caches or mid-tier caches like
TimesTen~\cite{timesten} and others~\cite{csql, dbcache, mtcache,
  garrod08:_scalab_query_resul_cachin_for_web_applic}, 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 themselves. % 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{yu99:_scalab_web_cache_consis_archit,
  zhu01:_class_based_cache_manag_for,
  challenger99:_scalab_system_for_consis_cachin,
  candan01:_enabl_dynam_conten_cachin_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 various
different ways to invalidate data. These systems do not offer
transactional consistency, but do take care of invalidating stale
data. However, the web application must regenerate whole pages when a
piece of data becomes stale, reducing the effectiveness of these
caches.

Application object
caches~\cite{memcached,bakalova04:_websp_dynam_cache,oracl_web_cache}
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 offer
no semantics, but scale well. Applications are responsible for either
explicitly invalidating stale data or setting up some sort of policy
for invalidation. 

\txcache is most similar to memcached~\cite{memcached}, a popular
application object cache. Facebook alone has over 28 terabytes of
memory dedicated to
\memcached~\cite{saab08:_scalin_memcac_at_faceb}. The goal of
memcached is to respond to requests as quickly as possible. Memcached
accomplishes this goal by guaranteeing that data is never swapped to
disk and requests never block. Memcached gives the application a
put/get/invalidate interface and does not give any semantic
guarantees. \txcache designed for the same class of operations as
memcached, but offers consistency semantics and a 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.

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