PHP实现协同编辑：基于RGA的CRDT原理与实战

多人同时编辑同一个文档光标互不干扰、文字不互相覆盖这在今天看起来是再普通不过的产品能力。但真到了自己动手实现的时候你会发现“两个人同时往同一行里塞一句话”这件事远比想象的棘手。我之所以会去研究 CRDTConflict-free Replicated Data Type无冲突复制数据类型是因为团队知识库产品需要实时协同编辑能力而后端技术栈偏偏是 PHP。调研了一圈OTOperational Transformation算法太复杂自己写容易出边界问题Yjs 很成熟但它是 Node 生态为这个功能单独起一套 Node 服务运维成本和心智负担都不小。最终我们决定在 PHP 侧实现一套基于 RGAReplicated Growable Array的 CRDT 核心配合 WebSocket 做同步通道。整个过程踩了不少坑也有几个“原来如此”的时刻。这篇文章就把从原理到落地的完整过程整理出来给同样是 PHP 技术栈、又有协同编辑需求的团队一个可参考的路线。无论你是后端工程师还是全栈只要想在不更换技术栈的前提下获得协同编辑能力这篇都值得认真读完。1. 先弄懂 CRDT 到底解决什么问题1.1 协同编辑的并发冲突谜题先说一个最经典的场景协作文档里原本有一段话“我喜欢吃苹果”用户 A 把光标放在“苹果”前面输入“红”用户 B 同时把光标放在“苹果”前面输入“青”。两个人都希望最终结果是“ 红苹果”和“青苹果”的某种组合而不是某一方被覆盖。传统方案遇到这个问题通常会选择三种路加锁编辑时把整个文档锁住其他人只能等。体验极差多人协作直接变排队。LWWLast Write Wins谁的时间戳更晚听谁的。实现简单但会丢操作——总有一个用户的输入被悄悄抹掉。OTOperational Transformation把每次编辑抽象成一个操作在服务端做转换。Google Docs 早期用的就是这个。能解决并发但算法复杂状态一多维护成本直线上升。CRDT 给了第四种思路所有副本都可以自由修改不需要跟“中心节点”商量也不存在“谁覆盖谁”的问题。它从数学上保证只要每个副本最终接收到同样的变更集合无论以什么顺序合并结果必然一致。用大白话说——永远不用担心合并出错误结果。这个特性非常契合协同编辑节点离线了也能编辑联网后自动同步合并两个用户的并发修改都能保留下来而不是靠时间戳互相踩踏。1.2 基于操作与基于状态两条技术路线怎么选CRDT 本身分成两大类理解这个对后续工程选型很重要CmRDT基于操作副本之间广播的是操作本身比如“insert(id, value, origin)”“delete(id)”。前提是网络传输需要可靠、有序、无重复否则会出现状态分叉。适合 RPC、消息队列这类通道比较可控的场景。CvRDT基于状态副本之间同步的是整个状态或者说把对方的“全部家底”拿来和本地合并。它不要求消息有序只要网络最终连通合并一定会收敛。代价是单次传输的数据量可能变大。维度CmRDT基于操作CvRDT基于状态同步单位操作日志全量/增量状态网络要求可靠、有序、去重最终可达即可实现难度中等但要处理消息乱序相对简单但状态体积可能大典型场景OT、消息队列式协作分布式数据库、离线优先应用我在 PHP 项目里选了CvRDT状态合并。原因很实际我们的同步通道是 WebSocket Redis做不到严格的消息顺序保证。比如用户断网重连服务器无法精准重放他没收到的每一条 op除非为每个客户端维护游标但直接把当前状态发送过去、让客户端做一次 merge逻辑上就简单多了。1.3 为什么说 PHP 也能做 CRDT很多人的第一反应PHP 不是只能“请求进来-处理-返回”吗这种常驻内存的实时任务它能行吗答案是能行关键别用传统 PHP-FPM 思路写。我们用的是Swoole 常驻内存模式利用它的 WebSocket Server 保持长连接文档状态直接放在 worker 进程内存里。这样做有一个额外好处CRDT 的合并操作是 CPU 密集和内存密集型工作PHP 底层是 C 实现处理几万字级别的文档完全不是问题。实测下来合并一个 1000 节点左右的 RGA 树耗时基本在毫秒级别。再加上 PHP 的数组和对象操作非常灵活用 PHP 写树状数据结构的原型速度反而是所有语言里最快的。等以后真的需要更高性能核心合并逻辑也是一个独立的类直接改写成 Go 或 C 迁移成本很低。2. 从计数器到文本树核心数据结构逐个拆2.1 最小的 CRDTG-Counter 和 PN-Counter要说最直观的 CRDT计数器当之无愧。G-CounterGrow-only Counter只能递增设计极其简单每个副本维护一个数组数组下标是副本 ID值是该副本递增的次数。合并时逐位取最大值。class GCounter { private array $counts []; // [replicaId count] public function inc(string $replicaId): void { $this-counts[$replicaId] ($this-counts[$replicaId] ?? 0) 1; } public function merge(self $other): void { foreach ($other-counts as $replicaId $count) { if ($count ($this-counts[$replicaId] ?? 0)) { $this-counts[$replicaId] $count; } } } public function value(): int { return array_sum($this-counts); } }为什么合并要取最大值而不是直接加总因为如果直接相加同一个副本的递增操作在网络重传或重复合并时会被重复计算CRDT 要求合并操作必须幂等。取最大值天然满足这个约束。但 G-Counter 不能减只能增。实际业务里我们大多需要“可增减的计数”于是就有了PN-Counter用两个 G-Counter 分别存正数和负数最终值就是增加计数减掉减少计数。这个结构在设计思路上给我们的启发是CRDT 不解决所有业务问题但可以通过组合基础结构来覆盖更多场景。2.2 集合类G-Set 与 OR-Set如果计数器是加减法那集合就是“有或无”。G-SetGrow-only Set只允许添加元素合并就是取并集。它没法删除实用性有限。真正常用的是OR-SetObserved-Removed Set。OR-Set 的精髓在于“删除不是真的删除”。每个元素在加入集合时附带一个唯一的 tag比如 UUID删除时不是把元素本身抹掉而是把这个 tag 加入一个“删除墓碑”集合。合并时如果某个元素的 tag 存在于任意一方的删除集中就把这个元素标记为不存在。class ORSet { private array $added []; // tag value private array $removed []; // tag 1 public function add(string $value): void { $tag bin2hex(random_bytes(16)); $this-added[$tag] $value; } public function remove(string $value): void { foreach ($this-added as $tag $v) { if ($v $value) { $this-removed[$tag] 1; } } } public function merge(self $other): void { foreach ($other-added as $tag $value) { $this-added[$tag] $value; } foreach ($other-removed as $tag $unused) { $this-removed[$tag] 1; unset($this-added[$tag]); } } public function values(): array { return array_values($this-added); } }这个“删除墓碑”设计几乎是整个 CRDT 思路里最关键的一步。它告诉我们一个反直觉的事实为了最终删除得干净必须先保留一些“删除的证据”。后面要做协同文本删除靠的就是同一套思想只是从“元素集合删除”变成了“节点树剪枝”。2.3 协同编辑的主角RGA 序列数据结构CRDT 家族里文本编辑需要的是“序列”语义——既要保持字符顺序又要支持任意位置插入和删除。RGAReplicated Growable Array是其中的经典结构。RGA 把文档看成一棵树每个节点是一个字符也可以是一个块级元素节点里包含id全局唯一 ID由“副本 ID 自增序列号”组成value字符内容origin前驱节点 ID也就是插入时“这个字符被插在哪个字符后面”deleted是否已被标记删除插入时生成新节点挂在 origin 节点后面。如果同一个 origin 下面插入了多个并发节点靠比较 ID 决定它们之间的先后顺序。我最初搞混了一个地方为什么文档是线性的却要搞成树实际上这就是 RGA 的高明之处。把“谁插在谁后面”存下来合并的时候才能确定各个并发节点的相对位置。如果只存一个数组下标A、B 同时插入同一个位置下标瞬间就冲突了。存“前驱关系”相当于把插入的因果依赖显式保留下来位置自然稳定。2.4 为什么选 RGA 而不是 YATA 或 WOOT关于 CRDT 文本结构市面上还有 WOOT、YATA 等方案。我的选型理由如下WOOT最早被提出的文本型 CRDT基于偏序关系理论扎实但实现偏重节点之间的约束关系复杂跑起来性能一般。YATAYjs 的底层算法处理并发插入的“避让”机制很成熟无 tombstone 设计让它内存占用有优势。但文档相对复杂而且围绕 JS 生态设计我需要在 PHP 里重写一套。RGA结构简单直观合并算法只用“比较 ID 插入到对应位置”在文档规模 10 万字以下性能完全够用且论文资料非常充分。对 PHP 技术栈来说RGA 是性价比最高的选择。它不是最强的但是最容易“用 PHP 写对”的。3. PHP 侧完整实现插入、删除与合并代码实操3.1 整体架构与数据模型设计我先把架构图摊开来说客户端浏览器通过 WebSocket 连接 Swoole 服务端服务端每台 Swoole worker 内存中维护若干个 Document 对象同步通道Redis Pub/Sub 做跨 worker 的消息转发MySQL 定期存全量快照每个 Document 对象内部就两个核心成员一个 RgaTree节点树一个 VersionVector用于记录各个副本的同步进度。数据模型代码如下class Document { public string $docId; public RgaTree $tree; public VersionVector $version; public function applyNode(Node $node): void { $this-tree-insertNode($node); $this-version-record($node;); } public function mergeDocument(Document $remote): void { foreach ($remote-tree-getAllNodes() as $node) { $this-tree-insertNode($node); } $this-version-merge($remote-version); } }这里没有神秘技巧就是把“合并”简化为“把对方的每个节点都试图插到本地树里”。结果收敛的核心正是insertNode里排序规则的确定性。3.2 节点 ID 生成策略别踩全局时钟的坑节点 ID 是 RGA 排序的第一依据生成策略必须慎重。我最初的版本用了microtime(true) . random_int()结果并发测试一跑排序不稳定原因是微秒时间戳在高并发下没有单调性随机数又加剧了不确定性。后来改成“副本 ID 本地自增序号”?php function generateNodeId(string $replicaId, int $seq): string { // 例如 replica_7f3a 1024 return $replicaId . _ . $seq; }规则副本 ID 用短 UUID 前缀比如r7f3a保证所有客户端全局唯一自增序号是每个副本本地单调递增的比如 1、2、3、4ID 拼接后是字符串比较时用字符串比较保证总序关系稳定对比 ID 的时候我们只看 ID 本身不看“谁的时间更晚”。也就是说RGA 的排序逻辑不是“后写入的排前面”而是按 ID 的大小关系排。这也是它能避免依赖全局时钟的关键。3.3 插入、删除与定位的完整实现核心的insertNode方法长这样class RgaTree { private array $nodes []; private string $rootId root; // 虚拟头节点 public function insertNode(Node $node): void { // 1. 节点已存在则直接返回保证幂等 if (isset($this-nodes[$node-id])) { return; } // 2. 如果前驱节点还没插入先递归/排队插入前驱节点 $originId $node-origin ?? $this-rootId; if ($originId ! $this-rootId !isset($this-nodes[$originId])) { $this-pending[] $node; return; } // 3. 找到前驱节点扫描它的后代找到合适插入位置 $pos $this-findInsertPosition($originId, $node-id); $this-nodes[$node-id] $node; array_splice($this-sequence, $pos, 0, [$node]); } private function findInsertPosition(string $originId, string $newId): int { $index array_search($originId, array_column($this-sequence, id)); $cursor $index 1; while ($cursor count($this-sequence)) { $candidate $this-sequence[$cursor]; if ($candidate-origin ! $originId) { break; } if (strcmp($newId, $candidate-id) 0) { break; } $cursor; } return $cursor; } public function deleteNode(string $id): void { if (isset($this-nodes[$id])) { $this-nodes[$id]-deleted true; } } }几个容易卡住的细节幂等性合并过程中同一个节点可能被多次 insert必须先判存在。这也正是 CRDT 合并规则里“幂等”要求。前驱未就绪网络同步时可能会先收到一个“儿子”节点它的“父亲”还没收到。这很正常先放进 pending等前驱节点插入后再补插。删除只标 tombstone删除时只把deleted置为 true不真删除节点。为什么因为其他副本可能还没见过这个节点直接删除会让它们后续同步时误以为这是一个新插入最终导致幽灵字符。3.4 合并算法细节保证穷尽同步后必然收敛文档同步最核心的问题两个副本各自插入了一批节点merge 之后为什么必然得到同一个文档先看一个简单例子。基础文本是 “A”副本 X 插入节点X1位置在 A 后面。副本 Y 也插入节点Y1位置同样在 A 后面。合并时两个副本都执行以 A 为前驱尝试插入 X1再以 A 为前驱尝试插入 Y1插入次序不同但结果的 AB 顺序是确定的A的后续节点排序按strcmp(X1, Y1)来决定。也就是说无论先处理谁的节点只要比较规则一致最终排列顺序一定相同。再看一个更复杂的例子X 在 A 后面插入 X1随后又在 X1 后面插入 X2Y 在 A 后面插入 Y1。合并时树的结构变成了A - X1 - X2A - Y1X1 和 Y1 是 A 的两个并发后继按 ID 排序。X2 挂在 X1 后面属于 X1 的因果后代。这样整棵树的遍历结果就是一个确定性的线性文档。反复 merge 多次只要树里每个节点的“前驱”和“ID”不变遍历结果永远一样。这就是 RGA 收敛的全部秘密——不存在全局时钟不依赖消息顺序只依赖每个节点自带的结构化信息。合并函数还要处理一个分支如果同一批节点在两个副本上有着不同的 origin 记录怎么办这是非常罕见的错误数据但是规范起见要把 origin 也作为合并冲突的一部分来校验。如果 origin 不一致以本地已有节点为准并且记一条日志便于排查数据篡改或协议 bug。3.5 同步协议与持久化WebSocket 通道和快照压缩服务端与客户端的同步消息我用的是紧凑 JSON{ type: sync, docId: doc_123, version: { r7f3a: 1024, r9c2d: 2048 }, nodes: [ { id: r7f3a_1024, origin: r9c2d_2048, value: 红, deleted: false } ] }客户端发来的编辑指令在服务端 merge 后广播给房间内其他客户端服务端合并完立即更新内存中的版本向量定时任务比如每 30 秒把整个 Document 对象快照写入 MySQLfield 用 JSON 序列化关于持久化有个点必须提醒不要频繁全量序列化。节点一多JSON 序列化耗时几十毫秒还要占用内存做字符串拷贝。建议在后台异步任务里做或者用 RedisRDB的快照机制做临时缓存再由一个消费者进程落库。tombstone 的积累是个隐患。文档长期编辑后大量已删除节点仍然停留在内存里。压缩的方法当所有活跃副本的 VersionVector 都已经大于等于某个 tombstone 节点产生的版本时说明没有任何副本还依赖这个节点来定位前驱此时可以物理删除它。这个策略在实现上不难但要注意在压缩前必须确认所有客户端都已离线或已完成同步否则可能造成后到的客户端补不全历史。4. 踩坑实录PHP 做 CRDT 的几个隐藏注意点4.1 PHP 字符串排序的稳定性陷阱CRDT 合并的正确性极度依赖节点 ID 的排序一致性。PHP 的排序函数如sort()默认是SORT_REGULAR对“数字字符串”和“字母字符串”的处理很微妙。我的经验是全部手写比较函数不要依赖 PHP 内置的排序默认行为usort($nodes, function ($a, $b) { return strcmp($a-id, $b-id); });strcmp用的是 PHP 内部二进制安全字符串比较不会受到 locale 的影响结果稳定。如果采用 ID 里混着整数和字母的格式更要小心8.0 之前的 PHP 会把“10”排在“9”前面这种细节足以让合并不收敛还特别难排查。4.2 json_encode 引起的 ID 精度丢失这是一个我险些没发现的坑。node ID 如果用的是 PHP 整数类型json_encode在 64 位系统上没问题但一旦 ID 超过PHP_INT_MAX在 32 位或某些特殊环境下就会转成 float序列化后精度丢得一塌糊涂。规避方案很简单ID 一律用字符串。即使只包含数字也写成1024而不是1024。字符串在 JSON 中不会发生精度变化跨语言比如将来迁移到 Go时也能保证一致。4.3 WebSocket 重连时全量同步还是增量同步客户端重连时第一反应是“把整个文档状态发过去”。这个方案实现最快但当文档膨胀到几 MB 时体验会很差。我最终采用的是“版本向量增量同步”客户端带上自己最后的 version vector服务端找出所有大于该版本的节点 ID 集合只把缺的节点发给客户端这要求服务端为每个 Document 维护一份节点变更日志op log。这个日志不需要永久保留只需要覆盖足够长的回溯窗口。如果客户端落后太多比如离线了一周日志已经被清理那就回退到全量快照同步。两种方式互为兜底实际效果最稳。4.4 常驻进程的内存泄漏与 GCSwoole 常驻内存模式下最大的敌人是内存只增不减。PHP 的引用计数在普通 request 生命周期中会自动清理但常驻 worker 里如果一个对象被全局变量引用崩溃级的内存泄漏不至于但 GC 不及时是常有的。我们早期版本在做频繁 merge 时内存会持续上涨原因不是 PHP 泄漏而是大量对象在循环内互相引用gc_collect_cycles()没有被触发。解决办法是每处理完一批消息主动调用一次gc_collect_cycles()每一个节点对象在用完后unset($node)释放局部引用定期重启空闲的 worker兜底处理一切意外状态对于 PHP 程序员来说这些操作平时不太需要关心但一旦做常驻服务就得把内存当成一等公民来管理。4.5 并发模拟与收敛性测试CRDT 最容易出的问题是“看起来没问题稍微复杂并发一下就不收敛”。所以测试脚本一定要写而且要模拟随机插入、删除、交换顺序同步。我建议的测试思路开 N 个副本每个副本随机执行 200 次插入/删除操作每个副本的操作顺序随机然后将这些操作以随机顺序 merge 到同一个目标断言最终结果的字符序列完全一致这个测试脚本不复杂但价值极高。一旦哪次 merge 不完全收敛它会立刻暴露比任何单元测试都好使。我在实际测试中就靠它捉到过 3 个隐蔽 bug。一个典型 bug 是节点 A 已存在于序列中但它的 origin 节点被本地删除了结果 findInsertPosition 去数组里搜索 origin 时一无所获导致插入位置为 0整个文档乱套。4.6 常见问题速查表问题现象根因解决办法合并后出现“幽灵字符”tombstone 被物理删除了但其他副本还不知道压缩 tombstone 前必须确认所有副本同步进度两个客户端并发插入同一位置顺序乱跳ID 使用了时间戳随机数改用“副本 ID 自增序列号”并使用 strcmp序列化后再同步ID 变成 1.234E...整数 ID 超出 PHP_INT_MAX 转 floatID 全部用字符串不要用 int服务端内存暴涨对象循环引用未回收定期 gc_collect_cycles unset 局部引用重连后文本缺字增量同步时版本向量判断有误用“大于本地版本”的集合而不是“不等于”合并 10000 个节点耗时过高每次循环都 array_search 扫描全序列为节点维护 origin - 后续节点索引5. 实操总结与后续扩展思路做这轮 CRDT 方案我最深的体会有两点。第一CRDT 不是银弹但它是目前解决协同冲突最优雅的数学保证。它不需要服务端实时协调不依赖消息顺序天然支持离线编辑。文档合并的收敛性不是靠“计谋”而是靠数据结构本身的代数性质这让系统变得非常可靠。如果你需要的只是简单“多人同时编辑一个 JSON 或文本”CRDT 比 OT 更容易在团队内落地。第二PHP 完全可以扛起协同编辑的服务端重担。很多人对 PHP 的认知停留在“Web 框架”阶段但实际上Swoole 常驻模式 合理的类设计足以支撑小到中型团队的知识库、编辑器、白板等场景。关键是别把 CRDT 合并逻辑跟 HTTP 请求生命周期绑在一起而是把它设计成独立的内存对象让同步协议只管分发和接收状态。后续如果继续扩展我会优先做三件事Undo/Redo 支持CRDT 的 undo 一直是难点需要对每个操作生成逆操作还要注意版本向量的变化需要单独设计。多层级块元素支持现在只处理了文本字符如果要支持段落、图片、表格等块级元素RGA 树的节点需要增加类型字段和子列表引用。端到端加密因为状态合并是纯数据操作理论上可以对节点 value 加密后再同步服务端只负责 merge不感知内容这是很多企业级场景的硬需求。最后分享一个调试小技巧真出问题的时候别急着上断点先在insertNode开头加一句日志打印当前节点 ID、origin、本地树中 origin 是否存在、插入位置。大多数并发不一致问题看日志一眼就能定位。这个习惯救了我很多次。