存储系统实例

分布式存储不是把一致性哈希、Paxos、Gossip 等名词放在同一张图上。每种机制都有明确职责，系统的保证来自它们如何配合。本文比较 2007 年 Dynamo 与 2012 年 Spanner 论文的设计问题，理解它们为什么选择不同组合。

这里的 Dynamo 指论文中的内部系统，不等同于当前 DynamoDB 产品；Spanner 的论文机制也不代替当前服务版本和隔离级别文档。先读 分布式读写路径，可以更容易区分下文的复制与事务层。

从业务不变量开始比较

设有两类业务：购物车希望部分节点故障时仍能接受编辑，账户转账希望扣款与入账共同成立。第一类可能接受冲突后合并，第二类通常不能接受“先都成功，以后再决定钱从哪里来”。

这只是用于理解的业务模型，不意味着某个产品只能承载其中一类。真正的问题是：哪些操作可以独立接收，哪些操作需要在确认前协调；出现冲突后，谁有能力给出正确合并规则。

Dynamo：把并发版本留给后续协调

论文中的 Dynamo 使用 key-value 接口，通过分区与副本选择分散数据，读写等待可配置数量的响应；节点暂不可达时可以借助临时承接与提示回放。多个副本可能同时接受更新，因此对象版本和应用辅助冲突解决是架构的一部分。Dynamo 原论文 是这些机制的依据。

向量时钟不是一个可以对所有版本排序的整数。若版本 A 覆盖 B，可以认为 B 的历史已被包含；若 A、B 并发，就必须保留冲突或执行合并。将“比较向量时钟”简写成“取最大的最新版”，会漏掉这套设计最重要的分支。

购物车合并可以举一个简单例子：客户端甲新增一本书，客户端乙新增一支笔，并集能保留两次新增；若乙的操作是删除书，并集却可能恢复被删条目。业务若要求删除优先，需要保留删除与因果信息，而不是只合并当前集合。版本检测不等于业务冲突已经解决。

“高可用”仍受可达节点数、存储容量、故障域和恢复条件限制。所有候选节点都不可达时，没有机制能凭空存储数据。无主也不代表运维简单，修复积压与冲突状态同样需要管理。

合并值以后，还要合并“看过哪些版本”的上下文

初始购物车有书，版本向量为 (A=1,B=0)。两个客户端都从这个版本出发：经 A 处理的更新增加笔，成为 (2,0)；经 B 处理的更新删除书，成为 (1,1)。一个在 A 分量更大，一个在 B 分量更大，互不覆盖。

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"}  # 并集会恢复被删除的书

context = tuple(max(x, y) for x, y in zip(left, right))
merged_write = (context[0] + 1, context[1])  # 经 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)

模型固定 A、B 两个分量，并假设协调节点为新写增加自己的计数，没有涉及向量截断或节点替换。若业务把合并后的值写回，却只携带左分支上下文，新版本 (3,0) 仍与右分支 (1,1) 并发，下一次读仍可能得到 sibling。合并值与合并因果上下文因此是两项工作。

这里没有替业务决定书应不应该存在。要实现删除优先，需要保留操作或删除的因果信息，并制定相应规则；把向量合并正确不等于把购物车合并正确。Dynamo 原论文第 4.1、4.4 节把读取的 context 带回后续 put，正是为了表达更新依赖的版本历史。接口与版本机制原文

Spanner：复制、事务与时间分别负责什么

Spanner 的关键在于区分三种协调：副本间确定持久操作顺序，多个数据分片共同决定事务结果，以及将事务顺序与外部观察到的时间顺序联系起来。经典设计使用 Paxos、两阶段提交和 TrueTime，各自解决不同问题。

经典跨组写事务中，参与组先准备并持久化必要状态，协调者确定提交决定和时间戳；事务还需要满足提交等待条件。日志复制与等待可以有重叠，不能机械地把所有阶段当成严格串行的固定 RTT 总和。详细协议见 Spanner 论文。

TrueTime 的关键是显式不确定区间

普通时钟 API 给出一个数，容易让调用者假装它就是精确真实时间。TrueTime 返回包含真实时间的不确定区间 [earliest, latest]。区间宽度可变化，某次测得几毫秒不意味着所有环境都有固定误差常数。

若提交时间戳为 s，只选择“足够大的时间戳”还不够。返回成功前需要等待到可以确定真实时间已经越过 s，例如满足 TT.now().earliest > s。这样，当另一个事务在观察到本事务完成之后再开始，其时间戳选择才可以与先前完成顺序相容。

把时间戳选到未来却立即返回，会留下问题：另一个节点可能随后开始操作，但它的时间区间仍落在先前时间戳之前。commit wait 正是在消除这个不确定窗口。区间越宽，可能需要等得越久；时钟基础设施因此同时影响正确性前提与延迟。

±5 ms 的不确定性，为什么可能需要越过 10 ms

做一个有意简化的算例：真实时间为 t，某节点始终返回 [t−5,t+5]，单位为毫秒。在 t=100 时取提交时间戳 s=105，并假设参与者准备时间等其他约束不要求更大的 s。等待条件是 t−5>105，因此必须等到 t>110；不是从 100 再等 5 ms 就够了。

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  # 相等仍不满足严格的 after
assert tt(111, 5)[0] > s

# 若 T1 在 t=100 就提前返回，随后开始的 T2 可能选到更小时间戳。
s2_without_wait = tt(101, 3)[1]
assert s2_without_wait == 104 < s

# 等到 t=111 返回，T2 在 t=112 开始，则其上界必然晚于 s。
s2_after_wait = tt(112, 3)[1]
assert s < 111 < 112 <= s2_after_wait

第二个节点的区间 [98,104] 同样包含真实时间 101，因而“各节点误差都有界”本身并不防止 105、104 这样的反序。提交等待建立的是一条可推导的链：T1 的时间戳早于 T1 返回时的真实时间；T2 在返回之后才开始，所以它随后选择的合法提交时间戳也必须更晚。

若复制从 t=100 开始、t=108 完成，在这个整数采样模型中只需再等 3 ms，通过两项条件的总时间为 11 ms，不能把复制的 8 ms 和整段时间等待的 11 ms 相加。它也不是实际 Spanner 延迟预测：真实区间会变化，时间戳可能受其他约束抬高，还存在锁、协调和应用等阶段。论文说明了 commit wait 与 Paxos 通信可重叠的设计。Spanner 提交协议

区间上界选好以后，为什么还要等？

把“从选时间戳开始等多久”和“复制完成后还要等多久”放在同一时间轴上。下图在 t=100 取 s=100+ε，earliest=t−ε，因此时间条件要求 Δt>2ε。整数毫秒采样下首个满足时刻是 2ε+1 ms；它与复制耗时取较大值，而不是相加。这个等式来自固定对称误差模型，不能当作真实系统的固定延迟。

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

外部一致性与快照读

外部一致性要求事务表现为一个串行执行，并尊重外界已经观察到的先后关系。若 T1 完成后 T2 才开始，不能让读者观察到等价于 T2 在 T1 之前的事务顺序。并发重叠事务则由系统确定一个合法顺序。

MVCC 允许选择历史时间戳读取一致快照。历史读返回旧状态是其明确语义，不等于副本随机滞后造成的不一致；强读与历史读也不能混为一个承诺。当前 Spanner 的外部一致性说明与隔离级别适用范围见 TrueTime and External Consistency。

如何比较，而不把系统压成两列标签

与其写“Dynamo 快、Spanner 慢”，更有意义的比较是：

• 操作跨几个 key、分区或地域，需要经过哪些协调边界。
• 成功响应前确认了哪些副本、事务状态和时间条件。
• 允许什么并发冲突，合并由谁负责，哪些业务不变量不能暂时打破。
• 故障时哪些读写仍可继续，恢复后如何处理临时版本和落后副本。
• 客户端是否能显式选择陈旧读、事务隔离与地理放置。

延迟取决于副本距离、负载和协议路径，运维成本取决于修复、容量、升级与故障处理。两篇论文提供可复用的设计思路，不是一张对所有现代数据库都成立的性能排名表。

参考

• Dynamo，SOSP 2007
• Spanner 论文及扩展版本
• Spanner：TrueTime 与外部一致性
• 反熵与数据修复
• 时间与时钟

关键词：Dynamo、Spanner、并发版本、Paxos、2PC、MVCC、TrueTime、commit wait、外部一致性