intro.tex

\section{Introduction}

Modern distributed data stores offer a choice of consistency
models. Weak consistency models are fast and guarantee ``always-on''
behavior but provide limited guarantees. Stronger consistency models
are easier to reason about but are slower and potentially
unavailable~\cite{davidson-survey}. The choice of a consistency model
has wide-ranging implications for application writers, operations
management, and end-users.  Yet, in light of its performance
benefits~\cite{abadi-pacelc}, weak consistency is often considered
acceptable.

Eventual consistency---perhaps the most commonly deployed weak
consistency model---is particularly weak: in the absence of new writes
to a data item, reads will eventually return the same
value~\cite{vogels-defs}. This eventual consistency provides no
guarantees as to when new writes will become visible to readers and
what versions of data items will be presented in the
interim. For example, reading all \texttt{null}
values from a database satisfies eventual consistency. Similarly, the
data store can delay writes for weeks and not violate eventual
consistency guarantees. Yet, despite these weak semantics, there is
common sentiment among practitioners that eventual consistency is
often ``good enough'' and ``worthwhile'' for many Internet
applications.

In recent work, we provided quantitative metrics and accompanying
techniques for analyzing the consistency provided by eventually
consistent stores, called Probabilistically Bounded Staleness, or
PBS~\cite{pbs-vldb2012}. Eventually consistent stores do not make
promises about the length of time required to observe an update or the
staleness of values, but this does not preclude us from making
informed statements about a store's expected behavior. By using expert
knowledge of the underlying data store and its replication protocols
and performing lightweight in-situ profiling, we can inform data store
users about what consistency they are likely to observe in the
future. PBS provides a probabilistic answer to the question of
``how eventual and how consistent is eventual consistency?''

PBS predictions are part of a larger trend towards providing
quantitative measurements and analysis of weakly consistent
stores. Recent work ranges from theoretical~\cite{podc-hpl} to
experimental studies~\cite{hotdep} of properties such as linearizability,
serializability, and regular register semantics. PBS in particular has
experienced relative popularity in the NoSQL community and our
implementation of PBS for quorum-based systems was integrated with
Cassandra's mainline source and released as a feature of the 1.2.0
release in January 2013~\cite{cassandra-pbs-patch}. Our discussions
with other researchers indicate the possibility of additional
technology transfer of monitoring and verification techniques in the
future.

While monitoring and prediction are useful in themselves, perhaps more
importantly, they enable a rich space of applications that were
previously infeasible or impossible. Among these applications, we
consider three to be the most promising: \textit{i.)} dynamic
request-based consistency parameters, or auto-tuning request routing
based on latency- and consistency-based service level agreements
(SLAs), \textit{ii.)}  database administration tasks with respect to
the impact of slow nodes and networks, replication factors, and data
store parameters like anti-entropy rates, and \textit{iii.)} enhancement
of traditional alerting and monitoring frameworks. We elaborate
further in Section~\ref{sec:scenarios}, but, in short, these
quantitative metrics allow new ways to improve the performance,
semantics, and maintenance of eventually consistent stores.

In this demo paper, we outline these advanced use cases in detail
(Section~\ref{sec:scenarios}), describe how quantitative metrics can
be integrated into existing data stores based on our experiences with
the Cassandra community (Section~\ref{sec:architecture}), and sketch
how we plan to demonstrate this newly enabled functionality, allowing
SIGMOD attendees to act as end-users, operations managers, and
adversaries of an eventually consistent internet service
(Section~\ref{sec:demo}).

\subsection{PBS Metrics}
To provide background on consistency metrics, we briefly summarize the
metrics proposed in PBS~\cite{pbs-vldb2012}. Data
staleness is expressed in terms of two metrics: wall-clock time
and versions.

\textbf{t-visibility:} $t$-visibility captures the ``window of
inconsistency`` in terms of wall clock time after a write happens. An
eventually consistent system will eventually respond to all read
requests with the last written value, and $t$-visibility provides an expected
value for this ``eventuality.''  More formally, $t$-visibility is the
probability that a read operation starting $t$ seconds after the
previous write completed will see the most recent value from the data
store. For example, if a data store configuration has $t$-visibility of
95\% at 100ms, it means that 100ms after the last write completes,
95\% of read operations will see the most recent value.

\textbf{k-staleness:} $k$-staleness determines the probability of a
read returning a value within a bounded number of versions. This
estimate can be useful for estimating the probability of experiencing
monotonic reads, under which users will never read older versions than
they have already read (i.e., reads do not ``go back in
time'')~\cite{vogels-defs}.

\textbf{$\langle$k, t$\rangle$-staleness:} We can combine $t$-visibility
and $k$-staleness to consider both time- and version-based staleness
together, called $\langle k, t \rangle$-staleness. For example, if a
data store configuration has $\langle k, t \rangle$-staleness of 75\%
at 10ms and 3 versions, then 10ms after the last write completes, 75\%
of reads will return a value that is no more than 3 versions old.