Distributed Key-Value Store

Dynamo-style storage

Design a key-value store spread over many machines that keeps accepting reads and writes when machines fail, in the style of Amazon's Dynamo.

Overview

A key-value store has the smallest possible interface: put(key, value) and get(key). The values are opaque blobs to the store; it does not look inside them. The difficulty is entirely in running that interface on hundreds of machines, where some are always failing, without losing data and without making clients wait.

The classic answer is Amazon's Dynamo, described in a 2007 paper. Dynamo was built so that services such as the shopping cart could always write: a customer adding an item must succeed even if disks are failing or the network is split. That one requirement drives the design: data is partitioned by consistent hashing, each key is copied to N nodes, reads and writes wait for only some of them (R and W), and replicas that disagree are reconciled later. This problem walks through those choices; the individual techniques each have their own topic, named in the sections below, so here the focus is on how they fit together.

Questions to ask first

How much data and traffic? — 100 TB of unique data; 1 million operations a second, 70% reads
How big are values? — About 1 KB on average; a hard limit such as 1 MB
Availability or consistency first? — Availability: writes must succeed during failures, and conflicts are resolved later
Must reads see the latest write? — Usually yes (R + W > N), but callers can trade that for speed
Queries beyond one key? — No: single-key operations only
One data center or several? — Several; replicas are placed across them

What you will be able to do

Partition keys with consistent hashing and virtual nodes, and say how much data moves when a node joins.
Choose N, R and W for a workload and explain what R + W > N does and does not guarantee.
Keep writes available through failures with a sloppy quorum and hinted handoff, and repair replicas afterwards.
Detect conflicting versions with vector clocks and explain who resolves them.
Contrast this leaderless design with a leader-based one such as Amazon DynamoDB.

Key concepts

Consistent hashing
Virtual nodes
Preference list
Quorums (N, R, W)
Sloppy quorum
Hinted handoff
Vector clocks
Read repair
Merkle-tree anti-entropy
Gossip membership

Functional requirements

put(key, value, context): store a value; the context carries the version the client last read
get(key): return the value, or several conflicting versions plus a context
delete(key): remove a key (written as a tombstone)
Per-request choice of how many replicas must answer
Optional time to live on a key

Non-functional requirements

Writes stay available when nodes fail or the network splits
p99.9 latency under 10 ms for single-key operations inside one region (a target we chose)
No acknowledged write is lost while fewer than W replicas have failed permanently
Adding a node moves only its share of the data, while the store stays online
No single point of failure: no master, every node runs the same code

Interview questions

How do you partition the data, and what happens when a node joins?
Explain N, R and W. What do you choose?
How do you keep accepting writes when replicas are down?
Two clients update the same key during a partition. What happens?
How do replicas that drifted apart get back in sync?
How do nodes know who is in the cluster and who is down?
How is this different from DynamoDB or a Raft-based store?
What does each node store on disk, and how do deletes work?