基于Android平台差异化增量更新的实现

张 敏, 韩俊刚, 李 涛

(西安邮电大学 计算机学院, 陕西 西安 710121)

基于Android平台差异化增量更新的实现

张 敏, 韩俊刚, 李 涛

(西安邮电大学 计算机学院, 陕西 西安 710121)

针对Android平台下应用程序频繁更新升级所产生的数据流量增加问题，提出一种增量更新的升级方式。该方式采用服务器/客户端模型，将差异化算法应用到Android客户端，在服务器端保存应用程序的各个版本，当客户端触发更新事件时，上报当前应用程序的版本号，服务器端借助BSDiff算法生成两个版本的差异化序列并下发到客户端，客户端使用BSPatch技术将差异化序列与本机安装的版本进行合成，完成一次增量更新。实验结果表明,相比原有的全量更新方式，增量更新节省将近一半的流量。

安卓；差异化；增量更新；BSDiff；BSPatch

随着Android终端手机的普及，大量基于Android的应用程序涌入了人们的生活，2012年安卓市场的应用程序总数已超过了450,000，下载量可达100亿[1]。由于bug的修复和新特性的加入导致应用程序的更新升级变得非常频繁，再加上追求功能的丰富与用户界面的炫酷效果，程序的安装包也在不断增大。即使新包与旧包只有略微的差别,每次版本的升级仍下载完整的新安装包进行替换安装，这种全量更新的方式不仅浪费了较多的客户端网络流量，同时也增加了升级过程所耗费的时间。

增量更新是指基于差异化算法计算出两个版本的差异化序列，客户端只需要更新下载该序列即可。在差异化算法中，BSDiff多用于比较二进制文件的变化,因其产生的patch包较小而得到广泛的应用[2]。BSDiff最早是应用在Unix系统中[3]，现代软件中如谷歌浏览器也使用了该算法来减少升级包的大小。因此本文提出一种增量更新方式来减少应用程序升级时所需的数据流量。

本文的组织结构如下：第1章为LCS算法介绍，第2章介绍Android应用程序增量更新的实现。第3章是实验与性能分析。第4章总结全文。

1 LCS算法概述

在差异化算法BSDiff中，主要使用了最长公共子序列(Longest Common Subsequence ，LCS)来计算出两个序列的最大公共子序列。 该子序列并不要求是连续，只要求其字符的顺序一致[4，5]。该算法在代码防剽窃系统[6]、数据清洗[7]和DNA序列匹配[8]等领域都有广泛应用，现以DNA序列ATCTGATC与TGCATAC两个序列为例，其最大的子序列为TCTAC。求LCS的过程实际就是在给V串和W串插入空格使得两个串在最大程度上对齐(相应元素对映),如图1所示。

图1 求ATCTGATC与TGCATAC

利用计算编辑距离的方法计算LCS，现将以上过程对应到一个二维的矩阵上，首先建立一个横向为V，纵向为W的坐标系，如图2所示。

图2 坐标建立(一条路径)

计算图中每个节点的数值[4]

(1)

其中i为纵坐标，j为横坐标。当i=0，j=0时，该值为S0,0=0。

图2为其中一条路径演示过程。先从矩阵的左上角点(0,0)出发沿任意方向，计算坐标对应元素是否相等，根据式(1)计算节点的数值，以图2中点(2,2)为例，T和G不相等，故S应等于S1,2或S2,1中的大者。按照以上方法计算出矩阵中每个节点的值，从S=i到S=i+1的斜线的终点，也就是S值得分加1的点都是两个串相等的点。图2最下角节点的S值就是相等点的个数。其中水平横箭头代表i串(TGCATAC)插入一个空与j对齐，竖直箭头代表j串(ATCTGATC)插入一个空与i串对其。这样整个表的各节点值做完后就可以直接得到LCS的长度(最右下角的S值)和最大子序列。

2 Android应用程序增量更新的实现

在3G或WiFi环境下，大部分的应用程序使用全包安装来更新，即下载应用程序的新版本，利用Android手机上自带的packageManager卸载手机上的旧版本并且安装新版本，完成应用程序的升级更新。在手机为root权限时，可以自动实现完成这一过程，而不需用户的同意。

为了实现Android应用程序的增量更新，使用客户端/服务器模型，客户端与服务端是同一个系统中的不同进程，客户端根据需求向服务端请求某种服务[9]。增量更新整体框架如图3所示。在服务器端保存应用的多个版本，利用BSDiff计算不同版本之间的差异数据，生成不同的补丁包下发到客户端。其中每个补丁包的生成用单独的线程来实现，可以提高CPU的利用率。生成补丁包后在手机客户端利用BSPatch合成新的安装包。由此可见，增量更新的关键是服务器端BSDiff算法与客户端BSPatch算法的实现。

图3 增量更新整体结构

2.1 BSDiff的实现过程

利用LCS找出最大公共子序列，然后再加上额外信息组成patch包，这种方法可以产生小的patch 补丁。具体实现过程如图4所示。

图4 BSDiff实现流程图

定义两个数组newbuf[],oldbuf[]将新旧安装包的文件序列分别存入其中，并获得其长度newsize，oldsize。根据图4中的每个步骤获得几个数据段，其中diffBlock表示两个序列同一位置的差异数据段；extblock表示新包与旧包相比的额外数据段；extlen表示extblock的长度；invalidlen表示新旧安装包序列对比后，旧安装包中的无效数据段长度；ctrlblock包含一些记录控制信息的小块,其内容包括从旧包和diffBlocky读取的序列长度，从extblock中读取的序列长度，以及从旧包中跳过不读的序列长度。

将各个数据段写入patch文件中，其中diffBlock与extraBlock经过gzip算法压缩后写入patch文件中，由于diffBlock记录的是新版软件安装包和旧版软件安装包各个相似段的差异，所以diffBlock的取值都较小且取值接近，经过gzip算法达到较大的压缩率，可以最大化的减少patch包的大小，更好的实现增量更新。

2.2 BSPatch的实现过程

由BSDiff产生的patch包主要含6部分内容：controlBlock_length、diffBlock_length、newFile_length、controlBlock、diffBlock、extraBlock。

根据patch序列的内容，将patch包与本机的旧安装包合成，生成新安装包。具体实现流程如图5所示。

定义数组oldbuf[]存入就安装包序列，读取patch包中ctrlblock中存入的控制信息，根据对应的控制信息在oldbuf[]与patch包中交替读取数据，存入newbuf[]中，合成新的安装包序列。

图5 BSPatch的实现流程

2.3 增量更新的总体实现过程

完成一次完整的增量更新具体过程如下。

(1)服务器端保存多个应用的多个版本，含最新版本，并根据BSDiff计算出不同版本的差异，生成不同的补丁包保存在服务器端。

(2)通过Android自带的PackageManager查看手机上已安装的所有应用程序列表，用户可以根据其意愿选择需要升级的应用。

(3)手机连接服务器，上报手机上已安装包信息，包括安装包名，版本号，渠道号等。

(4)服务器收到上报的软件列表信息后，与服务器端进行对比查看是否有最新版本，若发现最新版本并已经合成了补丁包，则进行增量更新，否则为普通更新。将补丁包的URL发送到手机端。

(5)当用户收到可更新信息时，用Handler发送消息，显示在界面上。

(6)当用户触发某个应用的下载时，通过应用补丁包的URL下载补丁包，在手机端通过BSPatch合成新的安装包并安装。

3 实验与性能分析

实验使用PC机作为服务器端，三星S5830作为手机客户端。两个设备连入同一局域网，选取手机上安装的多个应用，并在服务器端保存这些应用的多个版本，当客户端触发更新事件时，服务器端使用BSDiff计算出patch包，并将patch包，patch包大小，新版本的原有大小组成一串数据，使用Message下发到客户端，并用Handler更新界面，对比新版本原有大小和patch包大小，结果如图6所示。

图6 全量更新与增量更新包大小对比

图中横坐标为选取的应用程序名称，纵坐标为安装包的包大小。可以看出，差异化算法产生的补丁包，比全量更新时大小平均减少了45%，其中减少最多的为67%(微信)，减少最少的为13%(百度地图)。选取应用程序的两个连续的版本(相邻时间发布的应用版本号)，其补丁包的大小取决于新旧安装包之间的差异化序列对比。结果表明，Android手机应用使用增量更新的方式进行升级更新，不仅缩短了升级的时间，还节省了所产生的用户流量。假设每个人的手机安装20个应用程序，每个应用10M，全球Android手机大概500多万部，每个应用升级更新平均节省一半流量，所有应用整体升级一次将节省大概500TB流量，数字相当可观。所以使用差异化算法对Android手机应用进行增量更新是很有必要的。

4 结束语

研究Android平台下的应用增量更新，使用差异化算法，在服务器端利用BSDiff对比新旧安装包的文件序列生成补丁包。手机客户端用户通过补丁包的URL下载补丁包并利用BSPatch合成新的安装包，实现差异化增量更新。实验结果表明此过程可节省用户流量。

[1] Samteladze N, Christensen K.Delta Encoding for Less Traffic for Apps[C]// Damla Turgut. IEEE 37th Conference. Colorado State University：Jens Tölle,2012:212-215.

[2] 张珺垚. 基于P2P网络文档协同平台系统的设计与实现[D]. 长春：吉林大学, 2009:47-48.

[3] Hunt J W, MacIlroy M D. An algorithm for differential file comparison[EB/OL].(1976-7)[2013-11-2]. https://nanohub.org/infrastructure/rappture/export/2189/trunk/gui/src/diff.pdf.

[4] 牛永洁，张成. 多种字符串相似度算法的比较研究[J]. 计算机与数字工程， 2012, 40(3): 14-17.

[5] 李大卫.基于动态规划的序列比对的并行算法研究[J].井冈山大学学报:自然科学版, 2011,32(3):80-84.

[6] 钟美，张丽萍，刘东升.基于XML的C代码抄袭检测算法[J]. 计算机工程与应用，2011,47(8): 215-218.

[7] 刁兴春，谭明超，曹建军. 一种融合多种编辑距离的字符串相似度计算方法[J]. 计算机应用研究，2010,27(12): 4523-4525.

[8] Wise M J. Neweyes: A System for Comparing Biological Sequences Using the Running Karp-Rabin Greedy Stringtiling Algorithm[C]// Burkhard Rost .In Third International Conference on Intelligent System for Molecular Biology . Oxford Journals:Ambridge,1995:393-401.

[9] 陈莉君，张超.Android进程间通信Binder扩展模型的设计与实现[J]. 西安邮电大学学报，2013，18(3)：96-99.

[责任编辑:祝剑]

Realization of incremental updates on delta encoding based on the Android platform

ZHANG Min， HANG Jungang， LI Tao

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to solve the data traffic increasing problem which is caused by applications in Android platform upgrade frequently,we propose an incremental update of the upgrade. This method uses a server / client model.We apply the difference algorithm to Android client and save each version update application on the server side. When the client triggered update event, it sends the information about the current version of the application to the sever in the same time.In the server-side ,it uses BSDiff algorithm to calculate the different sequences between the two versions and sends them to the client.And then client uses BSPatch technology combining differentiation sequence and the installed version,which completes an incremental update. Experimental results show that compared to the full amount of the original update method, incremental updates save nearly half of traffic.

Android, delta encoding, increased update, BSDiff; BSPatch

10.13682/j.issn.2095-6533.2014.01.018

2013-11-20

国家自然科学基金资助项目(61136002)

张敏(1990-)，女，硕士研究生，研究方向为网络与多媒体通信。E-mail: club822@126.com 韩俊刚(1943-)，男，教授，从事计算机图形学，集成电路设计等研究。E-mail: hanjungang@163.com

TP393

A

2095-6533(2014)01-0082-04