Shapiro 2011：副本收敛是半格或可交换操作，不是共识协议

破除误解：无冲突不是没有并发，会合也不是线性化#

第一层误解把「Conflict-free」听成「不会有两个人同时改」。论文假定并发是常态。无冲突说的是：并发更新到达之后，不必再开一轮协商来挑选赢家。合并函数自己给出唯一结果。两个副本同时对计数器加一，会合后是加二，不是「选其中一次」。两个副本同时往集合里放不同元素，会合后两个都在。冲突被类型消化掉了，不是被禁止发生。把无冲突读成互斥锁，句子就接反了。

第二层误解把 CRDT 听成 分布式共识算法 的替代品，或听成「有了半格就再也不需要 Paxos」。共识锁定的是一个已被提出的值，或一条命令的全序。本页锁定的是另一句：交付了同一组更新的正确副本，状态必须等价。需要全局唯一序号、一次选举一个值、线性化库存，仍然要协调。夏皮罗等人没有宣称共识死亡。他们划出一类更新——单调膨胀、可交换——使会合可以从协议里搬进类型。把本页读成反共识宣言，会把规格偷换成另一道题。

第三层误解把强最终一致性听成 Dynamo 那句「过一会儿大概一样」，或听成购物车冲突交给客户端去合并。论文里的 SEC（Strong Eventual Consistency）有三款：更新若在某台正确副本上交付，终将交付到所有正确副本；方法调用终止；已经交付同一组更新的正确副本，状态立即等价。最后一款比口头上的最终一致更硬。它不要求再跑一轮反熵去「对齐」已经到齐的更新。Dynamo 把冲突值留给应用；本页要求类型把合并写死。两者都接受分区下继续写，合同不是同一份。分布式系统 总览里的最终一致段落是路标，不是 2011 年的定义。

第四层误解把状态型与操作型收成两种产品口味，或收成「一个发快照、一个发日志」。论文把它们写成对偶的证明对象。状态型（CvRDT）要求载荷是一个 join-半格，合并 \(\sqcup\) 是上确界，因此幂等、交换、结合；更新必须使状态在偏序里膨胀。操作型（CmRDT）要求并发操作可交换，并把可靠的因果广播写进通道假设。他们还证明两种形态可以互相模拟。把其中一种写成实现窍门、把另一种写成过时，会把等价定理读丢。

第五层误解把本页听成协同编辑教程，或听成「如何在分区两侧各写各的」。目录里的计数器、寄存器与集合，是为了让半格看得见，不是一份编辑器施工图。操作变换要把针对同一文档的插入、删除改写成对已应用过其他操作仍有意义的操作，正确性往往随操作种类重做。本页不把 OT 写成对象，只用它标明另一条路：变换函数对交错负责，半格对上确界负责。CALM 把「逻辑单调则不必协调」写成程序性质，年份与陈述都不是 SSS 2011。本页也不把 数据库与事务 的隔离级别或原子提交塞进半格。概念证据停在类型，不进菜谱。

装置：SEC、join-半格、可交换操作#

装置从复制对象开始。若干副本各持一份载荷。客户端把查询或更新交给某一副本。副本之间可以发信，也可以在一段时间里完全不发。正确性不要求存在一个可线性化的单副本历史。它要求：只要更新终将交付到全体正确副本，并且已经交付同一集合的那些副本拿出来比较，状态必须等价。这就是 SEC。它比「终将有那么一天看起来差不多」更强，因为它禁止「更新都到了、却还要再等一次同步才相等」。它比原子寄存器更弱，因为它允许分区窗口里读到尚未全局可见的值，也允许并发写按类型规定的方式并存，而不是按实时先后排成一条线。

状态型一侧把载荷做成偏序集 \((S,\preceq)\)，并且任意两个状态都有最小上界。合并就是取这个上界。收到对侧状态 \(s'\)，本地做 \(s \sqcup s'\)。因为 \(\sqcup\) 幂等，重复投递不改结果；因为交换与结合，到达次序不改结果。更新必须是膨胀：新状态在偏序里高于或等于旧状态，否则后来的 join 可能把一次更新「往回压」。查询是载荷上的函数，不必可交换。定理说：在终将交付与终止的前提下，满足这些代数条件的状态型对象是 SEC。证明的几何很短。全体已交付更新对应载荷里的一组状态；join 的上确界唯一；每个副本对这组状态做有限次合并，都得到同一个上界。没有领导者，没有多数派，没有「选一个时间戳当裁判」这一步——除非你把时间戳写进类型，那已经是另一种半格，例如最后写入获胜的寄存器，会丢掉并发值中的一个。丢掉是规格，不是实现事故。

操作型一侧不发整份状态，而广播更新。通道被假设为可靠因果广播：不丢、不重、因果前驱先于后继到达。相继发生的操作不必可交换，因为因果送达会保持它们的顺序。真正必须可交换的，是并发的那一对。若 \(u\) 与 \(u'\) 互不 happens-before，则先 \(u\) 后 \(u'\) 与先 \(u'\) 后 \(u\) 必须给出等价载荷。定理说：在这种通道上，并发可交换的操作型对象是 SEC。因果广播把「还没看见前驱」从本地决策里拿掉；交换律把「看见的并发集合以何种次序排」拿掉。少了通道，交换律推不出会合——迟到且永不补送的增量会让一侧永远缺一块。论文把这条假设写在类型外面，而不是假装 UDP 自己会补。

两种形态的等价是装置的第三件。任一状态型对象可以改写成操作型：把使状态膨胀的那一步当成操作去广播，接收方再做同等膨胀。任一操作型对象可以改写成状态型：载荷改成「已见操作的集合」，合并取并，查询按某种确定次序重放；因为并发操作可交换，重放次序在并发子集上无所谓。这不是工程上「哪种更省带宽」的比较。它标明：收敛条件可以写在状态的 join 上，也可以写在操作的交换律上，两者指同一类对象。后文的增量 CRDT、墓碑压缩、成员纪元，都是在这层等价之上减通信量或减元数据，不是 2011 年已经证完的另一条定理。

例子只用来看见半格，不展开成总览里的目录。只增计数器最干净：每个副本只在自己的槽位上加，状态是向量，合并取逐分量最大，查询是各分量之和。分量上的 \(\max\) 是全序的上确界，向量上的逐分量 \(\max\) 是积半格的上确界。两个副本同时加一，会合后两个槽位都增，和为二。它显然满足膨胀。只增集合同样干净：合并是并。并是幂等、交换、结合的典型例子。论文还写了正负计数器、两相集合、带观察删除的集合、以及用时间戳打破平局的寄存器。那些变体要回答的是「加与删并发时留下什么」，答案被写进半格，不是留给运行时去投票。本页不把它们写成实现清单。看见「上确界唯一 ⇒ 会合唯一」这一句，装置就够了。

Gilbert 与 Lynch 2002 禁止的是异步网上原子寄存器在丢信执行里又可用又原子。本页换了规格：放弃原子历史，保留分区下继续更新，用半格换回会合。那不是对定理 1 的反例，是换合同。两阶段提交 要全体准备之后才允许生效，已准备者在决定未到时必须等待。CRDT 的合并不等待宣布，因为它不宣布「提交或中止」这种全局结局，只计算上确界。Paxos 的多数相交锁定一个已提出的值；半格不投票。Dynamo 可以交出冲突版本，让购物车逻辑自己选；SEC 要求类型里已经没有未定义的冲突。OT 的变换函数对「对方刚做了什么」做即时改写；join 不改写历史，只取上界。把这些名字搅成「都是最终一致」，会把 2011 年真正写下的那一句稀释掉。

它证明了什么，没有覆盖什么#

它证明了：若状态型复制对象的合并是 join-半格上的上确界，更新是膨胀，并且更新终将交付、方法终止，则正确副本在交付同一组更新之后状态等价。它证明了：若操作型复制对象的并发更新可交换，并且通道提供可靠因果广播，则同样得到 SEC。它证明了两种写法可以互相模拟，因此「收敛是代数性质」不是一句比喻，而是可以在状态与操作之间搬动的条件。它把「冲突」从运行时协商里拿走，放到类型设计时就必须闭合的那一步：你得先决定并发更新的上确界是什么，纸上才能保证会合。

它没有证明会合等于用户意图。半格给出一个值，不保证这个值是「只准卖一份」的库存，也不保证「删除应当压过尚未看见的添加」。换一种上确界，就换一种业务。意图要另写一层，或回到线性化对象。它没有证明可以拿掉通道假设。操作型若丢失一条增量，会合停在缺口上；状态型若某份状态永远送不到，上确界缺一块。终将交付是 SEC 的前提，不是半格自动生产的网络。它没有覆盖成员加入、退出、副本标识重用。2011 年的证明常把副本集合当成固定的。标识撞车会让观察删除那一类标签对错一次添加，那是后来的纪元与垃圾回收问题，不是本页已经闭合的代数。

它也没有覆盖 CALM。约瑟夫·赫勒斯坦（Joseph M. Hellerstein）与彼得·阿尔瓦罗（Peter Alvaro）后来说：规范若逻辑单调，最终一致的输入上也能得到正确输出。集合的并、计数器的和是单调的；「尚未收到」「恰好一次」不是。CRDT 是把单调更新封进数据类型的一条工程路，不是 CALM 的陈述，也不是它的证明。本页不把后文定理提前写进 SSS。它更没有覆盖如何把一份 JSON 文档做成产品，没有覆盖 Figma 式的字段折中，没有覆盖协同编辑里墓碑如何压缩。那些工作引用 2011 年的规格当背景；背景不是对象。

对照要停在规格边界上。CAP 的 C 是原子寄存器；本页的会合不是那一个 C。可用性在这里表现为：分区一侧仍可对本地载荷做膨胀更新并回答查询，而不等待对侧邮件。这不是把整库永久标成 AP。需要唯一性约束的那一列，仍可能要求协调。原子提交 保证不会出现一半提交、一半中止；CRDT 根本不生产那种跨资源结局。把半格当成两阶段提交的加速版，会把安全性质听错。概念上，2011 年给出的是一类对象的充分条件，不是一份在活系统上复现写冲突、或干扰对侧副本的步骤。缩短元数据、改通道、加成员协议，都是后来的实现工作。概念证据到此为止。

跨域连接#

• 科学哲学：2011 年把「副本会不会分叉」从一则关于协议实现的经验判断，改写成一条可被代数推翻的命题。证伪条件很硬：若合并既不交换、又不幂等，或更新并不膨胀，SEC 的证明就不再适用。半格不是对运行日志的归纳概括，而是事先写下的不变量。后来某次产品会合了，并不能回过头证明类型是 CRDT；一次可重复的分叉，却足以表明 join 没有闭合。把「我们最终一致」当成观察口号，缺少的正是这种可被证伪的规格。
• 认识论：每个副本只有自己收到的状态或操作当证据，没有上帝视角来宣布「真状态此刻在哪一台」。SEC 不要求任何人在分区窗口里知道全局；它要求的是：一旦证据集合相同，判断必须相同。状态型的 join 把对侧证据并入本地，操作型的交换律保证并发证据的排列不改变结论。可用性意义上的继续回答，是在欠定证据上给出局部上界，而不是拒绝作答。真由全体更新的上确界构成，知由已经交付的子集构成。两者暂时分开，并不自动变成两份互相矛盾的真理——只要上确界唯一。
• 同一性：复制对象凭规格被认作「那一个计数器」或「那一个集合」，不凭某次运行里哪一台持有较新的字节。分区两侧各自膨胀之后，观察者手里会暂时出现两份载荷。数值同一问的是：它们是否仍是同一半格里的两个元素，其 join 是否还给出规格所承认的那一个对象。若合并随到达次序给出两个不可比较的终态，规格不再承认这是同一个 CRDT，不是因为机器换了，而是因为外延对不上。换一批副本、甚至换成操作型模拟，只要上确界不变，同一性在正确性条件的意义上保持。
• 信息不对称：分区把同一对象切成两个暂时无法对盘的信息集。一侧已经写入的膨胀，对侧在邮件到达前无法核实。经济学里的不对称通常假定通道还在、只是一方知情；这里的通道按模型可以沉默，知情本身不能被对侧报价。愈合不是靠中间人宣布价格，而是靠事先写好的 join 把两本账合成上界。这与柠檬市场里卖方隐瞒质量不是同一句话：半格不评价哪一次更新「更真」，只保证合成规则唯一。把这种结构读成「请去切断别人的复制」，会离开对象。
• 知识：公共知识要求不仅人人知道，而且人人知道人人知道。SEC 不生产这种高阶闭合。更新在某一副本交付，只说明这一侧已经把它收进知识状态；它并不因此成为全体的共同知识。会合完成时，各正确副本持有等价状态，仍不必知道别人已经知道自己已经会合。活性失败是交付迟迟不能齐；分叉才是同一更新集却闭合出两份状态。本页的代数管的是后一种错误不得发生，不管抄本在路上走多久。

参考文献#

• Marc Shapiro, Nuno Preguiça, Carlos Baquero & Marek Zawirski, "Conflict-free Replicated Data Types", in X. Défago, F. Petit & V. Villain (eds.), Stabilization, Safety, and Security of Distributed Systems (SSS 2011), Lecture Notes in Computer Science 6976, Springer, 2011, pp. 386–400. DOI: 10.1007/978-3-642-24550-3_29. —— 本文对象：SEC、状态型 join-半格、操作型并发可交换，以及两种形态的等价。
• Marc Shapiro, Nuno Preguiça, Carlos Baquero & Marek Zawirski, "Conflict-free Replicated Data Types", INRIA Research Report RR-7687, 2011. —— 与 SSS 文本并行的研究报告，定义与定理与会议版同一对象。
• Marc Shapiro, Nuno Preguiça, Carlos Baquero & Marek Zawirski, "A Comprehensive Study of Convergent and Commutative Replicated Data Types", INRIA Research Report RR-7506, 2011. —— 同组作者的类型目录，用作对照，不是本页要展开的清单。
• Giuseppe DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", SOSP, 2007. DOI: 10.1145/1294261.1294281. —— 最终一致与冲突交给应用的工程合同，用以标明 SEC 把合并收进类型。
• Seth Gilbert & Nancy Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News 33(2), 2002, pp. 51–59. DOI: 10.1145/564585.564601. —— 原子寄存器在丢信执行中不能又可用又原子；本页换的是规格，不是反例。

延伸阅读#

• 与 无冲突复制数据类型 对读：总览里的目录、墓碑与产品折中是路标，本页才是 2011 年的代数对象，不要把总览再织长。
• 与 Dynamo、分布式共识算法 对读：先分清「冲突版本留给应用」「多数锁定一个值」与「上确界写进类型」。
• 与 Gilbert 与 Lynch 2002、Gray 1978 两阶段提交 对读：原子历史与原子提交各是另一份合同；半格既不恢复线性化，也不宣布提交或中止。
• Clarence A. Ellis & S. J. Gibbs, "Concurrency Control in Groupware Systems", ACM SIGMOD, 1989, pp. 399–407. —— 操作变换的早期陈述，用作本页明确不覆盖的那一条对照轴。