Home

Awesome

sfpatcher:针对应用商店的apk增量算法

v1.0.15 已正式上线,为亿级手机终端用户提供更新服务,当前最新版本 v1.3.0
sfpatcher 命令行工具下载(支持Windows、Linux、MacOS), 命令行使用说明
需要商业授权(含源代码&培训),请联系作者: housisong@hotmail.com

定义

app:本文档一般指智能手机和Pad设备上的软件,包括应用和游戏等。
应用商店:这里指当前安卓智能设备上负责管理app的软件,支持app的下载、更新、推荐等功能;软件也可能分成应用市场游戏中心两个独立应用。
apk:安卓设备上的约定的软件包格式,它属于特殊约定格式的zip压缩档案格式的一种。为了防止篡改,发布的apk都带有签名。
diff:这里指一种创建补丁的算法,它能计算出两个数据之间的差异,比如生成从旧版本数据到新版本之间的补丁数据。
patch:打补丁,diff算法的逆算法,它能在旧版本数据基础上应用补丁来得到新版本的数据。

背景

随着智能手机的普及和应用数量的爆发式增长,手机上大量app的下载和更新将产生巨大的数据流量。手机上的应用商店一般都会部署增量更新系统来节省大量的服务带宽成本和提升用户体验(节省用户流量和减少下载时间),而不用每次都下载完整版本。

应用商店使用的增量更新算法一般选择使用的是基于字节的 diff 和 patch 算法,包括:BsDiff xdelta3HDiffPatch等。

针对apk的diff&patch算法

前面提到的增量更新实现方案都只是把apk单纯的看作文件数据直接用算法进行diff&patch,而没有考虑apk包本身是一个zip压缩包的事实。这种简单使用方式可以概括为公式:

  diffFile:= diff(oldApk,newApk)
  newApk  := patch(oldApk,diffFile)

大家可以试试:一个大文件在1/4处简单进行修改,如果把修改前后的2个文件分别压缩成zip文件,用二进制工具打开2个zip文件对比会发现:前面一部分的编码相同(那这部分约占1/4),但后面部分的编码数据很可能会完全不同。
压缩算法破坏了修改“现场”,diff算法的优势无法真正发挥出来(生成了巨大的补丁)。那么我们是否可以开发针对apk文件格式的diff&patch算法呢? 它能够识别出上面的情况:其实只是修改了一个字符!(即生成极小的补丁)
很容易想到的一个优化思路,先解压再diff不就好了!原理可以概括为公式:

  diffFile:=diff(decompress(oldApk),decompress(newApk))
  newApk  :=recompress(patch(decompress(oldApk),diffFile))

公式里面的diff和patch函数很好办,选择上面提到的一种基于字节的diff&patch算法就行;decompress函数的实现也较简单,就是zip包的解压缩算法;recompress函数的实现比较麻烦一些,需要保证精确的原样还原出newApk(避免破坏签名和运行等)。
archive-patcherApkDiffPatch 正是这种思路的实现方案,也包括本文章要介绍的 sfpatcher 方案都基于这个思路。

sfpatcher 是什么?

针对压缩档案文件的高性能增量更新方案。类似于 archive-patcher 方案可部署于应用商店的diff&patch算法,该领域的重要技术进展。
内部使用了 HDiffPatch 算法作为基础,用C\C++语言开发,当前支持为deflate格式压缩的数据创建优化的补丁(用zlib压缩的支持最好),支持在多种档案格式文件之间创建优化的补丁。

sfpatcher 之道

注1:所有测试数据来源于收集的一些常用apk应用,共32个用例;并在ARM CPU Kirin980上测试了部分patch。(见性能测试对比数据)

方案主要特性对比

sfpatcher 和 archive-patcher

sfpatcher 和 ApkDiffPatch

参与测试的diff&patch方案

测试目的

对比多种diff&patch方案在apk文件增量更新方面的运行数据;
测试项主要包括:diff速度、diff内存占用、补丁大小(用压缩率代替,压缩后补丁大小/新版本apk大小)、patch速度、patch内存占用(后面这3项指标可能更重要一些)

测试用例

收集了32组测试用例;这些apk下载于小米应用商店、谷歌Play商店,按照下载量大和最近进行过更新为标准进行收集。
限于有限的用例和收集偏差,数据和实际情况可能略有差异。 旧版本apk平均大小103.2MB,新版本apk平均大小103.8MB。

编号app新apk <-- 旧apk新apk大小旧apk大小
1<img src="https://github.com/sisong/sfpatcher/raw/master/img/cn.wps.moffice_eng.png" width="36">cn.wps.moffice_eng_13.30.0.apk <-- 13.29.09590491894914262
2<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.achievo.vipshop.png" width="36">com.achievo.vipshop_7.80.2.apk <-- 7.79.9127395632120237937
3<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.adobe.reader.png" width="36">com.adobe.reader_22.9.0.24118.apk <-- 22.8.1.235872735143727087718
4<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.alibaba.android.rimet.png" width="36">com.alibaba.android.rimet_6.5.50.apk <-- 6.5.45195314449193489159
5<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.amazon.mShop.android.shopping.png" width="36">com.amazon.mShop.android.shopping_24.18.2.apk <-- 24.18.07632885876287423
6<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.baidu.BaiduMap.png" width="36">com.baidu.BaiduMap_16.5.0.apk <-- 16.4.5131382821132308374
7<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.dragon.read.png" width="36">com.dragon.read_5.5.3.33.apk <-- 5.5.1.324511265843518658
8<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.ebay.mobile.png" width="36">com.ebay.mobile_6.80.0.1.apk <-- 6.79.0.16120258761123285
9<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.eg.android.AlipayGphone.png" width="36">com.eg.android.AlipayGphone_10.3.0.apk <-- 10.2.96122073135119046208
10<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.google.android.apps.translate.png" width="36">com.google.android.apps.translate_6.46.0.apk <-- 6.45.04889296748843378
11<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.google.android.googlequicksearchbox.png" width="36">com.google.android.googlequicksearchbox_13.38.11.apk <-- 13.37.10190539272189493966
12<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.jingdong.app.mall.png" width="36">com.jingdong.app.mall_11.3.2.apk <-- 11.3.0101098430100750191
13<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.netease.cloudmusic.png" width="36">com.netease.cloudmusic_8.8.45.apk <-- 8.8.40181914846181909451
14<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.reddit.frontpage.png" width="36">com.reddit.frontpage_2022.36.0.apk <-- 2022.34.05020511947854461
15<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.sankuai.meituan.takeoutnew.png" width="36">com.sankuai.meituan.takeoutnew_7.94.3.apk <-- 7.92.27496589374833926
16<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.sankuai.meituan.png" width="36">com.sankuai.meituan_12.4.207.apk <-- 12.4.2059361373293605911
17<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.sina.weibo.png" width="36">com.sina.weibo_12.10.0.apk <-- 12.9.5156881776156617913
18<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.smile.gifmaker.png" width="36">com.smile.gifmaker_10.8.40.27845.apk <-- 10.8.30.27728102403847101520138
19<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.ss.android.article.news.png" width="36">com.ss.android.article.news_9.0.7.apk <-- 9.0.65444400353947221
20<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.ss.android.ugc.aweme.png" width="36">com.ss.android.ugc.aweme_22.6.0.apk <-- 22.5.0171683897171353597
21<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.taobao.taobao.png" width="36">com.taobao.taobao_10.18.10.apk <-- 10.17.0117218670117111874
22<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.tencent.mm.png" width="36">com.tencent.mm_8.0.28.apk <-- 8.0.27266691829276603782
23<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.tencent.mobileqq.png" width="36">com.tencent.mobileqq_8.9.15.apk <-- 8.9.13311322716310529631
24<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.tencent.mtt.png" width="36">com.tencent.mtt_13.2.0.0103.apk <-- 13.2.0.00459734274797296757
25<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.tripadvisor.tripadvisor.png" width="36">com.tripadvisor.tripadvisor_49.5.apk <-- 49.32874449828695346
26<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.twitter.android.png" width="36">com.twitter.android_9.61.0.apk <-- 9.58.23614184035575484
27<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.ubercab.png" width="36">com.ubercab_4.442.10002.apk <-- 4.439.100026992323264284150
28<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.ximalaya.ting.android.png" width="36">com.ximalaya.ting.android_9.0.66.3.apk <-- 9.0.62.3115804845113564876
29<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.xunmeng.pinduoduo.png" width="36">com.xunmeng.pinduoduo_6.30.0.apk <-- 6.29.13089683330951567
30<img src="https://github.com/sisong/sfpatcher/raw/master/img/com.youdao.dict.png" width="36">com.youdao.dict_9.2.29.apk <-- 9.2.28110624682110628778
31<img src="https://github.com/sisong/sfpatcher/raw/master/img/org.mozilla.firefox.png" width="36">org.mozilla.firefox_105.2.0.apk <-- 105.1.08307846483086656
32<img src="https://github.com/sisong/sfpatcher/raw/master/img/tv.danmaku.bili.png" width="36">tv.danmaku.bili_7.1.0.apk <-- 7.0.0104774723104727005

测试条件

在一台笔记本PC上对比测试:Windows11, CPU R9-7945HX, SSD PCIe4.0x4 4T, DDR5 5200MHz 32Gx2
patch时标注tmpf表示使用了临时文件来储存中间数据;mem表示在内存中执行不使用临时文件;limit表示使用限制内存占用的模式执行;而标注MT表示开启了多线程(8个)并行。
BsDiff v4.3 还是保持着使用bzip2算法压缩补丁。
xdelta v3.1.0 使用-e -n -f -s来创建补丁, 而用-d -f -s参数来执行的patch。
HDiffPatch v4.6.3 支持2种diff模式,-s-16-m-1 -cache -block模式分别测试,输出补丁时分别测试了用lzma2、zstd压缩的测试。HDiffPatch支持输出兼容bsdiff的补丁(bzip2压缩),补充了-BSD -m-1 -cache -block参数后的测试结果。
archive-patcher v1.0 一般使用gzip或brotli算法压缩补丁,这里为了diff速度并更好的和其他方案对比补丁大小,diff时输出不压缩的补丁,然后再额外使用lzma2压缩补丁。 需要注意:这时收集到的diff数据不包含额外压缩时的时间和内存消耗,收集到的patch数据也不包含解压的时间和内存消耗等。
ApkDiffPatch v1.6.0 使用了lzma2来压缩输出的补丁。
sfpatcher v1.1.1 支持多个级别的diff,-1,-2和-3分别测试; sfpatcher支持不需要旧版本apk而直接重新压缩新版本apk的模式(标记为pre);sfpatcher支持多种可选压缩输出,这里测试了-c-zstd-21和-c-lzma2-9这2种。
sfpatcher补充测试了用ApkNormalized(ApkDiffPatch方案)处理过的apk文件,分别进行增量测试和lzma2重压缩测试(标记为Norm)。
sfpatcher v1.3.0 新增了专用的标准化处理流程$sf_normalize -cl-A和-cl-4, 对测试apk进行标准化并重新签名后,分别进行增量测试和zstd重压缩测试(标记为clA和cl4,重压缩标记为pre)。

另外在一部安卓手机(CPU:Kirin980 2×A76 2.6G + 2×A76 1.92G + 4×A55 1.8G)上对hpatchz&hsynz&sfpatcher进行了一些patch时间测试,补充到了最后一列。

测试结果

其中:平均压缩率=(补丁大小/新apk大小)的平均值; 单次测试的内存占用统计值为峰值私有内存;

diff方案平均压缩率平均内存平均速度patch平均内存最大内存平均速度arm Kirin980
zstd --patch-from53.18%2199M3.6MB/smem209M596M609MB/s
xdelta354.51%422M3.8MB/smem98M99M170MB/s
bsdiff53.84%931M1.2MB/smem218M605M54MB/s
hdiffz54.40%509M8.8MB/smem5M6M682MB/s443MB/s
hdiffz lzma252.93%525M4.1MB/smem21M22M260MB/s131MB/s
hdiffz zstd53.04%537M5.4MB/smem21M22M598MB/s371MB/s
hdiffz -s zstd53.44%221M10.1MB/smem20M22M620MB/s
archive-patcher31.65%1448M0.9MB/stemf558M587M14MB/s
ApkDiffPatch18.44%1003M2.2MB/smem164M453M20MB/s
ApkDiffPatch18.44%1003M2.2MB/smemMT257M628M64MB/s
ApkDiffPatch18.44%1003M2.2MB/stmpf21M25M17MB/s
ApkDiffPatch18.44%1003M2.2MB/stmpfMT101M211M46MB/s
sfpatcher-3 Norm18.35%1147M2.2MB/slimit43M59M21MB/s
sfpatcher-318.35%1147M2.2MB/slimitMT49M65M77MB/s
sfpatcher-3 Norm18.35%1147M2.2MB/smemMT170M452M99MB/s
sfpatcher-3pre Norm64.91%610M1.7MB/smem37M41M14MB/s
sfpatcher-3pre64.91%610M1.7MB/smemMT42M46M64MB/s
sfpatcher-1 zstd31.08%818M2.3MB/slimit15M19M201MB/s92MB/s
sfpatcher-1 zstd31.07%1025M4.6MB/slimitMT18M25M424MB/s189MB/s
sfpatcher-1 lzma229.75%819M2.3MB/slimit14M19M104MB/s50MB/s
sfpatcher-1 lzma229.75%809M5.3MB/slimitMT17M24M167MB/s74MB/s
sfpatcher-2 zstd26.27%975M2.1MB/slimit15M20M43MB/s
sfpatcher-2 zstd26.29%1002M4.7MB/slimitMT20M27M155MB/s
sfpatcher-2 lzma224.11%976M2.1MB/slimit15M20M37MB/s19MB/s
sfpatcher-2 lzma224.15%968M5.0MB/slimitMT20M26M108MB/s45MB/s
sfpatcher-3 lzma223.53%997M2.0MB/slimit16M20M31MB/s17MB/s
sfpatcher-3 lzma223.56%987M4.5MB/slimitMT21M26M98MB/s40MB/s
sfpatcher-2pre zstd81.36%376M2.8MB/smem19M23M37MB/s
sfpatcher-2pre zstd81.36%1646M7.1MB/smemMT24M30M193MB/s
sfpatcher-3pre zstd79.20%387M2.4MB/smem20M23M29MB/s
sfpatcher-3pre zstd79.20%1698M6.5MB/smemMT25M30M144MB/s
sfpatcher-2pre lzma275.23%378M1.9MB/smem20M23M24MB/s12MB/s
sfpatcher-2pre lzma275.42%1091M8.3MB/smemMT24M28M63MB/s26MB/s
sfpatcher-3pre lzma273.34%386M1.7MB/smem20M23M21MB/s11MB/s
sfpatcher-3pre lzma273.53%1126M8.1MB/smemMT25M29M60MB/s24MB/s
sfpatcher-2 cl4 zstd21.72%1141M2.3MB/smemMT19M24M38MB/s
sfpatcher-2 cl4 zstd21.74%1158M5.2MB/smem25M30M123MB/s
sfpatcher-3pre cl4 zstd74.30%451M1.9MB/smemMT21M26M29MB/s
sfpatcher-3pre cl4 zstd74.29%1990M5.5MB/smem28M33M155MB/s
sfpatcher-1 clA zstd21.72%1141M2.5MB/smemMT19M22M85MB/s63MB/s
sfpatcher-1 clA zstd21.74%1156M5.4MB/smem26M29M240MB/s129MB/s
sfpatcher-3pre clA zstd74.30%450M2.1MB/smemMT20M22M61MB/s46MB/s
sfpatcher-3pre clA zstd74.30%1991M5.8MB/smem28M32M264MB/s129MB/s

游戏测试用例

最近收集了32组游戏测试用例,这些apk下载于小米应用商店、TapTap商店、谷歌Play商店,按照下载量大和最近进行过更新为标准进行收集。
对比测试了 xdelta、bsdiff、HDiffPatch、sfpatcher; 因为有大游戏所以放弃了无法完成测试的archive-patcher。
sfpatcher v1.1.1 测试时,调整了部分参数,相比前面的测试增大了patch时的内存需求。
旧版本apk平均大小1029.5MB,新版本apk平均大小1040.9MB。

编号app新apk <-- 旧apk新apk大小旧apk大小
1<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.blizzard.wtcg.hearthstone.png" width="36">com.blizzard.wtcg.hearthstone_24.4.150659.apk <-- 24.2.148211119192491118798993
2<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.hypergryph.arknights.png" width="36">com.hypergryph.arknights_1.9.21.apk <-- 1.9.0115773580491530216284
3<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.igg.android.lordsmobile.png" width="36">com.igg.android.lordsmobile_2.88.apk <-- 2.866915111168970887
4<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.imangi.templerun2.png" width="36">com.imangi.templerun2_6.5.1.apk <-- 6.5.0142692127141981473
5<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.joym.legendhero.mi.png" width="36">com.joym.legendhero.mi_6.0.0.apk <-- 5.0.0857787066801198664
6<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.kiloo.subwaysurf.png" width="36">com.kiloo.subwaysurf_3.36.1.apk <-- 3.36.0172657047172348585
7<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.king.candycrushsaga.png" width="36">com.king.candycrushsaga_1.237.0.3.apk <-- 1.236.0.38961960489410785
8<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.knight.union.mi.png" width="36">com.knight.union.mi_4.3.1.apk <-- 4.3.0281337183279734645
9<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.mfp.jelly.xiaomi.png" width="36">com.mfp.jelly.xiaomi_8.20.0.6.apk <-- 8.19.5.2454515054444262109
10<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.miHoYo.enterprise.NGHSoD.png" width="36">com.miHoYo.enterprise.NGHSoD_6.1.0.apk <-- 6.0.0633463833617956855
11<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.miHoYo.Yuanshen.png" width="36">com.miHoYo.Yuanshen_3.1.0.apk <-- 3.0.0292959792281028246
12<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.dwrg.mi.png" width="36">com.netease.dwrg.mi_1.5.69.apk <-- 1.5.6720873541042083304114
13<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.g104.mi.png" width="36">com.netease.g104.mi_3.18.1.apk <-- 3.17.519007046151853407883
14<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.g67.mi.png" width="36">com.netease.g67.mi_1.6.0.apk <-- 1.5.420213301012016955181
15<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.harrypotter.png" width="36">com.netease.harrypotter_1.20.212190.apk <-- 1.20.21126021463510761976476298
16<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.l10.mi.png" width="36">com.netease.l10.mi_1.11.5.apk <-- 1.11.418976641561835964179
17<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.mc.mi.png" width="36">com.netease.mc.mi_2.3.15.apk <-- 2.3.5986369238982878980
18<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.onmyoji.png" width="36">com.netease.onmyoji_1.7.48.apk <-- 1.7.4720376535772029429678
19<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.netease.sky.png" width="36">com.netease.sky_0.10.0.apk <-- 0.9.913206670041188304200
20<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.nianticlabs.pokemongo.png" width="36">com.nianticlabs.pokemongo_0.251.0.apk <-- 0.249.25191950951538569
21<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.outfit7.mytalkingtom2.mi.png" width="36">com.outfit7.mytalkingtom2.mi_3.5.0.514.apk <-- 3.4.0.496151118938152738799
22<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.papegames.nn4.cn.png" width="36">com.papegames.nn4.cn_2.1.1147531.apk <-- 2.1.109466118042000581911303194
23<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.rovio.baba.dbzq.m.png" width="36">com.rovio.baba.dbzq.m_3.6.0.apk <-- 3.2.1285160536298220983
24<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.ig.png" width="36">com.tencent.ig_2.2.0.apk <-- 2.1.011238487121161724820
25<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.lolm.png" width="36">com.tencent.lolm_3.5.0.6093.apk <-- 3.4.0.593517434712261956378264
26<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.tmgp.cf.png" width="36">com.tencent.tmgp.cf_1.0.280.apk <-- 1.0.26020891320741998168460
27<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.tmgp.cod.png" width="36">com.tencent.tmgp.cod_1.9.35.apk <-- 1.9.3421021314142109943466
28<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.tmgp.sgame.png" width="36">com.tencent.tmgp.sgame_3.81.1.8.apk <-- 3.74.1.619600326461976668388
29<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.tencent.tmgp.speedmobile.png" width="36">com.tencent.tmgp.speedmobile_1.33.0.apk <-- 1.32.021228190582096029603
30<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.ustwo.monumentvalleyzz.png" width="36">com.ustwo.monumentvalleyzz_2.5.2.apk <-- 2.5.1159780651160263061
31<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.wooduan.ssjj.mi.png" width="36">com.wooduan.ssjj.mi_6.9.2.apk <-- 6.8.115885574731534719411
32<img src="https://github.com/sisong/sfpatcher/raw/master/gimg/com.yodo1.tew.mi.png" width="36">com.yodo1.tew.mi_2.10.6.297.apk <-- 2.9.5.286655222738622939950

游戏测试结果

diff方案平均压缩率平均内存平均速度patch平均内存最大内存平均速度最差速度
zstd36.35%5297MB3.2MB/smem2088MB4033MB852MB/s576MB/s
xdelta3 lzma54.14%423MB3.5MB/smem99MB104MB94MB/s30MB/s
xdelta3 lzma +hpatchz -m54.14%423MB3.5MB/smem79MB83MB258MB/s84MB/s
bsdiff36.15%9284MB1.1MB/smem2085MB4042MB89MB/s32MB/s
bsdiff +hpatchz -m36.15%9284MB1.1MB/smem1045MB2029MB95MB/s33MB/s
bsdiff +hpatchz -s36.15%9284MB1.1MB/smem14MB14MB87MB/s32MB/s
hdiffz p1 zstd35.41%3812MB6.3MB/smem23MB23MB712MB/s291MB/s
hdiffz p8 zstd35.42%4249MB25.3MB/smem22MB23MB703MB/s284MB/s
hdiffz p1 lzma235.26%3813MB5.3MB/smem22MB23MB344MB/s136MB/s
hdiffz p8 lzma235.28%3842MB29.9MB/smem22MB23MB344MB/s135MB/s
sfpatcher-1 zstd22.23%4491MB5.4MB/slimit23MB35MB412MB/s152MB/s
sfpatcher-1 zstd22.20%4684MB15.5MB/slimitMT26MB38MB634MB/s308MB/s
sfpatcher-2 lzma219.61%5162MB4.9MB/slimit26MB47MB101MB/s13MB/s
sfpatcher-2 lzma219.62%5121MB16.8MB/slimitMT32MB54MB249MB/s44MB/s
sfpatcher-3 lzma217.87%5682MB4.6MB/slimit32MB47MB49MB/s6MB/s
sfpatcher-3 lzma217.91%5631MB15.6MB/slimitMT39MB54MB157MB/s26MB/s

sfpatcher的大规模测试

收集了Top500中多个app应用(不含游戏)和其多个历史版本,形成了4695个测试用例,进行了diff和patch多种参数测试并分别使用了lzma2压缩和zstd压缩输出补丁。
测试条件:v1.0.15 用了-lp-2m加8m压缩字典 -pre时用的16m压缩字典

方案平均压缩率
hdiffz lzma250.8%
sfpatcher -1 lzma231.5%
sfpatcher -2 lzma229.3%
sfpatcher -3 lzma226.7%
sfpatcher -2 pre lzma281.9%
sfpatcher -3 pre lzma276.6%
hdiffz zstd50.9%
sfpatcher -1 zstd32.6%
sfpatcher -2 zstd30.7%
sfpatcher -3 zstd28.3%
sfpatcher -2 pre zstd86.3%
sfpatcher -3 pre zstd82.3%

节省CDN带宽费用估算(仅供参考)

单个apk一次升级节省的流量估算:用户的安卓手机现在经常使用的应用apk一般都越来越大(游戏平均更大),假设按平均100MB算。
一般bsdiff或HDiffPatch创建的补丁平均为原apk大小的50%--60%(按51%计算);sfpatcher按-o-1算,创建的补丁为平均原apk大小的33%。
那sfpatcher相比bsdiff或HDiffPatch方案单次继续节省 100x(51%-33%) = 18MB (游戏apk平均节省会成倍数增加)
假设apk商店每天有1亿次apk升级,按峰值带宽计费,假设单价每天0.48元/Mbps; 而按经验,峰值带宽一般是平均带宽的2倍:
每月节省费用:100000000x(18x1024x1024x8/1000/1000)/(3600x24)x2x0.48*30 = 503.3万元
如果按流量计费,假设单价0.11元/GB:
每月节省费用:100000000x(18/1024)x0.11x30 = 580.1万元


需要商业授权,请联系作者: housisong@hotmail.com