\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: