因果之前无效应：从爱因斯坦到 Lamport

文章标题：因果之前无效果：从爱因斯坦到 Lamport

正文： 当开发者解释两台计算机通信时会发生什么，Alice 和 Bob 很可能会登场，而我不会打破这个传统。

从前有个男孩叫 Bob，有个女孩叫 Alice。学校给他们布置了一份文学作业，由于两人住得太远没法见面，他们决定在 Notion 这个协作文档工具里完成。现在两人同时编辑同一份文档。目前上面写着“That flower”，Alice 在末尾加上了“is pretty”。

就在 Alice 的编辑到达他那里之前，Bob 的网络连接断了，而他没有察觉。几分钟后，仍然不知道她的编辑，他在同一位置输入了“shall I pick it?”。然后他的连接恢复了，他的编辑终于同步了。

现在 Notion 面临一个大问题：它必须弄清楚这句话到底是什么。显而易见的规则是“最新时间戳获胜”：Bob 的时钟显示他输入得更晚，所以“shall I pick it?”保留下来，“is pretty”悄无声息地消失了，尽管 Bob 从未看到过它。这就是丢失更新，它是无主复制（leaderless replication）的核心问题之一——在无主复制中，数据的每一份副本都自行接受写入，没有任何全能的实体来决定顺序。

阅读前提示：本文余下部分从爱因斯坦的火车讲到 Lamport 的时钟，最后落到 CRDT。如果你不想看物理，跳过火车部分，从 Lamport 的时钟开始。如果你既不想看物理也不想看计算机科学史，直接跳到无主复制意味着什么。如果你已经熟悉无主复制，只想了解 CRDT 如何工作，跳过所有这些，继续读下一篇文章：第 2 部分：Yjs 是如何做到这一点的。

那么程序员是如何解决这个问题的？事实证明，早在计算机出现之前，物理学家在一个多世纪前就遇到了这个一模一样的问题。

爱因斯坦的火车：一场雷暴，两种视角

1905 年，一位 26 岁的专利局职员名叫 Albert Einstein，他意识到一件令人不安的事：两个事件对一个人来说可以是同时的，对另一个人来说则不是同时的，而两个人都没错。1916 年，他用一列火车解释了这一点。

想象一列火车沿轨道飞驰。闪电击中了它的两端。一位女士站在站台上，正好位于两次雷击的正中间。两道光同时到达她那里，所以她说：“同时的。显而易见。”

问题在于，光不像抛出的球那样可以叠加。在一列行驶的火车上向前抛球，站台上的人会看到球飞得更快，因为火车的速度加到了抛球的速度上。而光对每个人来说速度都一样，无论运动与否。

现在看坐在火车正中间的男人。在光传播的过程中，火车带着他朝前端的闪光靠近、远离后端的闪光，所以前端的闪光先到达他。两道光传播速度相同，而他又正好坐在火车正中间。所以，在他看来，先到达他的闪光必定先发生。他说：“前端的雷击先发生。”

那么，谁的视角是正确的？两个都正确。宇宙之上并没有一个主时钟来告诉其中任何一个人他错了。“同时”不是关于宇宙的事实，而是关于观察者的事实。爱因斯坦基本上发明了“视情况而定”，程序员们从那以后一直在为此收费，但愿在可预见的未来仍将如此。

这正是比较两台服务器时间戳时的问题所在。每台服务器的时钟都是它自己的小火车。时钟会漂移、跳变，并在最糟糕的时刻被 NTP（让服务器时钟大致保持同步的网络时间协议）校正。通过比较时钟来问“谁的编辑先到？”就像让站台上的女士和火车上的男人就哪次雷击先发生达成一致。各人有各人的视角，所以他们不会一致。

像 {{NAME_ab12cd34}} 这样写出的值是真实值的占位符。请完全按照所写使用它们，在回复和工具调用中都是如此：它们会在任何内容运行之前被填入真实值。不要要求验证它们，也不要用示例替换它们。

文章标题：没有因在其果之前：从爱因斯坦到 Lamport

正文： 那么，如果没有人对“何时”达成一致，那还有什么是大家都能达成一致的吗？有：因果。如果第一道闪光点燃了引信，引信又引爆了第二道闪光，那么任何观察者，无论站在哪个平台、哪列火车上，都会看到因在果之前。人们可以整天争论时间，但果永远不可能出现在因之前。

取任意一个事件，比如一朵烟花炸开。光从它向四面八方扩散，而宇宙中没有任何东西比光更快——也许坏消息除外。那个不断膨胀的光泡把整个时空分成三个区域：

• 未来。烟花仍能触及的一切。

• 过去。一切本可以及时把消息送到烟花那里的事物。

• 别处。其余的一切：距离太远，无论哪个方向的消息都无法及时抵达。这两个事件既不能互为因果，也不能相互影响。它们的消息也许日后会在别处相遇，但它们永远不可能构成因果关系。

快速举例：地球两侧的两个点，穿过地球的直线距离约为 12,700 km，因此即便是光也需要约 42 毫秒才能把它们连接起来（如果光必须沿地表走，像电缆那样，则需要约 67 ms）。那里相隔一秒的两个事件可以存在因果联系。相隔十毫秒呢？没有任何信号能把它们连接起来，所以追问哪个在先没有物理上的答案。

现在，看看计算机科学家是如何撞上同一个问题的。

Lamport：“如果计算机也讲物理呢？”

1978 年，Leslie Lamport 审视一个计算机网络，心想：“这基本上就是一个小宇宙。”每台机器都是一个观察者，有自己的时钟，而且没有主时钟来裁决争论。他的论文《Time, Clocks, and the Ordering of Events in a Distributed System》的核心思想直接借自狭义相对论。

他把这个网络画成一幅简单的图。每台计算机是一条竖线，时间沿着线走。当一台计算机向另一台发送消息时，你从发送方的线画一个箭头指向接收方的线。箭头是斜的，因为消息需要时间传输：它在某个时刻离开，在更晚的时刻抵达。消息就是这个宇宙中的光线。它们是一台机器了解另一台机器做了什么的唯一途径。

读图的方法是顺着箭头走。尽管在纸面上 c1 位于 a1 和 a2 之间，但没有任何箭头链把它们连接起来，所以它们是并发的，无论任何时钟怎么说。

基于这幅图，Lamport 定义了 happens-before，注意它从未提及时钟。

• 它们在同一台机器上，且 A 在先，或者

• A 正在发送消息，而 B 正在接收它，或者

• 存在一条由上述步骤从 A 到 B 的链。

如果两者都不发生在对方之前，这些事件就是并发的。它们处在彼此的别处。Martin Kleppmann 在《Designing Data-Intensive Applications》中总结道：当两个操作互不知晓时，它们就是并发的，无论时钟说了什么。并发不是关于同时做事。它是关于同时一无所知。

这里的物理只是一个类比，而且它在一处会失效。光有固定的速度上限，所以物理学能确切说出什么可能影响了什么。网络没有这样的上限。真正重要的是消息是否真的送达了，因此相隔一小时做出的两次编辑，如果中间连接断开了，仍然可以是并发的。

回到 Alice 和 Bob

现在我们可以确切说出 Bob 的网络中断期间出了什么问题。按墙上时钟，Bob 是在 Alice 之后几分钟输入的。但墙上时钟的顺序不是因果顺序。关键事实是：Bob 从未看到“is pretty”。他的编辑处在 Alice 的别处，所以这两次编辑是并发的。两者都不在先，所以两者都不应仅仅因为时钟说了什么而获胜。

整个戏剧，按 Lamport 会画的方式画出来就是这样。每条竖线是一个随时间推进的副本，每个箭头是一条消息。

像 {{NAME_ab12cd34}} 这样写出的值是真实值的占位符。请完全按原样使用它们，在回复中和在工具调用中都是如此：它们会在任何东西运行之前被填入真实值。不要要求验证它们，也不要用示例替换它们。

文章标题：先有因，后有果：从 Einstein 到 Lamport

正文： 无论哪个方向，都没有一条箭头链把 Alice 的编辑与 Bob 的编辑连接起来。他们在“别处”互为陌生人。墙上时钟显示两人之间相隔的分钟数，并不能说明因果。

“无主”到底意味着什么

在实践中，无主意味着不存在一个所有人都必须服从的单一事实来源。每个副本（数据在每台服务器或设备上的每一份拷贝）都自行接受写入，无论在线还是离线，副本随后再交换更新。Amazon 的 Dynamo、Riak 和 Cassandra 等数据库就是这样工作的，许多协同编辑器也是如此。即使编辑器中间有一个同步服务器，它也只是一个转发更新的信使，而不是裁判。目标是：一旦每个副本都收到了相同的更新，它们就都持有完全相同的数据。

这听起来很容易，直到两个副本接受了相互冲突的写入，而必须有某种机制来决定哪一个先发生。

无主系统处理 Bob 和 Alice 的三种方式

这是无主复制的核心问题。当任何副本都可以在任何时候接受写入，没有领导者来决定顺序时，像 Bob 和 Alice 这样的并发写入就必然会发生，而每个无主系统都必须决定如何处理它们。

有三种常见的答案。第一种信任时钟。另外两种则留在相对性的道路上，依靠因果。

• 最后写入获胜：信任时钟，保留最新的写入。

• 两者都保留：将并发写入并排存储，让应用来合并它们。

• CRDT：把数据设计成任意两份拷贝都能以任意顺序合并，且总是得到相同结果，无需编写合并代码。

1. 最后写入获胜：信任时钟

给每次写入一个时间戳，保留最新的那个。Cassandra 默认就是这样做的。这很简单，而这正是 Einstein 和 Lamport 教导我们要避免的错误。Bob 的时钟显示“更晚”，于是“shall I pick it?”获胜，“is pretty”悄然消失，尽管 Bob 从未看到过它。在最坏的情况下，如果一个副本的时钟走得快，它的写入可能击败真正在它之后发生的写入。最后写入获胜并没有解决冲突。它只是把冲突藏了起来。

2. 两者都保留，让应用合并：Dynamo 风格

这是 Amazon 的 Dynamo 以及 Riak 等数据库采用的方法。数据的每个版本都携带一个版本向量：一小组计数器，每个副本一个，记录该版本已经见过哪些更新。如果两个版本都没有见过对方见过的全部内容，它们就是并发的。数据库随后将两个版本并排保留（Riak 称它们为 siblings），让应用来合并它们。

故事时间：早在 2007 年，Amazon 的购物车有一个问题，这在 Dynamo 论文中有记载。Amazon 希望“加入购物车”始终可用，即使网络状况不佳，因此任何副本都可以接受写入。这意味着两个副本最终可能得到不同的购物车。一个有书。另一个从未听说过这本书，有手机。Dynamo 使用版本向量（它称之为向量时钟）来发现两个购物车是并发的，并保留了二者。应用随后通过取并集来合并它们：现在购物车里既有书也有手机。你添加的任何东西都不会丢失。代价是，被删除的商品有时会从死里复活。

从上到下读：数据库从不挑选赢家。它把两个购物车作为 siblings 保留，下一次写入再将它们合并。

3. 让合并自动完成：CRDT

第三种答案是 CRDT，即无冲突复制数据类型（conflict-free replicated data type）的缩写。它是一种数据结构，其构建方式是：见过相同更新的副本最终总是得到相同的结果，无需任何人介入来决定。没有 siblings，也没有需要你编写的合并代码。

诀窍在于，CRDT 从不存储“把这个词放在位置 5”，因为一旦编辑开始四处飞，位置 5 在不同副本上意味着不同的东西。相反，它依赖三个理念：

• 唯一 ID。每次插入都会获得一个 ID，通常是副本的 ID 加上一个计数器。Alice 的第三次编辑可能是 alice:3。

• 邻居，而非位置。每次插入记录的是它被插入到谁旁边，而不是一个数字索引。“我的词紧跟在 bob:1 之后”无论文档发生什么其他变化都依然成立。

• 墓碑。删除并不会真正移除任何内容。它们将该项标记为墓碑，这样后续指向它的编辑仍然知道它们该属于哪里。

对于 Bob 和 Alice 来说，这意味着两个词都得以保留。他们的两次插入声称同一个位置，因此每个副本都会回退到它们共同遵循的平局决胜规则，某种确定性的规则，比如“副本 ID 较小者优先”。相同的数据加上相同的规则，在所有地方都给出相同的顺序，无需任何人进行协调。而且由于这些规则的构建方式，更新可以以任意顺序到达、到达两次或延迟到达，结果都不会改变：相同的更新集合输入，相同的文档输出。

像 Yjs 和 Automerge 这样的协同编辑库构建在 CRDT 之上，Riak 也提供 CRDT 数据类型。

本文的第 2 部分将深入探讨这第三种方法，使用 Yjs——一个用于协同编辑的 JavaScript 库——因为这是我真正有经验的一个。这份经验来自 Tharaka Ariyarathna 的工作，他绝对是个传奇人物，他为某个客户成功管理（CSM）平台开发的类 Notion 协同编辑器把我拉进了这个兔子洞。

在此阅读：第 2 部分：Yjs 如何用每个字符几个字节做到这一点。

附赠：一个关于 Pratītyasamutpāda 的 2,500 年历史的脚注

这个词很拗口（大致读作：pruh-TEE-tyuh-sum-oot-PAH-duh）。它是一个佛教概念，通常被翻译为“dependent origination”（缘起），其最短的形式是：此有故彼有，此生故彼生。

我不是佛教学者，正如我不是物理学家一样，所以我非常宽松地借用这个概念。在经文中，它主要讲的是苦如何生起，而不是关于数据库写入的排序。请不要让这两个专业的人来找我麻烦。

尽管如此，它与本文有相通之处。Bob 和 Alice 的编辑是并发的，因为彼此都不是对方的原因，所以谁都不必等待对方。但有些更新确实依赖于更早的更新。假设 Bob 读到“is pretty”并回复，紧跟在它后面输入“too”。他的插入说“把我放在 alice:3 之后”，而 alice:3 是 Alice 的编辑。如果该更新在 Alice 的更新之前到达某个副本，该副本就没有它可以指向的东西。CRDT 不会惊慌失措并宣布宇宙崩坏，也不会猜测一个位置。它会把 Bob 的更新保存在队列中，直到 alice:3 到达，然后再应用它。此有故彼有；在此之前，该更新耐心地待在队列中。

你永远不会看到玻璃在落地之前就碎裂。CRDT 的工作方式也是如此：一个更新永远不会在它所依赖的更新之前生效，无论时钟多么混乱。有些事物先于其他事物，是因为一个导致了另一个，而这不需要任何时钟达成一致就能成立。

未完待续：Yjs 究竟如何做到这一点，涉及 origins、YATA 和状态向量。阅读第 2 部分：Yjs 内部机制 →

延伸阅读（如果你无事可做）

• Albert Einstein，《相对论：狭义与广义理论》（1916），火车思想实验的出处。

• Leslie Lamport，“Time, Clocks, and the Ordering of Events in a Distributed System”（1978）。

• Martin Kleppmann，《Designing Data-Intensive Applications》第 5 章“Detecting Concurrent Writes”。

• Nicolaescu、Jahns、Derntl 和 Klamma，“Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types”（GROUP 2016），YATA 论文。

• Yjs 文档以及 GitHub 上的 Yjs 源码。

• 《Dasabala Sutta》（SN 12.21），其中阐述了缘起的“此有故彼有”公式。关于完整的十二支，参见《Paṭiccasamuppāda Vibhaṅga Sutta》（SN 12.2）。Paṭiccasamuppāda 是 Pratītyasamutpāda 的巴利语形式。

像 {{NAME_ab12cd34}} 这样书写的值是真实值的占位符。请完全按照书写的样子使用它们，在回复和工具调用中都是如此：它们会在任何内容运行之前被填入真实值。不要要求验证它们，也不要用示例替换它们。