\svnInfo $Id$ \txcache is designed for systems consisting of one or more application servers that interact with a database server. These application servers could be web servers running embedded scripts (\eg{with \texttt{mod\_php}}), or dedicated application servers, as with Sun's Enterprise Java Beans. The database server is a standard relational database; for simplicity, we assume the application uses a single database to store all of its persistent state. \begin{figure}[tp] \centering \includegraphics{arch3.pdf} \caption{Key components in a \txcache deployment. The system consists of a single database, a set of cache nodes, and a set of application servers. \txcache also introduces an application library, which handles all interactions with the cache server.} \label{fig:architecture} \end{figure} \txcache introduces two new components, as shown in Figure~\ref{fig:architecture}: a cache and an application-side cache library, as well as some minor modifications to the database server. The cache is partitioned across a set of cache nodes, which may run on dedicated hardware or share it with other servers. The application never interacts with the cache servers; the \txcache library transparently translates an application's cacheable functions into cache accesses. \subsection{Programming Model} \label{sec:model:programming} Our goal is to make it easy to incorporate caching into a new or existing application. Towards this end, \txcache provides an application library with a simple programming model, shown in Figure~\ref{fig:library-api}, based on \emph{cacheable functions}. Applications developers can cache computations simply by designating functions to be cached. % XXX Library also provides consistency. \begin{figure}[t] \newcommand{\cmdarg}[1]{\textit{#1}} \addtolength{\leftmargini}{1.5em} \begin{itemize} \itemindent=-1.5em \item \command{begin-ro}(\cmdarg{staleness}) : Begin a read-only transaction. The transaction sees a consistent snapshot from within the past \cmdarg{staleness} seconds. \item \command{begin-rw}() : Begin a read/write transaction. \item \command{commit}() $\to$ \cmdarg{timestamp} : Commit a transaction and return the timestamp at which it ran \item \command{abort}() : Abort a transaction \end{itemize} \vspace{0.2em} \begin{itemize} \itemindent=-1.5em \item \command{make-cacheable}(\cmdarg{fn}) $\to$ \cmdarg{cached-fn} : Makes a function cacheable. \cmdarg{cached-fn} is a new function that first checks the cache for the result of another call with the same arguments. If not found, it executes \cmdarg{fn} and stores its result in the cache. \end{itemize} \vspace{0.2em} \if 0 \begin{itemize} \itemindent=-1.5em \item \command{query}(\cmdarg{SQL}) $\to$ \cmdarg{result} : Sends a SQL query to the database server. \end{itemize} \fi \caption{TxCache library API} \label{fig:library-api} \end{figure} Programs group their operations into transactions. \txcache requires applications to specify whether their transactions are read-only or read/write by using either the \command{begin-ro} or \command{begin-rw} function. Transactions are ended by calling \command{commit} or \command{abort}. Within a transaction block, \txcache ensures that, regardless of whether the application gets its data from the database or the cache, it sees a view consistent with the state of the database at a single point in time. % through the % \txcache library's \command{begin} and \command{commit} % functions. When starting a transaction, the program declares whether % it will be a read-only or read/write transaction. If read-only, the % application can also specify any requirements for how fresh the data % must be; Section~\ref{sec:stale:anomalies} discusses how applications % can use these freshness requirements. We focus on optimizing % read-only transactions, as these are most common in most % workloads.\edatnote{DRKP}{Citation for this?} Read/write transactions % do not take advantage of caching; \txcache's library forwards them % directly to the database, so they execute exactly as they would on an % unmodified system. Within a transaction, operations can be grouped into \emph{cacheable functions}. These are actual functions in the program's code, annotated to indicate that their results can be cached. A cacheable function can consist of database queries and computation, and can also make calls to other cacheable functions. To be suitable for caching, functions must be pure, \ie{} they must be deterministic, not have side effects, and depend only on their arguments and the database state. For example, it would not make sense to cache a function that returns the current time. \txcache currently relies upon programmers to ensure that they only cache suitable functions, but this requirement could also be enforced using static or dynamic analysis~\cite{guo10:_towar_pract_increm_recom_scien, salcianu05:_purit_side_effec_analy_java_progr}. %We believe it is reasonable %for programmers to identify such cacheable functions. Cacheable functions are essentially memoized. \txcache's library provides a \command{make-cacheable} function that takes an implementation of a cacheable function and returns a wrapper function that can be called to take advantage of the cache. When called, the wrapper function checks if the cache contains the result of a previous call to the function with the same arguments that is consistent with the current transaction's snapshot. If so, it returns it. Otherwise, it invokes the implementation function and stores the returned value in the cache. With proper linguistic support (\eg{Python decorators}), marking a function cacheable can be as simple as adding a tag to its existing definition. Our cacheable function interface is easier to use than the \command{get}/\command{put} interface provided by existing caches like \memcached. It does not require programmers to manually assign keys to cached values and keep them up to date. Although seemingly straightforward, this is nevertheless a source of errors because selecting keys requires reasoning about the entire application and how the application might evolve. Examining MediaWiki bug reports, we found that several \memcached-related MediaWiki bugs stemmed from choosing insufficiently descriptive keys, causing two different objects to overwrite each other~\cite{mediawiki-keys}. In one case, a user's watchlist page was always cached under the same key, causing the same results to be returned even if the user requested to display a different number of days worth of changes. \txcache's programming model has another crucial benefit: it does not require applications to explicitly update or invalidate cached results when modifying the database. Adding explicit invalidations requires global reasoning about the application, hindering modularity: adding caching for an object requires knowing every place it could possibly change. This, too, has been a source of bugs in MediaWiki~\cite{mediawiki-invalidations}. For example, editing a wiki page clearly requires invalidating any cached copies of that page. But other, less obvious objects must be invalidated too. Once MediaWiki began storing each user's edit count in their cached \textsc{User} object, it became necessary to invalidate this object after an edit. This was initially forgotten, indicating that identifying all cached objects needing invalidation is not straightforward, especially in applications so complex that no single developer is aware of the whole of the application. % \txcache instead tracks each application data object's dependencies on % particular database state, and automatically generates invalidations % when it is updated. To achieve this, the \txcache library interposes % on an application's database queries, as noted in % Figure~\ref{fig:library-api}. However, it does so only to receive % metadata from the database server, as noted in % Section~\ref{sec:library}. It does not attempt to parse or rewrite the % SQL queries or results themselves. \subsection{Consistency Model} \label{sec:model:consistency} \txcache provides \emph{transactional consistency}: all requests within a transaction see a consistent view of the system as of a specific timestamp. That is, requests see only the effects of other transactions that committed prior to that timestamp. For read/write transactions, \txcache supports this guarantee by running them directly on the database, bypassing the cache entirely. Read-only transactions use objects in the cache, and \txcache ensures that nevertheless they view a consistent state. \if 0 It is not practical to simultaneously guarantee both transactional consistency and \emph{freshness}, where the cache reflects the latest state of the system. To do so would require a concurrency control scheme like two-phase locking~\cite{gray77:_granul_of_locks_and_degrees} or optimistic concurrency control~\cite{kung81:_optim_method_for_concur_contr}. Then, read-only transactions, even ones that access only the cache, could be blocked or force other transactions to block or retry, negating the benefits of the cache. In order to provide consistency without requiring transactions to block, \txcache relaxes its freshness guarantee for read-only transactions. It achieves this using a multiversion concurrency control approach similar to snapshot isolation databases~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}, where read-only transactions are assigned a timestamp, and then are only allowed to read values that are current as of that timestamp. \fi Most caches return slightly stale data simply because modified data does not reach the cache immediately. \txcache goes further by allowing applications to specify an explicit \emph{staleness limit} to \command{begin-ro}, indicating that that the transaction can see a view of data from that time or later. However, regardless of the age of the snapshot, each transaction always sees a consistent view. This feature is motivated by the observation that many applications can tolerate a certain amount of staleness~\cite{keeton09:_lazyb}, and using stale cached data can improve the cache's hit rate~\cite{liskov04:_trans_file_system_can_be_fast}. Applications can specify their staleness limit on a per-transaction basis. Additionally, when a transaction commits, \txcache provides the user with the timestamp at which it ran. Together, these can be used to avoid anomalies. For example, an application can store the timestamp of a user's last transaction in its session state, and use that as a staleness bound so that the user never observes time moving backwards. More generally, these timestamps can be used to ensure a causal ordering between related transactions~\cite{lamport78:_time_clock_and_order_of}. We chose to have read/write transactions bypass the cache entirely so that \txcache does not introduce new anomalies. The application can expect the same guarantees (and anomalies) of the underlying database. For example, if the underlying database uses snapshot isolation, the system will still have the same anomalies as snapshot isolation, but \txcache will never introduce snapshot isolation anomalies into the read/write transactions of a system that does not use snapshot isolation. Our model could be extended to allow read/write transactions to read information from the cache, if applications are willing to accept the risk of anomalies. One particular challenge is that read/write transactions typically expect to see the effects of their own updates, while these cannot be made visible to other transactions until the commit point. %%% Local Variables: %%% mode: latex %%% TeX-PDF-mode: t %%% TeX-master: "paper.tex" %%% End: % LocalWords: versioned versioning php timestamp Cacheable cacheable memoized % LocalWords: invalidations