\svnInfo $Id$  

%Problem: database become bottleneck in web app because they do not
%scale well
Today's web applications are used by millions of users and demand
implementations that scale accordingly. A typical system includes
application logic (often implemented in web servers) and an underlying
database that stores persistent state, either of which can become a
bottleneck~\cite{amza02:_bottl_charac_of_dynam_web_site_bench}.
%Either type of bottleneck can be addressed, but with
%difficulty.
Increasing database capacity is typically a difficult and costly
proposition, requiring careful partitioning or esoteric distributed
databases. Application server bottlenecks can be easier to address by
adding more nodes, but this also quickly becomes expensive.

\emph{Application-level data caches}, such as
\emph{\memcached}~\cite{memcached}, are a popular solution to server
and database bottlenecks. They are deployed extensively by well-known
web applications like LiveJournal, Facebook, and MediaWiki. These
caches store arbitrary application-generated data in a lightweight,
distributed in-memory cache. This flexibility allows an
application-level cache to act as a database query cache, or to act as
a web cache and cache entire web pages. But increasingly complex
application logic and more personalized web content has made it more
useful to cache the result of \emph{application computations} that
depend on database queries. Such caching is useful because it averts
costly post-processing of database records, such as converting them to
an internal representation, or generating partial HTML output. It also
allows common content to be cached separately from customized content,
so that it can be shared between users. For example, MediaWiki uses
\memcached to store items ranging from translations of interface
messages to parse trees of wiki pages to the generated HTML for the
site's sidebar.



% Not surprisingly, many types of caches have been used to address these
% bottlenecks. Dynamic web caches can store entire web pages produced by
% the application~\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}, but the need to regenerate
% pages that change makes them less useful for today's increasingly
% dynamic content. Database replication
% systems~\cite{kemme00:_dont_be_lazy_be_consis, amza03:_distr,
%   petersen97:_flexib_updat_propag_for_weakl_consis_replic}, or
% query/mid-tier caches~\cite{timesten, mtcache,
%   garrod08:_scalab_query_resul_cachin_for_web_applic} can improve
% database performance, but offer no relief for application server
% load. They also typically require replicating much of the
% functionality (and drawbacks) of the database in the cache.


Existing caches like \memcached present two challenges for developers,
which we address in this paper:

First, they cannot ensure transactional consistency with the rest of
the system state.  That is, there is no way to ensure that accesses to
the cache and the database return values that reflect a view of the
entire system at a single point in time. While the backing database
goes to great length to ensure that all queries performed in a
transaction reflect a consistent view of the database, \ie{it can
  ensure serializable isolation}, it is nearly impossible to maintain
these consistency guarantees while using a cache that operates on
application objects and has no notion of database transactions. The
resulting anomalies can cause incorrect information to be exposed to
the user, or require more complex application logic because the
application must be able to cope with violated invariants.

% The lack of transactional consistency can lead to incorrect behavior.
% For example, the title of each MediaWiki article is repeated several
% times on the page. Mediawiki keeps the title in an object that is
% cached in \memcached. If a user renames the article, MediaWiki will
% update the database, then invalidate the cache entry. An inconsistency
% could easily appear if one user changes the title of an article while
% it is being rendered for another user. When the title is rendered at
% the top of the page, there would be a hit in the cache, so the cached
% title is used. Then the other user renames the article and MediaWiki
% invalidates the cache entry. The second time the title is printed,
% MediaWiki will miss in the cache and retrieve the new title from the
% database, causing the article to have two different titles printed on
% the page. One way to avoid this problem is to only fetch each object
% once, but that would require passing a large number of objects to all
% of the functions that render the page and there could still be
% inconsistencies between objects. In fact, with \memcached, there is no
% way to avoid this problem because it is impossible to get a consistent
% view of the whole system.

Second, they offer a only \command{get}/\command{put} interface,
placing full responsibility for explicitly managing the cache with the
application. Applications must assign names to cached values, perform
lookups, and keep the cache up to date. This has been a common source
of programming errors in applications that use \memcached. In
particular, applications must explicitly \emph{invalidate} cached data
when the database changes. This is often difficult; identifying every
cached application computation whose value may have been changed
requires global reasoning about the application.

% Accordingly, application-level caches have seen use primarily for
% applications for which consistency is not necessary
% (\eg{social networking websites}). In applications with stricter
% consistency requirements (\eg{online banking or e-commerce}), exposing
% inconsistent values to the user can have undesirable consequences. For
% example, in an eBay-like auction site, the item's current price and
% highest bidder might be cached separately. An inconsistency between
% the two could lead a user to observe his own top bid attributed to
% someone else, causing that user to then attempt to outbid himself.
% Furthermore, even in applications where correctness is not critical,
% the potential for inconsistencies leads to more complex application
% logic, because the application must be able to cope with violated
% invariants.

% Developers are thus forced to choose abandoning transactional
% consistency or sacrificing the benefits of application-level
% caching. In this paper, we resolve this tension by extending
% transactional semantics to an application-level cache. We introduce a
% transactional cache, \emph{\txcache{}}, which guarantees that all data
% seen by the application reflects a consistent snapshot of the
% database, whether it comes from application-level objects in the cache
% or from database queries.

We address both of these problems in our transactional cache,
\emph{\txcache{}}. \txcache integrates with a modified database to
provide transactional consistency, guaranteeing that all data
seen by the application reflects a consistent snapshot of the
database, whether it comes from application-level objects in the cache
or directly from database queries. To better utilize cached data,
\txcache allows applications that can tolerate stale data to access
slightly stale but nevertheless consistent snapshots.

\txcache includes a library that provides a simple programming model.
Applications simply designate functions as \emph{cacheable} and the
\txcache library automatically inserts the result of the function into
the cache, and retrieves it the next time the function is called with
the same arguments, provided that it satisfies consistency and
freshness requirements. Rather than requiring applications to provide
explicit invalidations, it tracks dependencies on database objects to
automatically invalidate results when they change.

To achieve these goals, \txcache introduces the following noteworthy
mechanisms:
\begin{itemize}
\item a protocol for ensuring that transactions see only consistent
  cached data by efficiently computing the validity times of
  database queries and attaching them to cache objects
\item a lazy timestamp selection algorithm that assigns a transaction
  to a timestamp in the recent past based on the availability of
  cached data.
\item an automatic invalidation system that tracks each object's
  database dependencies using dual-granularity invalidation tags, and
  produces notifications if they change
\end{itemize}

We tested \txcache using the \rubis auction website
benchmark~\cite{amza02:_specif_and_implem_of_dynam}. Our cache
improved peak throughput by $1.5$ -- $5.2\times$ depending on the
cache size and staleness limit, only slightly less than a
non-transactional cache.
%Our experimental evaluation shows\HERE

The next section gives an overview of the programming model and
consistency semantics. Section~\ref{sec:architecture} sketches the
structure of the system, and
Sections~\ref{sec:cache}--\ref{sec:library} describe each component
in detail. Section~\ref{sec:evaluation} presents our experimental
results, and Section~\ref{sec:related-work} reviews the related work.

% LocalWords:  memcached DRKP lookups versioned timestamp online invalidations
% LocalWords:  serializable Facebook cacheable

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