\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 implementation
follows the three-tier model, in which client machines contact web
servers that implement the application logic, relying on an underlying
database for storing and managing their persistent state. Frequently,
the database layer becomes the bottleneck, because databases are
difficult to scale effectively.
 
% how people solve it: use application caching
Application data caches are an effective way to reduce the load on the
database. These caches have the added benefit that they reduce
computational load on the application servers as well as query load on
the database server. A promising new approach for building such a
cache has recently emerged: a distributed in-memory shared cache.
This approach, exemplified by \emph{\memcached}~\cite{memcached}, has
seen widespread use on well-known web applications such as LiveJournal
and Facebook, which find it to be the most scalable and cost-effective
way to improve application performance.

% explain how it works
\memcached provides a straightforward hash-table interface, storing
application-defined key to value mappings. The application can use
this hash table in many different ways, from caching the results of
database queries to caching application objects or entire generated
web pages.  \memcached achieves excellent performance and scalability
by storing these mappings in RAM, partitioned across a cluster of
machines. If the data requested is no longer in the cache, memcached
simply notifies the application of a cache miss, forcing it to
recompute the value.

%what's wrong with it
Although flexible and scalable, \memcached has some drawbacks. Most
notably, it does not provide transactional consistency: there is no
way to ensure that two accesses to the cache return consistent values.
In fact, it is nearly impossible to maintain the consistency
guarantees of the backing database while using \memcached.

Accordingly, \memcached has seen use primarily for applications for
which consistency is not particularly critical (\emph{e.g.}~social
networking websites). In applications with stricter consistency
requirements (\emph{e.g.}~online banking or e-commerce), inconsistent
values must never be exposed to the user. 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, for
example, 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
implementations, because they must be able to cope with violated
invariants.

%how we're going to fix it
%more here
We argue that providing transactional semantics is not incompatible
with cache performance and scalability. We introduce a transactional
cache (\txcache), which guarantees that only consistent values are
returned from the cache during a transaction. \txcache ensures this
property by maintaining versions in the cache, associating each cached
item with the times at which it was valid. Thus, transactions can
request data that is valid at a particular timestamp. To take better
advantage of cached data, \txcache allows read-only transactions to
run at timestamps slightly in the past; we show that this does not
impact application correctness.

\HERE
% Adding cache support to an application can also be challenging,
% because most application-level caches, including \memcached, require
% the application to manage the cache. In particular, applications must
% invalidate the cache whenever 

% LocalWords:  memcached DRKP lookups versioned timestamp online

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