Design a Key-Value Store
A key-value store is a non-relational database where every value is reached by a unique key, e.g. "last_logged_in_at" → "2023-07-01 10:20". It supports two operations: put(key, value) and get(key). Famous examples are Amazon DynamoDB, Memcached and Redis. In this chapter we design one that is distributed, highly available and scalable.
- 6.1Scope, and a single-server key-value storeRequirements Small key-value pairs: less than 10 KB each Ability to store big data High availability: responds quickly, even during…
- 6.2The CAP theoremA distributed system can't provide more than two of these three guarantees at the same time: Consistency: every client reads the same,…
- 6.3Data partition and replicationPartitioning: the data is too big for one server, so split it. The two challenges, distributing data evenly and moving as little as…
- 6.4Consistency: quorum consensus (N, W, R)Replicas must be kept in sync. Quorum consensus guarantees consistency for both reads and writes: N = number of replicas W = write quorum:…
- 6.5Inconsistency resolution: versioning and vector clocksReplication gives availability but can cause conflicts: two servers accept different writes to the same key at the same time. Versioning…
- 6.6Failure detection: the gossip protocolOne server saying "B is down" isn't enough; it might just have a bad network link. We need at least two independent sources. All-to-all…
- 6.7Handling failures: sloppy quorum, hinted handoff, data center outagesTemporary failures Strict quorum would block reads and writes when replicas are down. Instead, use a sloppy quorum: pick the first W…
- 6.8Anti-entropy with Merkle treesHow do two replicas find which data differs without comparing every key? A Merkle tree (hash tree): every non-leaf node is labeled with the…
- 6.9System architecture: the write path and the read pathPutting it all together (based on Cassandra's design): Clients talk to the store through get(key) and put(key, value) via a coordinator…