MaaRelease
MaaRelease copied to clipboard
MaaAssistantArknights
[RFC] 新增量更新（OTA）格式
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"
暂定方案： 本分支版本按时间排序后，非本分支版本寻找位置插入，使得按顺序加权后的总文件变化数量最小。
更新包内的文件级索引
预期用途：修复单个损坏的文件。
结论：谁啊，不认识。
解压时增量清单及二进制增量数据 entry 的处理
增量更新程序不将增量清单及二进制增量数据提取到文件系统。
对于手动解压的情况，二进制增量数据在压缩包内的路径使用约定的临时目录，首次运行时删除。
游戏资源热更
是否也使用此方式，作为独立更新通道更新？
非线性版本历史的方案：按发布时间排序。
二进制增量的配合修改： 每个起始版本的二进制增量都可以跨越多个版本，存储体积最小的组合。 元数据修改：
MaaUpdateEngine.1.DeltaType=[bsdiff,zstd,bsdiff-zstd,...][^1]MaaUpdateEngine.1.DeltaFrom=[version],[size],[hash]MaaUpdateEngine.1.DeltaTo=[version],[size],[hash]
[^1]: bsdiff-zstd 指将 BSDIFF4 中的 bzip2 替换为 zstd（警惕 biased benchmark：zstd wiki 中的比较是基于 linux kernel source tarball，包含大量文本压缩）
二进制增量的配合修改： 每个起始版本的二进制增量都可以跨越多个版本，存储体积最小的组合。 元数据修改：
也就是说可能在版本之间跳来跳去? 感觉打包和和解压的算法会比较复杂?
是不是还应该假设大部分人都是从比较近的版本更新, 应该保证他们下载更少的分块而不是要跳好几次, 远古版本没什么人用就无所谓了 (
版本之间跳来跳去
整体只支持更新到最新版本，二进制差分只支持往前跳多个版本。
比如说要支持 1 2 3 4 5 五个版本更新到 6，可以打包 1-3, 2-3, 3-5, 4-5, 5-6。这样版本 3 更新时还是不会下载到给版本 1 和 2 准备的分块。
~~至于打包算法，穷举一下（~~
哦只要不会出现 5-3, 3-6 这样反向的就好, 另外如果 5 有 1000 个用户, 4 有 100 个用户, 3 有 10 个用户, 那 3-4, 4-5, 5-6 存储积体积小, 但是 3-4, 4-6, 5-6 总下载量小, 这种情况怎么算, 是不是比较组合的时候还得有个系数之类的 (现在服务器是怎么算费用的来着)
虽然不大知道 TAR 文件级索引是什么意思, 但为啥会需要部分下载, 客户端一般都是只需要整个分块然后下载完了再一起更新吧 (除非是要一边下载一边更新文件?), 下载断了也是继续下载当前分块?
打包程序：https://github.com/MaaAssistantArknights/UpdateEngine
~~解包程序要先鸽一会了（~~已经搞定了