\chapter{Introduction} This thesis addresses the problem of maintaining consistency in a cache of application-computed objects. Application-level caches are a popular solution for improving the scalability of complex web applications: they are widely deployed by many well-known websites. They are appealing because they can be implemented with a simple, scalable design, and their flexibility allows them to address many bottlenecks, as we discuss below. However, existing caches place a substantial burden on application developers. They do not preserve the isolation guarantees of the underlying storage layer, introducing potential concurrency bugs. They also place the responsibility for locating and updating data in the cache entirely in the hands of the application, a common source of bugs. Consider, for example, the following report of a major outage at one of the world's most-visited web sites: \begin{quotation} Early today Facebook was down or unreachable for many of you for approximately 2.5 hours. This is the worst outage we’ve had in over four years, and we wanted to first of all apologize for it. We also wanted to provide much more technical detail on what happened and share one big lesson learned. The key flaw that caused this outage to be so severe was an unfortunate handling of an error condition. An automated system for verifying configuration values ended up causing much more damage than it fixed. The intent of the automated system is to check for configuration values that are invalid in the cache and replace them with updated values from the persistent store. This works well for a transient problem with the cache, but it doesn’t work when the persistent store is invalid. Today we made a change to the persistent copy of a configuration value that was interpreted as invalid. This meant that every single client saw the invalid value and attempted to fix it. Because the fix involves making a query to a cluster of databases, that cluster was quickly overwhelmed by hundreds of thousands of queries a second. \dots The way to stop the feedback cycle was quite painful -- we had to stop all traffic to this database cluster, which meant turning off the site. \attrib{Robert Johnson, Facebook~\cite{johnson10:_more_detail_today_outag}} \end{quotation} This incident highlights both the importance of application-level caches -- not a mere optimization, they are a critical part of the site's infrastructure -- and the challenges of cache management. This thesis presents techniques that address these challenges while preserving the flexibility and scalability benefits of existing application-level caches. \section{The Case for Application-Level Caching} 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 storage layer (often a relational database) for managing persistent state. Either layer 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 complex distributed databases. Application server bottlenecks can be easier to address -- simply adding more nodes is usually an option -- but no less costly, as these nodes don't come for free. Not surprisingly, many types of caches have been used to address these problems, ranging from page-level 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} to database replication systems~\cite{kemme00:_dont_be_lazy_be_consis, amza03:_distr, petersen97:_flexib_updat_propag_for_weakl_consis_replic} and query/mid-tier caches~\cite{timesten, mtcache, garrod08:_scalab_query_resul_cachin_for_web_applic}. But increasingly complex application logic and more personalized web content has made it more useful to cache the result of \emph{application computations}. As shown in \autoref{fig:intro:memcache-arch}, the cache does not lie in front of the application servers (like a page-level web cache) or between the application server and database (like a query cache). Rather, it allows application to cache arbitrary objects. These objects are typically generated from the results of one or more database queries along with some computation in the application layer. \begin{figure}[tbp] \centering \includegraphics[scale=0.75]{figures/memcache-arch} \caption{Architecture of a system using an application-level cache} \label{fig:intro:memcache-arch} \end{figure} This flexibility allows an application-level cache to replace existing caches: it can act as database query cache, or it can act as a web cache and cache entire web pages. But application-level caching is more powerful because it can cache \emph{intermediate computations}, which can be even more useful. For example, many web sites have highly-personalized content, rendering whole-page web caches largely useless; application-level caches can separate common content from customized content and cache the common content separately so it can be shared between users. Database-level query caches are also less useful in an environment where processing is increasingly done within the application. Unlike database-level solutions, application-level caches can also address application server load; they can avert costly post-processing of database records, such as converting them to an internal representation, or generating partial HTML output. 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. \section{Existing Caches Are Difficult to Use} Existing application-level caches typically present a hash table interface to the application, allowing it to \command{get} and \command{put} arbitrary objects identified by a key. This interface offers two benefits: \begin{itemize} \item the interface is flexible, in that it allows the application to use the cache to store many different types of objects. As discussed above, it can be used to hold database query results, entire generated web pages, or anything in between. \item the interface lends itself to a simple, scalable implementation. A typical example is \memcached~\cite{memcached}, which stores objects on a cluster of nodes using a consistent hashing algorithm~\cite{karger97:_consis_hashin_and_random_trees} -- making the cache a simple implementation of a distributed hash table~\cite{stoica03:_chord, ratnasamy01:_scalab_conten_addres_networ, rowstron01:_pastr, zhao04:_tapes}. Importantly, the cache is stored entirely in memory, and does not attempt to do any processing other than returning the object identified by the requested key. This architecture scales well; the largest \memcached deployment has thousands of nodes with hundreds of terabytes of in-memory storage~\cite{kwiatkowski10:_memcache}. \end{itemize} But the \command{get}/\command{put} interface has a serious drawback: it leaves responsibility for managing the cache entirely with the application. This presents two challenges for developers, which we address in this thesis. \paragraph{Challenge 1: Transactional Consistency.} First, existing caches do not ensure \emph{transactional consistency} with the rest of the system state. That is, there is no way to ensure that accesses to the cache and the underlying storage layer 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, these consistency guarantees are violated when data is accessed from the cache.. % 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 anomalies caused by inconsistencies between cached objects can cause incorrect information to be exposed to the user. Consider, for example, an eBay-like auction site. Such an application might wish to cache basic metadata about an auction (its title and current price) separately from more detailed information like the history of bidders. This division would be useful because the basic item metadata is used to construct indexes and search results, whereas both objects are needed when a user views the detailed auction information. Placing a new bid should update both objects. If a subsequent request sees inconsistent versions of the objects, it might, for example, display the latest auction price but not the updated bid history, leaving a user confused about whether his bid has been registered. Accordingly, \memcached has seen use primarily for applications for which the consequences of incorrect data are low (\eg social networking websites). Applications with stricter isolation requirements between transactions (\eg online banking or e-commerce) could also benefit from application-level caching: it would improve their performance, reducing their operating costs and allowing them to scale further. However, adding a cache would require them to sacrifice the isolation guarantees provided by the database, a price that many are unwilling to pay. Even in cases where exposing inconsistent data to users is not a serious problem, transaction support can still be useful to simplify application development. Serializable isolation between transactions allows developers to consider the behavior of transactions in isolation, without worrying about the race conditions that can occur between concurrent transactions. Compensating for a cache that violates these guarantees requires complex application logic because the application must be able to cope with temporarily-violated invariants. For example, transactions allow the system to maintain referential integrity by removing an object and any references to it atomically. With a cache that doesn't support transactions, the application might see (and attempt to follow) a reference to an object that has been deleted. \paragraph{Challenge 2: Cache Management.} The second challenge existing caches present for application developers is that they must explicitly manage the cache. That is, the application is responsible for assigning names to cached values, performing lookups, and keeping the cache up to date. This explicit management places a substantial burden on application developers, and introduces the potential for errors. Indeed, as we discuss in \autoref{cha:programming-model}, cache management has been a common source of programming errors in applications that use \memcached. A particular challenge for applications is that they must explicitly \emph{invalidate} data in the cache when updating the backing storage. That is, the cache requires developers to be able to identify every cached application computation whose value might have been affected by a database modification. This analysis is difficult to do, particularly in a complex and evolving application, because it requires global reasoning about the entire application to determine which values may be cached, violating the principles of modularity. % \section{Application-Level Caching Presents New Challenges} % \label{sec:intro:hard} % \begin{outline} % \item previous section argued that the problem is important. But is it % *hard*? or can we just expect to solve it by applying the usual % replication techniques for ensuring consistency? % \item hard because it involves two separate layers: the storage layer % and the application % \item want to support general operations and computations, which means % that we can't make any assumptions about the data format/schema or % what the application might do with it. Not going to assume % application is running some kind of object-relational framework or % get into parsing SQL and PHP to figure out what it's doing. % \item those things make naming/invalidations challenging % \item consistency is hard too % \item the replication systems you might think about applying % to this are really for replicating *data*. Can assume % \item we are dealing with caching *computations*. Can't exactly % compute all possible computations the app might ask for and keep % them up to date all the time. % \item Might want to use data that is out of date. Need a new % consistency protocol that can integrate cached objects that were % computed at different times as long as they're consistent. % \end{outline} \section{Contributions} This thesis addresses both challenges described above in the context of a new transactional, application-level cache which we call \txcache. \txcache aims to preserve the flexibility of existing application-level caches while minimizing the challenges it poses for application developers: adding caching to a new or existing application should be as simple as indicating which data should be cached. We describe how to build an application-level cache that guarantees \emph{transactional consistency} across the entire system. That is, within a transaction, all data seen by the application reflects a consistent snapshot of the database, regardless of whether the data obtained from the cache or computed directly from database queries. This preserves the isolation guarantees of the underlying storage layer. Typically, the entire system can provide serializable isolation (assuming that the database itself provides serializability). \txcache can also provide snapshot isolation, when used with a database that provides this weaker isolation guarantee. \txcache provides a consistency model where the system allows read-only transactions to access stale -- but still consistent -- snapshots. Applications can indicate a freshness requirement, specifying the age of stale data that they are willing to tolerate We argue that this model matches well with the requirements of web applications, and show that it improves cache utilization by allowing cache entries to remain useful for a longer period. % Although our cache guarantees transactional consistency, it does not % guarantee \emph{freshness}: the data seen by applications may not % reflect the latest state of the database. We show that guaranteeing % freshness is impossible without introducing undesirable % blocking. Instead, \txcache intentionally \emph{relaxes} freshness, % requiring applications to indicate the extent to which they can % tolerate stale data. It then provides applications with access to % slightly stale but nevertheless consistent snapshots. This improves % cache utilization by allowing cache entries to remain useful for a % longer period. Furthermore, we propose a simple programming model based on \emph{cacheable functions}. In this model, applications do not need to interact explicitly with the cache, avoiding the challenges of cache management described above. Instead, developers simply designate certain existing application functions as cacheable. A cache library then handles inserting the result of the function into the cache and retrieving that result the next time the function is called with the same arguments. Rather than requiring applications to invalidate cache data, we integrate the database, cache, and library to track data dependencies and automatically invalidate cache data. Towards these ends, this thesis makes the following technical contributions: \begin{itemize} \item a protocol based on \emph{validity intervals} for ensuring that transactions see only consistent data, even though that data consists of cached objects that were computed at different times \item techniques for modifying an existing multiversion database to generate validity information which can be attached to cache objects \item a \emph{lazy timestamp selection} algorithm that selects which snapshot to use for a read-only transaction based on the application's freshness requirement and the availability of cached data. \item an automatic invalidation system, based on \emph{invalidation tags} for tracking the data dependencies of cache objects, and \emph{invalidation locks}, which use a variant on existing concurrency control mechanisms to detect data dependencies and generate notifications when they are modified. \end{itemize} We have implemented the \txcache system. We evaluated the effectiveness of its programming model in two ways. We ported the \rubis web application benchmark, which emulates an auction site, to use \txcache. We also examined \mediawiki, a popular web application that uses \memcached, and analyzed some bugs related to its use of caching. Both experiences suggest that our programming model makes it easier to integrate caching into an existing application, compared to existing caches. We evaluated cache performance using the \rubis benchmark~\cite{amza02:_specif_and_implem_of_dynam}. Compared to a system without caching, our cache improved peak system throughput by $1.5$ -- $5.2\times$, depending on the system configuration and cache size. Moreover, we show that the system performance and cache hit rate is only slightly (less than five percent) below that of a non-transactional cache, showing that consistency does not have to come at the expense of performance. \section{Outline} This thesis is organized as follows: We begin with a high-level overview of the system architecture and how it integrates with existing components in a web application, and state our assumptions (\autoref{cha:arch}). We then describe \txcache's cacheable function programming model, explain how to implement a simplified version of the system that provides this programming model but does not support transactions, and discuss how the programming model can avoid common sources of caching-related application bugs (\autoref{cha:programming-model}). We then turn to the question of how to provide support for whole-system transactional consistency. \autoref{cha:consistency-model} describes the semantics that the system provides for transactions. \autoref{cha:consistency-protocol} explains how the system ensures that all data accessed by the application within a transaction reflects a consistent view of the storage state; it introduces the concept of validity intervals and explains how the cache and library use them. The consistency protocol requires some support from the storage layer; \autoref{cha:storage-layer} explains how to provide this support. We describe both how to design a new storage system (here, a simple block store) to provide the necessary support, and how to retrofit it into an existing relational database. \autoref{cha:invalidations} discusses how the system tracks data dependencies and uses invalidations to notify the cache of database changes that affect cached objects. \autoref{cha:evaluation} evaluates the performance of \txcache using the \rubis benchmark. \autoref{cha:related-work} surveys the related work, and \autoref{cha:conclusion} concludes. \autoref{cha:rw} describes an extension to the system that allows read/write transactions to safely use cached data. \autoref{cha:serializability-appendix} provides an explanation about how \txcache's consistent reads property allows the system to ensure either serializability or snapshot isolation. % LocalWords: memcached DRKP lookups versioned timestamp online invalidations % LocalWords: serializable Facebook cacheable scalability invariants %%% Local Variables: %%% mode: latex %%% TeX-command-default: "Make" %%% TeX-PDF-mode: t %%% TeX-master: "main.tex" %%% End: % LocalWords: transactional modularity serializability multiversion % LocalWords: metadata