\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 the use of 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
\memcached~\cite{memcached},
Velocity/AppFabric~\cite{sampathkumar09:_introd_cachin_window_server_appfab_beta}
and NCache~\cite{ncache}, 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 do not 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 only a \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 problems in our transactional cache,
\emph{\txcache{}}.  \txcache provides the following features:
\begin{itemize}
\item transactional consistency: all data seen by the application
  reflects a consistent snapshot of the database, whether the data
  comes from cached application-level objects or directly from
  database queries.

\item access to slightly stale but nevertheless consistent snapshots
  for applications that can tolerate stale data, improving cache
  utilization.

\item a simple programming model, where applications simply designate
  functions as cacheable. The \txcache library then handles inserting
  the result of the function into the cache, retrieving that result
  the next time the function is called with the same arguments, and
  invalidating cached results when they change.
\end{itemize}

To achieve these goals, \txcache introduces the following noteworthy
mechanisms:
\begin{itemize}
\item a protocol for ensuring that transactions see only consistent
  cached data, using minor database modifications to compute 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 ported the \rubis auction website prototype and \mediawiki, a
popular web application, to use \txcache, and evaluated it using the
\rubis 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, an improvement oonly slightly below
that of a non-transactional cache.
%Our experimental evaluation shows\HERE

The next section presents 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:exp} describes our
experiences porting applications to \txcache,
Section~\ref{sec:evaluation} presents a performance evaluation, 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: