高德车载导航的差分更新优化实践
导读
随着车载设备联网化，越来越多的车载设备从离线走到了线上。高德车载导航也早已从过去的离线安装包更新演进到了在线迭代更新。但原车载设备的Android硬件配置远低于手机，主要表现在处理器主频低、内存和存储空间有限，导致车载导航在车机上会出现无法下载新版本数据包、更新过程耗时长导致卡顿的情况，对导航应用的性能提出了要求。
为提高用户体验，高德技术团队立项解决了该问题。本文小结了高德车载导航在版本自更新演进过程中二进制差分解决方案的性能优化实践。
差分更新方案比较
对于应用程序的版本更新迭代，除了分发全量的安装包，还有一种更低成本的方式是分发增量包，即通过下发前后两个版本的差异部分(这个过程下面简称Diff)，然后在客户端对原版本进行补丁更新(这个过程下面简称Patch)。因此也叫差分更新。
业内比较流行的差分方案主要有: bsdiff、Xdelta3和Courgette。最后一个方案Courgette来自于谷歌，主要解决的是可执行文件的差分，而导航更新资源不仅包含可执行文件，还包含了图片等各种资源文件。所以，我们主要对比bsdiff和Xdelta3方案。
bsdiff和Xdelta3方案比较
下面是我们对选取的几个文件做的bsdiff和Xdelta3差分性能对比：
bsdiff的优势是压缩比高，生成的差分文件非常小，但Patch过程耗时。而Xdelta3的优势是Patch过程耗时极短，但内存消耗非常大。
相比高德车载导航自身运行内存开销不足100MB的情况，Xdelta3的Patch内存消耗无法接受。因此我们选用了bsdiff作为自更新方案。
原生bsdiff方案缺陷与改进
原生bsdiff方案使得压缩比问题得到解决，但在车载导航自更新中还存在下面两个缺陷：
内存消耗大，整个过程会占用10~35MB左右的内存。
耗时长，整个包更新时间在3分钟左右。
在对bsdiff的优化探索中我们发现Chromium开源项目中存在一份基于bsdiff的优化版本。该版本将bsidff的默认sufsort算法替换成了divsufsort算法，在Patch时间上有了较大的提升。
使用Chromium版本的bsdiff, 高德车载导航的自更新性能如下：
内存消耗在10~20MB。
整个Patch过程耗时仍然长达25秒左右。
耗时依然很长。
由于Patch过程是一个CPU密集型的操作，且车载设备CPU的性能普遍不足，这意味着在整个升级过程中用户能明显感受到导航的操作卡顿。同时，更新时间越长意味着遭遇断电的可能性也越大。
基于以上分析，我们决定对Chromium版本的bsdiff进行CPU和内存上的性能优化。
bsdiff在车载自更新业务中的性能优化实践
在车载自更新业务上，我们设定的目标是整体更新时间小于6秒，且内存开销小于2MB。整个优化的过程就是围绕时间和空间的取舍。
内存优化方案
经过对bsdiff源码的分析，其Patch内存主要开销来自文件内容在内存中的读写暂存和Bzip2的解压开销。通过调整Bzip2参数可以降低部分内存，但无法达到期望。而文件读写的内存占用主要来自于其在内存中的暂存。
基于bsdiff差分Patch包的文件格式，我们增加了滑动窗口缓冲区的Patch特性，使其在文件的流式处理上能够有更好的内存消耗可控性。每次读取和写入指定的滑动窗口大小数据，使数据即来即走。
算法优化方案
经过上述的优化后，Patch过程的主要性能瓶颈在于Bzip2的解压算法中，即使调整Bzip2参数也无法减少本身的计算量。
bsdiff差分算法的一个特性就是差分出的Patch数据包含了大量连续的01冗余数据，而Bzip2算法的优点就是对这类数据可以做到高度的压缩，这也是bsdiff压缩比高的原因。不过现在是目前的瓶颈。
此外，我们会制作软件整体的压缩差分包(即生成tar.bz2或zip格式文件)，也就是说针对每个Bzip2压缩后的差分文件还要再经过一次压缩归档。这也意味着在客户段要进行两次的解压。
替换压缩算法
类似的冗余压缩算法有RLE(Run-length encoding)，这个算法也是Bzip2算法的第一步。简单来说RLE算法就是针对连续多个冗余字节去掉其冗余字节，仅保留冗余的长度信息。这个算法相对更简单。
因此，我们将Bzip2压缩算法替换成了RLE算法，实际结果发现生成的Patch文件很大, 压缩比很低。但是可以通过再次压缩归档制作一次差分包，就可以达到和Bzip2几乎相同的压缩比效果。唯一的不足就是在客户端解压后会占用多一些磁盘空间, 而这个代价相对廉价多了。
优化性能对比
经过上述整体优化后，性能对比如下：
经过内存优化后的方案空间复杂度将为了O(1)。
上面的耗时差异在ARM车机会更明显：
最终优化收益：内存消耗控制在2MB以内，整体Patch更新耗时3~5秒。
小结
通过对bsdiff的优化，高德车载导航在自更新性能上取得了较大收益。大幅缩短了用户下载和更新时间，降低了对ARM车机的硬件资源要求。为推动车载导航OTA更新提供了技术基础，对未来高德车载导航在分发新功能、新业务上铺平了道路。
也许你还想看
招聘
高德工程技术中心长期招聘Java、Golang、Python、Android、iOS 前端资深工程师和技术专家，职位地点：北京，欢迎有兴趣的同学投递简历到tongxian.wxx@alibaba-inc.com （请注明来源：高德技术微信，简历投递）。