CRDT

Swift 语言中基于 ∂-state 的无冲突复制数据类型 (CRDT) 的实现。

此库将广为人知的基于状态的 CRDT 实现为 Swift 泛型，有时也称为收敛复制数据类型 (CvRDT)。 该实现包括 delta-state 复制功能，可以在协作端点之间同步时实现更紧凑的表示形式。另一种方法是为每次同步复制整个状态。

CRDT API 文档托管在 Swift Package Index 上。

• G-Counter (只增计数器)
• PN-Counter (正负计数器)
• LWW-Register (后写入优先寄存器)
• G-Set (只增集合)
• OR-Set (观察删除集合，具有后写入优先添加偏差)
• OR-Map (观察删除映射，具有后写入优先添加或更新偏差)
• List (因果树列表)

有关 CRDT 的更多信息，Wikipedia 上关于 CRDT 的页面 非常好。 我还建议访问网站 CRDT.tech，这是一个出色的资源集合。此库中的实现主要基于 Nuno Preguiça、Carlos Baquero 和 Marc Shapiro (2018) 在 无冲突复制数据类型 中描述的算法，并受到 ReplicatingTypes 包的强烈影响/源自该包，该包由 Drew McCormack 创建，并在许可（MIT）下使用。

Drew 代码中最显著的两个变化是

• 始终将用于识别协作实例（无论是人、进程还是机器）的类型公开为泛型类型
• 添加显式的 delta-state 传输机制，因此您无需传输整个 CRDT 实例到另一个位置即可合并数据。

与 ReplicatingTypes 包一样，此包根据 MIT 许可证提供，您可以随意使用，只需承认它是源自这里即可。

如果您的目标是创建 local-first 软件，那么此实现是一个好的开始，但（在我看来）对于这些需求来说并不完整。 特别是，没有包含任何序列化优化，这些优化可以减少将实例完整序列化以进行存储时所需的空间。 也没有任何其他库（例如 Automerge 或 Yjs）中包含的优化，这些优化可以改善支持更长篇幅的协作文本交互所需的内存开销。

这些限制将来可能会改变，欢迎贡献。

CRDT 的其他 Swift 实现

• https://github.com/appdecentral/replicatingtypes
  • 相关文章： Swift 中的无冲突复制数据类型 (CRDT)
• https://github.com/bluk/CRDT
• https://github.com/jamztang/CRDT
• https://github.com/archagon/crdt-playground
  • 相关文章： 与历史交织的数据：因果树和操作 CRDT
• Objc.io 视频系列： CRDT – 简介

用于协作文本编辑的两个非常成熟的 CRDT 库

• Automerge
  • (视频) CRDT：困难的部分，作者：Martin Kleppmann)
• Y.js (及其多语言端口 Y-CRDT)
  • Yrs 数据结构内部： https://bartoszsypytkowski.com/yrs-architecture/

讨论权衡、算法细节和性能的文章，特别是对于基于序列的 CRDT

• Delta-state CRDT：具有 YATA 的索引序列
• 5000 倍速 CRDT：一次优化冒险
• CRDT：困难的部分
  • CRDT：困难的部分视频

运行库

swift run -c release crdt-benchmark library run Benchmarks/results.json --library Benchmarks/Library.json --cycles 5 --mode replace-all
swift run -c release crdt-benchmark library render Benchmarks/results.json --library Benchmarks/Library.json --output Benchmarks

当前基准测试

在 ExternalBenchmarks 目录下还有使用 package-benchmark 的桩基准测试。 这些额外的基准测试主要是一维的，并且确实需要安装额外的库 (jemalloc) 才能运行。 如果您只是想探索，则此存储库中的 .devContainer 设置包含该库 - 因此很容易从 VSCode 和 Docker 中进行试用。 要探索一维外部基准测试

cd ExternalBenchmarks
swift package benchmark