Communications of the ACM

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.