and workload changes and for dynamically tuning system behavior. Taken together, measurement and prediction
form a useful toolkit.
Probabilistically bounded staleness.
As a brief deep dive into how to quantify eventually consistent behavior, we
will discuss our experiences developing, deploying, and integrating state-of-the art prediction techniques into
Cassandra, a popular NoSQL. Probabilistically Bounded Staleness, or PBS,
provides an expectation of recency for
reads of data items. 4 This allows us to
measure how far an eventually consistent store’s behavior deviates from that
of a strongly consistent, linearizable
(or regular) store. PBS enables metrics
of the form: “ 100 milliseconds after
a write completes, 99.9% of reads will
return the most recent version,” and
“85% of reads will return a version that
is within two of the most recent.”
IllustratIon by cycloneProject / shutterstock.com
Building PBS. How does PBS work?
Intuitively, the degree of inconsistency
is determined by the rate of anti-entropy. If replicas constantly exchange
their last written writes, then the window of inconsistency should be bounded by the network delay and local processing delay at each node. If replicas
delay anti-entropy (possibly to save
bandwidth or processing time), then
this delay is added to the window of inconsistency; many systems (Amazon’s
Dynamo, for example) offer settings
in the replication protocol to control
these delays. Given the anti-entropy
protocol, then—given the configured
anti-entropy rate, the network delay,
and local processing delay—you can
calculate the expected consistency.
In Cassandra, we piggyback timing
information on top of the write distribution protocol (the primary source of
anti-entropy) and maintain a running
sample. When a user wants to know the
effect of a given replication configuration, we use the collected sample in a
Monte Carlo simulation of the protocol
to return an expected value for the consistency of the data store, which closely
matches consistency measurements
on our Cassandra clusters at Berkeley.
PBS in the wild. Using our PBS consistency prediction tool, and with the
help of several friends at LinkedIn and
Yammer, we quantified the consistency of three eventually consistent stores
running in production. PBS models
predicted that LinkedIn’s data stores
returned consistent data 99.9% of the
time within 13.6ms; and on SSDs, within
1.63ms. These eventually consistent configurations were 16.5% and 59.5% faster
than their strongly consistent counterparts at the 99.9th percentile. Yammer’s
data stores experienced a 99.9% inconsistency window of 202ms at 81.1% latency reduction. The results confirmed
the anecdotal evidence: eventually consistent stores are often faster than their
strongly consistent counterparts, and
they are frequently consistent within
tens or hundreds of milliseconds.
In order to make consistency prediction more accessible, with the help of
the Cassandra community, we recently
released support for PBS predictions in
Cassandra 1. 2.0. Cassandra users can
now run predictions on their own production clusters to tune their consistency parameters and perform what-if
analyses for normal-case, failure-free
operation. For example, to explore
the effect of adding solid-state drives
(SSDs) to a set of servers, users can adjust the expected distribution of read
and write speeds on the local node.
These predictions are inexpensive; a
JavaScript-based demonstration we
have created4 completes tens of thousands of trials in less than a second.
Of course, prediction is not without
faults: predictions are only as good as
the underlying model and input data.
As statistician George E.P. Box famous-
ly stated, “All models are wrong, but
some are useful.” Failure to account
for an important aspect of the system
or anti-entropy protocol may lead to
inaccurate predictions. Similarly, pre-
diction works by assuming that past
behavior is correlated with future be-
havior. If environmental conditions
change, predictions may be of limited
accuracy. These issues are fundamental
to the problem at hand, and they are a
reminder that prediction is best paired
with measurement to ensure accuracy.
Programming eventual Consistency
While users can verify and predict the
consistency behavior of eventually consistent systems, these techniques do