execution rule.
Now, in the East Coast datacenter,
the operations can appear only in an
order that agrees with causality:
Op1 [Alice uploads photos.]
Then
Op1 [Alice uploads photos.]
Op2 [Alice creates an album.]
Then
Op1 [Alice uploads photos.]
Op2 [Alice creates an album.]
Op3 [Alice adds photos to the album.]
but never in a different order that results in an empty album or complicates
what a programmer must think about.
What causal consistency cannot do.
Anomaly 4 represents the primary limitation of causality consistency: it cannot enforce global invariants. Anomaly
4 has an implicit global invariant—that
bank accounts cannot go below $0—
that is violated. This invariant cannot
be enforced in an ALPS system. Availability dictates that operations must
complete, and low latency ensures they
are faster than the time it takes to communicate between datacenters. Thus,
the operations must return before the
datacenters can communicate and discover the concurrent withdrawals.
True global invariants are quite
rare, however. E-commerce sites,
where it seems inventory cannot go below 0, have back-order systems in place
to deal with exactly that scenario. Even
some banks do not enforce global $0
invariants, as shown by a recent concurrent withdrawal attack on ATMs
that extracted $40 million from only 12
account numbers.
14
tion and b is a read operation that returns the value written by a, then a → b.
3. Transitivity. For operations a, b,
andc, if a → b and b → c, then a → c.
Thus, the causal relationship between
operations is the transitive closure of
the first two rules.
Causal consistency ensures operations appear in an order that agrees
with these rules. This makes users happy because their operations are applied
everywhere in the order they intended.
It makes programmers happy because
they no longer have to reason about
out-of-order operations.
Causal consistency prevents each of
our first three anomalies, turning them
into regularities.
Regularity 1: No Missing Comments
In the West Coast datacenter, Alice
posts, and then she and Bob comment:
Op1 Alice: I’ve lost my wedding ring.
Op2 Alice: Whew, found it upstairs.
Op3 [Bob reads Alice’s post and
comment.]
Op4 Bob: I’m glad to hear that.
Op1 → Op2 by the thread-of-execu-tion rule; Op2 → Op3 by the reads-from
rule; Op3 → Op4 by the thread-of-execu-tion rule.
Write operations are only propagated and applied to other datacenters, so
the full causal ordering that is enforced
is Op1 → Op2 → Op4.
Now, in the East Coast datacenter,
operations can appear only in an order
that agrees with causality. Thus:
Op1 Alice: I’ve lost my wedding ring.
Then
Op1 Alice: I’ve lost my wedding ring.
Op2 Alice: Whew, found it upstairs.
Then
Op1 Alice: I’ve lost my wedding ring.
Op2 Alice: Whew, found it upstairs.
Op4 Bob: I’m glad to hear that.
but never the anomaly that makes Bob
look unkind.
Regularity 2: No Leaked Photos3
In the West Coast datacenter, a grad
student carefully deletes incriminating
photos before accepting an advisor as
a friend:
Op1 [Student deletes incriminating
photos.]
Op2 [Student accepts advisor as a
friend.]
Op1 → Op2 by the thread-of-execu-tion rule.
Now, in the East Coast datacenter,
operations can appear only in an order
that agrees with causality, which is:
Then
[Student deletes incriminating
photos.]
[Student accepts advisor as a friend.]
but never the anomaly that leaks pho-
tos to the student’s advisor.
Regularity 3: Normal Photo Album
In the West Coast datacenter, Alice uploads photos and then adds them to
her Summer 2013 album:
Op1 [Alice uploads photos.]
Op2 [Alice creates an album.]
Op3 [Alice adds photos to the album.]
Op1 → Op2 → Op3 by the thread-of-
Figure 6. Causality and dependency. Figure 6. Causality and dependency.
User OpID Operation
Alice w1 write(Alice: Town, NYC)
Bob r2 read(Alice:Town)
Bob w3 write(Bob:Town, LA)
Alice r4 read(Bob:Town))
Carol w5 write(Carol:Likes, ACM, 8/31/12)
Alice w6 write(Alice:Likes, ACM, 9/1/12)
Alice r7 read(Carol:Likes, ACM)
Alice w8 write(Alice:Friends, Carol, 9/2/12)
Op ID Dependencies
w1 —
w3 w1
w5 —
w6 w3w1
w8 w6w5w3w1
Car
ol
w1 w1
w3
w8
w6 w6
w5
w3
w5
r2
r4
r7
Bob Alice
L
o
gica
l
Time
L
o
gica
l
Time
(a) (b) (c) (d)