\chapter{Consistency Model} \label{cha:consistency-model} \txcache is designed to make application-level caching easy to integrate with existing systems. The cacheable function model described in the previous chapter supports this goal by making caching transparent: designating a function as cacheable should not produce any visible difference to callers of that function. However, there is one way in which the cache we have described so far violates transparency: like other existing caches, it does not provide support for transactions. Without the cache, the application accesses the storage layer directly and can rely on it to ensure isolation between transactions (\eg serializability). If the application uses data from the cache, however, there is no guarantee that cached values will be consistent with each other or with data from the database. The second goal of this work, therefore, is to provide transaction support in an application-level cache. Our model of consistency ensures isolation between transactions but explicitly trades off freshness, allowing applications to see slightly stale states of data in the cache. Nevertheless, the data is still consistent: the whole system can guarantee either serializability or snapshot isolation, depending on which the storage layer provides. This chapter defines these properties and argues that the relaxed freshness guarantee is appropriate for applications. \section{Transactional Consistency} \label{sec:consistency-model:transactional-consistency} \txcache provides transactional consistency for applications that use the cache. Our goal here is to preserve the isolation guarantees of the underlying storage layer. Most existing caches fall short at this goal: while they are typically used with databases capable of ensuring strong isolation between transactions (\eg serializability or snapshot isolation), the caches do not ensure consistency between data accessed from the cache and data accessed from the database. In contrast, \txcache ensures system-wide isolation guarantees. The strongest guarantee the system can provide is serializability: \begin{definition}{serializable isolation} the execution of concurrent transactions produces the same effect as an execution where transactions executed sequentially in some order \end{definition} This property is the standard correctness criterion for concurrent execution of transactions. Most databases provide serializable isolation as an option (as required by the ANSI SQL standard~\cite{ansi92:_datab_languag_sql}). When used with such a database, \txcache provides whole-system serializability: it ensures serializable isolation of transactions regardless of whether the data they access comes from the cache or directly from the database. We focus on serializable isolation because it is the strongest standard isolation level. Its strong semantics fit well with our goals because they simplify application development: developers can be certain that if their transactions do the right thing when run alone, they will continue to do so in any mix of concurrent transactions. \txcache ensures that this continues to be true even when the application accesses cached data. \txcache also supports storage systems that do not provide serializability, but instead offer the weaker guarantee of \emph{snapshot isolation}: \begin{definition}{snapshot isolation} each transaction reads data from a snapshot of the committed data as of the time the transaction started, and concurrent transactions are prevented from modifying the same data object \end{definition} Snapshot isolation is known to be a weaker property than serializability, allowing race conditions between concurrent transactions to cause anomalies that would not occur in a serial execution~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}. Nevertheless, it is a popular option for storage systems to provide (both relational databases and other systems~\cite{peng10:_large_increm_proces_using_distr_trans}) because it allows more concurrency than serializability, while still preventing many of the most common anomalies. When used with a database that provides snapshot isolation, \txcache provides snapshot isolation for the whole system: it ensures that every transaction sees a consistent snapshot of the data regardless of whether it comes from the cache or the database. Snapshot isolation the weakest isolation level that our system supports. Even weaker isolation levels are also common -- for example, most databases provide a \textsc{read committed} mode that ensures only that transactions do not see uncommitted data -- but it is not clear that it would be reasonable to use these with our system. In these cases, our cache would provide a \emph{stronger} isolation guarantee than the database, which is unlikely to be useful. % \begin{quotation} % \textbf{Transactional Consistency Property}: within a transaction, any % data the application accesses reflects a consistent view of the % storage layer as of a particular instant in time. Any queries sent % directly to the storage layer appear to execute at that instant, and % any cached objects accessed have the same values as though they were % computed from queries at that instant. % \end{quotation} % We purposely phrase our transactional consistency guarantee this way % rather than in more conventional terms like serializability or % snapshot isolation, because these isolation levels are a property of % the \emph{entire system}, including the storage layer. Therefore, they % depend on what guarantees the storage layer itself provides. As we % discuss in \autoref{sec:consistency-model:combining}, \txcache can % provide whole-system serializability when used with a database that % guarantees serializability. If used with a database that only provides % a weaker isolation level, such as snapshot isolation, \txcache provides % correspondingly weaker semantics. % \txcache also provides an important performance property: it does not % itself cause read-only transactions to block or abort. This property % is particularly appealing when the cache is used with a storage layer % that also guarantees that read-only transactions will never block or % abort, as the cache preserves this guarantee. (As we discuss in % \autoref{sec:consistency-model:combining}, some -- but not all -- % multiversion concurrency control systems provide this guarantee.) \section{Relaxing Freshness} \label{sec:consistency-model:relaxing-freshness} Our system guarantees transactional consistency (either serializability or snapshot isolation) but does not attempt to guarantee \emph{freshness}: the data in the cache may not reflect the latest data in the storage layer. \txcache relaxes this property in order to provide better performance for applications that can tolerate some stale data. Typical caches strive to keep the data in the cache as up to date as possible with respect to the backing store. Despite this, keeping the cache completely up to date is not practical. Most caches return slightly stale data simply because modified data does not reach the cache immediately. To ensure that the cache always reflects the latest changes made to its backing store would require using locking and an atomic commitment protocol between the cache and storage (\eg two-phase commit). This expensive protocol would negate much of the performance benefit of the cache. Furthermore, even with such an implementation, clients still do not have any guarantee that the values returned from the cache are up to date \emph{by the time they are received by the client}. Trading off freshness for consistency is a common strategy in concurrency control. For example, in snapshot isolation, all data read by a transaction reflects a snapshot of the database taken at the time the snapshot began~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}. This allows read-only transactions to run without blocking read/write transactions, at the expense of freshness: the read-only transaction might see older values of objects that were modified while it ran. % Our transactional consistency goal is also at odds with freshness. % To % ensure both properties requires using a % concurrency control scheme like two-phase % locking~\cite{gray77:_granul_of_locks_and_degrees} or optimistic % concurrency control % (OCC)~\cite{kung81:_optim_method_for_concur_contr}. % In such schemes, read-only transactions can be forced to abort, block % on other transactions, or cause other transactions to block. % For example, if a read-only transaction reads a value, and then a % read/write transaction attempts to modify it, either one transaction % must abort, or the read/write transaction must wait for the read-only % transaction to finish. If the read/write transaction were allowed to % make its modification, and the read-only transaction reads the value % again, either the freshness requirement or the consistency requirement % will be violated: the old value is no longer fresh, but the new value % is not consistent with its previous read. Using locking or OCC % resolves these problems, but is not a practical approach for a cache, % as updates done by read/write transactions would prevent read-only % transactions from being able to proceed or force them to abort, % negating much of the scalability advantage of the cache. Freshness is explicitly not a goal of our system. Instead, we allow read-only transactions to see somewhat stale, but still consistent views. That is, read-only transactions effectively read data from a snapshot taken up to $t$ seconds \emph{before} the transaction started. (Read/write transactions, on the other hand, always see the latest data, for reasons we discuss in \autoref{sec:consistency-model:rw}.) 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}. The staleness limit $t$ can be specified by the application, reflecting that different applications tolerate different levels of stale data. It can even be specified on a per-transaction basis, because different operations may have significantly different requirements. This means that there is a total order of the states visible to each read-only transaction, but that this order need not match the order in which transactions start or commit. That is, the system can provide serializability of these transactions, but does not provide linearizability~\cite{herlihy90:_linear}, a stronger condition that requires that operations take effect at some point between their invocation and response. (This comparison is somewhat imprecise, in that linearizability is defined in terms of individual operations, whereas our guarantees are in terms of multi-operation transactions.) The increased flexibility of allowing transactions to see older states improves the cache hit rate by allowing access to cached data even when it is not the most current version available. If multiple transactions access the same data within a short interval, they can use the same cached value, even if that value was updated in the meantime. As our experiments in \autoref{sec:eval:staleness} show, this is an important benefit for frequently-updated data. \subsection{Dealing with Staleness: Avoiding Anomalies} \label{sec:consistency-model:relaxing-freshness:anomalies} Because \txcache allows read-only transactions to run in the past, where they may see stale data, one potential concern is that using stale data might introduce new anomalies, or be incompatible with some applications. We argue here that these consistency semantics do in fact align well with application requirements and user expectations, as long as some restrictions are imposed on how far in the past transactions can run. \txcache makes it possible for applications to express these restrictions as freshness requirements. The main freshness requirement applications typically have is \emph{causality}: after a user has seen some data from a particular time, later actions on behalf of that user should not see older data. This requirement can easily be enforced: the application keeps track of the latest timestamp the user has seen, and specifies that \txcache should require a read-only transaction to run no earlier than that timestamp. \txcache leaves it to the application to track this and specify the appropriate freshness constraint, rather than attempting to implement causality tracking in the \txcache library, because causality requirements are application-specific. For example, a web service might consist of multiple application servers, each processing requests from many users; each user's requests should see a later state than that user's previous requests, even if they were processed by a different server. Furthermore, the data seen by one user should not impose restrictions on a transaction run by a \emph{different} user that happens to execute on the same server. In this case, the application can store the timestamp in each user's per-session state, \eg by storing it in a HTTP cookie. More generally, in distributed applications where multiple application servers interact with each other, causal interactions can be tracked using Lamport clocks~\cite{lamport78:_time_clock_and_order_of}, as used in systems like Thor~\cite{liskov99:_provid_persis_objec_in_distr_system} and ISIS~\cite{birman87:_exploit_virtual_synch_in_distr_system}. The reason that it is safe to run transactions in the past is that, within a short time period, applications must already be tolerant of transactions being reordered. If, for example, a read-write transaction $W$ and a read-only transaction $R$ are sent at nearly the same time, the database might process them in either order, and so $W$'s change might or might not be visible to $R$. Either result must be acceptable to the client executing $R$, unless it knows that $W$ took place from some external source. In other words, unless a causal dependency between the two clients exists, their transactions can be considered concurrent (in the sense of Lamport's \emph{happens-before} relation~\cite{lamport78:_time_clock_and_order_of}) and hence either ordering is acceptable. This type of consistency also fits well with the model of a web service. Users expect that the results they see reflect a recent, consistent state of the system, but there is no guarantee that it is the \emph{latest} state. By the time the result is returned to the user, a concurrent update might have made it stale. Indeed, if executed on a snapshot isolation database, there is no guarantee that the results are even current at the time the database returns an answer; new committed results may have arrived during query execution. If a transparent web cache is present, these effects are exacerbated. Even without a cache, to ensure that a result remains correct until the user acts on it (\eg an airline ticket reservation is held until paid for), some kind of lease or long-duration lock is necessary; \txcache does not interfere with these techniques, because it does not affect read-write transactions. % Each server keeps % track of the latest timestamp from which it has seen data, and % includes it in the messages. Whenever a server receives a message % containing a newer timestamp, it updates its timestamp. When starting % a read-only transaction, each server specifies its timestamp, and % \txcache ensures that the new transaction is ordered after it. Of course, causal interactions external to the system cannot be tracked. For example, nothing can be done about a user who sees a result on one computer, then moves to another computer and loads the same page. To limit the impact of this problem, applications can request a minimum freshness, \eg they might never be willing to accept data more than 30 seconds old. The value of this minimum freshness may vary dramatically depending on application requirements; some applications are able to tolerate significantly stale data. % \begin{outline} % \item forcing programmers to be explicit about how much staleness % their transaction can tolerate might even prevent bugs by making it % clear that this is an issue? % \end{outline} \section{Read/Write Transactions} \label{sec:consistency-model:rw} Our consistency model allows \emph{read-only} transactions to see stale data. We do not, however, allow read/write transactions to see stale data. We forbid this because it can allow certain non-serializable anomalies that would make it more difficult for application developers to ensure correct behavior. An application might read some cached objects, seeing an earlier state of the system, and use these to make an update. Consider the example of an auction website, which we discuss in \autoref{cha:evaluation}. Here, a small amount of staleness is useful for read-only queries: it is acceptable if the list of auctions is a few seconds out of date. But it is important to use the latest data for updates: if a user requests to place a bid, and the system sees stale data when checking if the bid is higher than the previous one, it might miss an even higher bid placed in the interim. These types of concurrency bugs are similar to the anomalies that can occur when using a snapshot isolation database~\cite{berenson95:_critiq_of_ansi_sql_isolat_level} -- but worse, because our relaxed-freshness model would allow applications to see a snapshot of the system from \emph{before} the transaction start. (This model has been formalized as Generalized Snapshot Isolation~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat}.) Our system could easily be adapted to work in this way, but we prefer the simpler approach of not allowing read/write transactions to see stale data, on usability grounds. It has been our experience that even the anomalies resulting from snapshot isolation are poorly understood by developers, and the analysis required to detect these anomalies is difficult to do~\cite{ports12:_serial_snaps_isolat_postg}. The fact that snapshot isolation anomalies have been discovered in deployed systems supports this conclusion~\cite{jorwekar07:_autom_detec_snaps_isolat_anomal}. A simple way to ensure that read/write transactions do not see stale data is to prevent them from using the cache entirely. In our implementation, we use the cache only for read-only transactions and bypass it for read/write transactions; read/write transactions access the storage layer directly, using its normal concurrency control mechanisms. Our experiments (\autoref{cha:evaluation}) show that this approach is effective for workloads with a high fraction of read-only transactions, a common pattern for many web applications. We describe a more sophisticated approach in \autoref{sec:extensions:rw} that allows read/write transactions to use cached objects. It uses an approach based on optimistic concurrency: when executing a read/write transaction, clients only access the latest versions of data from the cache, and validate on commit that the data they read remains current. An additional complication, which we also address in \autoref{sec:extensions:rw}, is that read/write transactions need to be able to see the effects of modifications made earlier in the transaction, but these effects should not become visible to other concurrent transactions until the transaction commits. % \drkp{Was going to describe more of the solution here, but decided to % move it to an extensions chapter or something -- the solution makes % use of invalidation tags, and we haven't described those yet.} \section{Transactional Cache API} \label{sec:consistency-model:api} The \txcache API is summarized in \autoref{fig:transactional-api}. The \command{make-cacheable} function remains as described in \autoref{sec:programming-model:model}. Now, the API also allows programmers to group 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 guarantees that all data seen by the application is consistent with a single state of the storage layer. The \command{begin-ro} operation takes the application's freshness requirement as an argument. This requirement can be expressed either in real-time terms (\eg the application is only willing to accept states from within the last 30 seconds) or logical terms (\eg the application must see a state at least as recent as a particular transaction). The latter option is intended to support causal consistency requirements such as ensuring that each user sees the effects of their latest change. Here, transactions are identified by \emph{timestamps}, as discussed in \autoref{cha:consistency-protocol}. The \command{commit} operation returns the timestamp at which a transaction ran; the application can subsequently use that timestamp as an argument to \command{begin-ro} to start a new transaction that must see the effects of the previous one. \begin{figure}[t] \begin{itemize} \itemindent=-1.5em \item \command{begin-ro}(\cmdarg{freshness-requirement}) : Begin a read-only transaction. The transaction sees a consistent view of the system state that satisfies the freshness requirement. \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} \caption{\txcache transactional API} \label{fig:transactional-api} \end{figure} % \section{Combining Cache and Storage Consistency Guarantees} % \label{sec:consistency-model:combining} % What kind of guarantees can a user of the system ultimately expect? % Ideally, the system would provide global serializability for all % transactions. \txcache can guarantee serializable isolation for the % entire system as long as the storage layer itself can execute % transactions with serializable isolation. (We also consider weaker % isolation levels below.) % Furthermore, we would like read-only transactions to never be required % to block, abort, or cause other transactions to block or % abort. Whether this is possible depends on how the storage layer % implements serializability. In particular, it depends on whether the % storage layer has the following ordering property: % \begin{quote} % the order in which transactions commit is the same as the apparent % serial order of execution. % \end{quote} % Note that this property is not required for serializability. (Indeed, % \txcache itself does not provide it!) % Several common serializability implementations do have this % property. For example, two-phase % locking~\cite{eswaran76:_notion_consis_predic_locks_datab_system, % gray77:_granul_of_locks_and_degrees} has this property, as does Kung % and Robinson's optimistic concurrency control % protocol~\cite{kung81:_optim_method_for_concur_contr}. With these % methods, any read-only transaction that runs on a consistent snapshot % of the system is serializable.\footnote{It is easy to verify that this % is true: a snapshot is defined by the set of transactions that % committed before the transaction and are therefore visible to it. If % the commit order matches the apparent serial order, than the set of % transactions visible in the snapshot is a prefix of the serial % order, and therefore a read-only transaction running on that % snapshot can serialized at that point in the serial order.} As a % result, \txcache's transactional consistency property guarantees % serializability. Importantly, it guarantees serializability without % any further involvement from the database's concurrency control, % beyond providing access to earlier versions. For example, because % read-only transactions run on a consistent snapshot, they do not need % to acquire locks or perform OCC validation. This provides the % desirable property that read-only transactions will not need to block % or abort, or cause other transactions to block or abort. % However, not all serializability implementations have this % property. For example, approaches based on serialization graph % testing~\cite{casanova81:_concur_contr_probl_datab_system} do not. One % example is Serializable Snapshot Isolation % (SSI)~\cite{cahill08:_serial_isolat_snaps_datab}, which is the basis % for the serializable isolation level in the \postgres % DBMS~\cite{ports12:_serial_snaps_isolat_postg} that we use in our % implementation of \txcache. This approach guarantees serializability, % but the serial order may not match the order in which transactions % commit. A consequence of this is that transactions -- even read-only % transactions running on a consistent % snapshot~\cite{fekete04:_read_only_trans_anomal_under_snaps_isolat} -- % may see anomalous, non-serializable states. SSI deals with this by % monitoring the read sets of all transactions to detect conflicts and % resolve them by aborting transactions. Because even read-only % transactions are subject to this monitoring, this has two implications % for \txcache. First, it needs some additional support from the % database to ensure that the conflict detection is done correctly for % read-only transactions that access the cache; we discuss this in % \autoref{XXX}. Second, this conflict detection might require some read-only % transactions to abort, or cause other read-only transactions to abort. % \begin{outline} % \item related work on this: % \item combining snapshot reads for r/o transactions with S2PL: % \cite{chan85:_implem_distr_read_only_trans, % chan82:_implem_integ_concur_contr_recov_schem, % bernstein83:_multiv_concur_contr}. % \item ordering property is useful: shown to be composable (as % ``dynamic atomicity'') in % \cite{weihl84:_specif_implem_atomic_data_types} % \end{outline} % \subsubsection{Weaker Isolation Levels} % We focus on serializable isolation because it is the strongest % standard correctness criterion for serializable isolation. These % strong semantics fit well with our goals because they can simplify % application development: developers can be certain that if their % transactions individually do the right thing, then they will continue % to do so even in any mix of concurrent transactions. However, it is % common practice for databases and other storage systems to provide % weaker isolation levels -- and, in many cases, for users to prefer % them -- because this can increase concurrency. % One common weak isolation level is snapshot isolation, which % guarantees that each transaction reads data from a consistent view of % the system, and prevents concurrent transactions from modifying the % same object. This isolation level does not provide serializability, % although it avoids several of the ``classic'' concurrency control % anomalies~\cite{berenson95:_critiq_of_ansi_sql_isolat_level, % adya00:_gener_isolat_level_defin}. It is widely used, however, because % it allows more concurrency than serializability. For example, Oracle's % DBMS provides snapshot isolation as its highest isolation level, as % did earlier versions of \postgres. % When used with a database providing snapshot isolation, \txcache's % transactional consistency property certainly ensures that the system % provides snapshot isolation. \txcache guarantees that read-only % transactions see a consistent snapshot, which is precisely the % requirement for snapshot isolation. (Snapshot isolation also requires % that concurrent read/write transactions cannot make conflicting % updates, but the cache does not interfere with these.) % Snapshot isolation is likely the weakest isolation level that would be % reasonable to use with our system. Weaker isolation levels are also % common -- for example, most databases provide a \textsc{read % committed} mode that ensures only that transactions do not see % uncommitted data -- but these are not a target use case for our % system. With these, the cache is providing a \emph{stronger} isolation % guarantee than the database, which is unlikely to be useful. % \subsubsection{Distributed Storage} % \drkp{Was going to put a section here, but maybe it's better to move % all mention of this to the extensions chapter} % \begin{outline} % \item this is harder! % \item 2PC systems are probably going to have to block sometimes, % because it isn't possible to read the value of an object that's in % the prepare phase: we don't know whether it's committed yet or at % what timestamp. % \item might be reasonable to run this on a system that doesn't do 2PC, % since many people don't use distributed transactions in practice. It % doesn't guarantee serializability for distributed read-only % transactions anymore, though -- even if you get a consistent % timestamp it might still be possible that one transaction already % committed on one node but not yet on another. % \end{outline} %%% Local Variables: %%% mode: latex %%% TeX-command-default: "Make" %%% TeX-PDF-mode: t %%% TeX-master: "main.tex" %%% End: % LocalWords: transactional serializability serializable timestamp % LocalWords: multiversion linearizability Lamport multi Kung OCC % LocalWords: Robinson's SSI cacheable SQL API