Bird
Raised Fist0

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

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design a Key-Value Store - Consistent Hashing, Vector Clocks, Gossip Protocol
45 min · senior
senior

You are building a distributed Key-Value Store for a startup with 50 million daily active users (DAU). The system must support strong consistency with conflict resolution, tolerate node failures gracefully, and maintain P99 read/write latency under 200ms. Data must be encrypted at rest and in transit. The system should support offline client operations with eventual sync. The cluster membership and failure detection must be decentralized and scalable.

Constraints
  • Support 50M DAU with peak 1M concurrent clients
  • P99 read/write latency under 200ms
  • Data encrypted at rest and in transit (TLS + disk encryption)
  • Offline client support with eventual sync and conflict resolution
  • Cluster membership and failure detection via decentralized protocol
  • Strong consistency with vector clock-based conflict resolution
📋
Guided Steps
1/5
Step 1
Data Partitioning and Node Assignment
How will you partition the keyspace across nodes to ensure balanced load and scalability?
💡 Hint
Consider a hashing scheme that minimizes data movement when nodes join or leave.
Key Decision
Use Consistent Hashing with virtual nodes to evenly distribute keys across Cassandra nodes, minimizing rebalancing during cluster membership changes.
Interviewer Expectation
Mid: Names consistent hashing for partitioning. Senior: Explains how virtual nodes reduce hotspotting and rebalancing overhead compared to simple modulo hashing, and mentions Cassandra's vnode implementation.
⚠️Common Wrong Answer
Using modulo-based partitioning - causes massive data reshuffling and hotspots when nodes fail or join, breaking availability.
Step 2
Versioning and Conflict Resolution
How will you track versions of values and resolve concurrent updates in an eventually consistent environment?
💡 Hint
Use a vector clock to capture causality and detect conflicts between versions.
Key Decision
Attach Vector Clocks to each key-value pair to track causal dependencies and enable deterministic conflict resolution on read or sync.
Interviewer Expectation
Mid: Mentions vector clocks for versioning. Senior: Details how vector clocks enable detecting concurrent writes and merging or exposing conflicts to clients, including how vector clocks are updated on writes and merged on reads.
⚠️Common Wrong Answer
Using timestamps only - leads to lost updates and incorrect conflict resolution under concurrent writes.
Step 3
Cluster Membership and Failure Detection
How will nodes discover each other and detect failures in a decentralized manner?
💡 Hint
Use a gossip protocol to propagate membership and failure info efficiently and scalably.
Key Decision
Implement the SWIM gossip protocol for scalable, decentralized cluster membership and failure detection with low false positives.
Interviewer Expectation
Mid: Names gossip protocol for membership. Senior: Explains SWIM’s failure detection accuracy, scalability benefits over centralized health checks, and how it reduces false positives via indirect probes.
⚠️Common Wrong Answer
Centralized health checks - single point of failure and does not scale to large clusters.
Step 4
Data Encryption and Security
How will you ensure data is encrypted both at rest and in transit without impacting latency beyond 200ms P99?
💡 Hint
Use TLS for transport and native disk encryption with hardware acceleration where possible.
Key Decision
Use TLS 1.3 for all client-node and inter-node communication and enable OS-level disk encryption (e.g., dm-crypt with AES-NI) on Cassandra nodes to secure data at rest.
Interviewer Expectation
Mid: Mentions TLS and disk encryption. Senior: Explains TLS 1.3 reduces handshake latency and hardware acceleration (AES-NI) keeps encryption overhead within latency budget.
⚠️Common Wrong Answer
Encrypting data at application layer only - adds complexity and latency, and risks inconsistent encryption standards.
Step 5
Offline Client Support and Sync
How will clients operate offline and later synchronize their changes with the cluster while preserving consistency?
💡 Hint
Use vector clocks to detect conflicts during sync and a sync protocol that merges or surfaces conflicts.
Key Decision
Clients maintain local vector clocks and batch offline writes; upon reconnect, they sync with the cluster using vector clocks to detect conflicts and resolve or expose them.
Interviewer Expectation
Mid: Describes offline caching and sync. Senior: Details vector clock usage in sync protocol and conflict resolution strategies, including how conflicts are surfaced or merged automatically.
⚠️Common Wrong Answer
Simple last-write-wins sync - causes data loss and inconsistent client views.
🔌
API Design Challenge
Sketch 3 core API endpoints for the Key-Value Store client: how clients write data, read data, and synchronize offline changes.
Hints
  • How does the client send a write with versioning metadata?
  • How does the client read the latest consistent value with conflict info?
  • How does the client sync offline changes and resolve conflicts?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Consistent Hashing with virtual nodes for scalable partitioning
  • Vector Clocks for versioning and conflict resolution
  • Gossip protocol (SWIM) for cluster membership and failure detection
  • Encrypted communication with TLS 1.3 and disk encryption
Good to Have - 30%
  • Offline client sync using vector clocks
  • Use of Cassandra for scalable storage
  • Conflict resolution strategies exposed to clients
Bonus - 10%
  • Hardware acceleration for encryption to meet latency SLAs
  • Detailed API design for client sync and conflict handling
Anti-patterns to Avoid
Modulo-based partitioning causing hotspots and massive data reshuffling on node changes, leading to availability degradation and increased latency.
Using timestamps alone for versioning leading to lost updates and inconsistent state due to inability to detect concurrent writes.
Centralized failure detection causing single point of failure and poor scalability, resulting in cluster outages under load.
Encrypting data only at application layer increasing latency and complexity, and risking inconsistent encryption standards across components.
Last-write-wins conflict resolution causing data loss in concurrent updates and inconsistent client views.
HTTP polling at 50M DAU: 50 million reconnects per minute just to check for messages - collapses under load and increases latency.
✅
Model Answer
▼ Reveal

The system uses Consistent Hashing with virtual nodes to partition keys across Cassandra nodes, Vector Clocks to track causal versions and resolve conflicts, and the SWIM gossip protocol for decentralized cluster membership and failure detection. TLS 1.3 and OS-level disk encryption secure data in transit and at rest. Clients maintain vector clocks locally to support offline writes and synchronize changes with conflict detection.

Key Decisions
  • Use Consistent Hashing with virtual nodes on Cassandra to balance load and minimize data movement
  • Attach Vector Clocks to each key-value pair to track causality and enable conflict detection and resolution
  • Implement SWIM gossip protocol for decentralized, scalable cluster membership and failure detection
  • Use TLS 1.3 for all network communication to reduce handshake latency and ensure encryption
  • Enable OS-level disk encryption with hardware acceleration (AES-NI) to secure data at rest without latency penalty
  • Clients maintain local vector clocks and batch offline writes; sync uses vector clocks to detect and resolve conflicts
  • Consistent Hashing with virtual nodes for balanced key distribution and minimal rebalancing
  • Vector Clocks for causal versioning and deterministic conflict detection/resolution
  • SWIM Gossip Protocol for decentralized, scalable cluster membership and failure detection
  • Cassandra as the storage engine for scalable, durable, and partition-tolerant key-value storage
  • TLS 1.3 for encrypted client-node and inter-node communication with low latency overhead
  • OS-level disk encryption (e.g., dm-crypt with AES-NI) for data at rest security
  • Client-side vector clock tracking and batch sync protocol for offline operation support
  • Conflict resolution surfaced to clients or merged automatically based on vector clock causality

Practice

(1/5)
1. In a distributed database, at Step 4 the coordinator node receives conflicting writes from two partitions during a network split. What state does the coordinator enter immediately after Step 4?
easy
A. Coordinator marks the writes as conflicting and delays commit until partition heals
B. Coordinator commits both writes immediately to maintain availability
C. Coordinator rejects all writes to maintain consistency during partition
D. Coordinator forwards writes to a third node to resolve conflicts synchronously

Solution

  1. Step 1: Trace coordinator behavior at Step 4

    The coordinator detects conflicting writes from partitions and cannot commit both safely.

  2. Step 2: Understand conflict resolution

    It marks writes as conflicting and delays commit until partitions heal to avoid inconsistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Coordinator defers conflicting writes until partition resolution [check]
Hint: Coordinator delays conflicting writes until partition heals [check]
Common Mistakes:
2. A globally distributed application requires strong consistency for writes but must tolerate network partitions gracefully. Which replication pattern best fits this scenario?
easy
A. Primary-replica replication with asynchronous replication to replicas
B. Multi-primary replication with asynchronous conflict resolution
C. Multi-primary replication with eventual consistency and last-write-wins
D. Primary-replica replication with synchronous writes to primary

Solution

  1. Step 1: Understand consistency requirements

    Strong consistency requires writes to be serialized and acknowledged before success.

  2. Step 2: Evaluate replication patterns

    Primary-replica with synchronous writes ensures all writes go through a single primary, preserving consistency. Multi-primary with async or eventual consistency cannot guarantee strong consistency.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Primary sync writes -> strong consistency, tolerates partitions by blocking writes [check]
Hint: Strong consistency -> single primary synchronous writes [check]
Common Mistakes:
3. A microservices system needs to ensure reliable event publishing without losing messages during local transaction commits. Which component best guarantees atomicity between database writes and event emission?
easy
A. Use a distributed transaction coordinator (2PC) across services
B. Implement the Outbox Pattern with a local transaction and event relay
C. Rely on eventual consistency with periodic reconciliation jobs
D. Use a message queue with at-least-once delivery without local persistence

Solution

  1. Step 1: Identify atomicity requirement

    The system must atomically write business data and produce events without distributed transactions.

  2. Step 2: Evaluate Outbox Pattern

    Outbox Pattern writes events in the same local DB transaction, then asynchronously relays them, ensuring no message loss.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Outbox Pattern ensures atomic DB write + event emission [check]
Hint: Outbox Pattern couples DB write and event emission atomically [check]
Common Mistakes:
4. 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:
5. For a search system with highly skewed term distributions and frequent query updates, which scoring approach is better and why?
medium
A. Use classic TF-IDF because it is simpler and faster to compute
B. Use raw term frequency only to avoid overhead of inverse document frequency
C. Use BM25 because it handles term saturation and document length normalization better
D. Use a vector space model with cosine similarity ignoring term frequency

Solution

  1. Step 1: Analyze term distribution and query update needs

    Skewed term distributions cause TF-IDF to overweight rare terms excessively; frequent updates require robust scoring.

  2. Step 2: Evaluate scoring methods

    BM25 accounts for term frequency saturation and normalizes by document length, improving relevance in skewed data; TF-IDF and raw TF lack these refinements; vector space ignoring TF loses relevance signals.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    BM25 handles skew and length normalization better than TF-IDF [check]
Hint: BM25 normalizes length and term saturation better than TF-IDF [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