基于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