引言在 _Livelymerge_ 项目里Dan Ingalls、Peter Van Hardenberg 和 Alex Warth 正在构建类似 Lively Kernel 的系统该系统堆含每个对象、类和方法是 Automerge 文档。从系列第一篇笔记起设想是这样能“免费”实现合并即多个用户共享相同对象内存可同时甚至离线操作Automerge 协调一切。不过合并实时系统状态不易且无法保证对象不变性不被破坏。本文通过具体示例直面此问题目前无解决方案只是对问题的认识并非宣告胜利。但会简要介绍看好的可能方案也欢迎大家提供想法。示例 A链表Automerge 承诺实现 _收敛_ 即两个客户端交换更改后会达相同状态但该状态不一定能被程序正常处理。对于很多应用场景如文档、待办事项列表、草图等Automerge 合并功能能满足需求。然而在 LM 项目中要让其合并正在运行的程序的堆包括指针这超出了 Automerge 的舒适区本文将探讨会出现的问题。假设有简单链表 1 → 2 → 3 → 4按 LM 中程序员做法构建每个节点有 next 属性指向另一节点。现在两个客户端同时修改客户端 A 交换 2 和 3通过执行 1.next ← 3、2.next ← 4 和 3.next ← 2链表变为 1, 3, 2, 4客户端 B 交换 3 和 4通过执行 2.next ← 4、3.next ← null 和 4.next ← 3链表变为 1, 2, 4, 3。当更改同步时Automerge 合并更改方式为每个客户端更改是一个 _事务_合并操作像先应用一个事务写入再应用另一个事务写入Automerge 会确定性选顺序两个客户端会得到相同结果单个写入的任意交错不可能限制了最终可能出现的状态数量。若后一个事务未触及前一个事务写入前一个事务写入保留若两个事务都对某属性写入则后一个事务写入覆盖前一个。看看两种可能顺序的结果。无论哪种情况1.next 来自客户端 A4.next 来自客户端 B但 3.next两个事务都写入取决于哪个事务后执行先 A 后 B3.next null从 1 开始遍历链表结果是“1, 3”链表被截断节点 2 和 4 被孤立先 B 后 A3.next 2从 1 开始遍历链表结果是“1, 3, 2, 4, 3, 2, 4, …”链表包含循环任何遍历该链表的代码将永远不会终止。需强调的是Automerge 没做错两个客户端按承诺确定性收敛到相同结果。问题在于应用客户端 A 更改后再应用客户端 B 的 _写入操作_ 与应用客户端 A 更改后再执行客户端 B 的 _意图_ 不同。客户端 B 基于原始链表 1 → 2 → 3 → 4 计算写入操作合并后该状态已不存在。若客户端 B 的“交换 3 和 4”操作在客户端 A 更改后实际执行会生成不同写入操作得到正常链表。合并操作只是重放操作效果而非意图且程序员定义的不变性每个节点只出现一次、没有循环、链表有结尾未以 Automerge 能识别的方式记录下来。所以仅实现收敛是不够的。问题不只是出在链表上可通过不使用 next 指针构建链表避免特定问题。Automerge 有内置数据类型合并语义良好如数组对象模型直接使用能以预期方式合并并发插入和删除操作各种类型映射也易表示。在系统核心的图形框架 Morphic 中大量依赖这些特性Morphic 起源于 Self 编程语言详见 [Maloney 等人的文章](https://dl.acm.org/doi/10.1145/215585.215636)后用于 Squeak 和 Dan 的 Lively Kernel。在 Morphic 中屏幕上看到的一切是一个 _变形体morph_ 即能包含其他变形体的对象直到按钮和文本。每个变形体的 submorphs 列表是 Automerge 数组两个用户的并发添加操作可很好交错。但组合这些数据类型时情况不同而编程中常发生这种情况合并操作对整个事务排序仍盲目重放写入操作所以任何跨越多个属性或对象的不变性对它不可见比如双向链表next 和 prev 必须对应、树结构Morphic 本身是例子每个变形体的 owner 必须与其所有者的 submorphs 一致两个用户同时对同一变形体重新父级操作可能破坏规则、必须与所汇总集合一致的缓存计数或索引、任何元素只能出现一次的约束。在 LM 系统中堆就是文档鼓励用户构建喜欢的数据结构这不是边缘情况而是正在积极思考的问题。不过问题出现频率比预期低。通过谨慎编程依赖 Automerge 内置数据类型避免使用可能产生不一致的冗余表示已能构建日常多用户使用表现良好的系统当然谨慎编程不是解决方案而是等待解决方案时的做法。我们看好的方向支持合并的数据类型目前合并操作在原始对象图层面进行低于程序员实际关心的抽象层面。根据分析自然做法是合并 _意图_ 而非编译后的写入操作。要注意意图不是“将 3.next 设置为 null”甚至不是“交换 3 和 4”后者仍是实现方式只是层次稍高。意图应是程序员在抽象类型层面表达的内容如“从列表中移除这个值”“将这个值插入到那个值之后”。Automerge 已在某些方面采用这种方式但仅适用于内置类型。对 Automerge 列表的更改以插入和删除 _操作_ Automerge 实际术语形式记录在文档历史中而非指针写入形式这就是对这些列表的并发编辑能很好合并的原因。所以有个想法若 Automerge 提供类似列表、类似映射、类似计数器的 _类型_ 概念让程序员定义的数据结构能声明属于这些类型会咋样呢文档内部表示方式可由程序员决定但读写操作通过类型接口进行记录为操作的是类型高级词汇。这样合并操作意味着合并这些操作每种类型的合并语义只需定义一次。若程序员能定义全新类型而非仅使用内置类型那就更好了。有先例表明对于非平凡类型可严格实现这一点Kleppmann 等人的 [复制树的移动操作](https://martin.kleppmann.com/papers/move-op.pdf) 直接将“重新父级操作不会创建循环”规则融入合并过程。该算法背后技术可广泛应用按单一确定性顺序如按时间戳重放每个人的操作重放中检查每个操作是否违反不变性跳过违反不变性的操作。因每个客户端以相同顺序重放相同操作收敛性自然实现且不变性通过构造得到保证[ECRO](https://dl.acm.org/doi/10.1145/3485484) 也是基于此想法构建的系统。不过这不是完美解决方案执行时有效的操作可能在时间戳较低的操作延迟到达时被追溯判定为无效用户可能看到之前接受的工作被回滚。对于用户定义类型还有更广泛开放性问题类型操作必须可交换或有确定方法解决不可交换情况但目前不清楚系统如何帮助程序员满足甚至检查这一要求。并非只有他们在探索该领域。Martin Kleppmann、Vincent Liu、Owen Lynch 及其合作者在 [Coln](https://coln-project.github.io/) 项目中直接解决此问题。Coln 是可合并的数据库有定义模式、查询和迁移的强大语言。在 Coln 中可对数据声明约束如“这是一个双向链表”且对违反约束情况处理严格若合并操作破坏约束合并将被拒绝必须由用户或人工智能将数据恢复到满足约束状态后才能合并。Martin 的 [《收敛》阅读列表](https://queue.acm.org/detail.cfm?id3546931) 是了解不变性和协调之间关系的好切入点。若对问题有想法或有更好解决方案欢迎交流下期预告在下一篇笔记中将详细介绍让上述内容落地的对象模型即如何让一个 Automerge 文档看起来和感觉起来像普通的 JavaScript 堆包括对象表、代理、垃圾回收等。