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