作者: 腾讯云游戏行业资深架构师 张晓愚
为何需要差异更新?
差异更新即在软件更新时只更新差异化的部分, 以达到用最小的下载量完成软件的更新需求该思想由来已久, 从刚接触电脑时的操作系统应用软件快速更新功能或填补漏洞, 到迭代更加频繁的移动应用时代更多了节省下载流量费用的需求尤其在移动游戏领域, 随着手机性能的提升和玩家对游戏体验的追求, 安装包亦是越来越大, 并且会频繁的更新以不断给玩家带来更新的玩法和更为优化的体验然而, 这种频繁的更新也同样会带来负面的影响: 更新包太大没流量; 更新速度太慢错过了本该用来玩游戏的碎片时间; 本地空间不足无法更新等问题, 这些负面影响都会导致一定程度上的玩家流失因此, 差异化更新能力目前已成为各应用下载渠道的必备能力之一, 更小的更新包才能提高更新的成功率
差异化更新可分为两种, 一种是基于源文件的差异化更新, 该种方式成功率高, 算法简单, 常用于平台相关的差异更新, 但在移动端保存巨大的源文件下载更新文件整合后再编译的方式显然是不现实的; 另一种即更为广泛使用的方法即对可执行文件的二进制更新方式, 本文中即将就该方式下的经典算法 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(1n)的某个排列 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
来源: https://www.qcloud.com/developer/article/1008518