尧图网页设计 
xi-editor 并发编辑的 CRDT 之道从 Rope Science 到 Rust 引擎中的 tombstone 实现【免费下载链接】xi-editorA modern editor with a backend written in Rust.项目地址: https://gitcode.com/gh_mirrors/xie/xi-editor导读本文基于 xi-editor 官方文档 rope_science_08.md 展开深入讲解 xi-editor 为何放弃传统的操作变换Operational TransformOT路线、转而采用 Conflict-free Replicated Data TypesCRDT来处理异步插件与输入法带来的并发编辑问题并揭示文档中空 / 已填充 / 已删除三态 cell 与 tombstone墓碑思想在 rust/rope/src/engine.rs 中的真实落地。读完本文你将掌握 CRDT 解决文本并发编辑的核心模型单调半格、坐标变换、tombstone、垃圾回收以及 xi-editor 中Engine::edit_rev、Engine::merge等核心接口的设计逻辑与调用关系。背景为什么异步插件需要并发编辑xi-editor 希望让插件以异步方式运行给插件留出一点思考时间尤其是程序深层分析这类耗时的任务但同时又不能牺牲键入的响应速度。文档开篇就点出了三类本质上都是并发编辑的场景异步插件插件在后台对缓冲区发起编辑与用户键入并发输入法input method输入法产生的文本提交本质上也是并发编辑大文件异步加载把大文件分块追加到缓冲区末尾同样是一种并发编辑且绝不能落入不一致状态。如果把所有编辑操作都当作同步操作处理实现会简单很多但 xi-editor 想做得更好。文档引用了 Xoogler Joseph Gentle 对 OT 的著名抱怨实现 OT 很痛苦。有一百万种算法、各有不同的取舍大多困在学术论文里正确实现又难又耗时……Wave 花了两年才写完今天重写一遍几乎还要花同样长的时间。OT 之所以难根源在于删除操作会丢失状态详见下文三态 cell的分析。而 CRDT 提供了一条不同的路径通过可交换、单调的更新操作让不同来源的编辑无论以何种顺序应用最终都能收敛到相同结果。与 OT 相比CRDT 通常被放在对等网络peer-to-peer语境下讨论网络分区、节点失效、移动设备长时间离线。xi-editor 的优势在于——编辑器核心是快速且可靠的并发规模有限因此可以借用 CRDT 的思想实现一个足够简单却做对事情的方案。简化假设先只增不删再引入预言机为了让问题容易起步文档提出两个高度简化的假设然后再逐步放宽只增加文本从不删除存在一个预言机oracle能预先知道每个字符在编辑会话结束时最终落在字符串的哪个位置。在只增不删的假设下编辑操作几乎平凡把文本表示为一组 cell单元格的序列编辑操作就是把某个 cell 的内容从空变为某个字符。熟悉 CRDT 理论的读者立刻能认出这就是一个单调半格monotonic semi-lattice更新操作显然可交换commutative——无论按什么顺序应用更新都能得到相同结果。预言机当然不现实但关键在于一个洞见只要知道增量delta让任意两个快照对齐是相当容易的。快照在概念上是最终字符串的一个视图其中一些 cell 为空、一些不为空。两个快照对比时有一部分 cell 共同填充、一部分只在一边填充、另一部分只在另一边填充快照的表示就是已填充 cell 的拼接。对齐两个快照本质上是找出一个坐标变换coordinate transform让所有共同填充的 cell 对齐。插入的坐标变换与 gap buffer 异曲同工以在某个点插入一段序列为例所有小于插入点的坐标保持不变大于插入点的坐标全部加上插入序列的长度。文档指出这个坐标变换和 gap buffer间隙缓冲区所做的几乎一样。而恰好落在插入点上的坐标是个有趣的情况最合理的处理方式是基于是谁发起的插入来做 tie-breaking平局裁决。例如自动缩进插件添加的空格应当排在用户键入的字符之前因为这样能更忠实地维持自动缩进插件快得无限的假象。这一点在 xi 引擎源码中得到了精确实现rust/rope/src/engine.rs中定义了#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq)] struct FullPriority { priority: usize, session_id: SessionId, }用于对并发插入排序。在mk_new_rev中针对基准版本之后的所有并发插入会以new_full_priority full_priority决定transform_expand(inserts, after)的先后engine.rs 第 368-376 行。Contents::Edit的注释也写明priority用于排序并发插入例如自动缩进应当排在键入文本之前undo_group则把相关编辑聚为一组使得自动缩进插入能与触发它的换行符一起被撤销engine.rs 第 133-141 行。提交请求时的坐标变换把上述机制落到具体流程上文档给出了一个非常简洁的模型一个 actor用户或插件发起编辑请求——即相对于它自己持有的缓冲区快照在某个点插入一段序列。核心core随后提交该请求而提交时可能需要做一次坐标变换以处理在这期间即当前状态与插件所引用快照之间到达的其他编辑。换句话说插件基于旧版本base_rev提交 delta核心把它 rebase 到当前 head 上再应用。这正是Engine::try_edit_rev所做的工作。三态 cell删除如何保持可交换性只增不删显然不现实。最直接的删除方式从缓冲区中删除序列并做同类坐标变换这次减去被删子序列的长度会毁掉可交换性——整个模型随之崩塌这也是 OT 变得无比复杂凌乱的根源。CRDT 的关键洞见是给每个 cell 三个状态——空empty、已填充filled、已删除deleted——并且每次更新只能沿这些状态向前单向推进就能重新获得单调的更新操作。数学上这又是一个单调半格。在具体实现中把 span 保留在共享状态里但标记为已删除这些保留的已删除片段就是所谓的 tombstone墓碑渲染到屏幕之前再真正过滤掉它们。xi 引擎正是这样实现的。Engine结构体engine.rs 第 43-74 行包含text: Rope——当前文档内容即屏幕上显示的内容tombstones: Rope——存放所有已被删除、但撤销删除或重做插入时可能重新出现的字符deletes_from_union: Subset——设想一条并集字符串union string包含所有曾插入的字符包括后来被删除的deletes_from_union表示其中当前处于删除状态、因此存在于 tombstone 而非 text 中的子集每个字符的计数代表它被删除的次数若一个字符被并发删除两次则计数为 2这样撤销其中一次删除时字符不会错误地重新出现。也就是说并集字符串可以由text、tombstones和deletes_from_union重构凡是在deletes_from_union中计数非零的区段就把tombstones中的对应片段拼接回text。这一设计与文档的保留 span、标记删除、渲染前过滤完全对应。在提交新编辑时mk_new_revengine.rs 第 342-424 行核心流程包括将 delta 分解为插入部分与删除部分delta.factor()把 delta rebase 到基准版本对应的并集上transform_expand再 rebase 到 head 并集上期间对每个并发插入按FullPriority裁决先后应用插入得到新 text再通过shuffle函数把被删除或已被撤销的插入从 text 移入 tombstoneengine.rs 第 401-406 行。shuffle与shuffle_tombstonesengine.rs 第 704-732 行专门负责基于新的/旧的删除集合在 text 与 tombstones 之间搬运片段。可选优化tombstone 的垃圾回收与撤销的权衡墓碑如果永远保留会无限膨胀因此文档提出可以加上某种垃圾回收GC来清理被移除的 span。在编辑器中可以合理假设并发规模很小——大多数正常操作下缓冲区会经常进入 quiesce无待处理编辑状态此时最简单的情况下可以直接把 span 删掉。但文档也敏锐地指出一个权衡实践中可能需要保留一部分已删除 span 用于撤销——如果撤销一次删除你确实希望被删文本出现在相对于其上下文的同一位置。即便如此在途编辑的数量足够小完全可以用非常简单的算法比如以 20 为界O(n²) 甚至 O(n³) 都没问题。xi 引擎实现了gc方法engine.rs 第 552-651 行对已撤销的 undo group把其插入/删除从并集中收缩并从tombstones中真正删除dels_from_tombstones.delete_from(self.tombstones)。而在上层editor.rs 的gc_undos采用延迟 GC只有当revs_in_flight 0没有任何在途插件编辑时才真正执行 GC否则先挂起——注释明确写着CRDT 引擎的 GC 会延迟到所有插件都确认新 rev 之后editor.rs 第 178-183 行。值得一提的例外是 Fuchsia 平台#[cfg(target_os fuchsia)]分支下永不执行 GC因为要保证对端不会使last_rev_id失效、且merge始终可用editor.rs 第 292-296 行。异步插件如何接入这套模型文档描述的 actor 模型插件基于自己的快照提交编辑、核心做坐标变换后提交在 xi 中落地为一条清晰的调用链插件构造PluginEdit携带rev、delta、priority、undo_group、author等字段核心调用Editor::apply_plugin_editeditor.rs 第 232-243 行解包后调用engine.try_edit_rev(priority, undo_group, rev, delta)成功后把self.text更新为引擎新 head每次用户编辑则通过commit_delta提交editor.rs 第 249-274 行它调用try_delta_rev_head计算出从上一已确认 rev 到当前 head的 delta并同步给前端。try_edit_revengine.rs 第 447-462 行是核心入口它调用mk_new_rev构造新Revision含rev_id、max_undo_so_far、Edit { priority, undo_group, inserts, deletes }然后更新text、tombstones、deletes_from_union并追加历史。如果插件引用的base_rev已被 GC 或不存在会返回Error::MissingRevision若 delta 的base_len与基准版本长度不符则返回Error::MalformedDelta。editor.rs的测试plugin_editeditor.rs 第 759-781 行演示了完整流程基于hello获取 head rev构造在位置 0 插入s的PluginEditpriority 55连续应用两次后断言缓冲区变为sshello——证明基于同一旧 rev 的多个异步编辑被正确 rebase 并叠加。从单机异步到对等编辑Engine::merge文档最后展望如果将来需要真正扩展到大规模协作编辑CRDT 文献中有丰富技术可供借鉴。而 xi 引擎实际上已经实现了完整的 CRDT merge/// Merge the new content from another Engine into this one with a CRDT merge pub fn merge(mut self, other: Engine) { ... }engine.rs 第 653-681 行其思路是找到两个引擎历史的分叉点find_base_index找出共同 revision把两侧各自从分叉点之后的 revision 重新排列rearrange再以compute_deltas把对方的新内容 rebase 到本方并集上合并。模块头注释对此有明确总结engine.rs 第 15-29 行本模块在Engine::edit_rev下实现了一个迷你 CRDT比常规 CRDT 实现技术简单得多因为所有操作都在这个中心引擎中被串行化。它提供的能力是应用那些基于先前已提交版本而非当前版本的编辑这对每个异步插件至多一个在途编辑的场景已经足够。此外在Engine::merge下还有完整的 CRDT 合并操作更强大但也更复杂可支持完整的异步甚至对等peer-to-peer编辑。编辑的身份由RevId标识96 位 session id 32 位序号即使在 rebase 或设备间合并后也保持不变engine.rs 第 78-90 行上层Editor::merge_new_state调用engine.merge后同步 head 文本与撤销组editor.rs 第 298-304 行。文档的学术脉络CRDT 概念从哪里来文档末尾附上了作者的阅读脉络这些资源虽然不在仓库内但构成了理解本设计的必要背景Marc Shapiro 2011 年在微软研究院的演讲解释 CRDT 概念及其底层的单调半格数学基础WOOT 论文2006协作编辑领域早期 CRDT 代表作擅长与 OT 对比作者明确表示不会照搬其实现细节《A comprehensive study of Convergent and Commutative Replicated Data Types》2011综述 state-based 与 operation-based 两种 CRDT 实现路径的对偶性并对 WOOT、TreeDoc 等协作文本编辑应用做了回顾把它们略显复杂的实现细节放进干净的数学框架。作者还提到差分同步differential synchronization是值得探索的分支但断言在协作编辑技术史上它终将被 merge 冲突吞没。读完这些材料后作者的结论是CRDT 框架清晰地告诉你——让 OT 真正工作需要让更新操作可交换、之所以难是因为删除操作丢失状态、而让生活变简单的方法是保留删除状态、事后做某种 GC。这与本文前述的 tombstone 机制互为表里。结语简单源于核心快且可靠这一前提贯穿全文的核心论点是xi-editor 之所以能用非常简单的实现处理并发编辑是因为它利用了核心快速可靠 并发规模有限这两个前提。在这种前提下坐标变换退化为 gap buffer 式的平移加上基于身份的 tie-breaking删除通过三态 cell 与 tombstone 保持单调性与可交换性GC 可以在缓冲区 quiesce 时用简单算法完成必要时为撤销保留少量墓碑每个异步插件至多一个在途编辑中心引擎串行化所有操作即可实现迷你 CRDT。而一旦未来真的需要扩展例如用于真正的协作编辑Engine::merge的存在表明仓库已经为此预留了完整的 CRDT 合并能力。文档作者的原话是感觉几天内就能做出原型而不是从零开始打 OT 这场持久仗——这个判断在今天的源码中已经得到了验证。深入阅读原始文档docs/docs/rope_science_08.mdCRDT 引擎实现rust/rope/src/engine.rsEngine、try_edit_rev、merge、gc、shuffle/shuffle_tombstones上层集成与插件编辑入口rust/core-lib/src/editor.rsapply_plugin_edit、commit_delta、merge_new_state及plugin_edit测试本系列其他篇章docs/docs/rope_science_00.md 至 docs/docs/rope_science_12.mdCRDT 在分布式存储中的背景补充docs/docs/fuchsia-ledger-crdts.md【免费下载链接】xi-editorA modern editor with a backend written in Rust.项目地址: https://gitcode.com/gh_mirrors/xie/xi-editor创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 xi-editor 并发编辑的 CRDT 之道：从 Rope Science 到 Rust 引擎中的 tombstone 实现
xi-editor 并发编辑的 CRDT 之道从 Rope Science 到 Rust 引擎中的 tombstone 实现【免费下载链接】xi-editorA modern editor with a backend written in Rust.项目地址: https://gitcode.com/gh_mirrors/xie/xi-editor导读本文基于 xi-editor 官方文档 rope_science_08.md 展开深入讲解 xi-editor 为何放弃传统的操作变换Operational TransformOT路线、转而采用 Conflict-free Replicated Data TypesCRDT来处理异步插件与输入法带来的并发编辑问题并揭示文档中空 / 已填充 / 已删除三态 cell 与 tombstone墓碑思想在 rust/rope/src/engine.rs 中的真实落地。读完本文你将掌握 CRDT 解决文本并发编辑的核心模型单调半格、坐标变换、tombstone、垃圾回收以及 xi-editor 中Engine::edit_rev、Engine::merge等核心接口的设计逻辑与调用关系。背景为什么异步插件需要并发编辑xi-editor 希望让插件以异步方式运行给插件留出一点思考时间尤其是程序深层分析这类耗时的任务但同时又不能牺牲键入的响应速度。文档开篇就点出了三类本质上都是并发编辑的场景异步插件插件在后台对缓冲区发起编辑与用户键入并发输入法input method输入法产生的文本提交本质上也是并发编辑大文件异步加载把大文件分块追加到缓冲区末尾同样是一种并发编辑且绝不能落入不一致状态。如果把所有编辑操作都当作同步操作处理实现会简单很多但 xi-editor 想做得更好。文档引用了 Xoogler Joseph Gentle 对 OT 的著名抱怨实现 OT 很痛苦。有一百万种算法、各有不同的取舍大多困在学术论文里正确实现又难又耗时……Wave 花了两年才写完今天重写一遍几乎还要花同样长的时间。OT 之所以难根源在于删除操作会丢失状态详见下文三态 cell的分析。而 CRDT 提供了一条不同的路径通过可交换、单调的更新操作让不同来源的编辑无论以何种顺序应用最终都能收敛到相同结果。与 OT 相比CRDT 通常被放在对等网络peer-to-peer语境下讨论网络分区、节点失效、移动设备长时间离线。xi-editor 的优势在于——编辑器核心是快速且可靠的并发规模有限因此可以借用 CRDT 的思想实现一个足够简单却做对事情的方案。简化假设先只增不删再引入预言机为了让问题容易起步文档提出两个高度简化的假设然后再逐步放宽只增加文本从不删除存在一个预言机oracle能预先知道每个字符在编辑会话结束时最终落在字符串的哪个位置。在只增不删的假设下编辑操作几乎平凡把文本表示为一组 cell单元格的序列编辑操作就是把某个 cell 的内容从空变为某个字符。熟悉 CRDT 理论的读者立刻能认出这就是一个单调半格monotonic semi-lattice更新操作显然可交换commutative——无论按什么顺序应用更新都能得到相同结果。预言机当然不现实但关键在于一个洞见只要知道增量delta让任意两个快照对齐是相当容易的。快照在概念上是最终字符串的一个视图其中一些 cell 为空、一些不为空。两个快照对比时有一部分 cell 共同填充、一部分只在一边填充、另一部分只在另一边填充快照的表示就是已填充 cell 的拼接。对齐两个快照本质上是找出一个坐标变换coordinate transform让所有共同填充的 cell 对齐。插入的坐标变换与 gap buffer 异曲同工以在某个点插入一段序列为例所有小于插入点的坐标保持不变大于插入点的坐标全部加上插入序列的长度。文档指出这个坐标变换和 gap buffer间隙缓冲区所做的几乎一样。而恰好落在插入点上的坐标是个有趣的情况最合理的处理方式是基于是谁发起的插入来做 tie-breaking平局裁决。例如自动缩进插件添加的空格应当排在用户键入的字符之前因为这样能更忠实地维持自动缩进插件快得无限的假象。这一点在 xi 引擎源码中得到了精确实现rust/rope/src/engine.rs中定义了#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq)] struct FullPriority { priority: usize, session_id: SessionId, }用于对并发插入排序。在mk_new_rev中针对基准版本之后的所有并发插入会以new_full_priority full_priority决定transform_expand(inserts, after)的先后engine.rs 第 368-376 行。Contents::Edit的注释也写明priority用于排序并发插入例如自动缩进应当排在键入文本之前undo_group则把相关编辑聚为一组使得自动缩进插入能与触发它的换行符一起被撤销engine.rs 第 133-141 行。提交请求时的坐标变换把上述机制落到具体流程上文档给出了一个非常简洁的模型一个 actor用户或插件发起编辑请求——即相对于它自己持有的缓冲区快照在某个点插入一段序列。核心core随后提交该请求而提交时可能需要做一次坐标变换以处理在这期间即当前状态与插件所引用快照之间到达的其他编辑。换句话说插件基于旧版本base_rev提交 delta核心把它 rebase 到当前 head 上再应用。这正是Engine::try_edit_rev所做的工作。三态 cell删除如何保持可交换性只增不删显然不现实。最直接的删除方式从缓冲区中删除序列并做同类坐标变换这次减去被删子序列的长度会毁掉可交换性——整个模型随之崩塌这也是 OT 变得无比复杂凌乱的根源。CRDT 的关键洞见是给每个 cell 三个状态——空empty、已填充filled、已删除deleted——并且每次更新只能沿这些状态向前单向推进就能重新获得单调的更新操作。数学上这又是一个单调半格。在具体实现中把 span 保留在共享状态里但标记为已删除这些保留的已删除片段就是所谓的 tombstone墓碑渲染到屏幕之前再真正过滤掉它们。xi 引擎正是这样实现的。Engine结构体engine.rs 第 43-74 行包含text: Rope——当前文档内容即屏幕上显示的内容tombstones: Rope——存放所有已被删除、但撤销删除或重做插入时可能重新出现的字符deletes_from_union: Subset——设想一条并集字符串union string包含所有曾插入的字符包括后来被删除的deletes_from_union表示其中当前处于删除状态、因此存在于 tombstone 而非 text 中的子集每个字符的计数代表它被删除的次数若一个字符被并发删除两次则计数为 2这样撤销其中一次删除时字符不会错误地重新出现。也就是说并集字符串可以由text、tombstones和deletes_from_union重构凡是在deletes_from_union中计数非零的区段就把tombstones中的对应片段拼接回text。这一设计与文档的保留 span、标记删除、渲染前过滤完全对应。在提交新编辑时mk_new_revengine.rs 第 342-424 行核心流程包括将 delta 分解为插入部分与删除部分delta.factor()把 delta rebase 到基准版本对应的并集上transform_expand再 rebase 到 head 并集上期间对每个并发插入按FullPriority裁决先后应用插入得到新 text再通过shuffle函数把被删除或已被撤销的插入从 text 移入 tombstoneengine.rs 第 401-406 行。shuffle与shuffle_tombstonesengine.rs 第 704-732 行专门负责基于新的/旧的删除集合在 text 与 tombstones 之间搬运片段。可选优化tombstone 的垃圾回收与撤销的权衡墓碑如果永远保留会无限膨胀因此文档提出可以加上某种垃圾回收GC来清理被移除的 span。在编辑器中可以合理假设并发规模很小——大多数正常操作下缓冲区会经常进入 quiesce无待处理编辑状态此时最简单的情况下可以直接把 span 删掉。但文档也敏锐地指出一个权衡实践中可能需要保留一部分已删除 span 用于撤销——如果撤销一次删除你确实希望被删文本出现在相对于其上下文的同一位置。即便如此在途编辑的数量足够小完全可以用非常简单的算法比如以 20 为界O(n²) 甚至 O(n³) 都没问题。xi 引擎实现了gc方法engine.rs 第 552-651 行对已撤销的 undo group把其插入/删除从并集中收缩并从tombstones中真正删除dels_from_tombstones.delete_from(self.tombstones)。而在上层editor.rs 的gc_undos采用延迟 GC只有当revs_in_flight 0没有任何在途插件编辑时才真正执行 GC否则先挂起——注释明确写着CRDT 引擎的 GC 会延迟到所有插件都确认新 rev 之后editor.rs 第 178-183 行。值得一提的例外是 Fuchsia 平台#[cfg(target_os fuchsia)]分支下永不执行 GC因为要保证对端不会使last_rev_id失效、且merge始终可用editor.rs 第 292-296 行。异步插件如何接入这套模型文档描述的 actor 模型插件基于自己的快照提交编辑、核心做坐标变换后提交在 xi 中落地为一条清晰的调用链插件构造PluginEdit携带rev、delta、priority、undo_group、author等字段核心调用Editor::apply_plugin_editeditor.rs 第 232-243 行解包后调用engine.try_edit_rev(priority, undo_group, rev, delta)成功后把self.text更新为引擎新 head每次用户编辑则通过commit_delta提交editor.rs 第 249-274 行它调用try_delta_rev_head计算出从上一已确认 rev 到当前 head的 delta并同步给前端。try_edit_revengine.rs 第 447-462 行是核心入口它调用mk_new_rev构造新Revision含rev_id、max_undo_so_far、Edit { priority, undo_group, inserts, deletes }然后更新text、tombstones、deletes_from_union并追加历史。如果插件引用的base_rev已被 GC 或不存在会返回Error::MissingRevision若 delta 的base_len与基准版本长度不符则返回Error::MalformedDelta。editor.rs的测试plugin_editeditor.rs 第 759-781 行演示了完整流程基于hello获取 head rev构造在位置 0 插入s的PluginEditpriority 55连续应用两次后断言缓冲区变为sshello——证明基于同一旧 rev 的多个异步编辑被正确 rebase 并叠加。从单机异步到对等编辑Engine::merge文档最后展望如果将来需要真正扩展到大规模协作编辑CRDT 文献中有丰富技术可供借鉴。而 xi 引擎实际上已经实现了完整的 CRDT merge/// Merge the new content from another Engine into this one with a CRDT merge pub fn merge(mut self, other: Engine) { ... }engine.rs 第 653-681 行其思路是找到两个引擎历史的分叉点find_base_index找出共同 revision把两侧各自从分叉点之后的 revision 重新排列rearrange再以compute_deltas把对方的新内容 rebase 到本方并集上合并。模块头注释对此有明确总结engine.rs 第 15-29 行本模块在Engine::edit_rev下实现了一个迷你 CRDT比常规 CRDT 实现技术简单得多因为所有操作都在这个中心引擎中被串行化。它提供的能力是应用那些基于先前已提交版本而非当前版本的编辑这对每个异步插件至多一个在途编辑的场景已经足够。此外在Engine::merge下还有完整的 CRDT 合并操作更强大但也更复杂可支持完整的异步甚至对等peer-to-peer编辑。编辑的身份由RevId标识96 位 session id 32 位序号即使在 rebase 或设备间合并后也保持不变engine.rs 第 78-90 行上层Editor::merge_new_state调用engine.merge后同步 head 文本与撤销组editor.rs 第 298-304 行。文档的学术脉络CRDT 概念从哪里来文档末尾附上了作者的阅读脉络这些资源虽然不在仓库内但构成了理解本设计的必要背景Marc Shapiro 2011 年在微软研究院的演讲解释 CRDT 概念及其底层的单调半格数学基础WOOT 论文2006协作编辑领域早期 CRDT 代表作擅长与 OT 对比作者明确表示不会照搬其实现细节《A comprehensive study of Convergent and Commutative Replicated Data Types》2011综述 state-based 与 operation-based 两种 CRDT 实现路径的对偶性并对 WOOT、TreeDoc 等协作文本编辑应用做了回顾把它们略显复杂的实现细节放进干净的数学框架。作者还提到差分同步differential synchronization是值得探索的分支但断言在协作编辑技术史上它终将被 merge 冲突吞没。读完这些材料后作者的结论是CRDT 框架清晰地告诉你——让 OT 真正工作需要让更新操作可交换、之所以难是因为删除操作丢失状态、而让生活变简单的方法是保留删除状态、事后做某种 GC。这与本文前述的 tombstone 机制互为表里。结语简单源于核心快且可靠这一前提贯穿全文的核心论点是xi-editor 之所以能用非常简单的实现处理并发编辑是因为它利用了核心快速可靠 并发规模有限这两个前提。在这种前提下坐标变换退化为 gap buffer 式的平移加上基于身份的 tie-breaking删除通过三态 cell 与 tombstone 保持单调性与可交换性GC 可以在缓冲区 quiesce 时用简单算法完成必要时为撤销保留少量墓碑每个异步插件至多一个在途编辑中心引擎串行化所有操作即可实现迷你 CRDT。而一旦未来真的需要扩展例如用于真正的协作编辑Engine::merge的存在表明仓库已经为此预留了完整的 CRDT 合并能力。文档作者的原话是感觉几天内就能做出原型而不是从零开始打 OT 这场持久仗——这个判断在今天的源码中已经得到了验证。深入阅读原始文档docs/docs/rope_science_08.mdCRDT 引擎实现rust/rope/src/engine.rsEngine、try_edit_rev、merge、gc、shuffle/shuffle_tombstones上层集成与插件编辑入口rust/core-lib/src/editor.rsapply_plugin_edit、commit_delta、merge_new_state及plugin_edit测试本系列其他篇章docs/docs/rope_science_00.md 至 docs/docs/rope_science_12.mdCRDT 在分布式存储中的背景补充docs/docs/fuchsia-ledger-crdts.md【免费下载链接】xi-editorA modern editor with a backend written in Rust.项目地址: https://gitcode.com/gh_mirrors/xie/xi-editor创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考