The CAP theorem in HLD - System Design Exercise

Design: Distributed Data Storage System

Design focuses on understanding trade-offs between consistency, availability, and partition tolerance in distributed systems. Implementation details of specific databases are out of scope.

Functional Requirements

FR1: Store and retrieve data across multiple servers

FR2: Ensure system availability even if some servers fail

FR3: Maintain data consistency across all servers

FR4: Handle network partitions gracefully

Non-Functional Requirements

NFR1: System must tolerate network failures between servers

NFR2: Latency for read and write operations should be under 200ms

NFR3: System should be available 99.9% of the time

NFR4: Data consistency must be guaranteed or availability prioritized depending on scenario

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Distributed data nodes or servers

Replication mechanisms

Consensus or coordination protocols

Failure detection and recovery modules

Client request routers or load balancers

Design Patterns

Leader-based replication

Quorum-based reads and writes

Eventual consistency

Partition detection and failover

Consensus algorithms like Paxos or Raft

Reference Architecture

          +---------------------+
          |     Client App      |
          +----------+----------+
                     |
          +----------v----------+
          |   Request Router    |
          +----------+----------+
           /          |          \
+----------v+  +------v------+  +--v----------+
| Data Node |  | Data Node  |  | Data Node   |
|  Server 1 |  |  Server 2  |  |  Server 3   |
+-----------+  +------------+  +-------------+
       |             |               |
       +-------------+---------------+
                     |
             Network Partition

Components

Client App

Any client platform

Sends data read/write requests to the system

Request Router

Load balancer or API gateway

Distributes client requests to data nodes

Data Nodes

Distributed servers with storage

Store replicated data and respond to requests

Replication Mechanism

Leader election or quorum protocol

Ensure data copies are consistent or eventually consistent

Network Partition

Simulated network failure

Represents communication breakdown between nodes

Request Flow

1. Client sends a read or write request to the Request Router.

2. Request Router forwards the request to one or more Data Nodes.

3. Data Nodes coordinate using replication protocol to maintain consistency or availability.

4. If a network partition occurs, nodes may become isolated.

5. Depending on system design, nodes either prioritize consistency (reject writes) or availability (accept writes with possible inconsistency).

6. Responses are sent back to the client via the Request Router.

Database Schema

Entities: DataItem {id, value, version} Relationships: Replicated copies of DataItem exist on multiple Data Nodes with version tracking for consistency.

Scaling Discussion

Bottlenecks

Network partitions causing data inconsistency or unavailability

Leader node becoming a single point of failure or bottleneck

High latency due to coordination among many nodes

Storage limits on individual data nodes

Solutions

Implement partition-tolerant designs choosing between CP or AP based on use case

Use consensus algorithms with leader failover to avoid single points of failure

Use quorum-based reads/writes to balance consistency and availability

Shard data across nodes to distribute storage and load

Interview Tips

Time: Spend 10 minutes explaining CAP theorem basics and trade-offs, 15 minutes designing a simple distributed system example, 10 minutes discussing scaling and real-world implications, 10 minutes answering questions.

Explain the three guarantees: Consistency, Availability, Partition tolerance

Clarify that only two can be fully achieved simultaneously in presence of partitions

Discuss real-world examples of CP and AP systems

Show understanding of trade-offs and how system requirements influence design choices

Mention how consensus and replication protocols help manage these trade-offs

Practice

1. Which two properties can a distributed system guarantee at the same time according to the CAP theorem?

easy

A. Consistency and Availability

B. Availability and Partition tolerance

C. Consistency and Partition tolerance

D. Consistency, Availability, and Partition tolerance all together

Solution

1. Step 1: Understand the CAP theorem basics

   The CAP theorem states that a distributed system can only guarantee two out of three properties: Consistency, Availability, and Partition tolerance.

2. Step 2: Identify which pairs are possible

   Systems can guarantee Availability and Partition tolerance or Consistency and Partition tolerance, but not all three simultaneously. However, only Availability and Partition tolerance can be guaranteed simultaneously in the presence of network partitions.

3. Final Answer:

   Availability and Partition tolerance -> Option B

4. Quick Check:

   CAP theorem = two properties only [OK]

Hint: Remember CAP means pick only two properties [OK]

Common Mistakes:

• Thinking all three properties can be guaranteed simultaneously
• Confusing Availability with Partition tolerance
• Ignoring network partitions in distributed systems

2. Which of the following is the correct definition of Partition tolerance in the CAP theorem?

easy

A. The system can handle unlimited data growth

B. All nodes always return the same data at the same time

C. The system is always available to respond to requests

D. The system continues to operate despite network failures between nodes

Solution

1. Step 1: Define Partition tolerance

   Partition tolerance means the system keeps working even if some network connections between nodes fail or messages are lost.

2. Step 2: Match definitions to options

   The system continues to operate despite network failures between nodes correctly describes Partition tolerance as handling network failures. Other options describe consistency, availability, or scalability.

3. Final Answer:

   The system continues to operate despite network failures between nodes -> Option D

4. Quick Check:

   Partition tolerance = handle network splits [OK]

Hint: Partition tolerance means surviving network splits [OK]

Common Mistakes:

• Confusing Partition tolerance with Availability
• Thinking Partition tolerance means data consistency
• Assuming Partition tolerance means unlimited scaling

3. Consider a distributed database that chooses Availability and Partition tolerance over Consistency. What is the expected behavior during a network partition?

medium

A. The system may return stale or inconsistent data but remains available

B. The system rejects all writes until the partition is resolved

C. The system becomes unavailable to maintain consistency

D. The system automatically merges all data without conflicts

Solution

1. Step 1: Identify chosen CAP properties

   The system chooses Availability and Partition tolerance, sacrificing Consistency.

2. Step 2: Analyze behavior during network partition

   Because it prioritizes Availability, the system stays up and responds to requests, but data may be inconsistent or stale.

3. Final Answer:

   The system may return stale or inconsistent data but remains available -> Option A

4. Quick Check:

   Availability + Partition tolerance = possible inconsistency [OK]

Hint: Availability + Partition tolerance means possible stale data [OK]

Common Mistakes:

• Assuming system rejects writes to keep consistency
• Thinking system becomes unavailable during partition
• Believing automatic conflict-free merges always happen

4. A developer claims their distributed system guarantees Consistency, Availability, and Partition tolerance simultaneously. What is the most likely issue?

medium

A. The system is using eventual consistency, not strong consistency

B. The system is only tested on a single node

C. The system is ignoring network partitions or failures

D. The system uses synchronous replication

Solution

1. Step 1: Recall CAP theorem limitation

   The CAP theorem states all three properties cannot be guaranteed simultaneously in a distributed system.

2. Step 2: Identify the likely mistake

   If the system claims all three, it probably ignores or does not handle network partitions properly, which is unrealistic in real distributed environments.

3. Final Answer:

   The system is ignoring network partitions or failures -> Option C

4. Quick Check:

   CAP theorem forbids all three together [OK]

Hint: All three CAP properties together is impossible [OK]

Common Mistakes:

• Assuming eventual consistency means full consistency
• Thinking synchronous replication solves CAP limits
• Ignoring real network failures in testing

5. You are designing a global online banking system where transactions must be accurate and consistent even during network failures. According to the CAP theorem, which two properties should you prioritize and why?

hard

A. Consistency and Partition tolerance, to maintain accurate data despite network partitions, even if some requests are delayed

B. Availability and Partition tolerance, to keep the system running even if data is temporarily inconsistent

C. All three properties equally, because banking requires perfect reliability

D. Consistency and Availability, to ensure all users see the same data and system is always responsive

Solution

1. Step 1: Understand banking system requirements

   Banking needs accurate, consistent transactions even if network issues occur, so data correctness is critical.

2. Step 2: Apply CAP theorem to design choice

   To keep data consistent during network partitions, the system must prioritize Consistency and Partition tolerance, accepting some availability delays.

3. Final Answer:

   Consistency and Partition tolerance, to maintain accurate data despite network partitions, even if some requests are delayed -> Option A

4. Quick Check:

   Banking = Consistency + Partition tolerance [OK]

Hint: Banking needs consistency over availability during partitions [OK]

Common Mistakes:

• Choosing availability over consistency for critical data
• Assuming all three CAP properties can be met
• Ignoring impact of network partitions on data accuracy