single request; therefore, low latency
in the storage system is critical for enabling fast page-load times, which are
linked to user engagement with a service—and, thus, revenue. An always-available and partition-tolerant system
can provide low latency on the order of
milliseconds by serving all operations
in the local datacenter. A strongly consistent system must contact remote
datacenters for reads and/or writes,
which takes hundreds of milliseconds.
Thus, systems that sacrifice strong
consistency gain much in return. They
can be always available, guarantee
responses with low latency, and provide partition tolerance. In Clusters
of Order-preserving Servers (COPS),
11
developed for our original work on
this subject, we coined the term ALPS
for systems that provide these three
properties—always available, low latency, and partition tolerance—and
one more: scalability. Scalability implies that adding storage servers to
each datacenter produces a proportional increase in storage capacity
and throughput. Scalability is critical
for modern systems because data has
grown far too large to be stored or
served by a single machine.
The question remains as to what
consistency properties ALPS systems
can provide. Before answering this,
let’s consider the consistency offered
by existing ALPS systems. For systems
such as Amazon’s Dynamo, LinkedIn’s
Project Voldemort, and Facebook/
Apache’s Cassandra, the answer is
eventual consistency.
Eventual Consistency
Eventual consistency is a widely used
ing, however, given it also enables the
storage system to provide low latency—
defined as latency for reads and writes
that is less than half the speed-of-light
delay between the two most distant
datacenters. A proof that predates the
CAP theorem by 14 years10 shows it is
impossible to guarantee low latency
and provide strong consistency at the
same time. Front-end Web servers read
or write data from the storage system
potentially many times to answer a
Figure 2. Anomaly 1: Comment reordering.
Figure 3. Anomaly 2: Photo privacy violation.
Figure 1. Geo-replicated storage.
Data
Store
Tier
Geo Replica+on
B B
B;;
B B
B;;
B B
B;;
B;;
B;;
B;; B;;
West Coast East Coast
Alice: “I’ve lost my wedding ring”
Alice: “Whew found it upstairs!”
Bob: “I’m glad to hear that”
Alice: “I’ve lost my wedding ring”
Bob: “I’m glad to hear that”
Alost
Afound
Bglad
Tim
e
Alost
Afound
Bglad
West Coast East Coast
[Student deletes incriminating photos]
[Student accepts advisor as a friend]
Advisor can see
incriminating photos
Sdelete
Saccept
Sdelete
Saccept
T
ime
