\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 database caching 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
maintain transactional consistency with the database. \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}. % In these systems, each
% database replica maintains a full snapshot of the database at a single
% point in time.
This approach is infeasible for an application-level objects as
it would require recomputing all relevant function results after each
update. \txcache's cache nodes contain only values recently computed
by the application, which were computed at different points in
time. % Making effective use of
% these values requires new techniques such as validity intervals
% and lazy timestamp selection, that are not required for replicated
% databases.

% 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. These caches are easier to scale
than replicated databases and offer more performance improvement per
node. 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. They reduce load on both the application
servers and the database, but they must regenerate the entire webpage
when any content changes. As more of the web becomes personalized and
dynamic, dynamic web caches are becoming less appealing to application
developers. Instead, web developers are increasingly turning to
application-level data
caches~\cite{oracl_web_cache,bakalova04:_websp_dynam_cache,memcached,sampathkumar09:_introd_cachin_window_server_appfab_beta,jboss}
for their flexibility. These caches allow the application to choose
what to store, including query results, arbitrary application data,
and fragments of or whole web pages. The most widely used are
distributed in-memory caches like \memcached~\cite{memcached}. Its
largest user, Facebook has a dedicated cluster of \memcached nodes
with over 28 terabytes of
memory~\cite{saab08:_scalin_memcac_at_faceb}.

Application-level data caches give the application a minimal
\command{put}/\command{get}/\command{invalidate} interface, so the
application developer must choose keys and correctly invalidate cached
objects. This requirement frequently leads to software bugs, as both
require the programmer to have global knowledge of the
system. Wikipedia, which also uses \memcached, has at least two bugs
in their Bugzilla bug tracker that are caused by incorrect key
selections and they often have issues with stale data in the cache
obscuring updates because of incorrect invalidations.  With \txcache's
programming model, these problems would be avoided because the
\txcache library selects keys and automatically handles invalidations
for the application.  Facebook also avoids these problems by using a
custom library that handles some cache management, but it is probably
not general-purpose enough for other applications to use and does not
provide consistency.

Most application object caches have no notion of consistency, so there
is no way to ensure even that two accesses to the cache return
consistent values. Some have a notion of transactions within the
cache, so the application can run transactions on a view of the cache
at a single point in
time~\cite{sampathkumar09:_introd_cachin_window_server_appfab_beta,jboss},
but none maintain transactional consistency with the database. In
fact, most application-level caches are completely unaware of the
underlying storage system. In contrast, \txcache offers consistency
across the entire system, so the application can expect a consistent
view regardless of whether the data is from the cache or the database.

% https://bugzilla.wikimedia.org/show_bug.cgi?id=7541
%https://bugzilla.wikimedia.org/show_bug.cgi?id=21975

% 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, and rely on a similar notion of validity
intervals. They assume a model similar to that of the replicated
database systems discussed previously, in which validity intervals 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