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