Bird
Raised Fist0

Design a Key-Value Store - Consistent Hashing, Vector Clocks, Gossip Protocol

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/6
Client

Sends PUT request with key-value pair

Client issues HTTP PUT /key,value to store data

Protocol:HTTP
BeforeClient has key-value pair locally only
AfterPUT request sent to Load Balancer
Load Balancer

Routes request to Coordinator

Load Balancer forwards HTTP request to a Coordinator node

Protocol:HTTP
BeforeLoad Balancer has incoming client request
AfterRequest forwarded to Coordinator (API Layer)
Coordinator (API Layer)

Processes vector clocks and prepares storage request

Coordinator updates vector clock for key and selects storage node

Protocol:gRPC
BeforeCoordinator received client request without vector clock
AfterCoordinator has updated vector clock and target node info
Consistent Hashing Ring

Maps key to storage node

Consistent Hashing Ring returns responsible storage node for key

Protocol:gRPC
BeforeCoordinator needs storage node for key
AfterCoordinator knows correct storage node for key
Storage Nodes (e.g., Cassandra or ScyllaDB)

Stores key-value with vector clock metadata

Storage node writes data and vector clock version

Protocol:gRPC
BeforeStorage node has no record for key or older version
AfterKey-value stored with updated vector clock
Gossip Protocol Cluster Manager

Shares cluster membership updates

Nodes exchange membership info to maintain consistent ring

Protocol:Gossip Protocol
BeforeCluster membership state may be stale
AfterCluster membership updated and consistent across nodes
🏗️
Architecture Diagram
Architecture Diagram
┌─────────┐
│ Client  │
└────┬────┘
     │ HTTP PUT /key,value
     ▼
┌───────────────────────┐
│ Load Balancer         │
│ (routes requests)     │
└────┬──────────────────┘
     │ HTTP
     ▼
┌───────────────────────────────┐
│ Coordinator (API Layer)        │
│ (handles vector clocks, logic)│
└────┬──────────────────────────┘
     │ RPC (gRPC)
     ▼
┌───────────────────────────────┐
│ Consistent Hashing Ring        │
│ (maps key to storage node)     │
└────┬──────────────────────────┘
     │ RPC
     ▼
┌───────────────────────────────────────┐
│ Storage Nodes (e.g., Cassandra/Scylla)│
│ (store key-value with vector clocks)  │
└────┬──────────────────────────────────┘
     │ Gossip Protocol
     ▼
┌───────────────────────────────┐
│ Gossip Protocol Cluster Manager│
│ (manages cluster membership)  │
└───────────────────────────────┘
Design Rationale

This architecture uses a Load Balancer to distribute client PUT requests to Coordinators, which handle vector clocks to maintain version consistency. The Coordinator consults the Consistent Hashing Ring to identify the correct Storage Node responsible for the key. Storage Nodes persist the key-value pair along with vector clock metadata to resolve conflicts. The Gossip Protocol Cluster Manager ensures all nodes share up-to-date cluster membership information, enabling consistent hashing to adapt to node changes. This design balances scalability, consistency, and fault tolerance by combining consistent hashing for data distribution, vector clocks for versioning, and gossip for cluster state.

Primary Focus

✓

Practice

(1/5)
1. A CDN caches content globally and needs to automatically remove stale content after a fixed duration without manual intervention. Which cache invalidation strategy best fits this requirement?
easy
A. Time-To-Live (TTL) expiration set on cached objects
B. Surrogate keys to selectively invalidate groups of content
C. Manual purge triggered by an admin when content updates
D. Client-side cache control headers only

Solution

  1. Step 1: Identify automatic expiration mechanism

    TTL automatically expires cached content after a set time without manual action.

  2. Step 2: Eliminate manual and selective invalidation

    Manual purge requires human action; surrogate keys target groups, not time-based expiry; client-side headers don't enforce server cache expiry.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    TTL auto-expires stale cache entries without manual purge [check]
Hint: TTL auto-expires cache after set time [check]
Common Mistakes:
2. A load balancer must detect unhealthy backend servers and reroute traffic without client impact. Which component is primarily responsible for detecting server health status?
easy
A. Health check module that periodically probes backend servers
B. Client-side retry logic to avoid failed servers
C. Load balancer's session persistence cache to track server availability
D. DNS resolver that removes unhealthy servers from DNS responses

Solution

  1. Step 1: Identify health detection responsibility

    The health check module actively probes backend servers to determine their health status.

  2. Step 2: Eliminate other options

    DNS resolver changes are slow and indirect; session persistence caches track sessions, not health; client-side retries do not detect server health.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Health check module probes servers directly for health [check]
Hint: Health checks probe servers directly to detect failures [check]
Common Mistakes:
3. For a high-throughput system where write latency must be minimized and occasional stale reads are acceptable, which caching pattern is the best choice?
medium
A. Write-Behind, to buffer writes and asynchronously update the database
B. Cache Aside, to update cache only on misses and write directly to the database
C. Write-Through, to ensure cache and database are always consistent synchronously
D. Read-Through, to load cache on reads and write directly to the database

Solution

  1. Step 1: Analyze write latency and consistency needs

    Write-Behind buffers writes, reducing write latency but allowing stale reads.

  2. Step 2: Eliminate other options

    Write-Through adds synchronous latency; Cache Aside and Read-Through write directly to DB, no buffering.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Write-Behind buffers writes for low latency, tolerates stale reads [check]
Hint: Write-Behind buffers writes, reduces latency, allows stale reads [check]
Common Mistakes:
4. Without a consistent hashing function in a hash-based sharding system, what exact failure occurs when a new shard is added?
medium
A. New shard receives no traffic because keys are not remapped dynamically
B. Range queries become inefficient due to overlapping shard boundaries
C. Directory lookup fails to find the new shard, causing requests to be dropped
D. All existing data must be rehashed and moved, causing massive downtime and inconsistent routing

Solution

  1. Step 1: Understand consistent hashing role

    Consistent hashing minimizes key remapping when shards change.

  2. Step 2: Trace failure without consistent hashing

    Adding a shard requires rehashing all keys, moving massive data, causing downtime and routing inconsistencies.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Without consistent hashing, shard addition triggers full rehash and data move [check]
Hint: Consistent hashing avoids full rehash on shard changes [check]
Common Mistakes:
5. At 10x scale, which component in the Airbnb search and booking system is most likely to become the first bottleneck, and why?
hard
A. The relational database storing user profiles, due to complex joins on large datasets
B. The Search Index cluster, because inverted indexes grow linearly and query latency spikes
C. The Booking Service's stateful session management, because sessions cannot be easily sharded
D. The Calendar Availability cache servers, due to memory limits and high update rates

Solution

  1. Step 1: Identify stateful components limiting horizontal scaling

    Stateful session management binds user sessions to specific Booking Service instances.

  2. Step 2: Analyze scaling challenges

    User profile DB (A) can be sharded; calendar cache (C) can be scaled horizontally; search index (D) scales with sharding and caching. Stateful sessions (B) require sticky sessions or complex migration, limiting scale.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful session management limits Booking Service horizontal scaling [check]
Hint: Stateful sessions block Booking Service scaling first [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard