CAP Theorem - Should you use for designing Systems ?

The Wrong Interpretation

CAP theorem is often interpreted as — given C (Consistency), A (Availability) and P (Partition), you can choose to have any two in your system. This understanding in itself is very misleading. Partition here refers to certain kind of fault where different nodes in a distributed system are alive but are not able to connect to each other due to some network issue. As a system designer or developer, we don’t have much control over the network or issues around it and thus have no choice in opting for the Partition in CAP theorem. There are also lots of nuances in CAP theorem which we should understand to actually define CAP theorem properly.

Consistency

The term Consistency is widely used across multiple definitions. Following are the examples:

1. ACID - ACID property is one of the ways to define the behaviour of database systems. A-atomicity, C- Consistency, I-Isolation, D-Durability. Consistency in this context means, database being in a good state from the application perspective. For example, in a banking system if Bob transfers $10 to Alice, Bob's balance should be reduced by $10 and Alice's balance should be increased by $10.

2. Eventual Consistency - In context of replicated systems, when replication occurs asynchronously, there can be slight delay in the process due to multiple reasons like network delays, system faults etc. Once the replication is completed, systems should have same state or data.

3. CAP theorem - In CAP theorem, Consistency means linearizability. We would discuss this shortly.

Consistency Models

In distributed systems, Consistency model provides certain set of guarantee about its behaviour which application developers can use to make implementation decisions. Following are the widely accepted consistency models:

1. Linearizability

2. Serailizability

3. Causal consistency

4. Eventual consistency

Linearizability

Linearizability is the strongest of all consistency models. In case of replicated database systems, if a client makes a write to one of the replicas, any read on any of the replica should return this new copy of data. To the clients, it gives a perception that there is only one replica or single copy of data where read and write is happening. In a way, linearizability provides a recency guarantee. In its formal definition, CAP theorem only talks about linearizability consistency model and doesn’t cover other models and behaviours.

The Tradeoff

For many systems, linearizability is important, like an application which shows score of a match or a banking system. In these types of systems, reads should always from the most recent writes and cannot be from stale or old data. In case of a network failure, nodes which are disconnected from the network won’t be able to process the incoming requests. Such applications can either wait for the disconnected nodes to come online or return an error in response of the request. This in turn makes the system unavailable.

On the other hand, if the application doesn’t require linearizability and each server can process the request independently, like an application which uploads images and displays them in any random order, such application can be implemented in a way that it would not wait on other nodes and keep processing the requests making the system available but not linearizable.

This tradeoff was known to distributed system designers and developers since 1970s, Eric Brewer in 2000 formalised this as CAP theorem. At the time, database designers were more inclined to building systems which were conforming to linearlizable properties. CAP theorem opened up discussions on exploring new ways of implementing shared nothing systems and propelled the way forward for NoSql databases.

CAP theorem can be better interpreted as — In a distributed system (where partition is inevitable), you can pick one of Availability or Consistency (linearizability). Definition of Availability is again understood and interpreted differently across different systems and can get confusing.

Limitations

Although CAP theorem has important historical significance, more precise models are available to define the behaviour and expectations from a distributed system. CAP theorem doesn’t consider network delays, dead nodes, timeouts and multiple other trade-offs. Many systems are non linearizable for performance reasons and not due to network partition. For example, even RAM inside a multicore process system is non linearizable. Each CPU core has its own cache which is used for reads and writes for better performance and the data is written asynchronously to the main memory from these caches. This behaviour results into multiple different copies of the same data across multiple caches making the RAM non linearizable. CAP theorem cannot be used to define this kind of inconsistency model.

Summary

CAP theorem should be credited for the cultural shift of building large scale non linearizable distributed systems and advancements of NoSql databases, it has mostly historical significance in current times. With its limited scope of Consistency i.e. linearizability and one type of fault i.e. Partition, confusions around definition of Availability, it’s better to avoid CAP while making design decisions. There are better models and more precise results available today which has superseded CAP theorem.