5000倍更快的CRDT：优化之旅
内容提要
本文讨论了实时协作编辑算法的性能，特别是CRDT（冲突自由复制数据类型）和OT（操作变换）算法。作者指出，某些算法被认为速度慢的原因在于实现细节。通过优化数据结构和算法，CRDT的性能得以显著提升，甚至超过传统文本编辑方式。作者强调了协作编辑的未来潜力，并推荐使用Yjs作为高效解决方案。
延伸解读
性能差异的根源：实现细节而非算法
文章指出，某些CRDT或OT算法被认为慢，往往是因为实现方式不佳，而非算法本身缺陷。例如，有论文将粘贴操作拆分成上千个独立操作，导致性能低下。作者强调，同一算法在不同语言或实现中性能可能相差百倍，因此基准测试结果需谨慎解读，不能简单归因于算法。
Yjs的优化策略：扁平列表与缓存
Yjs通过扁平列表存储所有项目，并缓存最近编辑位置，避免每次全文档扫描。同时，它将连续输入的字符合并为跨度，减少条目数量。这些优化使Yjs在编辑跟踪测试中比Automerge快300倍，内存使用仅为后者的十分之一，且性能不随文档增长而下降。
Rust与B树：进一步突破性能极限
作者用Rust实现了Diamond类型，采用范围树（基于B树）存储项目，支持按字符位置或ID快速查找，插入删除均为对数时间。Rust允许紧凑内存布局，减少碎片和GC开销。在相同编辑跟踪下，Diamond处理260k操作仅需56毫秒，比Yjs快5倍，比Automerge快5000倍。
实际应用中的权衡与建议
尽管Diamond性能卓越，但功能尚不完善，缺乏二进制编码、网络协议等。作者推荐目前使用Yjs，因其性能好、内存低且支持完善。Automerge团队也在改进性能。对于数据库语义或非文本协作场景，CRDT仍面临挑战，需要更多探索。
Q&A
CRDT和OT算法有什么区别？
CRDT（冲突自由复制数据类型）允许多个用户同时编辑同一数据，而OT（操作变换）则依赖于操作的顺序来同步编辑。CRDT不需要中心服务器，能够实现无延迟的本地编辑。
为什么某些CRDT实现速度较慢？
某些CRDT实现速度慢的原因在于实现细节，例如将大文本块拆分为多个小操作，而不是作为一个整体处理，这会导致处理时间显著增加。
Yjs是如何优化CRDT性能的？
Yjs通过使用扁平列表数据结构和缓存机制来优化性能，显著减少内存使用并提高处理速度，使其在协作编辑中表现优异。
作者的Rust实现Diamond类型有什么优势？
作者的Rust实现Diamond类型在性能上超过了Yjs，处理速度更快且内存使用更少，能够在56毫秒内处理260,000次编辑操作。
CRDT的未来潜力是什么？
CRDT的未来潜力在于能够实现高效的实时协作编辑，减少对中心化服务器的依赖，推动去中心化应用的发展。
如何选择适合的CRDT库？
选择CRDT库时应考虑性能、内存使用、文档支持和社区活跃度等因素。Yjs因其良好的性能和文档支持被推荐为优选方案。
