10 Dec 2013
In case you’ve missed it, there’s been a great discussion about consistency, availability, and durability on the Redis mailing list and Twitter over the past few days. I wanted to weigh in and specifically address antirez’s point that
While CAP and durability are orthogonal they are very related in actual systems….
We can effectively cast all statements about availability and consistency into the form:
If operations can contact AF of N correct replicas, the system provides a guaranteed response that is correct with respect to semantics S.
Availability is all about the precondition (AF of N): under what conditions is a safe response guaranteed? Gilbert and Lynch’s proof of the CAP theorem, shows that when S means linearizability and N is greater than 1, AF cannot equal 1. In fact, most implementations of linearizability use a notion of majorities to pick AF = (N+1)/2.
Now, let’s consider statements about durability:
The effects of operations will survive DF fail-stop server failures.
To survive DF failures, we need to contact DF+1 servers. Therefore, we can provide availability and durability only when enough servers are online and reachable.
As stated, two concepts are remarkably similar, but there’s an important difference. For semantics like linearizability, AF is typically a function of N and grows with replication factor. In contrast, DF is typically constant and independent of replication factor.
This brings us to antirez’s point. When N=3 and we want writes to survive one server failure, majority quorums require AF=2 and durability also requires DF=2; they’re the same! When we want higher durability without having to contact all servers, N=5 with DF=3 is a reasonable choice, and, again, durability matches majority quorum size. For large replication factors, N=100, the difference grows: we can still get DF=3, while majority quorums require AF=51. But, in practice, replication factors are often small, so the preconditions for availability when maintaining both durability and consistency are often equivalent.
It’s worth noting that AF=1 and DF=1 is an option, and it’s fast, but it will preclude durability in the event of server failures and also disallows linearizable semantics in the event that you have multiple active replicas (N > 2).
The above analysis doesn’t take into account reads, which, in weakly consistent systems, can contact any non-failing replica, but I think this sheds some light on the discussion.
- NSF Graduate Research Fellowship: N=1 Materials for Systems Research (03 Sep 2015)
- Worst-Case Distributed Systems Design (03 Feb 2015)
- When Does Consistency Require Coordination? (12 Nov 2014)
- Data Integrity and Problems of Scope (20 Oct 2014)
- Linearizability versus Serializability (24 Sep 2014)
- MSR Silicon Valley Systems Projects I Have Loved (19 Sep 2014)
- Understanding Weak Isolation Is a Serious Problem (16 Sep 2014)
- Bridging the Gap: Opportunities in Coordination-Avoiding Databases (22 Apr 2014)
- Without Conflicts, Serializability Is Free (14 Apr 2014)
- Scalable Atomic Visibility with RAMP Transactions (07 Apr 2014)