• 这个 Bug 出现在我试图用 Loro 来导入整个 Git Repo 的时候出现。分析了好几个小时最终才定位到 Bug，希望以后不要再有这种体验了，浅浅记录一下。
• 这 Bug 是以让人一头雾水的形态出现的。
• 首先背景是 Loro 支持记录 DAG 的操作历史结构，于是我想让它能够支持同步整个 Workspace 的内容，像 Git 一样。于是我这样设计：
  • 根文档：是一片 Loro Doc，内部用 Tree 的结构存储“目录”信息。它会保存整个仓库的 Git 历史，但它不会记录每个文件的具体修改，而是记录这些文件修改前后的具体版本。具体方式是把每个文件夹和文件都当作 CRDT Tree 上的一个节点，这个节点会有 name 信息，是否是文件夹的信息，以及到它内容的指针；如果它是纯文本文档就会用 CRDT 文档的方式记录，并且会记录它的版本信息
  • 内容指针：一个 Workspace 内的内容分成两种，一种是 CRDT 文档（用于同步纯文本信息），一种是二进制文件；所以在内容指针上也分成两种，分别指向不同的内容。
  • 纯文本 CRDT 文档：会在自己的 CRDT 文档的 DAG 保存自己这个文件的完整的编辑历史
  • 二进制文件：对于所有没办法转成合法 utf8 的内容都会直接用覆盖方式进行更新
• 最开始报的错误是根文档中 CRDT Tree 上的节点的 name 没有被设置。为了检查这个问题，我把所有对节点初始化的操作收束到一起，让它一定会在初始化的时候就设置好 name。但是无济于事，还是会有这个错误。加了相关的 Log 之后，发现这个节点 ID 就是被设置过 name。
• 会不会是因为出现了重复的 Peer ID 导致了呢？在导入 Git Repo 过程中，有时有些情况会允许我们重用 Peer ID，所以做了一些优化。但这个 bug 的出现让我对这些优化都产生了不自信，于是把它们关了，但是 bug 依旧存在。
• 我还继续检查了是不是 rename/copy 导致的错误，会不会是 delete 导致的错误。但都一一排除了。
• 会不会是因为我加了能够在单文档的不同版本上进行编辑的能力 https://github.com/loro-dev/loro/pull/473 之后出了错？这个功能会不会和现有的 Tree 内部的设计的 Invariants 产生冲突了？但思来想去没有想到合理的解释。
• 那还有一种可能性是我最不愿意考虑的：loro 内部的 bug 导致当前状态错误。Loro 老的版本中不支持在 detached 模式下进行编辑，有可能因为它的加入导致有些以前没考虑过的 corner case 被暴露出来。我们切换版本的时候往往都是根据版本之间的差异计算完成的，如果这里的差异计算出错，那么文档的状态就可能会错误。检查这种错误的最简便的方法就是回放历史，从而就能对比确认当前版本的状态复合从头开始回放文档计算出来的状态。
• 于是我在会出现找不到 name 的情况的位置加了确认 state 正确性的检查，结果发现真的是这里出错！正确的文档上是不存在这个节点的，我们恰好多了一个节点。那就是 Loro 内部的错误，之前没有被暴露出来。于是我先进行了下面的检查
  • 如果 DiffCalculator 不用复杂的优化会不会出错
  • 看看多出来的节点是不是曾经被删除过 - 不是
  • 确认 Consistency Check 本身的代码是不是正确的
  • 确认 Loro 现在是能够通过本身自己的所有内部测试的
  • Frontiers 转 VersionVector 和 VV 转 Frontiers 的实现是正确的
  • (感慨如果能通过 Log 直接生成测试用例来回放现场就好了，复现起来挺麻烦的
  • 测试了 Tree 的内部 State 的 Invariants 的正确性
• 上面这些检查都没有发现问题
• 随后的一个突破点来自添加了更多的 log 之后发现，出问题的那个节点它的节点 ID 大于当前的文档的 Version Vector，也就意味着这个节点在一次版本切换中本来应该被 Revert 掉的，结果没有发生这个 Revert。于是就顺着这个线索找问题。
• 我们的文档状态可以理解为是通过 Diff Calculator 来完成更新的，Diff Calculator 会通过事件告诉文档需要进行什么样的更新。随后我发现事件中存在这个文档的创建事件，但不存在 Revert 事件。那就意味着 Tree 相关的 Diff Calculator 上出问题了，Tree State 不背这个锅。
• 那到 Tree Diff Calculator 这一侧，它就是一棵保存了树的相关操作历史的树，当发生版本切换的时候就在它上面执行这些切换操作计算出 InternalDiff，然后交给 State 完成更新。这部分的代码相关的 invariants 很多，但是相关的自动检查不多，于是就加了一波检查，然后又再是读日志分析问题，把一些可能有问题的优化去掉，看看病症有没有好起来。
• 最后定位到了是一处优化上错误的过滤了 ops，导致有一个本应该被记录到 tree 中的 op 没有被记录，从而导致后续计算错误才产生了这个问题。将这个优化去掉之后整体就恢复正常了。

教训

• 目前 Fuzz 的覆盖率还不够高，没有覆盖到刚刚那种场景，未来要加强 Fuzz 的覆盖率
• Tree Diff Calculator 内部的 Invariants 需要加更多的检查来保证行为正确性
• 要引入一些机制让 State 错误更容易暴露出来
  • 例如提供对状态的 Hash，落盘前对内容做一次 Hash，在版本切换的时候检查 Hash 正确性
  • 在合适的时机做完整性检查