第 24 章 CRDT——2011年，为什么两台断网的计算机，最后竟然可以自动合并各自的修改？标记本章已读大字阅读打印本章回到上次阅读位置交互模块加载失败。正文仍可阅读，请刷新重试。正在加载交互实验…第一季 · 人类如何驯服数据来源历史主线：2009—2011年及后续应用 · 强最终一致性、半格、G-Counter、PN-Counter、OR-Set 与协同编辑2011年，一篇论文给分布式计算提出了一个非常有吸引力的答案。论文标题是：Conflict-Free Replicated Data Types《无冲突复制数据类型》。作者是四位研究者：Marc Shapiro、Nuno Preguiça、Carlos Baquero 和 Marek Zawirski。他们分别与法国 INRIA、巴黎的研究机构以及葡萄牙的大学有研究联系。论文发表于2011年的 SSS（Stabilization, Safety, and Security of Distributed Systems）会议，并于同年7月形成公开的 INRIA 研究报告。[Carlos Baquero][dblp][EECS Berkeley]他们希望解决的问题，不是怎样让一台机器执行得更快。而是：如果多台机器可以独立修改同一个逻辑对象，而且它们暂时无法互相通信，那么网络恢复后，能否不依靠人工处理每一次冲突，就让它们自动得到相同且符合预先定义语义的结果？这听起来有些不可思议。因为我们在上一章刚刚学过：多个副本如果不及时同步，就可能看到不同版本。第十六章的 Raft 则告诉我们：如果希望多个节点对某一操作顺序达成共同决定，通常需要消息交换和共识规则。那么，CRDT 是否真的找到了一条绕开这些协调成本的道路？答案是：对于某些经过特殊设计的数据类型，可以。但关键不在于忽略冲突。而在于：提前把并发修改应该如何合并，设计到数据结构的数学规则里。第一幕：两台服务器同时修改一个数字假设我们正在开发一个游戏。系统需要统计某场活动被玩家点击的总次数。有两台服务器：A 和 B。最初计数器为0。随后，服务器之间的网络连接中断。A 独立处理了3次点击。B 独立处理了5次点击。此时：服务器 A3本地新增3次服务器 B5本地新增5次网络恢复后，正确的业务总数应该是：3+5=83+5=83+5=8这似乎很容易。直接把两个数字相加即可。但这里藏着第一个陷阱。错误方案一：取较大的数字如果使用：max(3,5)=5\max(3,5)=5max(3,5)=5最终只剩5次点击。A 的3次点击没有被完整合并进去。错误方案二：每次同步就相加第一次同步：3+5=83+5=83+5=8看起来完全正确。但是，如果网络重试，把同样的状态又传了一遍呢？接收者可能再次计算：8+5=138+5=138+5=13产生重复计数。现实网络中，消息重传和重复到达十分常见。我们不能假设一条同步消息永远只会出现一次。于是问题比想象中困难得多：我们想保留各节点的独立增量，却又不想因为重复同步把这些增量算两次。CRDT 的第一种经典解决方案，就是 G-Counter。第二幕：G-Counter——不要只保存一个总数G-Counter 的 G 是：Grow-only，只增长。它是一种只能增加、不能减少的复制计数器。但它真正特别的地方不在于只允许加法。而在于数据的内部表示。普通计数器保存：text复制代码value = 8G-Counter 则保存：每个副本各自贡献了多少次增加。假设只有 A 和 B 两个副本。内部状态是一个向量：V=[cA,cB]V=[c_A,c_B]V=[cA,cB]其中：cAc_AcA 是 A 累计执行的增加量。cBc_BcB 是 B 累计执行的增加量。查询总值时才计算：value=cA+cBvalue=c_A+c_Bvalue=cA+cB网络断开后A 本地增加3：VA=[3,0]V_A=[3,0]VA=[3,0]B 本地增加5：VB=[0,5]V_B=[0,5]VB=[0,5]注意：A 并不知道 B 的5次增加。B 也不知道 A 的3次增加。但是它们各自记录了自己负责的那一部分。网络恢复后合并时，不是直接相加两个向量。而是对每个副本自己的分量分别取最大值：merge(VA,VB)=[max(3,0),max(0,5)]merge(V_A,V_B)= [\max(3,0),\max(0,5)]merge(VA,VB)=[max(3,0),max(0,5)]结果：[3,5]\boxed{[3,5]}[3,5]再把两个分量相加：value=8\boxed{value=8}value=8这就同时保留了 A 和 B 的修改。更精彩的是：再次同步同一份状态，结果也不会变化。merge([3,5],[3,5])=[3,5]merge([3,5],[3,5])=[3,5]merge([3,5],[3,5])=[3,5]不会变成16。也不会变成13。因为每个分量保存的是某个副本的累计贡献，不是一条需要再次执行的增量指令。2011年的研究报告专门讨论了 G-Counter 的这种构造：以各副本的非负整数分量保存状态，以逐分量最大值合并，最终查询值等于各分量之和。[reed.cs.depaul.edu]这就是 CRDT 最重要的设计技巧之一：改变数据的内部表示，就可以改变合并操作的数学性质。第三幕：亲手同步两个断网的计数器现在我们来模拟真正的副本状态合并。开始时：A 的状态是 [3,0]。B 的状态是 [0,5]。它们已经分别完成了3次和5次增加，但还没有互相同步。你可以先只同步一个方向，观察为什么两个副本不会立即同时变成8。也可以重复同步同一个状态，确认计数不会被重复累加。G-Counter 双副本实验室逐分量取 max服务器 A3内部状态 [3, 0]A贡献 3 · 已知B贡献 0A 本地 +3服务器 B5内部状态 [0, 5]已知A贡献 0 · B贡献 5B 本地 +5B → A 同步A → B 同步◇两个副本暂时不同步A当前看到 3，B当前看到 5；继续双向同步可以交换各自尚未获知的贡献。↶ 重新模拟断网后的状态这就是一种典型的 State-based CRDT（基于状态的 CRDT）。同步时，我们传输的是副本所保存的状态。接收方执行合并。不需要把远端每一次 +1 操作重新执行一遍。但请注意，这并不等于两个副本时刻拥有完全相同的结果。网络断开期间，A 只能看到自己已知的贡献，B 也是如此。只有当相应的状态最终互相传播并被合并后，双方才会收敛。第四幕：三个不起眼的数学性质，为什么能够保证收敛？2011年论文最重要的贡献之一，是把各种具体数据结构背后共同的数学规律整理出来。对于基于状态的 CRDT，一类经典的充分条件是：副本状态组成一个带有偏序关系的连接半格（Join-Semilattice）。合并操作计算两个状态的最小上界（Least Upper Bound）。同时，本地更新需要沿着偏序单调前进。听起来比较抽象。我们先不讨论完整的格论，而是研究刚才的合并运算：x⊔y=max(x,y)x\sqcup y=\max(x,y)x⊔y=max(x,y)在两个整数分量上分别执行。它有三个非常漂亮的性质。1. 交换律（Commutativity）x⊔y=y⊔x\boxed{x\sqcup y=y\sqcup x}x⊔y=y⊔x例如：max(3,5)=max(5,3)\max(3,5)=\max(5,3)max(3,5)=max(5,3)这意味着：先收到 A 的状态，还是先收到 B 的状态，最终不应该影响合并结果。2. 结合律（Associativity）(x⊔y)⊔z=x⊔(y⊔z)\boxed{(x\sqcup y)\sqcup z=x\sqcup(y\sqcup z)}(x⊔y)⊔z=x⊔(y⊔z)这意味着：先合并 A、B，再合并 C。和先合并 B、C，再合并 A。最终结果相同。当系统拥有几十台服务器时，这项性质尤其重要。因为我们不可能保证每个副本按照完全相同的分组和顺序进行同步。3. 幂等性（Idempotence）x⊔x=x\boxed{x\sqcup x=x}x⊔x=x这是应对重复消息最重要的性质。同一份状态即使被接收10次，也不会让结果额外增加10倍。三项性质分别解决什么问题？数学性质系统中的价值交换律消息到达顺序可以不同结合律合并过程可以分批、分组进行幂等性重复同步不会重复计算同一份状态但只有写下这三个等式，还不能无条件推出任何数据结构都是正确的 CRDT。真正的状态式 CRDT 还需要保证其状态更新的单调性，以及合并操作与状态偏序的对应关系。对于 G-Counter：[2,0]≤[3,0][2,0]\leq[3,0][2,0]≤[3,0]因为两个分量都没有减少。[3,0]≤[3,5][3,0]\leq[3,5][3,0]≤[3,5]也成立。但：[3,0][3,0][3,0]与：[0,5][0,5][0,5]并不是谁大于谁。它们是偏序中两个不可比较的状态。合并得到：[3,5][3,5][3,5]这个结果同时包含了两者已知的信息。因此，我们可以把合并理解为：寻找一个至少包含两边全部已记录贡献的最小共同状态。Shapiro 等人的原始论文正式给出了这种基于单调半格和最小上界的收敛条件，并证明在更新最终送达、相应执行能够完成的假设下，满足条件的状态式对象可以实现强最终一致性。[perso.lip6.fr]第五幕：什么叫“强最终一致性”？上一章，我们学习过 Eventual Consistency，即最终一致性。其直观保证是：如果停止产生新更新，并且复制过程最终能够推进，那么各副本终将收敛。2011年的 CRDT 研究则把一种更明确的性质称为：Strong Eventual Consistency（SEC），强最终一致性。其中非常重要的一点是：已经接收了相同更新集合的正确副本，应当具有等价的可观察状态。注意，它不是说：“不同副本必须在同一毫秒看到同一个数。”而是说：一旦它们最终得到了相同的相关更新信息，合并规则就不应该因为消息到达顺序不同而留下永久分歧。对于 G-Counter：A先收到B。还是B先收到A。状态先合并3次还是5次。都不会改变共同的最终结果。但这个保证依赖一定的假设。例如：正确副本最终能够交换必要信息。更新不会被永久遗失而完全无法恢复。副本状态没有发生不可恢复的损坏。运行时遵守 CRDT 所规定的规则。因此，不能把 SEC 理解为：“即使服务器磁盘全部损坏、消息永远无法传递，数据也会凭空恢复。”CRDT 不是魔法。它只是把某些原本需要协调才能安全合并的状态变化，转化为具有严格数学收敛规则的操作。第六幕：PN-Counter——如果我们还需要减少计数，怎么办？G-Counter 有一个明显限制。它只能增加。假设我们要统计：当前在线玩家人数。玩家上线，计数加1。玩家离线，计数减1。那么，G-Counter 就不够用了。你可能想到：“把某个副本的分量直接减1不就行了？”但这会破坏它的合并规则。例如，A 当前贡献5。之后减少2，变成3。而 B 还保存着旧状态5。两者再次执行：max(3,5)=5\max(3,5)=5max(3,5)=5刚才的减少就被旧状态覆盖了。这是因为我们原本规定每个分量只能单调增加。一个巧妙的解决方案：把加法与减法分开记录PN-Counter 中：P 代表 Positive。N 代表 Negative。我们不直接减少原来的计数分量。而是维护两组只能增加的计数器。一组记录累积增加量。一组记录累积减少量。最终可见值为：value=∑P−∑N\boxed{value=\sum P-\sum N}value=∑P−∑N假设 A、B 各有一个分量。A 增加10：PA=[10,0]P_A=[10,0]PA=[10,0]B 增加5：PB=[0,5]P_B=[0,5]PB=[0,5]随后 A 减少3：NA=[3,0]N_A=[3,0]NA=[3,0]B 减少2：NB=[0,2]N_B=[0,2]NB=[0,2]合并后：P=[10,5]P=[10,5]P=[10,5]N=[3,2]N=[3,2]N=[3,2]于是：value=(10+5)−(3+2)=10value=(10+5)-(3+2)=10value=(10+5)−(3+2)=10更重要的是，即使可见值从15下降到10，内部的 P、N 分量仍然只会增加。因此可以继续使用逐分量 max 进行状态合并。Shapiro 等人的2011年论文也专门用两组只增计数器构造这种支持递增与递减的计数器。[perso.lip6.fr]可见值下降，并不违反“状态单调”这是理解 CRDT 时最容易出现的误解之一。在 G-Counter 中，内部状态和可见数值都只能增长。但在 PN-Counter 中：内部的 P、N 累计状态仍然单调前进。然而查询结果：∑P−∑N\sum P-\sum N∑P−∑N可以上升，也可以下降。所以，CRDT 要求的单调性并不是：“用户看到的每一个数字都永远只能增加。”而是：它所依赖的内部状态，应按照定义好的信息偏序单调演进。第七幕：用 Python 实现能够断网同步的计数器现在我们真正写出一个简化的状态式 CRDT。首先实现只增计数器。python复制代码class GCounter: def __init__(self, replica_id, replica_ids): self.replica_id = replica_id self.counts = { rid: 0 for rid in replica_ids } def increment(self, amount=1): if amount < 0: raise ValueError("GCounter cannot decrement") self.counts[self.replica_id] += amount def merge(self, other): if self.counts.keys() != other.counts.keys(): raise ValueError("Replica sets differ") for rid in self.counts: self.counts[rid] = max( self.counts[rid], other.counts[rid], ) @property def value(self): return sum(self.counts.values())测试断网后同步：python复制代码a = GCounter("A", ("A", "B")) b = GCounter("B", ("A", "B")) # 模拟网络断开 a.increment(3) b.increment(5) print(a.value, b.value) # 3 5 # 恢复通信 a.merge(b) b.merge(a) print(a.value, b.value) # 8 8 # 重复同步 a.merge(b) b.merge(a) print(a.value, b.value) # 8 8这段代码已经具备一个状态式 G-Counter 的核心行为。它不会因为重复合并相同状态而重复计算已经包含的增量。在 G-Counter 基础上实现 PN-Counterpython复制代码class PNCounter: def __init__(self, replica_id, replica_ids): self.positive = GCounter( replica_id, replica_ids ) self.negative = GCounter( replica_id, replica_ids ) def increment(self, amount=1): self.positive.increment(amount) def decrement(self, amount=1): self.negative.increment(amount) def merge(self, other): self.positive.merge(other.positive) self.negative.merge(other.negative) @property def value(self): return ( self.positive.value - self.negative.value )使用：python复制代码a = PNCounter("A", ("A", "B")) b = PNCounter("B", ("A", "B")) a.increment(10) b.increment(5) a.decrement(3) b.decrement(2) print(a.value, b.value) # 7 3 a.merge(b) b.merge(a) print(a.value, b.value) # 10 10注意，中间出现的：7 和 3并不代表算法错误。它们只是两个副本在尚未交换全部更新时，各自能够观察到的局部结果。最终两个副本获得同样的状态信息后，结果收敛到10。这段代码是否可以直接用于生产？还不行。它假定副本集合固定、每个副本拥有独立且稳定的标识，而且单个副本对自己分量的修改已经正确串行化。真实系统还需要解决本地并发、进程重启、状态持久化、节点增加或退役、状态传输、权限和身份认证等问题。尤其要避免：同一个副本 ID 被两台彼此独立的机器重复使用。或者某台服务器重启后，以旧 ID 从零重新开始记录计数。这些行为可能破坏对每个分量累计贡献的假设。CRDT 提供的是数据类型的合并规则，不是完整的集群管理、持久化和通信协议。第八幕：2011年论文还有两条路线——状态式与操作式到这里，我们一直在传输完整状态：text复制代码A 的计数向量 B 的计数向量这种方式叫作：State-based CRDT，也称 CvRDT。但如果一个数据结构非常庞大，每次都发送整个状态，可能会浪费网络带宽。于是还有另一条路线：Operation-based CRDT，也称 CmRDT。它传输的是更新操作或其经过准备后的效果。例如：text复制代码A 执行 increment(3) B 执行 increment(5)如果这些操作满足适当的交换性质，那么：先执行 A 的增量，再执行 B 的增量。和先执行 B 的增量，再执行 A 的增量。最终结果可以相同。因为普通整数加法满足：3+5=5+33+5=5+33+5=5+3两种方式的关键区别维度状态式 CRDT操作式 CRDT传播内容状态或状态增量更新操作及其效果收敛核心合并得到最小上界并发操作满足交换条件重复消息幂等合并能够容忍需要符合协议的去重或交付保证乱序消息符合半格规则的状态合并可以乱序必须满足相应因果交付条件主要成本状态元数据与合并开销操作传播、排序与交付管理这里必须纠正一个容易造成严重工程错误的说法：不是所有 CRDT 都能把一条操作消息原封不动地执行任意多次。例如，如果 B 收到：text复制代码increment(5)直接执行加5。网络重试又发送一次同样的操作。如果 B 不做去重：text复制代码+5 +5就会重复计算。所以操作式 CRDT 不会因为名字里有“CRDT”，就天然允许应用层随便重放重复操作。2011年的原始理论模型对操作式 CRDT 明确采用了可靠、因果有序且无重复的交付假设。实际系统可以通过操作 ID、去重和其他可靠通信机制达到适当效果。[perso.lip6.fr]这也解释了为什么：状态式合并的幂等性，和操作式更新的交换性，不能简单混为一谈。第九幕：两个副本同时“添加”和“删除”，到底谁应该赢？计数器已经很有意思。但现实业务中的数据往往不是一个数字。例如：购物车。好友列表。收藏夹。项目任务集合。这些数据需要：添加一个元素。删除一个元素。现在出现一个比计数器更困难的问题。假设两个副本都保存着：text复制代码购物车 = {"苹果"}网络断开后：A 再次添加“苹果”。B 删除“苹果”。网络恢复后：购物车里到底还应该有苹果吗？如果简单对两个集合取并集，那么删除几乎无法生效。如果让删除永远优先，那么网络断开期间新添加的元素可能消失。如果按照物理时间戳选最后一次操作，还需要解决时钟偏差和并发顺序问题。所以，集合 CRDT 必须事先定义：当添加与删除并发发生时，哪一种行为具有优先权？一种经典答案是：OR-Set，Observed-Remove Set，已观察删除集合。给每次添加一个独一无二的身份假设最初添加苹果时，产生标签：text复制代码("苹果", t0)A 和 B 都知道这个标签。网络断开之后，A 再次添加苹果。注意，虽然集合看起来已经有苹果，但这次添加产生新的唯一标签：text复制代码("苹果", tA)于是 A 所掌握的添加记录是：text复制代码("苹果", t0) ("苹果", tA)B 此时执行删除苹果。但 B 只看见了：text复制代码("苹果", t0)因此，它只能明确删除自己已经观察过的这个添加事件。等到网络恢复，合并双方信息：添加记录包含：text复制代码t0, tA删除记录包含：text复制代码t0最后剩下：text复制代码tA所以苹果仍然存在。这意味着：并发的新增胜过尚未观察到它的删除。这就是一种常称为 Add-Wins 的并发语义。但如果 B 在删除前已经看到 A 的最新添加，那么 B 可以删除它所观察到的两个标签。这种情况下，苹果就会消失。Shapiro 等人的2011年研究讨论了支持集合添加、删除以及并发语义的 CRDT 构造，包含经典的已观察删除思想。[CiteSeerX][asc.di.fct.unl.pt]实验三：同时添加与删除，到底会发生什么？OR-Set 添加与删除实验室最初 A、B 都知道“苹果”的添加标签 t0。网络断开：A 再次添加苹果；B 没看见新添加就删除B 先看到了 A 的新添加，然后再删除苹果副本 A添加记录t0tA本地可见：苹果副本 B删除所观察到的标签t0本地删除：苹果◇ 网络恢复，合并两端状态A、B 暂时拥有不同的观察历史。点击合并，看看预先定义的集合语义如何决定最终结果。这项实验揭示了 CRDT 比普通“冲突时覆盖旧值”更深刻的地方。它不是在发现冲突后临时猜测谁应该赢，而是给每个更新保留足够的身份和因果信息，使并发语义可以被确定地计算。不过，这也带来了存储成本。如果不断添加、删除相同元素，系统可能积累大量事件标签和删除记录。工业实现通常还需要更紧凑的因果上下文、版本向量或元数据清理机制。清理不能随意进行，否则某个延迟很久才重新联网的副本，可能把早已删除的旧添加重新带回来。第十幕：用 Python 实现一个教学版 OR-Set我们先实现一个简单的状态式 OR-Set。内部维护两个集合：所有已经发生的添加事件。所有已经被删除的添加事件。这两个集合都只会增长。查询时，计算两者之间的差集。python复制代码class ORSet: def __init__(self, replica_id): self.replica_id = replica_id self.sequence = 0 self.adds = set() self.removed = set() def add(self, item): self.sequence += 1 tag = ( item, self.replica_id, self.sequence ) self.adds.add(tag) def remove(self, item): # 只删除当前已经观察到的添加事件 observed = { tag for tag in self.adds if tag[0] == item } self.removed.update(observed) def merge(self, other): self.adds |= other.adds self.removed |= other.removed @property def value(self): active = self.adds - self.removed return { item for item, replica, seq in active }现在模拟一个真实的并发场景。python复制代码a = ORSet("A") b = ORSet("B") # 最初 A 添加苹果 a.add("苹果") # 同步给 B b.merge(a) # 模拟网络断开 a.add("苹果") b.remove("苹果") print(a.value) # {'苹果'} print(b.value) # set() # 恢复网络，交换状态 a.merge(b) b.merge(a) print(a.value) print(b.value) # {'苹果'} # {'苹果'}这个结果完全符合我们刚才定义的 Add-Wins 语义。A 在断网期间产生了一次新的添加事件。B 的删除没有观察到它。因此，新添加的标签在最终合并后仍然有效。这段实现还有两个重要限制第一，事件标签必须在整个副本系统内保持唯一。本例使用：(replica_id, sequence)实现这一点。实际应用中，需要持久化序号，避免重启后复用标签。第二，adds 和 removed 会持续增长。这只是教学版。生产级实现需要处理长期运行时的元数据压缩和垃圾回收，而且必须考虑离线副本尚未同步的历史。这与上一章垃圾回收的主题又产生了联系：即使 CRDT 的可见集合已经删除一个对象，系统也未必能够立刻忘记与这次删除有关的因果信息。第十一幕：2009年，CRDT 已经开始解决多人协同编辑问题这里需要补充一段重要历史。2011年的论文并不代表研究者直到那一年才第一次想到无需集中协调的复制数据结构。此前已经有多种相关研究。2009年，Nuno Preguiça、Joan Manuel Marquès、Marc Shapiro 和 Mihai Leția 在第29届 IEEE 国际分布式计算系统会议（ICDCS）发表：A Commutative Replicated Data Type for Cooperative Editing《一种用于协同编辑的交换式复制数据类型》。他们提出了用于协同文本编辑的 Treedoc 结构。[perso.lip6.fr]为什么协同文本比计数器困难？假设初始文本为：text复制代码ABCAlice 与 Bob 离线编辑。Alice 在 A 与 B 之间插入 X。Bob 在 A 与 B 之间插入 Y。Alice 的结果是：text复制代码AXBCBob 的结果是：text复制代码AYBC两台设备重新联网后：最终应该是 AXYBC？还是 AYXBC？如果双方简单采用“最后保存者覆盖”策略，就可能丢失另一人的输入。如果使用协同编辑 CRDT，则可以为插入的字符分配具有确定排序语义的标识，确保不同副本最终能够以相同顺序排列它们。但注意：自动收敛不等于自动理解作者意图。如果 Alice 和 Bob 同时修改同一段文字，CRDT 可以按照预定规则得到一个共同的结果。但它无法保证最终文本在语法、逻辑和语义上一定符合两个人的共同期望。这正是协同编辑中必须区分的两个目标：计算层面的确定性收敛。用户层面的编辑意图协调。CRDT 擅长解决前者，却不能保证彻底解决后者。第十二幕：CRDT 为什么没有取代 Raft、Paxos 和数据库事务？这是本章最值得认真思考的问题。既然 CRDT 可以让不同节点离线修改，而且最终自动收敛，我们为什么还需要分布式共识？原因是：自动收敛，与维护所有业务约束，是两项不同的要求。假设这是一个库存系统库存初始有：101010件商品。A 与 B 两台服务器断网。A 接受一笔购买7件的订单。B 同时也接受一笔购买7件的订单。如果我们使用 PN-Counter：A 记录减少7。B 也记录减少7。最后合并：10−7−7=−410-7-7=-410−7−7=−4PN-Counter 正确合并了双方的修改。没有丢失任何一次减少。最终状态也能一致。但业务已经超卖4件。数学上正确收敛，不代表业务约束成立初始库存10总售出量14合并后库存−4两台服务器的 PN-Counter 都正确地保留了本地减少操作，但没有自动阻止总库存小于零。所以，我们要认识到一条重要边界：CRDT 可以让副本最终就某种状态达成一致。但它不一定阻止并发操作违反全局约束。例如：账户余额不能为负。库存不能超卖。某个用户名必须全局唯一。同一张优惠券只能被成功核销一次。这些业务不能仅靠任意一个普通 CRDT 就保证正确。能不能设计更复杂的 CRDT 来维护约束？有些约束可以。例如，针对数量下界可以研究 Bounded Counter 和 Escrow（资源配额）等设计。先把可以安全消耗的权利分配给不同节点。每台节点只允许消耗自己拥有的额度。这样即使断网，也不能无限制地超卖。但配额不足时，节点可能需要等待其他节点转移额度，或者拒绝新的操作。因此，维持业务不变量通常需要明确的资源分配、权限和协调策略。CRDT 并没有推翻共识理论，而是明确指出：对于一部分能够以交换、幂等与单调规则表达的操作，根本不必为每一次更新都取得全局共识。第十三幕：CRDT 在实际系统中如何应用？一个具有代表性的系统是 Riak。Riak KV 的文档介绍了以 CRDT 研究为基础的数据类型，包括：计数器。集合。映射。标志。寄存器。其文档明确说明，计数器可保留不同参与者的增减操作，集合在添加与删除并发发生时可以采用 Add-Wins 语义，复杂对象也可以通过组合其他复制数据类型构造。[Riak 文档][Riak 文档]这体现了一种重要的工程思想：不再只把存储系统理解成：text复制代码GET key PUT key, value而是允许客户端表达更明确的操作意图：text复制代码counter.increment(5) set.add("apple") set.remove("orange")服务器知道这个数据是计数器还是集合，才能使用正确的合并规则。如果只把所有数据保存为不透明的字节字符串：text复制代码"8"服务器很难知道：这个8是一次赋值？还是两台机器独立增加后的累计值？两次并发修改到底该相加、覆盖还是保留多个版本？这正是 CRDT 强调“数据类型语义”的原因。工程中仍然需要付出的成本问题CRDT 仍需要的机制网络长期断开最终恢复通信与状态传播节点重启持久化和恢复副本身份及状态操作重复投递幂等合并或可靠去重新增与退役节点成员管理、状态初始化与迁移删除大量元素因果元数据与墓碑清理权限和恶意节点身份认证、授权和输入验证全局业务不变量专门的约束算法或协调协议还有一个需要明确的假设：经典 CRDT 收敛研究通常考虑遵守协议的正确副本，以及崩溃、消息延迟与网络分区等故障。如果某台机器已经被攻击者完全控制，故意伪造副本身份、计数状态或操作内容，那就不能简单依赖普通 CRDT 的收敛证明。这与我们第十六章区分 Crash Fault 和 Byzantine Fault 的讨论相呼应。终章挑战：为什么合并必须具有幂等性？假设服务器 A 的 G-Counter 状态是：[4,2][4,2][4,2]服务器 B 的状态是：[3,7][3,7][3,7]现在它们使用逐分量最大值合并。最终应该得到什么？选择正确答案[7,9]，因为需要把两个向量直接相加[4,7]，最终可见计数为11[3,7]，因为 B 的总值更大必须先比较两个副本的物理时钟才能决定尾声：分布式系统的一次思想转变2009年，Treedoc 等研究开始展示：协同编辑中的某些并发操作可以被设计成自动收敛。2011年，Shapiro、Preguiça、Baquero 和 Zawirski 系统整理并形式化了 CRDT 的重要理论条件。他们展示了两种非常有代表性的路线：通过单调状态与最小上界合并，实现状态式收敛。通过具有正确交换性质的并发操作，实现操作式收敛。随后，这些思想进入复制计数器、集合、映射、协同编辑和其他分布式数据结构中。本章最重要的发现，其实不是某段复杂代码。而是：当系统无法控制网络消息何时到达时，我们可以尝试重新设计数据结构，让最终结果不再依赖消息到达顺序。这是一个非常深刻的算法设计原则。在单机算法中，我们经常通过排序，把无序数据变成有序数据，再完成计算。在传统分布式共识中，我们尝试让不同机器对操作顺序取得共同决定。而 CRDT 则指出：有些操作根本不需要统一的全局顺序，只需要保证它们可以按照预先定义的数学规则合并。这不是对共识的替代。而是让我们更加清楚：什么时候确实需要共识，什么时候可以直接利用数据类型的代数性质来降低协调成本。第二十四章知识总结概念核心思想CRDT无冲突复制数据类型Strong Eventual Consistency接收相同更新的正确副本具有等价状态，并满足最终交付等条件State-based CRDT通过合并状态实现收敛Operation-based CRDT通过适当交付条件下可交换的并发操作实现收敛Join-Semilattice具有最小上界运算的偏序结构Commutativity交换顺序不影响结果Associativity合并分组不影响结果Idempotence重复合并同一状态不影响结果G-Counter按副本记录累计增加量PN-Counter用正向、负向两组只增计数器支持加减OR-Set通过唯一添加标签与已观察删除定义集合并发语义Tombstone保留已经删除的更新身份，防止旧状态错误复活Business Invariant收敛本身不保证余额、库存等业务约束本章原始研究资料Shapiro 等（2011）：《Conflict-Free Replicated Data Types》原始论文Shapiro 等（2011）：《A Comprehensive Study of Convergent and Commutative Replicated Data Types》完整技术报告Preguiça 等（2009）：Treedoc 协同编辑 CRDT 论文Marc Shapiro（2011）：Microsoft Research 的 CRDT 学术演讲Riak KV：CRDT 计数器、集合与映射的工程文档CRDT 研究论文索引：从早期复制结构到后续算法下一章预告第二十五章：向量时钟——1988年，为什么两个事件的时间戳不同，却不代表它们有先后关系？1988年，澳大利亚研究者 Colin J. Fidge 发表论文：Timestamps in Message-Passing Systems That Preserve the Partial Ordering。与此同时，德国研究者 Friedemann Mattern 也独立推进了用时间向量描述分布式事件因果关系的研究，相关工作于1988年报告、1989年正式出版。[加州大学尔湾分校计算机科学系][BibTeX Entry]他们面对的问题非常尖锐。假设服务器 A 记录：text复制代码时间戳 = 100服务器 B 记录：text复制代码时间戳 = 105我们能否因此断定：A 的事件一定先于 B，而且影响了 B？不能。因为两台机器可能使用不同的本地时钟。即使物理时间完全同步，两件事也可能彼此独立，没有任何因果关系。于是研究者提出：不用单个数字表示逻辑时间。而是为每个参与者维护一个时间向量。例如：text复制代码A: [3, 1] B: [2, 4]通过比较向量中的各个分量，我们能够判断：某个事件是否在因果上先于另一个事件。或者，它们是不是彼此并发、无法形成因果先后关系。下一章，我们会从 Lamport 1978年的逻辑时钟讲起，再进入 Fidge 与 Mattern 的向量时钟，弄清楚分布式系统怎样在没有统一全局时钟的情况下追踪事件之间的因果关系。上一章第二十三章：一致性模型——1979年，为什么写入已经成功，另一台计算机却仍然读到了旧数据？下一章第二十五章：向量时钟——1988年，为什么两台计算机的时间戳不同，却不能证明谁先谁后？