高性能diff&patch算法 -- 如何将微信Apk的官方增量包20.4M缩小到7.0M
原创高性能diff&patch算法 -- 如何将微信Apk的官方增量包20.4M缩小到7.0M
原创
zhouyi
发布于 2018-06-12 16:21:38
发布于 2018-06-12 16:21:38
高性能diff&patch算法
-- 如何将微信Apk的官方增量包20.4M缩小到7.0M
作者: HouSisong@GMail.com 2018.03.16什么是diff&patch算法
- 原理抽象概述: … …
3种有效的diff算法
- 增量压缩流
- 同步流
- 覆盖线流
其他：按行、按文件等…
增量压缩diff算法
- 最容易实现的可以自己diy出来的一种有效算法
- 寻找一种高效的基础压缩算法
- 实现技巧：
- 拼接old+new一起压缩，输出new部分压缩得到的编码为补丁；patch时先压缩old并和补丁拼一起解压缩，丢弃前面old大小的数据，后面的就是新生成的new
- 优缺点：
- 容易实现，算法选择的好时效果很赞；适应范围较窄(数据较大时补丁可能突然异常变大)，因为要压缩速度可能慢等
覆盖线diff算法
- BsDiff
- HDiffPatch
- 实现原理：
- 二维矩阵概念
- 覆盖线概念
- 后缀数组(QuickSort\libdivsufsort)
- 优缺点：
- 补丁小、diff内存占用大、运行慢、patch快
- patch内存占用O(m+n)复杂度的误解： 这只是BsDiff的具体实现问题；HDiffPatch就可以做到实际内存占用O(1)的patch过程；（HDiffPatch也提供了降低diff时间和空间复杂度的实现版本：同步diff算法的实现）
- 小胡瓜Courgette：
- 原理：针对程序，反编译old和new、diff源代码、反编译old并patch源代码、编译成new
同步diff算法
- 原理：分块hash和roll hash的对比
- 一些实现：同步工具、xdelta?、HDiffPatch
- 优缺点：
- 可以支持动态CS模式(甚至允许C损坏)、速度快、可以支持超大文件；（xdelta对超大文件支持不好）
Apk的diff算法选择
- zip、jar、apk的关系 （另外: ipa）
- Jar包签名(Apk v1 Sign)
- BsDiff 、HDiffPatch
- 为什么微信Apk663版到665版的升级包是20.4M
- 遇到的适应问题：压缩算法破坏了“现场”
- 直观的解决思路：zip包的针对性优化
- 将zip抽象成未压缩状态的数据交给diff算法，patch时输出标准zip包
如何支持严苛的Apk V2版签名
- Apk v2 Sign介绍
- 额外：渠道包失效? 现在该如何在包中“夹带私货”
- 增量更新解决思路:
- newZip=AndroidSDK#apksigner(ApkNormalized(newZip)) before ZipDiff
- patch重建newZip时byte by byte的相等保证；
- 风险提示、安全保证手段
- ApkDiffPatch方案：
- Zip(Jar,Apk) file by file Diff & Patch, create minimal differential, support apk v2 sign & Jar sign(apk v1).
有了BsDiff或HDiffPatch为什么还需要ApkDiffPatch?
ApkDiffPatch: v1.0
BsDiff: v4.3
HDiffPatch: v2.2.6
Google Play patches: https://github.com/andrewhayden/archive-patcher v1.0
(test by https://github.com/googlesamples/apk-patch-size-estimator )
======================================================================================
BsDiff HDiffPatch archive-patcher ApkDiffPatch
oldVersion -> newVersion newSize (bzip2) (zlib) (gzip) (zlib) (lzma)
--------------------------------------------------------------------------------------
v63->chrome-64-0-3282-123.apk 43879588 32916357 32621974 18776996 15995242 13896562
chrome-64-0-3282-137.apk 43879588 28895294 28538751 1357320 1341073 1149331
chrome-65-0-3325-109.apk 43592997 31771385 31540550 16427116 14415021 12356765
v70->google-maps-9-71-0.apk 50568872 37992141 37531799 17293163 14562607 11430622
google-maps-9-72-0.apk 54342938 41897706 41475595 21301751 18752320 14066134
v660->weixin661android1220.apk 61301316 17565557 17372003 1927833 1794219 1659286
weixin662android1240.apk 63595334 38349926 38025483 22100454 18392769 15556315
weixin663android1260.apk 63595326 11614415 11531258 1044656 937920 940060
weixin665android1280.apk 63669882 21423459 21176790 9621032 9003472 7392063
--------------------------------------------------------------------------------------
Average Compression 100.0% 56.3% 55.8% 23.5% 20.4% 16.8%
======================================================================================额外：下载服务商的可能优化策略讨论
- 无法重新打包和签名的情况下如何支持v2签名Apk包的类似优化增量包？
- 收集常见的兼容压缩算法库；
- 动态计算出apk使用的可能压缩库和其压缩参数,以保证patch时byteByByte还原; 这样能解决绝大部分Apk的升级；否则剩下的Apk就退回类似直接diff的方案；
- Google Play patches : archive-patcher方案：
- file by file Diff & Patch; is an open-source project that allows space-efficient patching of zip archives. Many common distribution formats (such as jar and apk) are valid zip archives; archive-patcher works with all of them.
Authou：侯思松
分享于-Unity 深圳 meetup，2018.3.17，线下活动
技术分享PPT: https://pan.baidu.com/s/1JF66YeDYK1rOfdUJHV3msg 密码: wfe5原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录