The CAP Theorem in Real Life

The CAP theorem, also known as Brewer’s theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:

• Consistency
• Availability
• Partition tolerance

Consistency means that all nodes see the same information at the same time, which implies that when a piece of information is written to a node, the data replicates to the rest of the nodes in the system.

Availability states that every request made to the system will have a response. Thus, all clients will be able to read and write to and from the system.

Partition tolerance means the system will continue to work even when a portion of the nodes gets disconnected from the rest, or becomes unavailable.

Then we can classify systems as Consistent and Available (CA), Available and Partition tolerant (AP) or Consistent and Partition tolerant (CP).

As an example of CA, we can think of a stand alone MySQL server. It’s a single node. There’s no replication. It’s going to be available and consistent unless the node goes down. Consistency and availability are guaranteed by MySQL’s ACID compliance.

If we talk about AP systems, we can think of a distributed NoSQL database where replication to nodes happens asynchronously. The system will always respond, but not all the nodes will have the latest version of the data when queried.

In practice, there’s no difference between CA and CP.  And CAP seems to start making sense in real life only to describe the behavior of a system when network partitions happen.

This means that a system can have different behaviors depending on whether a network partition exists or not. For example, consider a system that is CA in normal circumstances, and when a network partition happens, it turns to AP. Such a system relinquishes consistency in favor of availability during the network partition.

If we continue looking to real life systems, some partition tolerant NoSQL databases look like they’re giving up both availability and consistency when they’re supposed to be able to keep either one, according to Brewer. This is when latency, one of the great fallacies of distributed computing, enters the game.

Latency is the one of the major reasons to give up consistency apart from partition tolerance. In high performance systems, low latency is sometimes deemed more important than consistency. And latency is also the reason why replication must happen asynchronously.

Riak, an implementation of Amazon Dynamo paper, is a key value store, which allows you to fine tune CAP at per request level by adjusting N, R, and W parameters.

N represents the number of nodes in the cluster that the data will be replicated to, and must be greater than 0 and less than or equal to the number of actual nodes in your cluster.

The R value represents the number of Riak nodes that must return results for a read before the read is considered successful. Finally, the W value represents the number of Riak nodes that must report success before an update is considered complete.

This introduces the concept of Eventual consistency, where requests can (and should) be tuned based on data model and business needs.

In a distributed and fault-tolerant system like Riak, server and network failures are expected. Riak is designed to respond to requests even when nodes are offline or the cluster is experiencing a network partition.

Riak enables conflicting copies of data stored in the same location (as specified by bucket type, bucket and key) to exist at the same time in the cluster. Riak also ships with a set of defaults regarding how data is replicated and how conflicts are resolved, and you can override them if you seek to employ an alternative strategy.

While we are approaching 700 words, we are just scratching the surface. Suffice it to say, it’s important that we consider CAP when dealing with distributed databases, and equally important that we remember, distributed database theory does not stop there.