CAP Theorem: not what we thought it was, not what we are looking for

The CAP theorem is often used to classify distributed systems, and the "two out of three" rule is often quoted. But the CAP theorem is widely misunderstood. What are the exact terms of the CAP Theorem? How does it differ from Brewer's original CAP Conjecture? Where does CAP fall short of meeting practical engineering expectations?

Transcript

1. CAP Theorem: 
 not what we thought it was, not what we are looking for Shlomi Noach GitHub DevOpsDays TLV 2019
2. About me @github/database-infrastructure Author of orchestrator, gh-ost, freno, ccql and others. Blog at http://openark.org 
 github.com/shlomi-noach
 @ShlomiNoach
3. GitHub
 Built for developers Largest open source hosting 40M+ developers
 2.9M+ organizations
 100M+ repositories, Supplier of octocat T-Shirts and stickers
4. Incentive Important part of our work is to keep the service available, so that users/customers have access to their data and can operate on their data.
5. CAP Conjecture Suggested by Eric Brewer, 1998-1999 Terms: • [strong] Consistency • [high] Availability • Partition tolerance Strong Consistency, High Availability, Partition-resilience: Pick at most 2. C A P
6. CAP Theorem Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services Seth Gilbert, Nancy Lynch
7. CAP Theorem A mathematical proof Uses different definition of Availability than CAP Conjecture’s definition Neither of the Availability definitions contain one another (or, are stronger than the other)
8. CAP Theorem In Math, a theorem only holds as long as its terms & conditions are met. CAP Theorem does not prove the CAP Conjecture.
9. CAP Theorem Terms, according to Gilbert & Lynch: - Consistency - Availability - Partition tolerance
10. CAP Theorem: Consistency Once a write is successful on a node, any read on any node must reflect that write or any later write. aka Atomic Consistency, aka Strong consistency, aka Linear consistency, aka Linearizability. C
11. CAP Theorem: Availability …every request received by a non-failing node in the system must result in a response. There is no constraint on the actual amount of time. Though it is not specified, it is implied that response must be valid, non-error. Contrast with Brewer’s definition of High availability: data is considered highly available if a given consumer of the data can always reach some replica. A
12. CAP Theorem: Partition Tolerance The system is able to operate on network partitioning. Partition tolerance is considered as a given condition, since network partitioning can and does take place regardless of a system’s design. P
13. CAP Theorem A distributed data store [web service] cannot provide more than two out of the three properties. Better illustrated as: • If the network is good, you may achieve both Availability and Consistency. • If the network is partitioned, you must choose between Availability and Consistency.
14. CAP Theorem The discussion is mostly about CP vs AP systems C A P
15. Proof of CAP theorem Simplified, not by much. Given two nodes replicating from each other ! ! n1 n2
16. Proof of CAP theorem We partition the network between the two nodes to an infinite amount of time. ! ! n1 n2
17. Proof of CAP theorem We write data to one node. If the system is Available, the write completes in a finite amount of time. ! ! n1 n2
18. Proof of CAP theorem We read data from the other node. If the system is Available that read completes in a finite mount of time. ! ! n1 n2
19. Proof of CAP theorem During that finite time the network was partitioned, hence our read could not reflect changes made by the write. QED ! ! n1 n2
20. The proof is mathematical Following solid Mathematical principles.
21. The proof is mathematical Reading data after writing is only possible when the write time is finite. Proves impossibility by counter example: we’ve shown a (single) scenario where we can’t have both Availability and Consistency.
22. CAP Theorem CAP does not say “you cannot have both A and C at the same time” * It says: “you cannot design a system where you will have both A and C together at all times” * * Assuming P
23. All purple dragons can fly
24. Vacuous truth A statement that asserts that all members of the empty set have a certain property. [wikipedia]
25. Vacuous truth All purple dragons can fly.
26. Vacuous truth All purple dragons can fly faster than the speed of light.
27. Vacuous truth All purple dragons can answer questions. All purple dragons cannot answer questions.
28. CAP Availability “…every request received by a non-failing node in the system must result in a response.”
29. CAP Availability It is vacuous truth, that if all the nodes in my system are crashed, then my system is Available.
30. Proposal to making my service available ! ! ! ! ! ! Shut down all database servers?
31. Proposal to making my service available ! ! ! ! ! ! Shut down all database servers? The CAP Theorem Availability definition goes against practical definition of availability.
32. Infinite network partitioning
33. Infinite network partitioning Illustrated
34. Meet Anna and Ben, SRE’s at example.com
36. One day, Anna's attention is drawn to what seems to be an unfolding crisis. oh, dear!
37. Ben, are you seeing what I’m seeing?
38. The two investigate It seems like our Virginia router is malfunctioning
39. Confirmed with the datacenter; they saw some smoke, and then it burned. It's literally melted.
40. So our Virginia DC is now network isolated.
41. You know what that means?
42. oh, wow! oh, wow!
43. The router is never coming back. This is an infinite network partitioning!
44. We will never have consistency ever again!
45. There's just no point 
 in anything. CAP 
 Theorem proves this.
46. For eternity!
47. We may as well enjoy our time! We can live A life of adventure!
48. We can go to
 Paris!
49. We can go to
 Rome!
50. We can go to
 DevOpsDays TLV!
51. Woohoo!
52. Enters Carmen, CTO for example.com
53. Hey there! What’s
 going on? Seems like
 we have an outage?
54. Our Virginia router
 burst up in flames.
 It is gone.
55. For eternity. We now
 have an infinite 
 network partitioning, 
 and will never again 
 have consistency.
56. There's just no point 
 in anything. CAP 
 Theorem proves this.
57. Can we expense 
 travel to 
 DevOpsDays TLV?
58. …
59. …
60. …
61. ben?
62. Yeah?
63. Here's my corporate credit card. 
 I'd like you to go to the store downtown, buy a new router, take it to our Virginia DataCenter and replace the old router.
64. gulp!
65. Yeah, 
 that also works!
66. Infinite network partitioning Is not a practical situation. Is not something we plan for. Is not something that concerns us as we engineer our systems.
67. Can we trade “infinite” with 
 “long enough”? This would break the proof. If a network partition is capped (pun intended) by t seconds we can stall any read by t+α, conveniently delaying beyond the network partitioning, allowing for consistency. Remember: there is no cap (pun again) to query response time. ! ! n1 n2
68. Can we rewrite CAP Theorem in terms of finite timeouts? Yes: • in a system where a network partition can last more than t • and where we require queries to respond within time t/2 • We can illustrate a proof similar to CAP Theorem’s where given such partitioning we cannot achieve both availability and consistency. • Let’s name it “Time Limited CAP” ! ! n1 n2
69. Questioning “time limited CAP” Is t a given constraint? Why would we necessarily require queries to complete in t/2? Is there system logic / customer logic to the above, or have we tailored this to fit a theorem we had?
70. Questioning “time limited CAP” Opinion: this chase is a fallacy. We seem to be trying to prove a theorem while we disagree with its terms, namely Availability.
71. CAP Conjecture Availability: data is considered highly available if a given consumer of the data can always reach some replica. Can we work with that?
72. n == 2?
73. n > 2 Availability: consumer always has access to data via at least one replica. Some node will have our data (we will likely need to detect which one) ! ! ! ! !
74. CAP is short of CAPacity
75. CAP is short of CAPacity™
76. CAP is short of CAPacity™®
77. CAP is short of CAPacity™® PATENTED
78. CAP Conjecture, capacity What if we agreed to quorum? q-Availability: assuming number of replicas is n, consumer always has access to data via at least ⌊n/2 + 1⌋ replicas. e.g. - in a 5-replicas cluster, quorum would be 3
 - in a 7-replicas cluster, quorum would be 4 ! ! ! ! !
79. Consensus algorithms: 
 Paxos, Raft
80. Consensus algorithms: 
 Paxos, Raft Depending on implementation, can guarantee: • A write is readily Available to read on quorum nodes • A write is made durable on quorum nodes ! ! ! ! !
81. ! ! ! ! ! Do consensus algorithms contradict CAP?
82. ! ! ! ! ! CAP network partitioning, n > 2
83. ! ! ! ! ! CAP network partitioning, n > 2
84. ! ! ! ! ! CAP network partitioning, n > 2
85. ! ! ! ! ! Reasonable confidence
86. CAP: recap Assuming P, you cannot design a system where you will have both A and C together at all times. Proven by giving a [single] counter example.
87. Absolutism
88. High Availability Commonly measured in 9’s. We agree that absolute availability is unrealistic.
89. CAP 9’s? “In practice, many applications are best described in terms of reduced consistency or availability… … there is a Weak CAP Principle which we have yet to characterize precisely…"
90. CAP is a subset Availability and Consistency are but two (important) properties of modern distributed systems. Geo distributions, transactions, latency, durability, consistent distributed snapshots, DR, failovers, backup options, mean time to recover, observability, operability…(some properties correlate) Which are important to your service?
91. The tradeoff exists We understand this as engineers. Multiple other tradeoffs exist. I believe CAP is not the model we should be looking for.
92. Harvest, Yield, and Scalable Tolerant Systems, Armando Fox, Eric A. Brewer
 https://pdfs.semanticscholar.org/5015/8bc1a8a67295ab7bce0550886a9859000dc2.pdf Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, Seth Gilbert, Nancy Lynch
 https://www.glassbeam.com/sites/all/themes/glassbeam/images/blog/10.1.1.67.6951.pdf A Critique of the CAP Theorem, Martin Kleppmann
 https://arxiv.org/pdf/1509.05393.pdf CAP Twelve Years Later: How the "Rules" Have Changed, Eric Brewer
 https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed Please stop calling databases CP or AP, Martin Kleppmann
 https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html Further reading
93. NewSQL database systems are failing to guarantee consistency, and I blame Spanner, Daniel Abadi
 http://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html Problems with CAP, and Yahoo’s little known NoSQL system, Daniel Abadi
 http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html PACELC theorem, Wikipedia
 https://en.wikipedia.org/wiki/PACELC_theorem "A Critique of the CAP Theorem”, Julia Evans
 https://jvns.ca/blog/2016/11/19/a-critique-of-the-cap-theorem/ CAP Theorem, FoundationDB
 https://apple.github.io/foundationdb/cap-theorem.html Further reading
94. Questions? github.com/shlomi-noach @ShlomiNoach Thank you!