游戏差异更新—BSDiff算法解析

作者：腾讯云游戏行业资深架构师 张晓愚

为何需要差异更新？

差异更新即在软件更新时只更新差异化的部分，以达到用最小的下载量完成软件的更新需求。该思想由来已久，从刚接触电脑时的操作系统、应用软件快速更新功能或填补漏洞，到迭代更加频繁的移动应用时代更多了节省下载流量费用的需求。尤其在移动游戏领域，随着手机性能的提升和玩家对游戏体验的追求，安装包亦是越来越大，并且会频繁的更新以不断给玩家带来更新的玩法和更为优化的体验。然而，这种频繁的更新也同样会带来负面的影响：更新包太大没流量；更新速度太慢错过了本该用来玩游戏的碎片时间；本地空间不足无法更新等问题，这些负面影响都会导致一定程度上的玩家流失。因此，差异化更新能力目前已成为各应用下载渠道的必备能力之一，更小的更新包才能提高更新的成功率。

差异化更新可分为两种，一种是基于源文件的差异化更新，该种方式成功率高， 算法简单，常用于平台相关的差异更新，但在移动端保存巨大的源文件、下载更新文件整合后再编译的方式显然是不现实的； 另一种即更为广泛使用的方法即对可执行文件的二进制更新方式，本文中即将就该方式下的经典算法BSDiff进行详细介绍。

普通二进制文件对比

熟悉Linux的同学提到二进制文件对比自然会想到一个命令：cmp。那可执行文件的二进制更新岂不是有了这个对比结果后， 然后拿更新结果修改旧文件的二进制串为新文件不就OK了？用个最简单的方法测试下，旧文件testDiffUpdate_Old与更新后文件testDiffUpdate_New内容仅差了第一个字符0。

xiaoyzhang$ cat testDiffUpdate_Old

123456789

xiaoyzhang$ cat testDiffUpdate_New

0123456789

通过CMP做两文件的对比后输出文件为testDiffUpdate_Delta，内容下：

xiaoyzhang$ cmp -l testDiffUpdate_New testDiffUpdate_Old > testDiffUpdate_Delta

cmp: EOF on testDiffUpdate_Old

xiaoyzhang$ cat testDiffUpdate_Delta

1 60 61

2 61 62

3 62 63

4 63 64

5 64 65

6 65 66

7 66 67

8 67 70

9 70 71

10 71 12

如文件内容可知，通过简单的二进制对比得出的差异文件用来更新显然是不靠谱的，差异文件的内容远远比新旧两文件还要大的多。

-rw-r--r-- 1 xiaoyzhang 1085706827 110 12 23 12:33 testDiffUpdate_Delta

-rw-r--r-- 1 xiaoyzhang 1085706827 11 12 23 12:29 testDiffUpdate_New

-rw-r--r-- 1 xiaoyzhang 1085706827 10 12 23 12:28 testDiffUpdate_Old

这个差异更新的问题看起来没有如此简单，但上述问题仍然比较好解决，使用经典动态规划算法——最长公共子序列即可。上述两个文件对比可以很轻易的找出最长公共子序列为123456789。这样，只要在更新差异文件中记录0和其对应的位置，并在旧文件中插入即可解决问题。这种方式下可以将差异更新转化为两个最基本的操作即：复制和插入，文件仅包含差异内容的复制及需要插入位置的索引即可，可以极大的减少更新包的大小，做到我们需要的差异化更新能力。

如上方式已经可以使用，但也仅可以使用在源文件的差异对比中，在可执行文件的二进制对比情况下，每次源码的轻微变动将会导致可执行文件的巨大变化，如下图中可执行文件A与可执行文件B仅仅加入了一小段代码（Inserted Code），但整个程序改动的内容远不仅如此，如图1所示：1）跳过插入代码的程序分支）（branch）位移改变；2）

数据段中指向其他位置的绝对指针(pointer)将替换为新的值，所有插入代码后续的地址均会后移。

图1：插入一小段代码会导致可执行文件大量变动 （Brenda S. Baker ，Compressing Differences of Executable Code）

如上问题会导致使用简单的“复制-插入”方式生成的更新文件远远大于我们所期望的大小，在可执行文件中仅插入一行代码将会产生近5-10%旧文件大小的更新文件。

为解决如上问题，“差异更新界“专家们做出了很多努力，试图找出一些规律来避免这种可执行文件更新包过大的问题，如一个指针指向地址A更新后变为指向地址B，那么所有指向地址A的指针也会随之更新为指向地址B。在仔细挖掘可执行文件的内在规律后，确实有许多更新算法对可执行文件的更新文件压缩效率非常高。但大多高效算法都是与可执行文件的类型深度绑定的， 而Colin Percival在2003年即提出了一个优秀的算法BSDiff，可在平台无关的环境下做到极高的更新文件压缩效率。

可执行文件二进制更新算法—BSDiff

可执行文件的更新会产生三类不同的文件变动：

1. 零阶变动：指编译过程中的固有变化，即完全相同的两段源代码在编译后也可能会发生变化。然而在现代大多数编译环境下，如Unix程序或Windows exe等，相同代码编译后并不会产生变化。

2. 一阶变动：直接修改源代码导致的变动，此变动会导致新旧文件大范围不一致。

3. 二阶变动：由于一阶变动间接引起的变动，每次插入或修改代码都会引起其他未修改代码部分的指针地址或寄存器地址变化，但该变动内的大部分其他二进制字段内容与旧文件保持相同。

在传统的差异更新算法中，要求新旧两文件的二进制的对比保持完全一致。而由于可执行文件中的二阶变动特点，完全一致的匹配方式会极大的增加更新包的大小。 类似ExeDiff等平台相关的更新算法可以将可执行文件反编译后找到可变部分并剥离出来，再进行其余指令的比对，将问题简化为源代码的比对问题。但在平台无关的可执行文件环境下，需要将问题转化为发现负责操作部分代码的二进制差异而非内存或寄存器信息的差异。

BSDiff算法的提出即针对可执行文件更新前后二阶变动的两个重要规律：1）没有被更新代码所影响的代码段，在变为可执行文件后，该区域的二进制内容的改变是极为稀疏的，即仅仅有部分指针或寄存器地址会变动，通常不会超过一两个字节；2）更新后的代码和数据会有很大的位置变动，但这种变动大多为整块的移动，即某一块位置中代码内的指针地址变动均会有相同的位移值。这两个规律导致一个重要的事实即：相同源代码对应的两个代码块中，大部分内容字节差为0，而少部分需要更新的地址位移数据又存在大量相同位移值，即源代码相同的代码块差异数据可以被高效压缩。

图2：差异文件包含大量0与相同偏移量2的字符，可被高效压缩

基于此思想，BSDiff算法使用如下步骤来进行生成差异更新包：

1. 将旧文件二进制使用后缀排序或哈希算法形成一个字符串索引。

2. 使用该字符串索引对比新文件，生成差异文件(difference file)和新增文件(extra file)。

3. 将差异文件和新增文件及必要的索引控制信息压缩为差异更新包。

首先是字符串索引的生成，该部分为差量更新算法的瓶颈部分，BSDiff算法里采用基于二分思想的Faster Suffix Sorting(更快的后缀排序)算法来进行索引的生成。后缀数组即一个一维数组，保存了i(1…n)的某个排列I[i],并且保证suffix(I[i])<suffix(I[i+1]), 即将S的n个后缀从小到大进行排序之后，把有序的后缀的开头位置顺次放入I中，如下图3所示, I[0]标识了后缀‘$’在原数组起始位置为13， I[1]表示后缀‘be$’在原数组起始位置为11，并且‘$’按字典序排序小于‘be$’。

图3 I[i]即为通过Faster Suffix Sorting排序算法生成的后缀数组， （Jesper Larsson, Faster Suffix Sorting）

该算法时间复杂度为O(nlogn)，空间复杂度为O(n)，其中n为旧文件的二进制字符串长度。

得到索引后，使用该索引依次查找新旧文件中完全匹配的最长二进制段，但并不会像传统更新算法一样直接打包，而是从该二进制段进行前后扩展，来生成范围更大的“近似匹配”，近似的要求是向前扩展的每个后缀及后向扩展的每个前缀至少有50%字节与旧字符串可以匹配(通常以8个不匹配字节作为阈值)。这些近似匹配可以认为是二阶变动导致的新代码，而非近似匹配的字段均可以认为是一阶变动新生成的字段。

在匹配完成后，更新包文件也即按此匹配方案生成，包含三个部分：1）控制文件，包含需要添加和插入二进制段的指引信息（”添加指令”指定旧文件中的偏移量和长度，从旧文件读取适当的字节数，并将其添加到差异文件中的相同字节数；”插入指令”只是指定一个长度，指定的字节数是从额外的文件中读取的）；2）差异文件，包含近似匹配字段的字节差异；3）新增文件，包含无法近似匹配的完全不同的字段。这三个文件加一起会比新文件略大，但其中控制文件和差异文件是高度结构化的，意味着其均可被高效压缩，所以可以使用类似bzip2等压缩工具将更新包总文件进行非常有效的压缩。

以上便是bsdiff算法的基本思想，并且作者也将该算法实现并开源出来，供所有有二进制差异更新需求的同学使用(下载链接：http://www.daemonology.net/bsdiff/ )。该工具不仅包含了bsdiff来生成二进制更新包，并且提供了bspatch工具可以将更新包与旧文件一起生成新文件,下文简单对该工具进行下测试。

随意选择两个可执行文件，这里就选择bsdiff工具里的bsdiff与bspatch，两个完全无关的可执行文件，bsdiff作为新文件，bspatch作为旧文件。

xiaoyzhang$ ls -ll

-rwxr-xr-x 1 xiaoyzhang 1085706827 17636 12 23 19:34 bsdiff

-rwxr-xr-x 1 xiaoyzhang 1085706827 13404 12 23 19:37 bspatch

xiaoyzhang$ md5 bsdiff bspatch

MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605

MD5 (bspatch) = cd8b33f3b125f6d7c5883b6322d8a158

使用bsdiff old new patch命令得到差异更新包delta.patch。

xiaoyzhang$ bsdiff bspatch bsdiff delta.patch

xiaoyzhang$ ls -ll

-rw-r--r-- 1 xiaoyzhang 1085706827 5351 12 23 20:06 delta.patch

使用bspatch old new patch命令得到新的可执行文件bspatch_new。

xiaoyzhang$ bspatch bspatch bspatch_new delta.patch

xiaoyzhang$ ls -ll

-rw-r--r-- 1 xiaoyzhang 1085706827 17636 12 23 20:07 bspatch_new

最后做md5校验看新文件是否与目标文件一致。

xiaoyzhang$ md5 bsdiff bspatch_new

MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605

MD5 (bspatch_new) = e775531d35bb8aff34ffd733fdf47605

可以看到，目标更新文件bsdiff与刚生成的新文件bspatch_new完全一致，实现了我们差异更新的需求，并且更新包delta.patch仅有5351bit, 可以为我们节省69%（（17636-5351）/17636）的更新文件大小，并且这二者还是完全无关的两个文件，在实际的更新场景中，该方式将会为我们节约更多的更新文件大小。在一些真实更新场景中测试数据如下图所示，可以看到，bsdiff仅比平台相关的Exediff压缩比例稍高，但其优秀的压缩比例及平台无关的特性，使其到目前为止都是一个非常优秀的二进制更新算法。

图4 几种二进制更新算法效率对比 （Colin Percival, Naive differences of executable code）

游戏更新还需要哪些能力

有了BSDiff，我们可以很方便的做到二进制文件的差异更新，但BSDiff也并非完美，比如其存在一些应对移动应用时的稳定性以及对DEX文件的压缩效率不高等问题。因此在真正的游戏更新场景中，仍然需要厂商基于各类二进制压缩算法进行针对游戏场景的定制化开发，以达到更优质稳定的服务和更高的压缩效率。并且，在实现了版本二进制差异更新以外，仍需要另外一种非常重要的更新能力，即程序内的热更新能力——无需跳转渠道，在游戏启动时即完成更新。目前AppStore, GooglePlay及国内很多如应用宝等知名渠道，都对程序内热更新做了很多限制，以避免热更新带来渠道无法控制的安全问题，为最终用户造成损失。因此，我们也需要在遵守渠道热更新规范的条件下，进行针对游戏内资源文件的热更新。同时，在面对多渠道多版本的管理时，我们也需要一套满足多种场景的功能强大的更新管理平台，可以供运维及运营人员更方便的审核并发布新版本，及时迭代以完善游戏体验。

以上需求都是一个想要长期运营的优质游戏所必不可少的，但又需要游戏厂商花费大量时间与精力去实现，有没有现成的解决方案可以即插即用呢？腾讯游戏云游戏更新Dolphin产品即可完美根治所有游戏更新中的疑难杂症：针对移动游戏应用结构定制研发的高效稳定的二进制差异更新算法，产品化后天然支持Unity等游戏引擎；只需简单的接入SDK，即可使用差异更新、资源热更新及多渠道多版本管理的全部功能；并且可以直接借助腾讯云全球部署的基础设施和CDN资源，一次接入全球使用，使玩家可以更快速的体验到游戏新版本。据不完全统计，腾讯内部手游在使用了该游戏更新方案后，更新的成功率高达99.7%，极大的减少了更新带来的玩家流失，为游戏的长久运营提供了坚实的技术支撑。目前游戏更新Dolphin已在腾讯云全量开放，希望可以帮助到各游戏厂商和开发者，为玩家带来“多快好省”的游戏更新体验。立即注册，每月专享100M免费体验流量： https://cloud.tencent.com/product/Dolphin