crudite

CRDT库。

要求

• 即使在大量数据结构上也能保持高性能
• 允许同步大量数据结构的一部分
• 允许任意数据结构，具有结构化的树形表示
• 有表示、插入和拼接文本的方式
• 自行提供网络代码，但CRDT算法不需要中央服务器

备注

从简单的opset crdt开始，没有拼接

待办事项

• 实现操作线性化
• 添加CRDT测试
• 实际的op/edit/crdt结构，结合opsets和jsontree
• 将数字类型添加到json树
• 完成Edit的更新fn
• 在数组之前清理代码
  • 测试字符删除，确保段合并
  • 检查段无法合并但达到零长度的案例
  • 将段代码移入单独的模块，正确测试段
  • 实际上不需要删除段，直到我们有了垃圾回收
• 将数组类型添加到json树
• 移动对象需要一些工作；需要检查循环，需要从上一个父对象中删除项目。也许可以将此修复与孤儿系统结合起来。
• 为访问列表/字符串项目提供更直观的API，更新测试
• 重写测试以仅使用公共API
• 需要跟踪父对象；您不需要删除以重新添加，这使得从同一位置多次移动不会正确组合。

未来工作

• 当前，DocOp的apply忽略了错误的ID。这是否正确？如何防止恶意ID的重用？中央服务器验证？
• 对恐慌和其他错误进行模糊测试
• 垃圾回收
• 选择子树同步
• 拼接操作？
• 也许编辑实际上不是ord，找出编辑的ID系统，以便我们可以删除它们？这将允许我们也有浮点数。
• 找出所有树删除的真实成本。我们能否在旧编辑插入oplist早期或当object_assign删除大子树时加快或推迟删除？

GC备注

• 我们还可以在特定时间点“冻结”文档状态，这被称为“基线”。一些基于用户的CRDT人员认为这是不必要的，因为用户编辑的数据并不大。但是，有一个整个数据库都是CRDT的，这会很好。这可能导致太多的编辑。同步整个历史是不可能的。
• 考虑到我们可以在操作树中的特定点序列化文档状态，我认为我们可以将基线T时的文档状态传递给新客户端，并且只需要在时间线上发送自T以来发生的编辑。
• 然而，由于离线模式的异步性，我们无法确保所有客户端都已看到T。那么我们该怎么办呢？我对于有一个中央服务器来跟踪所有编辑感到满意，而不仅仅是自T发生以来的垃圾收集的编辑。也许这个中央服务器可以操作变换地修改稍后发生的编辑？不幸的是，这遇到了经典的OT性能问题 O(N^2)，其中 N 是每个不同站点中的更改数量。opset CRDT算法允许我们在算法的早期插入字符，并可以在 ~O(N) 的时间复杂度下合并，假设操作处理是常时间的。
• 也许我们可以更新一个站点的基线。中央服务器承担 O(N) 成本来运行新的编辑到基线 T，形成一个新状态 T'。然后它与 T 和 T' 进行比较，并将差异发送到使用 T 的任何站点，这些站点将这些更改应用于其基线。比较差异是一个昂贵的操作吗？它可以被做得更便宜吗？我们可以在运行新的编辑到基线期间跟踪任何被编辑的东西，将其视为脏的，然后只比较这些？