Katkat
Back

Design a Key-Value Store, From the Single-Node Storage Engine to Replication

NVIDIASoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

A system design interview asks you to design a key-value store supporting put, get and delete. It tests how you scope consistency and durability, build a single-node storage engine, partition keys across machines, replicate data, and handle node failures, rebalancing and hot keys.

Design a key-value store: clients store a value under a key, read the value for a key, and delete keys. The round reported only the topic, so settle with the interviewer whether this is a single-machine store, a distributed one, or one that grows from the first into the second, and which guarantees it must give.

Constraints and Clarifications

  • Not given: data size, key and value sizes, read and write rates, latency targets, consistency requirements, and whether range scans are needed. Ask, or state your assumptions.

Clarifying Questions

  • Does the data fit in memory on one machine, and must it survive restarts?
  • What are typical key and value sizes, the total data size, and the read and write rates?
  • After a successful put, must every later get return the new value, or is eventual consistency acceptable?
  • Are range scans over ordered keys needed, or only point lookups?
  • Are expiry times, compare-and-set, or multi-key transactions needed?
  • During a network partition, should the store refuse some requests or accept writes on both sides?

Hints

Hint 1

Before you say "OK": Decide what must be on disk before a put is acknowledged, and how the store rebuilds its state after a crash without losing acknowledged writes.

Hint 2

Moving keys between machines: When a node is added or removed, consider how many keys your placement scheme forces to move, and what a reader sees while they are moving.

Follow-up questions

  • One key receives a large fraction of all reads. What do you do?
  • A client writes a key and immediately reads it through another replica. How do you guarantee it sees its own write?
  • Range scans become a requirement. What has to change?
  • A network partition splits the replicas of a shard two to one. What do clients on each side see?