Eventual Consistency (EC) is a well known concept. The CAP theorem, which defines Consistency, Availability and Partition tolerance is also well known. It describes some distributed systems such as CP, which has two properties: Consistency and Partition tolerance.
If we look at data stores just by how they stick to the definition of their consistency model and compare their speeds, which one would be the fastest? An EC or a CP store? Answering this question is a good excuse to go into some detail of their respective definitions and show some of their limits.
Contrary to popular belief, data stores can be very fast
Eventually Consistent
Eventually Consistent was defined by Werner Vogels in [E2]: "the storage system guarantees that if no new updates are made to the object, eventually all accesses will return the last updated value."
Let’s try a few implementations of a hypothetical key value store.
Implementation 1: Trying the simplest option
void put(key, value){
// do nothing
}
value get(key){
// Hey, it’s easy to implement! We’re going
// to pretend that we have not yet received
// the write, it is enough!
throw “no value for this key”
}
Is this an EC store? No, it is not, because it will never return the last updated value. To be an EC store you need to “eventually [...] return the last updated value.” That’s not what this implementation does, it will never return the last updated value.
So let’s try another one.
Implementation 2: Trying to be fast for reads
void put(key, value){
doRealPut(key, value) // does the ‘real’ job
}
value get(key){
if (random(2) == 1) // 50% of the time
throw “no value for this key”
else
return doRealGet(key)
// As, 50% of the time, I pretend
// that I have not yet received
// the first insertion, I
// divide the latency by two!
}
Is this an EC store? Again, it is not because it does not respect the property “eventually all accesses will return the last updated value.” The “all accesses” condition is not met.
The definition does not prevent us from doing ridiculous things however, such as:
Implementation 3: Playing on words
void put(key, value){
doRealPut(key, value)
}
value get(key){
if (currentDate.year < 2020)
throw “no value for this key”
else
return doRealGet(key)
// I will win all read benchmarks until 2020!
}
This last implementation complies with the definition, but it’s playing on words. At the end of the day, the fact that we have to return the last value is important because we cannot trick the availability by inventing default initial values.
Lastly, a kind of hard real-time store, with strict SLA and a “make it in the expected time or stop” policy, would not comply with the EC definition:
Implementation 4: Trying EC for hard real-time systems
void put(key, value){
doRealPut(key, value)
}
value get(key){
try (timeLimit = 10 ms) { // run in 10ms or throw
return doRealGet(key)
} catch (TimeOutException) {
// Max response time is 10ms!
throw “no value for this key”
}
}
This kind of behavior is sometimes useful. However, an EC store is not allowed to do that: it breaks its consistency contract. As the second implementation, the “eventually all accesses will return the last updated” promise is broken.
Nevertheless, this behavior can be added on top of any storage, eventually consistent or not. Actually, one can expect that there already is an option to set a similar timeout on many data stores (again, eventually consistent or not).
CAP and CP
If you are reading this, you have been exposed to CAP and its catchy definition: “Consistency, Availability, Partition tolerance: pick two”. CAP was first a conjecture, made by Eric Brewer in 2000 [C1]. In 2002, Seth Gilbert and Nancy Lynch proved it [C2].
Let us use the definition from the proof [C2].
Consistent is: “Atomic, linearizable, consistency [...]. There must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time.”
Available is: “For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.”
Partition is: “The network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost.”
This let us have a trivial implementation of a CP system:
Implementation 1: CP made easy
void put(key, value){
throw “not available”
}
value get(key){
throw “not available”
}
This “do nothing” implementation does comply with the definition of CP: it is not fully available--actually not available at all--but it is consistent. This is actually mentioned in [C2]: “If availability is not required, then it is easy to achieve atomic data and partition tolerance. The trivial system that ignores all requests meets these requirements.”
CAP and AP
Would it be different for an AP store? Not really: the CAP theorem does not require a minimal consistency for AP. [C2] mentions “It is possible to provide high availability and partition tolerance, if atomic consistency is not required. If there are no consistency requirements, the service can trivially return v0, the initial value, in response to every request.” It means we can use our minimal implementation that was not Eventually Consistent to do an available and partition tolerant store:
Implementation 2: AP is easy too
void put(key, value){
// do nothing
}
value get(key){
throw “no value for this key”
}
Is that a useful CP store?
Conclusion
The definition of the Eventual Consistency leads to a very clear behavior for any reasonable data store implementation. The definitions of AP and CP in CAP are much more permissive, and allow to build useless but perfectly CP or AP stores.
An immediate consequence is that any trivial application that crashes definitively when there is a partition gets the CP-partition-tolerance award.
 |
This post is part of the CAP theorem series
| |
References
[C1] Eric A. Brewer, PODC Keynote, July 19, 2000, Towards Robust Distributed Systems
[C2] Gilbert and Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News (2002)
[E2] Werner Vogels, Eventually Consistent, ACM Queue, Vol.6 No.6, 2008
No comments:
Post a Comment