--- title: Storage System Instances url: https://doc.liz6.com/en/distributed-systems/06-distributed-storage/03-storage-system-instances locale: en area: distributed-systems tags: - Dynamo - Spanner - leaderless - leader-based - consistent hashing - virtual nodes - gossip - quorum - Merkle tree - vector clock - eventual consistency - TrueTime - external consistency - Paxos - 2PC - GPS + atomic clock - commit wait - ε - always writeable - timestamp ordering - distributed-systems - distributed-storage date: 2026-06-30 modified: 2026-07-16 description: Dynamo (leaderless + gossip + quorum) and Spanner (leader-based + TrueTime + Paxos + 2PC) represent the two poles of distributed storage. This article combines the consensus, replication, partitioning, and membership discovery concepts discussed in the first five chapters into two complete system architectures. --- # Storage System Instances > Dynamo (leaderless + gossip + quorum) and Spanner (leader-based + TrueTime + Paxos + 2PC) represent the two poles of distributed storage. This article combines the consensus, replication, partitioning, and membership discovery concepts discussed in the first five chapters into two complete system architectures. ## Overview The previous five chapters covered [consensus](/distributed-systems/02-consensus-protocols/01-Raft.md), [replication](/distributed-systems/03-replication-and-consistency/01-replication-strategies.md), [partitioning](/distributed-systems/04-partitioning-and-routing/01-consistent-hashing.md), [membership discovery](/distributed-systems/05-members-and-discovery/02-gossip-protocol.md), and [read/write paths and repair](/distributed-systems/06-distributed-storage/01-distributed-read-write-path.md). These are not isolated concepts; in real-world distributed storage systems, they **operate simultaneously and interlock**. This article selects two classic systems to assemble the previous components into a complete vehicle: Dynamo (the leaderless + gossip + quorum path) and Spanner (the leader-based + TrueTime + external consistency path). These two systems represent the two poles of distributed storage; understanding them clarifies why each preceding chapter was structured as it was. ## Dynamo: A Puzzle Prioritizing Availability Amazon's 2007 Dynamo paper laid the foundation for the entire leaderless + eventual consistency path (Riak, Cassandra, and DynamoDB all descend from it). Its architecture is a **combination** of several independent mechanisms, each of which has been discussed individually in previous chapters—putting them together constitutes Dynamo: | Layer | Dynamo's Approach | Corresponding Previous Chapter | |----|--------------|-------------| | Partitioning | Consistent hashing; each node is responsible for a segment of the token range; introduces **virtual nodes** (~100 vnodes per physical node) for more uniform load distribution | [Consistent Hashing](/distributed-systems/04-partitioning-and-routing/01-consistent-hashing.md) | | Replication | After writing data to the coordinator, it writes to N successors in a clockwise direction (physical nodes where vnodes reside), ensuring replicas are distributed across different physical nodes | [Replication Strategy: Leaderless](/distributed-systems/03-replication-and-consistency/01-replication-strategies.md) | | Write | The coordinator writes to N replicas concurrently and returns once W ACKs are received; when W < N, some replicas are temporarily inconsistent | [Distributed Read/Write Paths](/distributed-systems/06-distributed-storage/01-distributed-read-write-path.md) | | Read | The coordinator reads from N replicas concurrently, waits for R responses, and takes the version with the latest timestamp (comparing vector clocks, not wall-clock timestamps); triggers read repair to asynchronously push the latest version to lagging replicas | Same as above | | Membership Discovery | Gossip protocol propagates node join/leave/heartbeat information, eventually ensuring every node has a complete routing table | [Gossip Protocol](/distributed-systems/05-members-and-discovery/02-gossip-protocol.md) | | Anti-Entropy | Background Merkle tree comparison, with gossip-driven repair | [Anti-Entropy and Data Repair](/distributed-systems/06-distributed-storage/02-anti-entropy-and-data-repair.md) | | Conflict Resolution | Vector clocks track causality; the application merges conflicts during reads (e.g., shopping cart: merge items from different replicas, do not lose data) | [Conflict Resolution](/distributed-systems/03-replication-and-consistency/02-conflict-resolution.md) | | Hinted Handoff | When the target node is unreachable, the coordinator temporarily stores its portion in its own hints area and replays it once the target recovers | [Distributed Read/Write Paths: Hint Section](/distributed-systems/06-distributed-storage/01-distributed-read-write-path.md) | When these layers interlock, two global constraints run through the entire stack: - **Always writeable**—even if some nodes are unreachable, the coordinator accepts writes (hinted handoff + sloppy quorum ensures W is met), at the cost of more frequent conflicts. - **Eventual consistency**—data eventually converges, but within the window before convergence, different reads may see different versions. The application layer must handle this (Dynamo pushes conflict resolution to the application layer, which is the core of its design philosophy: the storage layer does not make conflict decisions for the application). ### A Complete Write Journey in Dynamo (Connecting All Layers) A Complete Write Journey in Dynamo: Concurrent Write to Three Replicas, Returns as Soon as W=2 is Met put("cart:alice", {item:"book"}) Coordinator (Any Node) Has full cluster routing table (obtained via gossip propagation) hash("cart:alice") → token falls in range [A, B] Check routing table: N=3 vnodes are on physical nodes P1, P3, P7 P1, P3: Concurrent Write Success append WAL → fsync → write MemTable → ACK (version v5) P7: Unreachable Coordinator writes this to the local hinted handoff area for temporary storage W=2 ACK Received → Return SUCCESS (Background Async) Next gossip anti-entropy trigger → Merkle tree comparison finds P7 missing → Fills gap Always Writeable: P7 being temporarily unreachable does not affect writing; hinted handoff + sloppy quorum ensures W is still met; The cost is brief inconsistency—convergence relies on background anti-entropy, not on making all replicas consistent immediately during this write. ## Spanner: A Puzzle for External Consistency Google Spanner (2012) chose another path: **strong leader + external consistency**, supporting Google's advertising and F1 databases. It is also a combination of various mechanisms, but the goal is completely opposite—**willing to sacrifice availability to ensure "single-machine-like" transaction semantics**. | Layer | Spanner's Approach | Corresponding Previous Chapter | |----|---------------|-------------| | Partitioning | Range sharding; keys are split into tablets lexicographically; each tablet is a Paxos group | [Sharding Strategy](/distributed-systems/04-partitioning-and-routing/02-sharding-strategies.md) | | Consensus | Each tablet is internally a **Paxos group** (multi-replica, Paxos elects leader and replicates log) | [Paxos](/distributed-systems/02-consensus-protocols/02-Paxos.md) | | Replication | Paxos log replicated to majority within the group; all writes must go through the leader; reads can come from followers (but require **read transaction timestamps**) | [Replication Strategy: Single-Leader](/distributed-systems/03-replication-and-consistency/01-replication-strategies.md) | | Transaction | Cross-tablet writes use **2PC** (Two-Phase Commit); the coordinator is one of the Paxos leaders; commit timestamps are assigned by **TrueTime** | [Distributed Transactions](/distributed-systems/03-replication-and-consistency/03-distributed-transactions.md) | | Time | **TrueTime**: Each data center has GPS + atomic clock synchronization, ensuring global clock offset ≤ ε (~7ms). Assigns each transaction a timestamp "later than all committed transactions" to achieve external consistency | [Time and Clocks](/distributed-systems/01-basic-theory/02-time-and-clocks.md) | Spanner's core innovation is the combination of **TrueTime + 2PC + Paxos**, achieving **external consistency**—transactions are globally ordered by commit timestamp, and any read can see all writes that occurred before it. This is completely opposite to Dynamo's "eventual convergence, reads may see stale data." ### A Spanner Cross-Table Transaction (Connecting All Layers) ``` BEGIN UPDATE users SET balance = balance - 100 WHERE id = 42 -- In tablet A (Paxos group G1) UPDATE orders SET status = 'paid' WHERE id = 789 -- In tablet B (Paxos group G2) COMMIT Process: 1. Client → G1's Paxos leader (becomes 2PC Coordinator) 2. Coordinator: Sends prepare to leaders of G1 and G2 3. Each group's Paxos leader: Writes prepare record to Paxos log → Replicates to majority 4. All participants ACK → Coordinator selects commit timestamp: - ts = max(local times of each participant) + safety margin > TrueTime.now() + ε - This ensures ts is later than any committed transaction's timestamp (external consistency) 5. Coordinator: Writes commit record + ts to its own Paxos log → Replicates → Committed 6. Notifies participants to commit (Paxos log entry with ts) ``` Note: The `now() + ε` guarantee in step 4 ensures that because ε is the upper bound of clock deviation, the actual time "now" in all data centers cannot exceed `now() + ε`. Therefore, selecting `ts > now() + ε` ensures ts is in the future, allowing any read after ts to see this transaction. This is how Spanner provides "single-machine-like" serializable isolation for SQL—because timestamps are real, physically constrained global orders. ## Comparison of the Two Poles | | Dynamo | Spanner | |---|---|---| | Consistency | Eventual consistency | External consistency (Strong) | | Write Availability | Always (leaderless, any node can accept) | Requires leader (waits for election if leader fails) | | Conflict Resolution | Application layer (Vector clocks) | Storage layer (Global order by timestamp) | | Transactions | Does not support cross-key transactions | Full ACID (2PC + TrueTime) | | Latency | Low (No multi-round coordination) | High (Paxos + 2PC + commit wait) | | Clock Dependency | Loose (Only used for version comparison, no synchronization required) | Strict (TrueTime is a prerequisite for correctness) | | Operational Complexity | Low (No leader, nodes can fail arbitrarily) | High (GPS/atomic clock sync, leader election) | The choice between these two systems represents the **fundamental trade-off in distributed storage systems**—at any time when making a storage selection, you are essentially finding a position between the two columns of this table. ## References - **Dynamo Paper**: "Dynamo: Amazon's Highly Available Key-value Store" (DeCandia 2007) — The source of all leaderless systems - **Spanner Paper**: "Spanner: Google's Globally-Distributed Database" (Corbett 2012) — TrueTime + External Consistency *Keywords: Dynamo, Spanner, leaderless, leader-based, consistent hashing, virtual nodes, gossip, quorum, Merkle tree, vector clock, eventual consistency, TrueTime, external consistency, Paxos, 2PC, GPS + atomic clock, commit wait, ε, always writeable, timestamp ordering*