The (in)famous CAP Theorem

CAP or CA?

Although there is a lack of precision of consistency, availability and partition tolerance in the community, I will start with the definition of Wikipedia,

  • Consistency: Every read receives the most recent write or an error
  • Availability: Every request receives a (non-error) response, without the guarantee that it contains the most recent write
  • Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

Availability

Availability is the least discussed among the CAP triangle since the system availability is usually well defined and rare misunderstood. Distributed system achieve high availability and fault tolerance through data replication. In a nutshell, each nodes in the system can be replaced by a few other nodes (replication) without serious system downtime. However, there are some caveats when we discuss the availability. The precise requirement of availability in fact guides us toward a proper architecture for given use cases.

Read Availability vs. Write Availability

The read operations scan the data without any modification, which is as idempotent. All replicated data node can answer read request. Therefore, high read availability is usually not concerning for distributed data system design.

Availability vs. Scalability

Given the limited processing of a single commodity machine, the availability and scalability is usually very related. If there are more data size (storage scalability) or queries per second (computation scalability), the system will run out of resource and become unavailable. We will have to scale the system either vertical or horizontal. Therefore, a system with crippled availability can seldom scale well. For example, HBase is well criticized for its write operation scalability due to its single leader architecture.

Consistency

Almost all distributed data system tolerate node tolerance through data replication. Every piece of data is duplicated and stored on difference nodes to reduce the impact on individual node failure. Some data nodes may fail to keep in sync with each other. The data replication may be delayed due to a congested network. Some data nodes may be recovering from a system fault and catching up with recent data. There are countless possibilities to cause data discrepancy among data nodes. The consistency is system properties to quantify the discrepancy. In my opinion, we can read different consistency from timely and integral perspective. The timeliness ensures the user always sees the up-to-date data while the integrity guarantees no data loss or corrupted.

Eventual Consistency

Most replicated data systems provide at least eventual consistency, which means that if you stop writing to database, then eventually all read requests will return the same value. In other words, the inconsistency is temporary and data will eventually coverage to the same value. We can see eventual consistency guarantees data integrity. However, it is a very weak consistency level since there is no statement about when the replicas will coverage.

Linearizability

The linearizability is considered as the strongest level of consistency. A linearizable system acts as there is one and only one copy of the data regardless of underlying data replication strategies. Linearizability guarantees both data integrity and timeliness.

Causal Consistency

Causal consistency captures the potential causal relationships between operations, and guarantees that all processes observe causally-related operations in a common order. In other words, all processes in the system agree on the order of the causally-related operations. They may disagree on the order of operations that are causally unrelated. Causal consistency is also a weak consistency but since it matches application’s intuition about time and logical ordering. Additionally due to the cost of linearizability, most distributed data system claims causal consistency to boost performance. Causal consistency can be summarized in four shades:

  • Read Your Writes: If a process performs a write, the same process later observes the result of its write.
  • Monotonic Reads: the set of writes observed (read) by a process is guaranteed to be monotonically non-decreasing.
  • Writes Follow Reads: if some process performs a read followed by a write, and another process observes the result of the write, then it can also observe the read (unless it has been overwritten).
  • Monotonic Writes: If some process performs a write, followed some time later by another write, other processes will observe them in the same order.

What is Next

In this blog, we dive into the details of CAP theorem and clarified some misunderstanding about distributed system properties. In the last section, we briefly discussed the causal consistency needs proper concurrency or isolation design, which is an important properties of transactions. In the next blog, we will expand the scope of transaction and discuss distributed transactions, including the use cases and some implementation details.

Reference

Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store