CAP Theorem in Distributed Systems
Designing a Distributed System (DS) is a task that requires careful speculation and rationale. It requires foresight accumulated through years of experiences (manifested through issues and failures) and knowledge (awareness) on contemporary technologies so that cost and effort complement the final outcome. Caution needs to be exercised especially when it comes to expanding the scale of the system (both vertically and horizontally) and how the system faces the load with respect to the scale. Contemporary large-scale systems (Amazon, Google, etc.) use their own data-structures in terms of achieving their targetted design goals. Designing their own protocols, in-compliance with regulations is of significant importance since their infrastructures are not independent of the rest of the world. Furthermore, implementing their own protocol stacks and technologies aid each organization to optimize their own performance heuristics: be it availability, security or consistency of their services.
CAP theorem, which was first designed by Eric Brewer, is one way of discerning the design of a distributed system: but it’s not the only way. CAP stands for heuristics the theorem regards as significant when it comes to the design of a DS.
- Consistency
- Availability
- Partition-Tolerance
Consistency
Distributed systems are known for replication i.e. they work in clusters, co-operating with each other. There’s no notion of a global memory store, and thus, each node has to maintain its own copy of the memory chunks the cluster intends to share between each other. When an update (a write, usually originated by a client) occurs in a node, it should be reflected in all the other nodes, so that the rest of the clients observing the nodes (clients connected with other nodes) see the new, updated value. A system that is void of this consistency is called an inconsistent system.
There’s a hierarchical nomenclature for various types of consistencies, which I would not venture in this article. However, CAP theorem states and adheres to one particular level of consistency, which is called Linearizable Consistency which requires attending to.
A linearizable consistent system updates the replicas as soon as an update (a write, usually) occurs. It doesn’t spend time on updating the other nodes about the write, and thus, consistency could be maintained. However, it should be noted that this synchronous behavior is a cost, or an overhead in terms of performance since the update operations are not returned and the subsequent read operations are blocked until the replication is done.
Availability
Generally, the availability of a node is measured by its up-time. A node having a 90% up-time is more available than a node having that of 80%. However, there’s a distinct difference between the availability and CAP availability. CAP availability infers about non-failing nodes, where if a node has not failed it should reply to the incoming messages (it doesn’t matter whether the replies are errors). CAP availability also assumes an unbounded response time. The latter assumption is of less practical occurrence, as unbounded response time can lead to a loss of user groups. Furthermore, practicality dictates that generally, availability is discussed for an entire system — not just for each non-failing node. A highly available system is of significant importance, as it determines the discovery of services for the users. For instance, in a highly available system does not fail to provide the user with the required service even though some nodes have failed. Availability is readily achieved by the replication of nodes. The potential of availability, in Amazon’s paper on Dynamo, is explained as follows. [1]
“For example, customers should be able to view and add items to their shopping cart even if disks are failing, network routes are flapping, or data centers are being destroyed by tornados.”
Partition Tolerance
It is an inevitability that the network sometimes fails due to complexities both physical and logical. We are used to failing networks due to physical issues such as poor wiring, but there are other logical issues such as garbage collection, which can cause problems for networks. Quite inevitably, networks, therefore, are partitioned into multiple groups due to network failures. In the CAP theorem, partition tolerance is defined as the capability to account for any loss of a message between partitions. In other words, if there are two clusters G1 and G2 (partitions), we can assume, in the worst case, that the communication link between G1 and G2 has failed. The system should be able to account for it.
Can we have all CAP?
As explained below, in a practical system, we always have partition tolerance, i.e. network failures. The only exception which I can think of is a single node system, which is not regarded as a distributed system. However, low-proximity networks such as LAN can also be regarded as transparent to network failures, but we cannot guarantee it.
As a comprehensive proof of that, we cannot have all three CAP principles in a practical distributed system, we adhere to the principle of contradiction. Say, the observed system satisfies all three CAP principles. This essentially means that there is a connection failure between two nodes (we’ll name them G1 and G2).
Say that we have a variable v whose value is shared among the two nodes G1 and G2. A client (we’ll name it C) now messages G1 to update the value of v to v`. Because there is no communication link (partition tolerance) between G1 and G2, this update is simply not reflected in G2. Therefore, when the client queries for a select for value v, node G2 responds with the previous value v, which reflects an inconsistent system. According to our prior assumption that CAP is satisfied, we arrive at a contradiction. Therefore, we conclude that all the CAP principles cannot be achieved together in the same instance.
However, it is possible to achieve dual-systems (CA — not possible: we’ll examine why, CP and AP), which is our next topic.
Dual Systems
First, it is required to reminisce that P is inevitable. Therefore, P is a factor we cannot (practically) get rid of. Therefore, we shall reconcile CP and AP.
The opportunity cost of a system with consistency and partition tolerance is availability. For instance, G1 and G2 are not linked (because of P) and therefore, in order for the two-node system to become consistent, querying the outdated system (G2, as our previous discussion, where the value is still v) should be blocked i.e. G2 must not be available.
The opportunity cost of a system with availability and partition tolerance is consistency. Consider the same G1 and G2 (without a link because of P), and an update to G1 is not reflected in G2, sacrificing consistency for a highly available G1 and G2.
Therefore, we can deduce that achieving consistency and availability is a continuum, and attending and committing to one is reflected by sacrificing the other. This is of practical significance since some systems maintain their main requirement as availability (e.g. public REST endpoints) and others, consistency (e.g. banking applications). Furthermore, essential factors such as latency, fault-tolerance, and simplicity are not addressed in the CAP theorem, which is regarded as a con in the theorem itself.
References
[1] DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P. and Vogels, W., 2007, October. Dynamo: amazon’s highly available key-value store. In ACM SIGOPS operating systems review (Vol. 41, №6, pp. 205–220). ACM.
[2] An Illustrated Proof of the CAP Theorem. [Online]. Available: https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/. [Accessed: 05-Jan-2020].
[3] “Please stop calling databases CP or AP,” Please stop calling databases CP or AP — Martin Kleppmann’s blog. [Online]. Available: https://martin.kleppmann.com/2015/05/11/please-stop-calling-databases-cp-or-ap.html. [Accessed: 05-Jan-2020].
[4] Fox, A. and Brewer, E.A., 1999, March. Harvest, yield, and scalable tolerant systems. In Proceedings of the Seventh Workshop on Hot Topics in Operating Systems (pp. 174–178). IEEE.
[5] Brewer, E., 2012. CAP Twelve years Later: how the. Computer, (2), pp.23–29.
