记录 Region Diff 开发中的一些思考

背景

今年 4 月份的时候突然很想玩 Minecraft，跟群友商量过后决定开一个游戏服务器，服务器搭建在群友的 PC 上。

为了方便群友白嫖，服务器没有开启正版验证，也就是说任何人都可以进入存档并造成不可逆的破坏。为了防止群友的心血毁于一旦，我提议对存档进行备份，但是此时存档的大小已经有 2-3GB 左右了，PC 的硬盘空间也只有几百 GB，即使每小时备份一次、删除 48 小时前的备份，造成的空间占用也不能接受。

经过简单的分析，发现存档体积占用的 99% 都集中在 *.mca 文件，而后者的解析有非常多的社区文档。此外一个非常明显的结论是玩家正常游玩对游戏存档产生的影响是非常局限的。

后期测试发现，一个玩家在单个 .mca 文件中连续玩 6 天（每天 5 小时），所生成的差分文件大小仅为 600KB，而对应的 .mca 文件大小为 8000KB。

在这个背景下，我决定开发一个简单的命令行工具，对占用空间较大的 *.mca 文件提供差分支持。

项目已经开源到 GitHub。

差分

给定两个序列 S1 和 S2，他们的差分 D 满足以下性质：

• 把 D 应用到 S1 上可以得到 S2
• 把 D 应用到 S2 上可以得到 S1

这里有一个平凡的实现：差分存储 A 和 B 的完整信息，输入 A 时输出 B，输入 B 时输出 A。

当然也有一些更高效的实现，比如 LCS、Myer’s、Patience 等。这里使用比较主流的 Myer’s Diff 算法。

为了实现类似 git rebase -i 中的 squash 操作，我自己设计了一个简单的 squash 算法。

定义差分的 squash 操作：给定两个序列 S1, S2, S3，计算 S1 到 S2 的差分 D12、S2 到 S3 的差分 D23，令 D13 := squash(D12, D23)，此时 D13 满足以下性质：

• 把 D13 应用到 S1 上得到 S3
• 把 D13 应用到 S3 上得到 S1

经过调研没有发现合适的 squash 算法实现，于是花了几天时间写了一个，代码点这里。

利用文件结构加速差分计算

我们现在需要对文件做差分。一个非常 naive 的想法是参考 git diff 命令，使用 Myers Diff 算法对每个文件的二进制内容生成差分。

Myers Diff 算法的时间复杂度是 O(ND)，在最坏情况下，两个序列完全不同，此时 N=D，时间复杂度退化为 O(N^2)。对于 Git 的应用场景，这点时间开销是完全可以接受的，但是对于以 MB 计量的数据，时间开销非常客观，估算可以达到若干天。

然而每个区块的数据都是可解析的结构化数据，可以理解成 JSON，我们可以采用分而治之的思想对 JSON 里的一些瓶颈字段做单独的差分操作，这样问题规模就降低了很多。

这里说的很简单，但是在工程上有很多细节，比如利用时间戳跳过差分、利用 xyz 坐标提供的结构化信息等。

多线程的负载均衡

每个 .mca 文件都包含 1024 个区块数据，这些数据都是独立且只读的，因此可以使用多线程实现并行计算。然而区块的计算量服从幂律分布，也就是有少数区块占用了大部分计算时间。如果不能合理地把计算负载分配给 worker，那么在一段时间后，一些线程的总工作量较少提前返回了，而少数几个线程还在运行，导致 CPU 资源不能高效利用，所谓“一核有难，七核围观”。

第一版的实现使用 rayon 库的 .par_iter()，它会把工作负载序列均分为 n 等分，交给 n 个线程处理，某个线程处理完后会窃取其他线程的工作。当时我还没意识到有工作窃取的机制，还测试了对工作负载序列洗牌能不能提升性能，效果微乎其微。

假设我们有两个线程，任务的开销分别是 1, 1, 5, 1, 1, 1，那么线程在不同时刻处理的任务的甘特图如下：

1
2

thread-1  1 1 5 5 5 5 5
thread-2  1 1 1

为了让这些线程的工作量尽量相同，第二版的实现我们让不同的线程去争抢任务。因为要同步处理的进度，这个方法会比上一个方法产生更多的锁开销。甘特图如下：

1
2

thread-1  1 5 5 5 5 5
thread-2  1 1 1 1

可以看到确实有一些改善，但是线程 2 还是有两个 tick 的空闲时间。如果线程 1 能在一开始就处理开销为 5 的任务，那么正好能让两个线程同步返回：

1
2

thread-1  5 5 5 5 5
thread-2  1 1 1 1 1

这也是第三版的实现——预先估算任务的开销，并降序排序任务序列，这样能最大地平衡各个线程的工作量。