% -*- TeX-master: "report.tex"; TeX-PDF-mode: t -*-

The client-server protocol divides into three separate, but
interacting sub-protocols: A protocol for filling and maintaining
client-side caches, a protocol for committing read/write transactions,
and a protocol for assigning read-only transaction timestamps.

\subsubsection{Cache Coherence}
\label{sec:algorithm:protocol:cache}

% Key points
% * The server maintains a multiversion block store, which each client
%   maintains a local cache of
% * Because of its multiversion nature, the unit of storage---a
%   version---is essentially immutable, except that the latest version
%   of a block, which has an unknown upper bound in time, can be
%   replaced, and thus gain a known upper bound.  Asynchronous
%   deprecation messages are used to keep client caches up to date
%   about the upper bounds of versions
% * Updates always occur in monotonically increasing order, so client
%   caches keep track of a \emph{global least upper bound} (GLUB), a
%   timestamp before which no further updates can occur.  (Moved to
%   read-only transactions, since that's really what the GLUB affects,
%   even though it's maintained by the cache)

\begin{figure*}[ht]
  \centering
  \includegraphics{protocol.pdf}
  \caption{Protocol example with two clients.  (1)~Initially, the server
    is storing two blocks spanning times~1 to~3.  Both blocks have a
    single historical version and no clients are in either block's
    holder sets.  (2)~Client~1 requests A at time~2.  The server
    replies with the historical contents of A and the time range of
    that version.  (3)~Client~2 requests the latest version of B.  The
    server replies with the current contents and time range of B.
    Client~2's cache will now contain an unbounded copy of B, so the
    server adds client~2 to the B's holder set.  (4)~Client~1 requests
    B at time~2.  This is the current version of B, so the server adds
    client~1 to B's holder set.  (5)~Client~2 performs a commit,
    indicating which version of B it read and proposing a
    new version of B.  After validating the commit request, the server
    replies with the time assigned to the transaction.  Because the
    latest version of B was replaced, the server removes all of the
    clients from the holder set except the committing client and sends
    deprecations to these clients.}
  \label{fig:protocol}
\end{figure*}

The server maintains a multiversion block store, such as the one
depicted in step~(1) of Figure~\ref{fig:protocol}.  Each block in the
block store consists of a set of \emph{versions}, each of which is
valid over some non-overlapping range of time.  The current version of
a block is \emph{unbounded}, meaning that its upper bound is unknown
until a write to that block installs a new version at some later time.

Each client maintains a local cache with a structure similar to that
of the server's block store.  This cache provides two operations for
reading versions:
\begin{itemize}
\item \func{get}{\id{blockid}, \id{timestamp}}, which retrieves the
  contents of the block version whose range includes the given
  timestamp.  This may be the current version or a historical version
  of the block.
\item \func{getLatest}{\id{blockid}, \id{transaction}}, which
  retrieves the current version of a block.
\end{itemize}

If the requested version is not present in the client-side cache, it
forwards the request to the server, which responds with the contents
and time range of the appropriate version.  A typical historical
request can be seen in step~(2) of Figure~\ref{fig:protocol}.  If the
requested version turns out to be unbounded, then the server will add
the client that issued the request to \emph{holder set} for that
block.  In the example in Figure~\ref{fig:protocol}, this happens for
block B in steps~(3) and~(4).

Because of the block store's multiversion nature, a given version is
essentially immutable with the one proviso that an \emph{unbounded}
version can become a \emph{bounded} version when its upper bound
becomes fixed.  The holder set of a block tracks exactly which clients
have an unbounded version of a block in their cache so that when that
version becomes bounded, the server can immediately notify these
clients of this change via a \emph{deprecation} message.  For example,
step~(5) of Figure~\ref{fig:protocol} shows the deprecation message
sent to client~1 when a new version of B is installed at timestamp~4.

\subsubsection{Read/Write Transactions}
\label{sec:algorithm:protocol:rw}

% Key points
% * Read/write transactions use an optimistic write protocol with
%   validate-on-commit.
% * Asynchronous deprecations allow for active aborts, which not only
%   saves CPU time over regular optimistic concurrency, but admits a
%   simpler commit protocol.
% * Asynchronous deprecations make it practical for read/write
%   transactions to optimistically read from the local cache.
%
% I think these need to be emphasized better, or maybe briefly
% introduced somewhere

Read/write transactions use a protocol based on a mix of standard
optimistic concurrency
control~\cite{kung81:_optim_method_for_concur_contr} and multiversion
concurrency
control~\cite{bernstein81:_concur_contr_in_distr_datab_system}.  Block
reads are satisfied optimistically from the latest, unbounded version
of blocks in the client's cache whenever possible.  Block writes go to
a per-transaction side-store.  Upon commit, the read and write sets of
the transaction are sent to the server, which
\begin{enumerate}
\item Validates that all of the block versions read by the transaction
  are still unbounded.  This ensures that the transaction can be
  placed next in the serial ordering because it is consistent with the
  latest version of the block store.
\item Assigns the transaction a timestamp $\alpha$ one greater than
  that of previously committed transaction.  The timestamp indicates
  that the transaction read from the block store at time $\alpha$ and
  created the contents of the block store at time $\alpha+1$.
\item Installs the blocks from the transaction's write set at time
  $\alpha+1$.  If this causes existing block versions to become
  bounded, then the server will send out deprecations, as described in
  the previous section.
\end{enumerate}
This write protocol ensures global serializability of read/write
transactions.

When creating new blocks, the client generates a \emph{random} block
ID, which it transmits to the server with the commit request.  If the
block ID collides with an existing block ID, then the server will
abort the request.  Otherwise, the block write proceeds as usual.
Block ID's are considered sparse enough that this should rarely occur
in practice.  Our implementation, for example, uses 64-bit integers,
making the probability of a conflict negligible.

Our algorithm goes beyond the standard validate-on-commit approach of
optimistic concurrency control by employing \emph{active aborts}.
Because the cache is actively kept coherent by asynchronous
deprecation messages, the validation condition given above can be
checked continuously on the client side.  Specifically, if a
deprecation arrives for a block in an active transaction's read set,
then it is impossible for that transaction to pass validation, so it
can be aborted as soon
as possible.  Validation on commit is still necessary, however, as a
critical deprecation message and a commit message may have crossed
paths on the network; however, once a transaction requests a commit,
it is very likely that the commit will succeed simply because the
window during which such a conflict could arise is very small.

The standard optimistic approach of waiting until commit time to
detect conflicts has a number of drawbacks.  First, by waiting to
abort a transaction, work is wasted in the event of a
conflict~\cite{liskov99:_provid_persis_objec_in_distr_system}.
Second, in a distributed setting where the commit data does not reside
on the node performing validation, transactions must either send
committed data to the server in the commit request, or they must
engage in a multistage protocol to first validate the commit before
sending the data.  The first approach wastes network resources if the
commit fails, while the second approach incurs latency and may stall
other transactions if the commit succeeds.  Active aborts, on the
other hand, make it reasonable to use a single-stage protocol that
sends committed data along with the commit request because of the low
probability of a conflict.

Furthermore, asynchronous deprecations also permit better optimism
and cache usage when retrieving blocks.  A pessimistic alternative to
the read protocol given above is to employ a cache update protocol
that always contacts the server when requesting the latest version of
a block instead of assuming the cached copy is up-to-date.  This would
ensure that a read/write transaction always operates on the latest
copy of the data.  However, doing so incurs a full network round-trip
for every block read.  With asynchronous deprecations, the transaction
will know that it was overly optimistic and should therefore abort
within half the time of a network
round-trip of retrieving the block from the local cache.  Thus, the
only disadvantage of optimistically reading cached data is that events
during the half round-trip window following the read could force the
transaction to abort where the pessimistic read protocol would
simply have blocked.  However, we assume that write conflicts are
sufficiently rare in the workload that the trade-off is worthwhile.

\subsubsection{Read-Only Transactions}
\label{sec:algorithm:protocol:ro}

% Key points
% * Read-only transactions choose a timestamp and then operate at that
%   timestamp
% * The timestamp is chosen based on locally available information in
%   order to ensure local causality and conflict freeness
% * Network communication is sometimes, though not always, necessary
%   to ensure freshness.

Read-only transactions operate in a model similar to snapshot
isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}.  A
read-only transaction is assigned a timestamp as soon as it starts and
always reads versions from that timestamp.  Choosing a particular
timestamp to operate at ensures the global serializability of
read-only transactions with respect to read/write transactions.  Since
read-only transactions do not have observable effects, they are always
serializable with respect to each other.

Choosing an appropriate timestamp is critical both to ensuring the
properties laid out in Section~\ref{sec:algorithm:properties} and for
the efficiency of read-only transactions.  The more flexibility
afforded in the assignment of a timestamp, the better locally cached
data can be taken advantage of.

In order to guarantee local causality, the timestamp must be greater
than the largest timestamp assigned to any committed local read/write
transaction.  Because the read/write protocol assigns timestamps in
increasing order, it is sufficient to simply use a timestamp greater
than that of the last locally committed read/write transaction.  Note
that, because read-only transactions do not have effects, multiple
read-only transactions can be assigned the same timestamp.

The write protocol presented in the previous section ensures that
updates to the server's block store always occur with monotonically
increasing timestamps.  This means that each client can keep track of
a \emph{global least upper bound} (GLUB)---a timestamp before which no
further updates can occur---by keeping track of the timestamp of the
last deprecation message or local commit.  Because monotonicity
guarantees that read/write transactions cannot be assigned a timestamp
less than the GLUB, assigning a read-only transaction a timestamp less
than or equal to the GLUB is sufficient to ensure conflict-freeness
between read-only transactions and read/write transactions.

Furthermore, because local writes update the GLUB, the window of
allowable timestamps always contains at least one timestamp, read-only
transactions never have to block until another transaction widens the
window.

\paragraph{Freshness.}

While assigning timestamps less than or equal to the GLUB is
\emph{sufficient} to guarantee conflict-freeness, it is not
\emph{necessary}.  In particular, if the last GLUB update occurred
more than $\epsilon$ seconds ago, this may be too restrictive to
ensure freshness.  Thus, each client keeps track of the
\emph{wall-clock} time of the last update to its GLUB.  When a
transaction with $\epsilon$ freshness is started, if the GLUB is more
than $\epsilon$ seconds old, the client requests a GLUB update from
the server before assigning the transaction a timestamp.  On a
relatively active client with a large cache, such updates may not be
necessary very often because of frequent GLUB updates from other
communication with the server.

Assuming the network latency is less than $\epsilon$, assigning the
transaction a timestamp of the GLUB received from the server is
sufficient to guarantee freshness. If the network latency is greater
than $\epsilon$, then it is impossible to simultaneously provide
freshness and conflict-freeness in any system.

% This is interesting, but I don't have time to think about it:
%
% There's a distinction between begin causality and commit causality.
% RW transactions are always globally commit causal, and RO
% transaction can be globally begin causal by reducing epsilon to 0,
% but they can't be globally commit causal without resorting to making
% them RW transactions

% LocalWords: LocalWords timestamp multiversion serializability
% LocalWords: freeness serializable acausality GLUB
