\svnInfo $Id$  

\txcache provides a different consistency guarantee than most
caches. Standard caches typically strive to guarantee
\emph{freshness}: the cache always reflects the latest state of what
it is caching. \txcache guarantees \emph{transactional consistency}:
within a transaction block, the application sees a view consistent
with the state of the system (as captured by the database) at a
particular timestamp.  That is, it only sees the effects of other
transactions that had committed prior to that timestamp.
% In other
%words, the transaction is serializable: it can be assigned a position
%in a global serial ordering of transactions.

Ensuring both freshness and transactional consistency 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}. Using locking or
OCC in a cache, however, is not practical, as updates done by
read-write transactions would prevent read-only transactions from
being able to proceed, negating much of the scalability advantage of
the cache.  An alternative cache design might discard any data item
from the cache when it is updated by a transaction, but this also
limits performance by placing additional load on the database server
even in cases where applications are tolerant of non-fresh data.
Thus, a key requirement for \txcache is that read-only transactions
that are tolerant of non-fresh data should not be forced to abort or
block on another transaction, even if that transaction updates data
the read-only transaction accesses.

Instead of locks, previous versions of data can be used to ensure
transactional consistency with an application controlled freshness
tolerance.  \txcache uses this approach, as do multiversion
concurrency control algorithms for databases, such as snapshot
isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level} (used in
PostgreSQL and Oracle, for example) and
others~\cite{sqlserver,interbase,firebird}. In this scheme, read-only
transactions are assigned a timestamp, and only read values that are
current as of that timestamp. Accordingly, the transaction only sees
data committed prior to that timestamp.  Timestamps thus establish the
serialization order of transactions.

\subsection{Running Transactions in the Past}
\label{sec:stale}

Traditionally (\eg{in snapshot isolation}), a transaction is assigned
the most recent timestamp at the time it begins, causing it to see a
``snapshot'' of the database as of that instant. \txcache uses a different
approach whereby a read-only transaction can specify that it is tolerant
of some degree of staleness in the data, causing it to be assigned an
\emph{earlier} timestamp and to be run slightly in the
past. This approach provides two benefits: first, it improves the cache hit
rate by taking advantage of slightly stale cached data.  Second, it makes
it possible to avoid invalidations by explicitly tracking the 
ranges of times for which a cached result is valid, based on the timestamp
of transaction that generated the result.

By running transactions in the past, \txcache can use cached data even
when it is not the most current version available. In particular,
given an application's staleness tolerance $t$, \txcache assigns a
transaction a timestamp (that is at most $t$ seconds old) so as to
maximize the probability that the data it accesses will be available
in the cache; Section~\ref{sec:library:lazy} describes our algorithm
for doing this. The benefit here is that 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.

Running transactions in the past is also the mechanism that makes it
possible for \txcache to operate without invalidations. This is an
important benefit, because we have argued that requiring explicit
invalidations places a high burden on the programmer. The approach we
took in building \txcache is to modify the database server to report
the interval during which a result is valid
(Section~\ref{sec:database:validity} describes the necessary
modifications). \txcache tracks these intervals, and associates them
with each value stored in the cache.  Then, when a transaction invokes
a cacheable function in a transaction with a given timestamp, \txcache
can determine whether any cached values of that function can be reused
by comparing the transaction's timestamp to the validity intervals in
the cache.  \edatnote{DRKP}{This is not a great explanation --- maybe
  when I'm less sleepy...}

\subsection{Avoiding Anomalies}
\label{sec:stale:anomalies}

\txcache allows read-only transactions to run in the past, where they
may see potentially stale data. One potential concern is that using
such stale data might introduce alarming new anomalies, or be
incompatible with the operation of most applications.  We here argue
that these consistency semantics do in fact align well with
application requirements and user expectations.

The reason that this approach is safe 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 happen to 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 state
of the system, but there is no guarantee that it is the latest
state. By the time the result is returned to the user, a concurrent
update might have made it already 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 (e.g., a ticket reservation is held until paid for),
some kind of lease or long-duration lock is necessary; \txcache does
not interfere with these techniques.

To prevent application anomalies, some restrictions are necessary on
how far in the past transactions can run. \txcache makes it possible
for applications to express these freshness requirements. The first
requirement is straightforward: after a user has seen some data with
timestamp $t$, he should only see data that is valid after timestamp
$t$. This requirement can easily be enforced: the application keeps
track of the latest timestamp the user has seen, and requests that
\txcache never allow a read-only transaction to run before that
timestamp. The timestamp can be stored in the user's per-session
state, \eg{by storing it in a HTTP cookie}.

\edatnote{srm}{Suggest cutting this -- sounds complicated, and not
  clear to me one would ever really do this.}  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}. 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 prevent this from becoming a serious 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 depends on the application requirements; some
applications may be willing to tolerate significantly-stale data.

%%% Local Variables: 
%%% mode: latex
%%% TeX-command-default: "Make"
%%% TeX-PDF-mode: t
%%% TeX-master: "paper.tex"
%%% End: 

% LocalWords:  timestamp serializable transactionally multiversion
% LocalWords:  serializability invalidations