差量更新与bsdiff解读

二进制大文件的差量更新

Posted by Refone on August 11, 2018

意义与应用场景

文件差量更新是常常会遇到的一个场景,最典型的应用场景便是软件的更新。 用户本地的软件更新其本质是对软件文件进行一些增删修改。 软件更新最直接粗暴的方式便是将用户本地不再应该存在的文件删掉;新添加的文件整个让客户下载添加;而对于现有文件的修改,则让客户下载整个修改后的文件,将原文件替换掉。

然而这种更新方式的弊端不言而喻,假设一个大到500M的文件,有10M左右的内容更改(如上图中的D文件),其实我们不需要让客户端下载整整500M的文件。 只要合理地描述这10M左右的改动,再让客户下载这10M左右的元数据,我们就可以大大缩小补丁文件的大小。这就是差量更新。 这在手机软件领域尤其重要,若某天用户在流量环境下打开游戏,发现需要下载更新文件大达500M,相信客户此刻一定是崩溃的。

补丁技术介绍

diffpatch 是一对对应的操作。 diff操作对比两个版本的文件(或文件夹),分别是老文件(oldfile)和新文件(newfile),生成补丁文件(patchfile)。 patch操作则是由老文件和补丁文件生成新文件的过程。 用数学表达式来形容则是:

  • diff:

  • patch

  • 跨版本patch*

    其中 代表版本 到版本 的补丁, 代表版本

bsdiff解读

bsdiff是github上一个开源项目,其功能即是diff两个二进制文件,生成patch文件。

bsdiff的diff过程(略)

bsdiff的diff算法引用的是 Jesper Larsson FASTER SUFFIX SORTING

主要思想是建立老文件的前缀索引,然后扫描新文件,尽可能将新文件内容在老文件中找到相同片段,然后将新文件长为len 的数据片段用的oldposlen来表示,这样将原本需要 字节表示的内容仅需要用2个uint64_t的变量来表示,极大地压缩了patchfile的大小。

Faster Suffix Sorting的细节我没有看太明白,所以这里就不多说了,有兴趣可以去看原版论文。我着重搞清楚了bsdiff的patchfile文件结构,以及怎么从patchfile和oldfile恢复newfile。

bsdiff的patch解读

bspatch是由patchfile和oldfile生成newfile的过程,bspatch的主要流程为:

  1. 读取控制字段。在patch文件中读取三个64bit的控制字符ctrl[0],ctrl[1],ctrl[2]

  2. 构造字段ctrl[0]确定了patchfile中的diff字段长度,也确定了oldfile中原文长度以及新文件中恢复字段的长度 (如下图所示,三个文件中白色字段的长度是相等的)。newfile中恢复字段的每一个byte,由patchfile和oldfile中的对应位置的byte不进位相加得来。例如:

    // 以下皆为十六进制表示
    // old_byte + patch_byte = new_byte
        1 + 7 = 8
        8 + e = 6
    

    如果patchfile对应byte为0,则代表oldfile与newfile对应位置上的byte相等,bsdiff的这一特点使得patchfile可以大幅度被压缩。

  3. 新增字段ctrl[1]确定了patchfile中extra字段的长度,extra字段中的内容,就是基本在oldfile中找不到pattern,需要patchfile给出数据添加的。

  4. 删除字段ctrl[2]确定了oldfile中delete字段的长度,delete字段即为oldfile中被删除的部分,图中可见oldfile灰色字段的内容并没有再出现在newfile中。

至此,newfile中一段内容就生成完毕了,一个newfile的生成会经由这样一个到多个段顺序拼接而成,而每个段在各自文件中的位置,则由patchfile中对应段的ctrl字段唯一确定。

参考资料

[1] bsdiff github

[2] Larsson N J, Sadakane K. Faster suffix sorting[M]. Univ., 1999.

[3] [差量更新系列1]BSDiff算法学习笔记