Limited Transactions
In addition to causal consistency, our
systems provide limited forms of transactions. These include read-only transactions, which transactionally read data
spread across many servers in a datacenter, and write-only transactions, which
transactionally update data spread
across many servers in a datacenter.
These limited transactions are necessitated—and complicated—by the
current scale of data. Data for many
services is now far too large to fit on a
single machine and instead must be
spread across many machines. With
data resident on many machines, extracting a consistent view of that data
becomes tricky. Even though a data
store itself may always be consistent,
a client can extract an inconsistent
view because the client’s reads will
be served at different times by different servers. This, unfortunately, can
reintroduce many of the anomalies
inherent in eventual consistency. In
Figure 8, for example, in the West
Coast datacenter, a grad student removes photo-viewing permissions
from an advisor and uploads incriminating photos. The advisor concurrently tries to view the student’s photos and, incorrectly, is shown the
incriminating photos. To avoid these
anomalies, causal consistency must
be extended from the storage system
to the Web servers and then on to users of the service. This can be done
using read-only transactions.
Read-only transactions allow programmers to transactionally read data
spread across many servers, yielding a
consistent view of the data. The interface for a read-only transaction is simple: a list of data locations. Instead of
issuing many individual reads for different data locations, a programmer issues
a single read for all those locations. This
is similar to batching these operations,
which is often done to make dispatching reads more efficient—except it also
ensures the results are isolated.
With read-only transactions, anomaly 5 can now be converted into a regularity as well. Figure 9 shows that with
read-only transactions, the permissions and photos are read together
transactionally, yielding any of the
three valid states shown, but never the
anomaly that leaks the incriminating
photos to the student’s advisor.
operations until they can appear in
the correct order, as shown in Figure
7. The dependency check for Bglad does
not return until after Afound is applied
on the East Coast, which ensures Bob
is never misunderstood.
The system described thus far provides causal consistency and all of
the ALPS properties. Causal consistency is provided by tracking causality
with a client library and enforcing the
causal order with dependency checks
on replicated writes. Availability and
partition tolerance are ensured by
keeping all operations inside the local datacenter. Low latency is guaranteed by keeping all operations local,
nonblocking, and lock free. Finally, a
fully decentralized design ensures the
system has scalability.
The current system, however, is
inefficient. It has a huge amount of
dependency metadata that travels
around with write operations and a
huge number of dependency checks
to execute before applying them. Both
of these factors steal throughput from
user-facing operations and reduce the
utility of the system. Luckily, our sys-
tems can exploit the transitivity inher-
ent in the graph of causality to dras-
tically reduce the dependencies that
must be tracked and enforced. The
subset of dependencies being tracked
is the one-hop dependencies, which
have an arc to the current operation
in the graph of causality. (Note that
in graph theoretic terms, the one-hop
dependencies subset is the direct pre-
decessor set of an operation.) In Fig-
ure 6, the one-hop dependencies are
shown in bold. They transitively cap-
ture all of the ordering constraints on
an operation. In particular, because
all other dependencies are depended
upon by at least one of the one-hop
dependencies by definition, if this cur-
rent operation occurs after the one-
hop dependencies, then by transitivity
it will occur after all others as well.
Figure 8. Anomaly 5: Leaked photos.
West Coast
Friends Server Student
Photo Server
Advisor
remove advisor
THEN
add bad photos
friends check
and photo fetch
yes friends
bad photos
Sadd
Ti
me
Figure 9. Regularity 5: No leaked photos.
West Coast
Friends Server Student
Photo Server
Advisor
remove advisor
THEN
add bad photos
yes friends, old photos
OR
OR
not friends, old photos
not friends, bad photos
Sadd
Ti
me