高性能diff&patch算法 -- 如何将微信Apk的官方增量包20.4M缩小到7.0M

高性能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)
  • BsDiffHDiffPatch
    • 为什么微信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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

UUG深圳

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏iOSDevLog

Colab WordCount

712
来自专栏章鱼的慢慢技术路

用ARM实现音乐电子相册

1502
来自专栏开发 & 算法杂谈

构建动态数据竞争检测平台

之前的文章分别介绍了基于Lockset算法、基于happens-before关系以及基于两者混合的方法。对于这些方法,已有的一些论文中提到的有关实验对比可能都比...

2204
来自专栏机器之心

专栏 | 想免费用谷歌资源训练神经网络?Colab详细使用教程

51611
来自专栏腾讯云TStack专栏

FileStore压缩存储(优化篇)

前言 前面已经分析过RBD在Ceph的文件分布,就是将一个完整的块设备,映射成大小相同的数据块,然后通过Crush算法进行Map,最后存储在文件中。FileS...

6624
来自专栏腾讯安全应急响应中心

短网址安全浅谈

何谓短网址(Short URL)?顾名思义,就是形式上比较短的网址,当前主要是借助短网址来替代原先冗长的网址,方便传输和分享。短网址服务也就是将长网址转换为短网...

950
来自专栏PingCAP的专栏

线性一致性和 Raft

在讨论分布式系统时,共识算法(Consensus algorithm)和一致性(Consistency)通常是讨论热点,两者的联系很微妙,很容易搞混。一些常见的...

860
来自专栏IT大咖说

分布式强一致性数据库的灵魂 - Raft 算法

? 内容来源:2017 年 11 月 18 日,PingCAP首席架构师唐刘在“数据技术嘉年华——分会场五:云架构、数据架构”进行《分布式强一致性数据库的灵魂...

3956
来自专栏安恒信息

LOCKY勒索者新花样:通过PDF投递

摘 要 最近安恒APT团队截获一个新版的LOCKY勒索者病毒样本,区别之前大多数样本采用WORD文档投递并用宏代码远程下载执行的方式,该样本在原有的WORD文档...

2696
来自专栏铭毅天下

吃透 | Elasticsearch filter和query的不同

除了确定文档是否匹配外,查询子句还计算了表示文档与其他文档相比匹配程度的_score。

1182

扫码关注云+社区