15 CAP Theorem Interview Questions (ANSWERED) For System Design Interview

The CAP Theorem for distributed computing was published by Eric Brewer. This states that it is not possible for a distributed computer system to simultaneously provide all three of the following guarantees:

1. Consistency (all nodes see the same data even at the same time with concurrent updates )
2. Availability (a guarantee that every request receives a response about whether it was successful or failed)
3. Partition tolerance (the system continues to operate despite arbitrary message loss or failure of part of the system)

The CAP acronym corresponds to these three guarantees. This theorem has created the base for modern distributed computing approaches. Worlds most high volume traffic companies (e.g. Amazon, Google, Facebook) use this as basis for deciding their application architecture. It's important to understand that only two of these three conditions can be guaranteed to be met by a system.

No. You might have designed a system that is not heavily affected by it. That's good.

With multiple copies of the same data, we are faced with options on how to synchronize them so clients have a consistent view of the data:

• Weak consistency - After a write, reads may or may not see it. A best effort approach is taken. This approach is seen in systems such as memcached. Weak consistency works well in real time use cases such as VoIP, video chat, and realtime multiplayer games. For example, if you are on a phone call and lose reception for a few seconds, when you regain connection you do not hear what was spoken during connection loss.

• Eventual consistency - After a write, reads will eventually see it (typically within milliseconds). Data is replicated asynchronously. This approach is seen in systems such as DNS and email. Eventual consistency works well in highly available systems.

• Strong consistency - After a write, reads will see it. Data is replicated synchronously. This approach is seen in file systems and RDBMSes. Strong consistency works well in systems that need transactions.

Availability means the ability of the application user to access the system, If a user cannot access the application, it is assumed unavailable. High Availability means the application will be available, without interruption. Using redundant server nodes with clustering is a common way to achieve higher level of availability in web applications.

Availability is commonly expressed as a percentage of uptime in a given year.

• Consistency means that data is the same across the cluster, so you can read or write from/to any node and get the same data.
• Availability means the ability to access the cluster even if a node in the cluster goes down.
• Partition tolerance means that the cluster continues to function even if there is a "partition" (communication break) between two nodes (both nodes are up, but can't communicate).

If you have both availability (the cluster doesn't go down) and partition tolerance (the database can survive nodes being unable to communicate), then you can't guarantee that all nodes will always have all the data (consistency), because nodes are up and accepting writes, but can't communicate those writes to each other.

The CAP Theorem says that it is impossible to build an implementation of read-write storage/system in an asynchronous network that satisfies all of the following three properties:

• Availability - will a request made to the data store always eventually complete?
• Consistency - will all executions of reads and writes seen by all nodes be atomic or linearizably consistent?
• Partition tolerance - the network is allowed to drop any messages.

More informally, the CAP theorem tells us that we can't build a database/system that both responds to every request and returns the results that you would expect every time.

One such fallacy of distributed computing is that networks are reliable. They aren't. Networks and parts of networks go down frequently and unexpectedly.

A partition is when the network fails to deliver some messages to one or more nodes by losing them (not by delaying them - eventual delivery is not a partition).

The basic idea of CAP proof is that if a client writes to one side of a partition (namely, network fails), any reads that go to the other side of that partition can't possibly know about the most recent write. The proof of CAP relied on a total partition. In practice, these are arguably the most likely since all messages may flow through one component; if that fails then message loss is usually total between two nodes.

It's proofed by construction. Basically we demonstrate a single situation where a system cannot be consistent and available in the same time:

If a client writes to one side of a partition, any reads that go to the other side of that partition can't possibly know about the most recent write. Now you're faced with a choice: do you respond to the reads with potentially stale information, or do you wait (potentially forever) to hear from the other side of the partition and compromise availability?