\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
