Amazon DynamoDB Architecture

Dynamo maps keys to nodes using consistent hashing on a virtual ring. Each physical node owns multiple positions on the ring (virtual nodes or vnodes), typically 150–256 per node. When a node joins or leaves, only keys in adjacent ring positions are affected — roughly 1/N of all keys rather than the complete redistribution required by simple modulo hashing. Virtual nodes also solve the hotspot problem: a powerful machine gets more vnodes, receiving proportionally more data. The ring is the foundational abstraction that makes Dynamo horizontally scalable.

Dynamo uses a sloppy quorum system with parameters (N, R, W): each key is replicated to N nodes, reads require R responses, and writes require W acknowledgments. The consistency level is tunable per operation — setting W=1 gives maximum write availability, while R+W>N provides strong consistency. During node failures, hinted handoff allows writes to be temporarily stored on a healthy neighbor node with a 'hint' indicating the intended recipient. When the failed node recovers, hints are replayed to restore the correct replica placement.

Since Dynamo allows concurrent writes to succeed (availability over consistency), conflicts are inevitable. Vector clocks track the causal history of each write — each node increments its own counter on every update, producing a version vector like [(A,1), (B,2), (C,1)]. If two versions have incomparable vector clocks (neither dominates the other), both are preserved and returned to the application on the next read. The application then resolves the conflict using domain-specific logic — Amazon's shopping cart uses union merge so items are never silently lost.

Dynamo nodes discover each other and detect failures using a gossip protocol. Every second, each node picks a random peer and exchanges its membership list — a table of (node_id, heartbeat_counter, timestamp). If a node's heartbeat hasn't been updated within a timeout, it's marked as suspected failed. Gossip is eventually consistent — membership changes propagate across the cluster in O(log N) rounds. This decentralized approach avoids a single point of failure that a centralized coordinator like ZooKeeper would introduce.

Over time, replicas can diverge due to missed hinted handoffs or partial failures. Dynamo uses Merkle trees (hash trees) per key range to efficiently detect inconsistencies. Each leaf is a hash of a key-value pair; internal nodes are hashes of their children. Two nodes compare root hashes — if they match, all data is consistent. If they differ, they traverse the tree to find exactly which key ranges diverge, minimizing the data transferred for synchronization. This makes full-cluster repair feasible even at Amazon's scale.