and poorly defined (for example, what
does database ACID “consistency”
have to do with “strong consistency”?).
Fortunately, by identifying a large
class of programs and data types that
are tolerant of weak consistency, programmers can enjoy “strong” application consistency, while reaping the
benefits of “weak” distributed read/
write consistency.
Taken together, the CALM theorem and CRDTs make a powerful
toolkit for achieving “consistency
without concurrency control,” which
is making its way into real-world systems. Our team’s work on the Bloom
language3 embodies CALM principles. Bloom encourages the use
of order-insensitive disorderly programming, which is key to architecting eventually consistent systems.
Some of our recent work focuses on
building custom eventually consistent data types whose correctness is
grounded in formal mathematical
lattice theory. Concurrently, several
open source projects such as State-box21 provide CRDT-like primitives as
client-side extensions to eventually
consistent stores, while one eventually consistent store—Riak—recently
announced alpha support for CRDTs
as a first-class server-side primitive. 9
Stronger than eventual
While compensating actions and
CALM/CRDTs provide a way around
eventual consistency, they have shortcomings of their own. The former requires dealing with inconsistencies
outside the system and the latter limits the operations that an application
writer can employ. However, it turns
out that it is possible to provide even
stronger guarantees than eventual consistency—albeit weaker than SSI—for
general-purpose operations while still
providing availability.
The CAP theorem dictates that
strong consistency (SSI) and availability are unachievable in the presence
of partitions. But how weak does the
consistency model have to be in order
for it to be available? Clearly, eventual
consistency, which simply provides a
liveness guarantee, is available. Is it
possible to strengthen eventual consistency by adding safety guarantees to it
without losing its benefits?
Pushing the limits. A recent techni-
By analyzing
programs for
monotonicity,
you can “bless”
monotonic
programs as “safe”
under eventual
consistency
and encourage the
use of coordination
protocols in
the presence
of non-monotonicity.
cal report from the University of Texas
at Austin claims no consistency model
stronger than causal consistency is
available in the presence of partitions. 17 Causal consistency guarantees
each process’s writes are seen in order
writes follow reads (if a user reads a
value A= 5 and then writes B= 10, then
another user cannot read B= 10 and
subsequently read an older value of A
than 5), and transitive data dependencies hold. This causal consistency is
useful in ensuring, for example, comment threads are seen in the correct
order, without dangling replies, and
users’ privacy settings are applied to
the appropriate data. The UT Austin
report demonstrates that it is not possible to have a stronger model than
causal consistency (that accepts fewer
outcomes) without violating either
high availability or ensuring that, if
two servers communicate, they will
agree on the same set of values for
their data items. While many other
available models are neither stronger
nor weaker than causal consistency,
this impossibility result is useful because it places an upper bound on a
very familiar consistency model.
In light of the UT Austin result, several new data storage designs provide
causal consistency. The COPS and Eiger systems16 developed by a team from
Princeton, CMU, and Intel Research
provide causal consistency without
incurring high latencies across geographically distant datacenters or the
loss of availability in the event of data-center failures. These systems perform
particularly well, at a near-negligible
cost to performance when compared
to eventual consistency; Eiger, which
was prototyped within the Cassandra
system, incurs less that 7% overhead
for one of Facebook’s workloads. In
our recent work, we demonstrated how
existing data stores that are already deployed in production but provide eventual consistency can be augmented
with causality as an added safety guarantee. 6 Causality can be bolted-on without compromising high availability,
enabling system designs in which safety and liveness are cleanly decomposed
into separate architectural layers.
In addition to causality, we can consider the relationship between ACID
transactions and the CAP theorem.
While it is impossible to provide the