Trusted answers to developer questions

What is the CAP theorem?

Free System Design Interview Course

Many candidates are rejected or down-leveled due to poor performance in their System Design Interview. Stand out in System Design Interviews and get hired in 2024 with this popular free course.

The CAP theorem (also called Brewer’s theorem) states that a distributed database system can only guarantee two out of these three characteristics: Consistency, Availability, and Partition Tolerance.

widget

Consistency

A system is said to be consistent if all nodes see the same data at the same time.

Simply, if we perform a read operation on a consistent system, it should return the value of the most recent write operation. This means that, the read should cause all nodes to return the same data, i.e., the value of the most recent write.

Markdown Monster icon

Markdown Monster icon

Availability

Availability in a distributed system ensures that the system remains operational 100% of the time. Every request gets a (non-error) response regardless of the individual state of a node.

Note: this does not guarantee that the response contains the most recent write.

The figure on the left illustrates an “unavailable” system.

Partition Tolerance

This condition states that the system does not fail, regardless of if messages are dropped or delayed between nodes in a system.

Partition tolerance has become more of a necessity than an option in distributed systems. It is made possible by sufficiently replicating records across combinations of nodes and networks.

Markdown Monster icon

Trade-offs

In the CA (Consistency and Availability) scenario, the focus is on achieving both data consistency and system availability, with trade-offs including potential performance adjustments to maintain data accuracy. The CP (consistency and partition) scenario emphasizes maintaining data consistency even during network partitions, potentially leading to temporary unavailability to uphold data integrity. Finally, the AP (availability and partition) scenario prioritizes system availability despite network disruptions, accepting temporary data deviations to maintain operational resilience. Each scenario presents distinct trade-offs that influence the priorities of distributed systems in balancing consistency, availability, and partition tolerance.

Let's see some examples of the above mentioned trade offs.

Consistency and Availability trade-off (Key-Value Store)

class Distributed_KeyValueStore:
def __init__(self):
self.data = {}
def put(self, key, value):
self.data[key] = value
def get(self, key):
if key in self.data:
return self.data[key]
else:
return None
k_v_store = Distributed_KeyValueStore()
k_v_store.put("key1", "value_1")
print(k_v_store.get("key1"))

In the example above, consistency is prioritized by ensuring that every read (get operation) returns the write operation(put operation) that is the most recent. However, if case appears and a node fails or becomes unreachable, availability may be compromised as the system won't be able to respond to read or write requests until the node is restored. Hence, in this implementation, we prioritize consistency over availability.

Availability and Partition Tolerance trade-off

Now, lets see an example of disributed shopping cart, where we would be prioritizing availability and partition tolerance over consistency and where eventual consistency[object Object] is acceptable.

import time
class Distributed_ShoppingCart:
def __init__(self):
self.cart = {}
def add_item(self, user_id, item):
if user_id in self.cart:
self.cart[user_id].append(item)
else:
self.cart[user_id] = [item]
def get_items(self, user_id):
if user_id in self.cart:
return self.cart[user_id]
else:
return []
shopping_cart = Distributed_ShoppingCart()
shopping_cart.add_item("user1", "item1")
print(shopping_cart.get_items("user1"))

In the example above, we have prioritized availability by making sure that system continues to perform operations even in the case of failures. If the user adds an item to the cart but a network partition occurs before the data is replicated on all nodes, system might start returning inconsistent results but the mechanism of eventual consistency ensures that all the replicas become consistent.

To understand how to balance between Consistency, Availability and Partition in detail, see this Answer.

RELATED TAGS

system design
distributed systems
distributed database
database
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?