基于Android平臺差異化增量更新的實現(xiàn)

張 敏, 韓俊剛, 李 濤

(西安郵電大學(xué) 計算機學(xué)院, 陜西 西安 710121)

基于Android平臺差異化增量更新的實現(xiàn)

張 敏, 韓俊剛, 李 濤

(西安郵電大學(xué) 計算機學(xué)院, 陜西 西安 710121)

針對Android平臺下應(yīng)用程序頻繁更新升級所產(chǎn)生的數(shù)據(jù)流量增加問題，提出一種增量更新的升級方式。該方式采用服務(wù)器/客戶端模型，將差異化算法應(yīng)用到Android客戶端，在服務(wù)器端保存應(yīng)用程序的各個版本，當客戶端觸發(fā)更新事件時，上報當前應(yīng)用程序的版本號，服務(wù)器端借助BSDiff算法生成兩個版本的差異化序列并下發(fā)到客戶端，客戶端使用BSPatch技術(shù)將差異化序列與本機安裝的版本進行合成，完成一次增量更新。實驗結(jié)果表明,相比原有的全量更新方式，增量更新節(jié)省將近一半的流量。

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

隨著Android終端手機的普及，大量基于Android的應(yīng)用程序涌入了人們的生活，2012年安卓市場的應(yīng)用程序總數(shù)已超過了450,000，下載量可達100億[1]。由于bug的修復(fù)和新特性的加入導(dǎo)致應(yīng)用程序的更新升級變得非常頻繁，再加上追求功能的豐富與用戶界面的炫酷效果，程序的安裝包也在不斷增大。即使新包與舊包只有略微的差別,每次版本的升級仍下載完整的新安裝包進行替換安裝，這種全量更新的方式不僅浪費了較多的客戶端網(wǎng)絡(luò)流量，同時也增加了升級過程所耗費的時間。

增量更新是指基于差異化算法計算出兩個版本的差異化序列，客戶端只需要更新下載該序列即可。在差異化算法中，BSDiff多用于比較二進制文件的變化,因其產(chǎn)生的patch包較小而得到廣泛的應(yīng)用[2]。BSDiff最早是應(yīng)用在Unix系統(tǒng)中[3]，現(xiàn)代軟件中如谷歌瀏覽器也使用了該算法來減少升級包的大小。因此本文提出一種增量更新方式來減少應(yīng)用程序升級時所需的數(shù)據(jù)流量。

本文的組織結(jié)構(gòu)如下：第1章為LCS算法介紹，第2章介紹Android應(yīng)用程序增量更新的實現(xiàn)。第3章是實驗與性能分析。第4章總結(jié)全文。

1 LCS算法概述

在差異化算法BSDiff中，主要使用了最長公共子序列(Longest Common Subsequence ，LCS)來計算出兩個序列的最大公共子序列。 該子序列并不要求是連續(xù)，只要求其字符的順序一致[4，5]。該算法在代碼防剽竊系統(tǒng)[6]、數(shù)據(jù)清洗[7]和DNA序列匹配[8]等領(lǐng)域都有廣泛應(yīng)用，現(xiàn)以DNA序列ATCTGATC與TGCATAC兩個序列為例，其最大的子序列為TCTAC。求LCS的過程實際就是在給V串和W串插入空格使得兩個串在最大程度上對齊(相應(yīng)元素對映),如圖1所示。

圖1 求ATCTGATC與TGCATAC

利用計算編輯距離的方法計算LCS，現(xiàn)將以上過程對應(yīng)到一個二維的矩陣上，首先建立一個橫向為V，縱向為W的坐標系，如圖2所示。

圖2 坐標建立(一條路徑)

計算圖中每個節(jié)點的數(shù)值[4]

(1)

其中i為縱坐標，j為橫坐標。當i=0，j=0時，該值為S0,0=0。

圖2為其中一條路徑演示過程。先從矩陣的左上角點(0,0)出發(fā)沿任意方向，計算坐標對應(yīng)元素是否相等，根據(jù)式(1)計算節(jié)點的數(shù)值，以圖2中點(2,2)為例，T和G不相等，故S應(yīng)等于S1,2或S2,1中的大者。按照以上方法計算出矩陣中每個節(jié)點的值，從S=i到S=i+1的斜線的終點，也就是S值得分加1的點都是兩個串相等的點。圖2最下角節(jié)點的S值就是相等點的個數(shù)。其中水平橫箭頭代表i串(TGCATAC)插入一個空與j對齊，豎直箭頭代表j串(ATCTGATC)插入一個空與i串對其。這樣整個表的各節(jié)點值做完后就可以直接得到LCS的長度(最右下角的S值)和最大子序列。

2 Android應(yīng)用程序增量更新的實現(xiàn)

在3G或WiFi環(huán)境下，大部分的應(yīng)用程序使用全包安裝來更新，即下載應(yīng)用程序的新版本，利用Android手機上自帶的packageManager卸載手機上的舊版本并且安裝新版本，完成應(yīng)用程序的升級更新。在手機為root權(quán)限時，可以自動實現(xiàn)完成這一過程，而不需用戶的同意。

為了實現(xiàn)Android應(yīng)用程序的增量更新，使用客戶端/服務(wù)器模型，客戶端與服務(wù)端是同一個系統(tǒng)中的不同進程，客戶端根據(jù)需求向服務(wù)端請求某種服務(wù)[9]。增量更新整體框架如圖3所示。在服務(wù)器端保存應(yīng)用的多個版本，利用BSDiff計算不同版本之間的差異數(shù)據(jù)，生成不同的補丁包下發(fā)到客戶端。其中每個補丁包的生成用單獨的線程來實現(xiàn)，可以提高CPU的利用率。生成補丁包后在手機客戶端利用BSPatch合成新的安裝包。由此可見，增量更新的關(guān)鍵是服務(wù)器端BSDiff算法與客戶端BSPatch算法的實現(xiàn)。

圖3 增量更新整體結(jié)構(gòu)

2.1 BSDiff的實現(xiàn)過程

利用LCS找出最大公共子序列，然后再加上額外信息組成patch包，這種方法可以產(chǎn)生小的patch 補丁。具體實現(xiàn)過程如圖4所示。

圖4 BSDiff實現(xiàn)流程圖

定義兩個數(shù)組newbuf[],oldbuf[]將新舊安裝包的文件序列分別存入其中，并獲得其長度newsize，oldsize。根據(jù)圖4中的每個步驟獲得幾個數(shù)據(jù)段，其中diffBlock表示兩個序列同一位置的差異數(shù)據(jù)段；extblock表示新包與舊包相比的額外數(shù)據(jù)段；extlen表示extblock的長度；invalidlen表示新舊安裝包序列對比后，舊安裝包中的無效數(shù)據(jù)段長度；ctrlblock包含一些記錄控制信息的小塊,其內(nèi)容包括從舊包和diffBlocky讀取的序列長度，從extblock中讀取的序列長度，以及從舊包中跳過不讀的序列長度。

將各個數(shù)據(jù)段寫入patch文件中，其中diffBlock與extraBlock經(jīng)過gzip算法壓縮后寫入patch文件中，由于diffBlock記錄的是新版軟件安裝包和舊版軟件安裝包各個相似段的差異，所以diffBlock的取值都較小且取值接近，經(jīng)過gzip算法達到較大的壓縮率，可以最大化的減少patch包的大小，更好的實現(xiàn)增量更新。

2.2 BSPatch的實現(xiàn)過程

由BSDiff產(chǎn)生的patch包主要含6部分內(nèi)容：controlBlock_length、diffBlock_length、newFile_length、controlBlock、diffBlock、extraBlock。

根據(jù)patch序列的內(nèi)容，將patch包與本機的舊安裝包合成，生成新安裝包。具體實現(xiàn)流程如圖5所示。

定義數(shù)組oldbuf[]存入就安裝包序列，讀取patch包中ctrlblock中存入的控制信息，根據(jù)對應(yīng)的控制信息在oldbuf[]與patch包中交替讀取數(shù)據(jù)，存入newbuf[]中，合成新的安裝包序列。

圖5 BSPatch的實現(xiàn)流程

2.3 增量更新的總體實現(xiàn)過程

完成一次完整的增量更新具體過程如下。

(1)服務(wù)器端保存多個應(yīng)用的多個版本，含最新版本，并根據(jù)BSDiff計算出不同版本的差異，生成不同的補丁包保存在服務(wù)器端。

(2)通過Android自帶的PackageManager查看手機上已安裝的所有應(yīng)用程序列表，用戶可以根據(jù)其意愿選擇需要升級的應(yīng)用。

(3)手機連接服務(wù)器，上報手機上已安裝包信息，包括安裝包名，版本號，渠道號等。

(4)服務(wù)器收到上報的軟件列表信息后，與服務(wù)器端進行對比查看是否有最新版本，若發(fā)現(xiàn)最新版本并已經(jīng)合成了補丁包，則進行增量更新，否則為普通更新。將補丁包的URL發(fā)送到手機端。

(5)當用戶收到可更新信息時，用Handler發(fā)送消息，顯示在界面上。

(6)當用戶觸發(fā)某個應(yīng)用的下載時，通過應(yīng)用補丁包的URL下載補丁包，在手機端通過BSPatch合成新的安裝包并安裝。

3 實驗與性能分析

實驗使用PC機作為服務(wù)器端，三星S5830作為手機客戶端。兩個設(shè)備連入同一局域網(wǎng)，選取手機上安裝的多個應(yīng)用，并在服務(wù)器端保存這些應(yīng)用的多個版本，當客戶端觸發(fā)更新事件時，服務(wù)器端使用BSDiff計算出patch包，并將patch包，patch包大小，新版本的原有大小組成一串數(shù)據(jù)，使用Message下發(fā)到客戶端，并用Handler更新界面，對比新版本原有大小和patch包大小，結(jié)果如圖6所示。

圖6 全量更新與增量更新包大小對比

圖中橫坐標為選取的應(yīng)用程序名稱，縱坐標為安裝包的包大小?？梢钥闯?，差異化算法產(chǎn)生的補丁包，比全量更新時大小平均減少了45%，其中減少最多的為67%(微信)，減少最少的為13%(百度地圖)。選取應(yīng)用程序的兩個連續(xù)的版本(相鄰時間發(fā)布的應(yīng)用版本號)，其補丁包的大小取決于新舊安裝包之間的差異化序列對比。結(jié)果表明，Android手機應(yīng)用使用增量更新的方式進行升級更新，不僅縮短了升級的時間，還節(jié)省了所產(chǎn)生的用戶流量。假設(shè)每個人的手機安裝20個應(yīng)用程序，每個應(yīng)用10M，全球Android手機大概500多萬部，每個應(yīng)用升級更新平均節(jié)省一半流量，所有應(yīng)用整體升級一次將節(jié)省大概500TB流量，數(shù)字相當可觀。所以使用差異化算法對Android手機應(yīng)用進行增量更新是很有必要的。

4 結(jié)束語

研究Android平臺下的應(yīng)用增量更新，使用差異化算法，在服務(wù)器端利用BSDiff對比新舊安裝包的文件序列生成補丁包。手機客戶端用戶通過補丁包的URL下載補丁包并利用BSPatch合成新的安裝包，實現(xiàn)差異化增量更新。實驗結(jié)果表明此過程可節(jié)省用戶流量。

[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網(wǎng)絡(luò)文檔協(xié)同平臺系統(tǒng)的設(shè)計與實現(xiàn)[D]. 長春：吉林大學(xué), 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]. 計算機與數(shù)字工程， 2012, 40(3): 14-17.

[5] 李大衛(wèi).基于動態(tài)規(guī)劃的序列比對的并行算法研究[J].井岡山大學(xué)學(xué)報:自然科學(xué)版, 2011,32(3):80-84.

[6] 鐘美，張麗萍，劉東升.基于XML的C代碼抄襲檢測算法[J]. 計算機工程與應(yīng)用，2011,47(8): 215-218.

[7] 刁興春，譚明超，曹建軍. 一種融合多種編輯距離的字符串相似度計算方法[J]. 計算機應(yīng)用研究，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擴展模型的設(shè)計與實現(xiàn)[J]. 西安郵電大學(xué)學(xué)報，2013，18(3)：96-99.

[責(zé)任編輯:祝劍]

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

國家自然科學(xué)基金資助項目(61136002)

張敏(1990-)，女，碩士研究生，研究方向為網(wǎng)絡(luò)與多媒體通信。E-mail: club822@126.com 韓俊剛(1943-)，男，教授，從事計算機圖形學(xué)，集成電路設(shè)計等研究。E-mail: hanjungang@163.com

TP393

A

2095-6533(2014)01-0082-04