Distributed Key-Value Store

Introduction

In 2007, Amazon published the Dynamo paper. The company had built a shopping cart service and kept running into the same problem: a relational database, no matter how well tuned, eventually became the bottleneck. Worse, the database’s strong consistency guarantee meant that a network partition — a routine event at Amazon’s scale — could take the entire cart service down. The paper described a different trade: give up strong consistency, accept eventual consistency, and in return get a system that stays available even when nodes fail and network partitions occur. Dynamo became the blueprint for a generation of distributed key-value stores.

The distributed key-value store is the foundational read/write primitive of large-scale systems. Understanding how it works — and what it costs — is prerequisite knowledge for every other system in this book.

The Problem

Store billions of key-value pairs across hundreds of servers. Support reads and writes at hundreds of thousands of operations per second. Tolerate individual server failures without downtime. Distribute data automatically without manual shard assignment. Scale horizontally by adding nodes.

The constraints are fundamental: no single server can hold all the data, no single server can handle all the traffic, and any server can fail at any time.

Naive Approach and Why It Fails

The naive approach is a hash table: node = hash(key) % N where N is the number of nodes. This works until a node is added or removed. When N changes, almost every key maps to a different node. All cached data is invalid simultaneously. All clients must be updated. The system experiences a thundering herd as all clients reload from the database.

This is the modulo problem: simple hash-based distribution is not resilient to topology changes. At scale, topology changes are routine — nodes fail, capacity is added, hardware is replaced. An algorithm that invalidates the entire key space on every topology change is unusable.

Architecture Walkthrough

Consistent Hashing

Place all nodes on a circular hash ring. Each node owns a range of the hash space. Keys map to the ring by their hash value and are assigned to the first node clockwise from that position.

When a node is added or removed, only the keys in the adjacent range on the ring are reassigned. Adding a node with hash position 200 between Node A and Node B transfers only the keys in range [100, 200] — not the entire key space.

Virtual nodes solve hotspotting: each physical node is assigned multiple positions on the ring (typically 100–200 virtual nodes). This distributes load more uniformly and prevents a single node from owning a disproportionate slice of the ring.

Replication

Each key is stored on N nodes — the node that owns the key plus the next N-1 nodes clockwise on the ring. With N=3, any key survives the simultaneous failure of two of its three owners.

Quorum Reads and Writes

Consistency is tunable via the quorum formula: a read or write is considered successful when R read replicas and W write replicas respond, where R + W > N guarantees that at least one node has the latest write.

N = 3 (replication factor)
W = 2 (write quorum)
R = 2 (read quorum)
R + W = 4 > N = 3 → strong consistency

W = 1, R = 1 → eventual consistency, lowest latency
W = 3, R = 1 → strongly consistent reads, slow writes
W = 1, R = 3 → strongly consistent reads, fast writes

Low quorum values prioritise availability and latency. High quorum values prioritise consistency. The choice is AT1 (Consistency/Availability).

Gossip Protocol

Nodes maintain cluster membership through gossip: each node periodically contacts a random peer and exchanges state. Membership changes (nodes joining or leaving) propagate through the cluster in O(log N) rounds. No central coordinator is required.

Gossip propagation:
Round 1: Node A tells Node B [A joined]
Round 2: Node B tells Node C [A joined, B knows]
Round 3: Node C tells Node D [all three know]
...
O(log N) rounds to reach all N nodes

Conflict Resolution

With asynchronous replication, two clients can write to the same key concurrently. Conflict resolution strategies: last-write-wins (LWW) using wall clock timestamps (simple, loses updates), vector clocks (tracks causal ordering, complex), or application-level merge (most flexible, requires client logic). Dynamo uses vector clocks with application-level conflict resolution for the shopping cart — a cart merge is semantically meaningful.

Data Flow

Key Design Decisions

AT1 — Consistency/Availability: The quorum parameters W and R are runtime-configurable in Cassandra and DynamoDB. This is not a build-time choice — it is a per-operation choice. Critical operations (payment confirmation) use high quorums. High-throughput operations (view count updates) use low quorums.

AT5 — Centralisation/Distribution: Gossip-based membership eliminates the central coordinator — a SPOF (FM1). Every node can serve any request. The coordinator role is assumed by whichever node receives the request, not by a designated master.

AT9 — Correctness/Performance: Vector clocks are more correct than last-write-wins but more expensive to propagate and reason about. Most production systems accept LWW for non-critical data and use application-level logic only where correctness matters.

Failure Modes in This System

FM12 — Split-Brain: When a network partition separates nodes into two groups, each group may accept writes to the same key. When the partition heals, both versions exist. Split-brain is not a failure that can be fully prevented — it is an inherent consequence of the Consistency/Availability tradeoff. The mitigation is detecting it (vector clocks surface conflicts) and resolving it deterministically.

FM6 — Hotspotting: Virtual nodes mitigate but do not eliminate hotspotting. A key accessed by millions of clients simultaneously — a trending topic, a celebrity’s profile — concentrates load on the nodes that own that key regardless of ring distribution. Application-level caching or request deduplication is the mitigation.

FM4 — Data Consistency Failure: Eventual consistency means reads can return stale data. If an application assumes consistency where the storage layer provides only eventual consistency, it will produce incorrect results. Every eventual consistency deployment requires explicit staleness bounds and client-side handling of stale reads.

How It Evolves at Scale

At 10×: the ring has more nodes. Virtual node count increases to maintain uniform distribution. Quorum sizes may decrease to maintain acceptable write latency as the cluster grows.

At 100×: geographic distribution becomes necessary. Multi-region replication introduces cross-region latency into the quorum path. Strong consistency across regions requires W and R values that span regions — adding 50–100ms to every write. Most systems relax to per-region consistency with async cross-region replication.

The evolution path is: single cluster → multi-rack cluster → multi-data-centre cluster → multi-region cluster. Each step increases the consistency/latency tradeoff.

Real-World Variants

Amazon DynamoDB provides tunable consistency per read (eventually consistent or strongly consistent). It adds automatic partitioning, DAX (a dedicated caching layer), and global tables for multi-region replication. The operational complexity of Dynamo is hidden behind a managed service API.

Apache Cassandra exposes the quorum parameters directly. It uses leaderless replication (no primary node) and LWW by default. It excels at write-heavy workloads and time-series data. Read performance requires careful data modelling — secondary indexes are costly.

Redis Cluster uses a different sharding approach: 16,384 hash slots, each assigned to a primary node. Clients maintain a routing table and contact the correct primary directly. It provides strong consistency within a single shard but no cross-shard transactions. Suitable for caching and session storage, not general-purpose distributed storage.

Exercises