[RFC] 新增量更新（OTA）格式

[dantmnf]

issue 正文：

设计目标

减少增量更新的数据量（存储+传输）

基础格式

pax tar 带压缩

压缩要求

• 分为多个可独立解压的分块，分块之间支持无损连接，即 a.gz+b.gz 可以不经任何后续处理直接解压出 a+b。
• 配合索引实现部分解压
• 码流中支持嵌入解压缩时可忽略的内容
  • 用于存放索引

可用实现

• gzip (block-based + comment)
  https://www.rfc-editor.org/rfc/rfc1952.html#page-5
• zstd (frame-based + skippable frame)
  https://github.com/facebook/zstd/blob/release/doc/zstd_compression_format.md#skippable-frames

文件布局

总览

• 文件头：【Zstd skippable frame】或【解压后长度为 0 的 gzip block 中的 comment】
  • Magic signature
  • 清单分块长度
• 清单分块
  • 版本清单
    • 当前版本
  • 增量索引
    • 支持增量更新的版本
    • 后续各个分块的类型、偏移量及长度
• 当前版本压缩分块
  • 增量清单（二进制 patch 清单、删除文件清单）
  • 当前版本更新且无二进制增量的文件（如 *.png）
  • n-1版本到当前版本的二进制增量（如 MAA.exe）
• n-1版本压缩分块
  • 增量清单
  • n-1版本更新且无二进制增量的文件
  • n-2版本到n-1版本的二进制增量
• ……
• n-x版本压缩分块
  • 增量清单
  • n-x版本更新且无二进制增量的文件
  • n-x-1版本到n-x版本的二进制增量
• 后备分块（可选）
  • 当前版本更新且有二进制增量的文件
  • 先前版本更新的文件

更新时删除文件

删除的文件列表存放在增量清单内。

Corner Case

为确保完整解压时不会出现当前版本已删除的文件，不打包中间版本之间新增后删除的文件，即不能通过增量更新包更新到中间版本。

二进制增量更新

增量清单内存放：

• 需要 patch 的文件路径
• patch 数据在压缩包内的名称
• patch 类型
• patch 前后的文件长度及检验和
• patch 后版本

patch 后版本可以是新版本方向的任意版本，生成增量更新包时寻找体积最小的组合。

Corner Case

需要 patch 的文件与某一更新版本一致时，使用特殊 patch 类型标记且不存储 patch 数据。

实现

https://github.com/facebook/zstd/wiki/Zstandard-as-a-patching-engine

% zstd -19 --patch-from b495a16/MAA.exe 2428a46/MAA.exe -o MAA.exe.b495a16-2428a46
long mode automatically triggered
2428a46/MAA.exe :  0.25%   (  40.0 MiB =>    103 KiB, MAA.exe.b495a16-2428a46)

using ZstdSharp;


var dec = new Decompressor();
dec.LoadDictionary(File.ReadAllBytes(@"b495a16/MAA.exe"));
var a = dec.Unwrap(File.ReadAllBytes(@"MAA.exe.b495a16-2428a46"));
File.WriteAllBytes(@"2428a46/MAA.exe", a.ToArray());

效果

• 从n-3版本更新到当前版本，只需要根据索引下载n-3版本分块前的数据，即n-3更新到n-2、n-2更新到n-1、n-1更新到当前版本
  由于文件头包含清单长度，使用标准 HTTP Range request 时最多产生三个 GET 请求，允许中断一个完整 GET 请求时只需要一个请求。
• 完整解压含有后备分块的更新包文件，可获得当前版本
• 对于每个更新通道，服务端仅需保留最新的增量更新包

其他设计

ZIP 格式

• 不合并文件数据压缩，压缩率低
• 需要从文件尾读取 central directory，或完全依赖外部索引
• 外部索引也可以通过 SFX 方式放在 zip 头部，但功能跟 central directory 重复
• 通过后处理将 central directory 移到头部
  • 兼容性成谜
  • 数据格式定义语焉不详
  • central directory 空间效率低
    • 当前 MAA zip 包的 central directory 约 600 KiB
    • 如需继续扩展以存储元数据，则 central directory 将会包含大量重复文本且无法压缩（central directory compression 未见有开源实现，兼容性问题++）
• Zip - How not to design a file format.

未解决的问题

非线性版本历史（如 Cherry-pick）

例：

---
config:
  gitGraph:
    mainBranchName: alpha
    showCommitLabel: false
---
gitGraph
    
    branch release
    commit tag: "release-0" type: HIGHLIGHT
    checkout alpha
    commit tag: "alpha-1"
    checkout release
    merge alpha tag: "beta-1" type: HIGHLIGHT
    checkout alpha
    commit
    commit tag: "alpha-2"
    checkout release
    merge alpha tag: "release-2" type: HIGHLIGHT
    checkout alpha
    commit
    commit id: "fix" tag: "alpha-3" type: REVERSE
    checkout release
    cherry-pick id: "fix"  tag: "release-2.1"
    checkout alpha
    commit
    commit tag: "alpha-4"
    checkout release
    merge alpha  tag: "beta-4" type: HIGHLIGHT
    checkout alpha
    commit tag: "alpha-5"

Loading

暂定方案：
本分支版本按时间排序后，非本分支版本寻找位置插入，使得按顺序加权后的总文件变化数量最小。

更新包内的文件级索引

预期用途：修复单个损坏的文件。

结论：谁啊，不认识。

解压时增量清单及二进制增量数据 entry 的处理

增量更新程序不将增量清单及二进制增量数据提取到文件系统。

对于手动解压的情况，二进制增量数据在压缩包内的路径使用约定的临时目录，首次运行时删除。

游戏资源热更

是否也使用此方式，作为独立更新通道更新？

[AnnAngela]

不管怎么说，支持 zstd patching

[dantmnf]

@horror-proton @ABA2396 来看看这几个未解决的问题 😶

[dantmnf]

使用最近五个版本做测试，增量体积最小的是 good old bsdiff

[dantmnf]

非线性版本历史的方案：按发布时间排序。

二进制增量的配合修改：
每个起始版本的二进制增量都可以跨越多个版本，存储体积最小的组合。
元数据修改：

• MaaUpdateEngine.1.DeltaType=[bsdiff,zstd,bsdiff-zstd,...]¹
• MaaUpdateEngine.1.DeltaFrom=[version],[size],[hash]
• MaaUpdateEngine.1.DeltaTo=[version],[size],[hash]

Footnotes

1. bsdiff-zstd 指将 BSDIFF4 中的 bzip2 替换为 zstd（警惕 biased benchmark：zstd wiki 中的比较是基于 linux kernel source tarball，包含大量文本压缩） ↩

[horror-proton]

二进制增量的配合修改： 每个起始版本的二进制增量都可以跨越多个版本，存储体积最小的组合。 元数据修改：

也就是说可能在版本之间跳来跳去? 感觉打包和和解压的算法会比较复杂?

是不是还应该假设大部分人都是从比较近的版本更新, 应该保证他们下载更少的分块而不是要跳好几次, 远古版本没什么人用就无所谓了 (

[dantmnf]

版本之间跳来跳去

整体只支持更新到最新版本，二进制差分只支持往前跳多个版本。

比如说要支持 1 2 3 4 5 五个版本更新到 6，可以打包 1-3, 2-3, 3-5, 4-5, 5-6。这样版本 3 更新时还是不会下载到给版本 1 和 2 准备的分块。

至于打包算法，穷举一下（

[horror-proton]

哦只要不会出现 5-3, 3-6 这样反向的就好, 另外如果 5 有 1000 个用户, 4 有 100 个用户, 3 有 10 个用户, 那 3-4, 4-5, 5-6 存储积体积小, 但是 3-4, 4-6, 5-6 总下载量小, 这种情况怎么算, 是不是比较组合的时候还得有个系数之类的 (现在服务器是怎么算费用的来着)

虽然不大知道 TAR 文件级索引是什么意思, 但为啥会需要部分下载, 客户端一般都是只需要整个分块然后下载完了再一起更新吧 (除非是要一边下载一边更新文件?), 下载断了也是继续下载当前分块?

[dantmnf]

为啥会需要部分下载

资源热更只下载缺少的文件什么的，现在再看感觉是个 XY 问题（

[dantmnf]

打包程序：https://github.com/MaaAssistantArknights/UpdateEngine

~~解包程序要先鸽一会了（~~已经搞定了

[dantmnf]

打包解包都做好了，集成继续开鸽！

或者找几个帕鲁来写（