Katkat
Back

Design a Distributed Key-Value Store

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

Tests your ability to architect a highly available, horizontally scalable distributed key-value store, evaluating core concepts including consistent hashing, tunable quorum consistency, storage engine trade-offs, and failure recovery.

Scenario

Design a distributed key-value storage service (similar to Amazon DynamoDB or Apache Cassandra) to serve as the foundational persistence layer for cloud-scale applications. The service must scale horizontally across hundreds of commodity servers while maintaining predictable low latency and high availability.

Requirements

Functional Requirements

  • put(key, value): Insert or update the value associated with a string key.
  • get(key): Retrieve the latest value associated with a key.
  • delete(key): Remove a key-value pair.

Non-Functional Requirements

  • High Availability: The system should favor availability over strict consistency during network partitions (AP under CAP theorem), with configurable consistency levels.
  • Low Latency: Sub-10ms p99 latency for reads and writes.
  • Horizontal Scalability: Seamlessly scale out to support data growth and higher throughput without downtime.
  • Durability & Fault Tolerance: No data loss upon single or multi-node crashes.

Scale & Traffic Assumptions

  • Total storage: 50 TB initial capacity, scalable to petabytes.
  • Total throughput: 500,000 requests/second (80% read, 20% write).
  • Average key size: 64 bytes; average value size: 1 KB (max 1 MB).

What Your Design Should Cover

  1. API & Interface: Clear definitions for client-facing operations and protocol choices.
  2. Data Partitioning: Key distribution strategy across nodes (e.g., consistent hashing, virtual nodes) to avoid hot spots and handle topology changes.
  3. Replication & Consistency: Replication factor, replication topology, and quorum mechanics (N, R, W). Explain how read repair and hinted handoff work.
  4. Storage Engine Architecture: Per-node internal design (e.g., Log-Structured Merge-tree vs. B-tree, Write-Ahead Log, MemTable, SSTables, Bloom filters).
  5. Conflict Resolution & Failure Handling: Gossip protocol for membership and failure detection, Merkle trees for anti-entropy, and conflict resolution mechanisms (e.g., vector clocks or Last-Write-Wins).

Hints

Hint 1

Use consistent hashing with virtual nodes to distribute keys uniformly and minimize data migration when cluster nodes are added or removed.

Hint 2

Formulate your replication model around tunable quorum parameters (N, R, W) to allow clients to trade off strong consistency against latency.

Hint 3

For node-level persistence, consider an LSM-tree architecture to achieve high write throughput while leveraging Bloom filters to optimize read performance.

Follow-up questions

  • How does the system handle concurrent updates to the same key during a network partition, and what are the trade-offs between Last-Write-Wins (LWW) and Vector Clocks?
  • If a replica node experiences a transient network outage lasting several minutes, how does the system ensure durability without immediately triggering expensive full-range rebalancing?
  • How would you extend this design to support secondary indexes or multi-key atomic transactions across partitions?