stable & fast to patch apk archives, used by Android app store. ...

# sfpatcher：针对应用商店的apk增量算法 **v1.0.15 已正式上线**，为亿级手机终端用户提供更新服务，当前最新版本 v1.3.0 [**sfpatcher** 命令行工具下载](https://github.com/sisong/sfpatcher/releases)（支持Windows、Linux、MacOS）， [命令行使用说明](https://github.com/sisong/sfpatcher/blob/master/cmdline_doc.md) 需要商业授权(含源代码&培训)，请联系作者： <housisong@hotmail.com> ## 定义 **app**：本文档一般指智能手机和Pad设备上的软件，包括应用和游戏等。 **应用商店**：这里指当前安卓智能设备上负责管理app的软件，支持app的下载、更新、推荐等功能；软件也可能分成**应用市场**和**游戏中心**两个独立应用。 **apk**：安卓设备上的约定的软件包格式，它属于特殊约定格式的zip压缩档案格式的一种。为了防止篡改，发布的apk都带有签名。 **diff**：这里指一种创建补丁的算法，它能计算出两个数据之间的差异，比如生成从旧版本数据到新版本之间的补丁数据。 **patch**：打补丁，diff算法的逆算法，它能在旧版本数据基础上应用补丁来得到新版本的数据。 ## 背景 随着智能手机的普及和应用数量的爆发式增长，手机上大量app的下载和更新将产生巨大的数据流量。手机上的应用商店一般都会部署增量更新系统来节省大量的服务带宽成本和提升用户体验（节省用户流量和减少下载时间），而不用每次都下载完整版本。 应用商店使用的增量更新算法一般选择使用的是基于字节的 diff 和 patch 算法，包括：[BsDiff ](http://www.daemonology.net/bsdiff)、[xdelta3](https://github.com/jmacd/xdelta)、[HDiffPatch](https://github.com/sisong/HDiffPatch)等。 - **BsDiff** 是当前选择使用较多的算法，创建的补丁小，代码量小，容易移植。但diff和patch场景下执行速度都很慢、内存占用巨大，应用于应用商店等场景时需要进行一些修改定制。 - **xdelta3** 在diff和patch场景下执行速度都很快，输出标准化的补丁格式(vcdiff格式,也有改成gdiff的)，apk补丁大小和BsDiff接近或略大，内存占用中等。该算法在diff处理较大文件的时候（比如几百MB以上），常会输出不正常的巨大补丁，除非使用和文件大小相当的参考内存来diff和patch，而这时patch时内存占用可控的优点就没有了。 - **HDiffPatch** 是作者开源的算法，创建的补丁一般比BsDiff略小一些，diff(-s模式)和patch场景下执行速度都很快，内存占用可控并很小。 diff时也支持-m模式，用更大的内存和时间代价(这时也比BsDiff快很多倍)来得到更小一些的补丁包。 HDiffPatch 现在已经被**vivo**、**OPPO**、**小米**、**腾讯**、**华为**、**字节跳动**、**米哈游**等所使用；从为4KB RAM内存、8位CPU的MCU设备创建OTA增量补丁(4KB内存里一边解压一边patch!)，到为上百GB的游戏创建更新补丁，HDiffPatch 算法得到了越来越广泛的应用。 ## 针对apk的diff&patch算法 前面提到的增量更新实现方案都只是把apk单纯的看作文件数据直接用算法进行diff&patch，而没有考虑apk包本身是一个zip压缩包的事实。这种简单使用方式可以概括为公式： ```c diffFile:= diff(oldApk,newApk) newApk := patch(oldApk,diffFile) ``` 大家可以试试：一个大文件在1/4处简单进行修改，如果把修改前后的2个文件分别压缩成zip文件，用二进制工具打开2个zip文件对比会发现：前面一部分的编码相同（那这部分约占1/4），但后面部分的编码数据很可能会完全不同。 压缩算法破坏了修改“现场”，diff算法的优势无法真正发挥出来(生成了巨大的补丁)。那么我们是否可以开发针对apk文件格式的diff&patch算法呢？ 它能够识别出上面的情况：其实只是修改了一个字符！(即生成极小的补丁) 很容易想到的一个优化思路，先解压再diff不就好了！原理可以概括为公式： ```c diffFile:=diff(decompress(oldApk),decompress(newApk)) newApk :=recompress(patch(decompress(oldApk),diffFile)) ``` 公式里面的diff和patch函数很好办，选择上面提到的一种基于字节的diff&patch算法就行；decompress函数的实现也较简单，就是zip包的解压缩算法；recompress函数的实现比较麻烦一些，需要保证精确的原样还原出newApk（避免破坏签名和运行等）。 而 [archive-patcher](https://github.com/google/archive-patcher) 和 [ApkDiffPatch](https://github.com/sisong/ApkDiffPatch) 正是这种思路的实现方案，也包括本文章要介绍的 [sfpatcher](https://github.com/sisong/sfpatcher) 方案都基于这个思路。 - **archive-patcher** 谷歌开源的一个针对apk文件的diff&patch实现，在谷歌play商店中使用。内部使用了BsDiff算法作为基础，主要用java语言开发，针对解压状态总数据量小于512MB的并且使用了zlib的deflate压缩算法创建的apk文件，执行优化的补丁算法。 该方案在patch时比较慢，特别是部分略大的apk文件使用了较高的压缩级别时，这时重新压缩出新版本apk会慢的让用户无法接受，所以该优化方案一般用在可以后台更新的场景下。 - **ApkDiffPatch** 是作者开源的算法，为给自己团队开发的apk更新来开发的方案，创建的补丁平均比 archive-patcher 小很多，patch速度中等；方案一般用在可以自己对需要升级的apk进行重新签名的场景，而不能部署于应用商店。内部使用了 HDiffPatch 算法作为基础，用C\C++语言开发。为了patch时精确还原，和加快压缩还原时的速度，需要对发布的apk文件执行 ApkNormalized 预处理流程（使用了较快的压缩参数，处理过的apk需要重新签名）。 patch时可以支持并行压缩来加快apk还原速度，但这时内存资源占用比较严重，和多个线程正在分别压缩的多个文件源大小和其压缩后大小的总和相当。 ## sfpatcher 是什么？ 针对压缩档案文件的高性能增量更新方案。类似于 archive-patcher 方案可部署于应用商店的diff&patch算法，该领域的重要技术进展。 内部使用了 HDiffPatch 算法作为基础，用C\C++语言开发，当前支持为deflate格式压缩的数据创建优化的补丁(用zlib压缩的支持最好)，支持在多种档案格式文件之间创建优化的补丁。 ### sfpatcher 之道 - 针对应用商店的场景专门设计，优化补丁大小，支持大型游戏，patch时精确快速还原任意apk文件，能够用于用户交互场景。 - 多级可选的补丁包大小，极致的patch速度：提供比谷歌**archive-patcher**方案(+lzma2压缩)下载补丁小2%的情况下，patch速度是其30倍！补丁比其小24%的情况下，速度是其8倍(这时补丁比BsDiff方案小约55%并且速度快得多)！ （注1） - patch时的内存等资源占用可控；diff时支持多种方案限制patch时的最大内存占用到合适的约定水平。即支持patch时O(1)平均内存占用的优化补丁包(并且patch过程中不使用临时文件)！ - 优化的用户体验：因为补丁变小，下载时间也会变短，从而可能缩短整体更新时间，也更省电省流量。还可以支持下载数据的同时就开始patch，不用将补丁文件保存到内存或硬盘上，结合快速的patch，很多时候下载完成时，就可以得到了完整的新版本apk文件。 - 利用精确还原算法，对于初次下载的apk文件也能进行解压后的重压缩；从而节省用户初次下载apk时的流量。最多情况下平均比直接下载apk文件减少25%的数据，部分文件能减少35%以上的数据！ - 支持从中断的�