Consistency models (strong, eventual) in HLD - System Design Exercise

Design: Distributed Data Store with Consistency Models

Design focuses on consistency models implementation in a distributed data store. Does not cover user interface or specific database query languages.

Functional Requirements

FR1: Support read and write operations on distributed data

FR2: Provide strong consistency option where reads always see the latest writes

FR3: Provide eventual consistency option where reads may see stale data but system converges eventually

FR4: Allow clients to choose consistency model per operation

FR5: Handle network partitions and node failures gracefully

FR6: Ensure data durability and availability

Non-Functional Requirements

NFR1: System should handle 10,000 concurrent clients

NFR2: Read latency under strong consistency: p99 < 200ms

NFR3: Read latency under eventual consistency: p99 < 50ms

NFR4: Availability target: 99.9% uptime

NFR5: Data replication across at least 3 nodes for fault tolerance

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Client API layer to specify consistency preference

Replication protocol (e.g., consensus for strong consistency)

Conflict resolution mechanism for eventual consistency

Data storage nodes

Failure detection and recovery modules

Design Patterns

Consensus algorithms (Paxos, Raft) for strong consistency

Gossip protocols for eventual consistency

Quorum reads and writes

Vector clocks or version vectors for conflict detection

Reference Architecture

          +-------------------+
          |      Clients      |
          +---------+---------+
                    |
        +-----------+-----------+
        |    API Gateway Layer   |
        | (Consistency Selector) |
        +-----------+-----------+
                    |
       +------------+------------+
       |                         |
+------+-----+             +-----+-------+
| Strong Consistency Node  |  Eventual    |
|  Cluster (Consensus)     |  Consistency |
|  (Raft/Paxos)            |  Cluster     |
+------+-----+             +-----+-------+
       |                         |
       +------------+------------+
                    |
           +--------+--------+
           |   Persistent    |
           |   Storage       |
           +-----------------+

Components

API Gateway Layer

Custom service

Receives client requests and routes them to appropriate consistency cluster based on requested model

Strong Consistency Node Cluster

Raft consensus algorithm

Ensures linearizable reads and writes by replicating data with consensus

Eventual Consistency Node Cluster

Gossip protocol

Replicates data asynchronously allowing faster reads with eventual convergence

Persistent Storage

Distributed key-value store (e.g., RocksDB, Cassandra)

Stores data durably on each node

Request Flow

1. Client sends read or write request with consistency preference to API Gateway.

2. API Gateway routes request to Strong Consistency Cluster if strong consistency requested.

3. Strong Consistency Cluster uses Raft to replicate write and confirm commit before responding.

4. Reads in Strong Consistency Cluster query leader node to get latest data.

5. If eventual consistency requested, API Gateway routes request to Eventual Consistency Cluster.

6. Eventual Consistency Cluster applies writes asynchronously and replicates via gossip.

7. Reads in Eventual Consistency Cluster may return stale data but system converges eventually.

8. Both clusters persist data locally to durable storage.

9. Failure detection triggers leader election in Strong Consistency Cluster or repair in Eventual Consistency Cluster.

Database Schema

Entities: - DataItem: key (string), value (blob), version (vector clock or term number) Relationships: - Each DataItem replicated across multiple nodes - Versioning used to detect conflicts in eventual consistency - Strong consistency cluster maintains single leader with committed version - Eventual consistency cluster nodes exchange versions via gossip

Scaling Discussion

Bottlenecks

Strong consistency cluster leader becomes bottleneck under high write load

Network latency impacts consensus protocol performance

Eventual consistency cluster may have stale reads during partitions

Storage capacity limits on each node

API Gateway can become a single point of failure

Solutions

Partition data by key ranges to multiple strong consistency clusters (sharding)

Use faster consensus algorithms or optimize network topology

Implement conflict resolution and version reconciliation in eventual cluster

Add horizontal scaling with auto-scaling storage nodes

Deploy multiple API Gateway instances behind load balancer

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain difference between strong and eventual consistency with examples

Describe how consensus algorithms ensure strong consistency

Discuss trade-offs between latency, availability, and consistency

Show understanding of replication and failure handling

Highlight how clients can choose consistency per request

Practice

1. Which statement best describes strong consistency in distributed systems?

easy

A. All users see the same data immediately after an update.

B. Data updates are delayed and may differ temporarily between users.

C. Data is never synchronized between nodes.

D. Users see different versions of data permanently.

Solution

1. Step 1: Understand strong consistency definition

   Strong consistency means every read returns the most recent write, so all users see the same data instantly.

2. Step 2: Compare options with definition

   All users see the same data immediately after an update. matches this definition exactly, while others describe delayed or inconsistent views.

3. Final Answer:

   All users see the same data immediately after an update. -> Option A

4. Quick Check:

   Strong consistency = immediate data sync [OK]

Hint: Strong consistency means instant data visibility everywhere [OK]

Common Mistakes:

• Confusing strong consistency with eventual consistency
• Thinking data can be permanently inconsistent
• Assuming delays are allowed in strong consistency

2. Which of the following is a correct characteristic of eventual consistency?

easy

A. No synchronization happens between nodes.

B. All nodes update simultaneously with no delay.

C. Data is always consistent after every write operation.

D. Data updates propagate over time and become consistent eventually.

Solution

1. Step 1: Recall eventual consistency meaning

   Eventual consistency means updates may take time to reach all nodes, but eventually all nodes will have the same data.

2. Step 2: Match options to definition

   Data updates propagate over time and become consistent eventually. correctly states that data updates propagate over time and become consistent eventually.

3. Final Answer:

   Data updates propagate over time and become consistent eventually. -> Option D

4. Quick Check:

   Eventual consistency = delayed but eventual sync [OK]

Hint: Eventual consistency means data sync happens over time [OK]

Common Mistakes:

• Assuming immediate synchronization in eventual consistency
• Confusing no synchronization with eventual consistency
• Thinking eventual consistency means permanent inconsistency

3. Consider a distributed database using eventual consistency. If a user updates a record on one node, what is the expected behavior immediately after the update?

medium

A. Other nodes may temporarily show the old record until synchronization completes.

B. All other nodes instantly reflect the updated record.

C. The update is rejected until all nodes confirm availability.

D. The record is deleted from all nodes except the updated one.

Solution

1. Step 1: Analyze eventual consistency update behavior

   In eventual consistency, updates propagate asynchronously, so other nodes may temporarily have stale data.

2. Step 2: Evaluate options against this behavior

   Other nodes may temporarily show the old record until synchronization completes. correctly states that other nodes may show old data until synchronization finishes.

3. Final Answer:

   Other nodes may temporarily show the old record until synchronization completes. -> Option A

4. Quick Check:

   Eventual consistency = temporary stale reads [OK]

Hint: Eventual consistency allows temporary stale data [OK]

Common Mistakes:

• Expecting instant update on all nodes
• Confusing update rejection with consistency model
• Assuming data deletion on other nodes

4. A system claims to provide strong consistency but users report seeing outdated data after updates. What is the most likely cause?

medium

A. The system uses synchronous replication correctly.

B. The system is actually using eventual consistency under the hood.

C. Users are refreshing their data too often.

D. The network is too fast causing data to update too quickly.

Solution

1. Step 1: Understand strong consistency guarantees

   Strong consistency guarantees all users see the latest data immediately after update.

2. Step 2: Analyze why outdated data appears

   If users see outdated data, the system likely does not enforce strong consistency, possibly using eventual consistency instead.

3. Final Answer:

   The system is actually using eventual consistency under the hood. -> Option B

4. Quick Check:

   Outdated data means no strong consistency [OK]

Hint: Outdated data means strong consistency is not enforced [OK]

Common Mistakes:

• Blaming network speed for outdated data
• Assuming user refresh frequency causes inconsistency
• Confusing synchronous replication with eventual consistency

5. You are designing a global e-commerce platform. Which consistency model should you choose for the inventory stock count to ensure customers never buy more items than available, and why?

hard

A. Eventual consistency, because it improves performance and availability.

B. No consistency model is needed for inventory data.

C. Strong consistency, because it guarantees all users see the latest stock count immediately.

D. Use eventual consistency with no synchronization.

Solution

1. Step 1: Identify critical data requirements

   Inventory stock count must be accurate to prevent overselling, requiring immediate data correctness.

2. Step 2: Choose consistency model based on requirements

   Strong consistency ensures all users see the latest stock count instantly, preventing overselling.

3. Final Answer:

   Strong consistency, because it guarantees all users see the latest stock count immediately. -> Option C

4. Quick Check:

   Critical data needs strong consistency [OK]

Hint: Critical data needs strong consistency for accuracy [OK]

Common Mistakes:

• Choosing eventual consistency for critical stock data
• Ignoring consistency needs for inventory
• Assuming no consistency is acceptable