Storage System Instances

Distributed storage is not about putting terms like consistent hashing, Paxos, and Gossip on the same diagram. Each mechanism has a clear responsibility, and the system's guarantees come from how they work together. This article compares the design problems in the 2007 Dynamo paper and the 2012 Spanner paper to understand why they chose different combinations.

The Dynamo here refers to the internal system in the paper and is not equivalent to the current DynamoDB product; the mechanisms in the Spanner paper do not replace the current service version and isolation level documentation. Reading Distributed Read/Write Paths first can help distinguish the replication and transaction layers discussed below.

Start Comparing from Business Invariants

Consider two types of businesses: a shopping cart wants to accept edits even when some nodes fail, while an account transfer wants the deduction and the credit to stand together. The first type might accept merging conflicts afterward, while the second usually cannot accept "both succeed first, and decide where the money comes from later."

This is just a business model for understanding; it does not mean a product can only support one of these types. The real question is: which operations can be received independently, and which need coordination before confirmation; when conflicts occur, who has the ability to provide the correct merge rules.

Dynamo: Leaving Concurrent Versions for Subsequent Coordination

The Dynamo in the paper uses a key-value interface, dispersing data through partitioning and replica selection, with read/write operations waiting for a configurable number of responses; when nodes are temporarily unreachable, it can rely on temporary handoff and hint replay. Multiple replicas may accept updates simultaneously, so object versions and application-assisted conflict resolution are part of the architecture. The original Dynamo paper is the basis for these mechanisms.

Vector clocks are not integers that can sort all versions. If version A covers B, it can be considered that B's history is already included; if A and B are concurrent, conflicts must be kept or merged. Simplifying "comparing vector clocks" to "taking the largest latest version" misses the most important branch of this design.

A simple example of shopping cart merging: Client A adds a book, Client B adds a pen, and the union preserves both additions; if Client B's operation is to delete the book, the union might restore the deleted item. If the business requires deletion priority, it needs to retain deletion and causal information, rather than just merging the current set. Version detection does not mean business conflicts are already resolved.

"High availability" is still limited by the number of reachable nodes, storage capacity, failure domains, and recovery conditions. When all candidate nodes are unreachable, no mechanism can store data out of thin air. Leaderless does not mean simple operations; fixing backlog and conflict states also requires management.

After merging values, you must also merge the context of "which versions have been seen"

The initial shopping cart has a book, with a vector clock of (A=1, B=0). Both clients start from this version: the update processed by A adds a pen, becoming (2,0); the update processed by B deletes the book, becoming (1,1). One is larger in the A component, the other in the B component, neither covering the other.

def dominates(a, b):
    return all(x >= y for x, y in zip(a, b)) and any(x > y for x, y in zip(a, b))

base = (1, 0)
left, right = (2, 0), (1, 1)
assert dominates(left, base) and dominates(right, base)
assert not dominates(left, right) and not dominates(right, left)
left_cart, right_cart = {"book", "pen"}, set()
assert left_cart | right_cart == {"book", "pen"}  # Union restores the deleted book

context = tuple(max(x, y) for x, y in zip(left, right))
merged_write = (context[0] + 1, context[1])  # One merged write accepted by A
assert merged_write == (3, 1)
assert dominates(merged_write, left) and dominates(merged_write, right)
wrong_context_write = (left[0] + 1, left[1])
assert not dominates(wrong_context_write, right)
assert not dominates(right, wrong_context_write)

The model fixes two components, A and B, and assumes the coordinating node increments its own count for new writes, without involving vector truncation or node replacement. If the business writes the merged value back but only carries the left branch's context, the new version (3,0) is still concurrent with the right branch (1,1), and the next read might still yield a sibling. Merging values and merging causal context are therefore two separate tasks.

This does not decide whether the book should exist for the business. To implement deletion priority, you need to retain the causal information of the operation or deletion and formulate corresponding rules; correctly merging vectors does not mean correctly merging the shopping cart. Sections 4.1 and 4.4 of the original Dynamo paper bring the read context back to subsequent puts precisely to express the version history on which updates depend. Original text on interfaces and versioning mechanisms

Spanner: What Replication, Transactions, and Time Are Responsible For

The key to Spanner lies in distinguishing three types of coordination: determining the order of persistent operations between replicas, jointly deciding transaction results across multiple data shards, and linking transaction order with the time order observed externally. Classic designs use Paxos, two-phase commit, and TrueTime, each solving different problems.

In classic cross-group write transactions, participating groups prepare and persist necessary states first, and the coordinator determines the commit decision and timestamp; the transaction also needs to satisfy commit wait conditions. Log replication and waiting can overlap; you cannot mechanically treat all stages as a strict serial sum of fixed RTTs. See the Spanner paper for detailed protocols.

The Key to TrueTime is the Explicit Uncertainty Interval

A normal clock API gives a number, which easily leads callers to pretend it is exact real time. TrueTime returns an uncertainty interval [earliest, latest] containing the real time. The interval width can vary; measuring a few milliseconds at one time does not mean all environments have a fixed error constant.

If the commit timestamp is s, simply choosing a "large enough timestamp" is not enough. Before returning success, you need to wait until you can determine that real time has passed s, for example, satisfying TT.now().earliest > s. This way, when another transaction starts after observing this transaction complete, its timestamp selection can be compatible with the previous completion order.

Choosing a timestamp in the future but returning immediately leaves problems: another node might subsequently start an operation, but its time interval still falls before the previous timestamp. Commit wait is precisely to eliminate this uncertainty window. The wider the interval, the longer you might need to wait; thus, the clock infrastructure affects both correctness premises and latency.

Why might ±5 ms uncertainty require passing 10 ms?

Let's do a deliberately simplified example: real time is t, a node always returns [t−5, t+5], in milliseconds. At t=100, take commit timestamp s=105, and assume other constraints like participant preparation time do not require a larger s. The wait condition is t−5 > 105, so you must wait until t > 110; waiting just 5 ms from 100 is not enough.

def tt(real_time, epsilon):
    return real_time - epsilon, real_time + epsilon

s = tt(100, 5)[1]
assert s == 105
assert not tt(105, 5)[0] > s
assert not tt(110, 5)[0] > s  # Equality still does not satisfy strict after
assert tt(111, 5)[0] > s

# If T1 returns early at t=100, T2 starting later might pick a smaller timestamp.
s2_without_wait = tt(101, 3)[1]
assert s2_without_wait == 104 < s

# If waiting until t=111 to return, and T2 starts at t=112, its upper bound must be later than s.
s2_after_wait = tt(112, 3)[1]
assert s < 111 < 112 <= s2_after_wait

The second node's interval [98, 104] also contains real time 101, so "each node's error is bounded" itself does not prevent out-of-order timestamps like 105 and 104. Commit wait establishes a derivable chain: T1's timestamp is earlier than the real time when T1 returns; T2 starts after returning, so its subsequently selected valid commit timestamp must also be later.

If replication starts at t=100 and completes at t=108, in this integer sampling model, you only need to wait 3 ms more, with a total time of 11 ms to pass both conditions; you cannot add the 8 ms of replication to the 11 ms of total waiting time. This is also not an actual Spanner latency prediction: real intervals change, timestamps might be raised by other constraints, and there are also lock, coordination, and application stages. The paper explains the design where commit wait and Paxos communication can overlap. Spanner Commit Protocol

After selecting the interval upper bound, why wait?

Place "how long to wait from selecting the timestamp" and "how long to wait after replication completes" on the same timeline. The figure below takes s=100+ε at t=100, earliest=t−ε, so the time condition requires Δt > 2ε. Under integer millisecond sampling, the first satisfying moment is 2ε+1 ms; it takes the larger value of replication time and time waiting, not the sum. This equation comes from a fixed symmetric error model and cannot be treated as a fixed delay in real systems.

$$\Delta t_{\mathrm{return}}=\max (\Delta t_{\mathrm{replication}},2\epsilon +1\mathrm{ms})$$

External Consistency and Snapshot Reads

External consistency requires transactions to appear as if they are executed serially and respect the order observed externally. If T2 starts after T1 completes, readers should not observe a transaction order equivalent to T2 preceding T1. Concurrent overlapping transactions are assigned a valid order by the system.

MVCC allows choosing historical timestamps to read a consistent snapshot. Historical reads returning old states is their explicit semantics, not inconsistency caused by random replica lag; strong reads and historical reads cannot be mixed into a single promise. See TrueTime and External Consistency for current Spanner external consistency descriptions and isolation level applicability.

How to Compare Without Reducing Systems to Two Columns of Labels

Instead of writing "Dynamo is fast, Spanner is slow," a more meaningful comparison is:

• Across how many keys, partitions, or regions do operations need to go, and what coordination boundaries must they cross.
• Which replicas, transaction states, and time conditions are confirmed before a successful response.
• What concurrent conflicts are allowed, who is responsible for merging, and which business invariants cannot be temporarily broken.
• Which reads and writes can continue during failures, and how to handle temporary versions and lagging replicas after recovery.
• Whether the client can explicitly choose stale reads, transaction isolation, and geographic placement.

Latency depends on replica distance, load, and protocol paths; operational costs depend on repair, capacity, upgrades, and failure handling. The two papers provide reusable design ideas, not a performance ranking table that holds true for all modern databases.

References

• Dynamo, SOSP 2007
• Spanner Paper and Extended Version
• Spanner: TrueTime and External Consistency
• Anti-Entropy and Data Repair
• Time and Clocks

Keywords: Dynamo, Spanner, Concurrent Versions, Paxos, 2PC, MVCC, TrueTime, Commit Wait, External Consistency