高性能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 条评论
登录 后参与评论

相关文章

来自专栏unlike

用paxos实现多副本日志系统--basic paxos部分

为了理解paxos协议,开始时看了好些资料,但始终没有理解透,直到我看了这个视频:http://v.youku.com/v_show/id_XNjgyODc3O...

4447
来自专栏韩东吉的Unity杂货铺

零基础入门 31:游戏中的变速效果

今天给大家带来一篇短小精悍的内容,那就是游戏中的变速效果,变速包括了快速和慢速,有的时候在游戏关卡结尾的时候通过慢速慢镜头来展示结束动作特效等,有不错的表现效果...

682
来自专栏CSDN技术头条

开源神器,无需一行代码就能搞定机器学习,不会数学也能上手

作者丨Shantanu Kumar 翻译丨魏伟 对于机器学习和数据科学的初学者来说,最大的挑战之一是需要同时学习太多知识,特别是如果你不知道如何编码。你需要快速...

2168
来自专栏微信终端开发团队的专栏

Windows微信DPI适配

一、背景 随着近些年屏幕设备的不断发展,各种显示设备的分辨率也越来越高,在尺寸保持基本不变的情况下,分辨率越高,设备的DPI也越高,清晰度也就越高。高DPI的...

3159
来自专栏我是极客人

图片去霾算法实践】NDK下二维数组的传递

最近看到了一篇关于图片“去霾算法”的文章,一下子就有了兴趣,所以想着能不能实现。由于数学能力捉急,无法理解文章的思想和相关论文。于是在Github上找到了相关的...

673
来自专栏偏前端工程师的驿站

Thinking in React Implemented by Reagent

983
来自专栏Material Design组件

Human Interface Guidelines —— 活动视图(Activity Views)

3509
来自专栏小樱的经验随笔

CTF---密码学入门第五题 传统知识+古典密码

传统知识+古典密码分值:10 来源: 霜羽 难度:易 参与人数:2297人 Get Flag:735人 答题人数:938人 解题通过率:78% 小明某一天收到一...

35312
来自专栏点滴积累

geotrellis使用(十二)再记录一次惨痛的伪BUG调试经历(数据导入以及读取瓦片)

Geotrellis系列文章链接地址http://www.cnblogs.com/shoufengwei/p/5619419.html 目录 前言 BUG还原...

2654
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之SP/SI帧

当前视频编码标准主要包括三种的帧类型:I帧、P帧和B帧。随着H.264/AVC为了顺应视频流的带宽自适应性和抗误码性能的要求,又定义了两种新的帧类...

791

扫码关注云+社区