基于BSDiff的改進(jìn)遠(yuǎn)程增量更新方案

陳迪榮，包曉安，杜 鵬，胡逸飛，蘇鴻斌

(浙江理工大學(xué) 信息學(xué)院，浙江 杭州 310018)

物聯(lián)網(wǎng)被視為繼計(jì)算機(jī)、互聯(lián)網(wǎng)之后信息技術(shù)產(chǎn)業(yè)發(fā)展的第三次革命[1-2]。基于物聯(lián)網(wǎng)技術(shù)的智能可穿戴設(shè)備、智能家居、智能傳感器等應(yīng)用越來越成熟[3-5]，相應(yīng)的應(yīng)用端業(yè)務(wù)的更新和迭代也越來越頻繁。由于終端設(shè)備數(shù)量龐大且布設(shè)范圍廣，為了更好地維護(hù)相應(yīng)的設(shè)備，遠(yuǎn)程在線更新固件的功能十分重要[6]。傳統(tǒng)的遠(yuǎn)程固件更新通常采用全量更新的方式。這種更新方式往往需要長時(shí)間占用網(wǎng)絡(luò)帶寬，同時(shí)還可能會(huì)出現(xiàn)丟包、斷連等情況，不僅增加流量資費(fèi)，還增加終端設(shè)備功耗[7]。因此，減少更新傳輸?shù)臄?shù)據(jù)量，提高升級(jí)的效率是物聯(lián)網(wǎng)終端設(shè)備遠(yuǎn)程更新需要解決的關(guān)鍵問題。

文獻(xiàn)[8]基于LWM2M 協(xié)議對(duì)物聯(lián)網(wǎng)云平臺(tái)進(jìn)行優(yōu)化，提高了遠(yuǎn)程更新的通用性、可靠性和穩(wěn)定性。文獻(xiàn)[9]針對(duì)無法主動(dòng)進(jìn)行聯(lián)網(wǎng)更新的終端設(shè)備，提出了通過與終端設(shè)備相連的主控設(shè)備進(jìn)行郵遞式升級(jí)的方案。但是該方案沒有對(duì)接云平臺(tái)，在批量作業(yè)中缺乏靈活性。文獻(xiàn)[10]通過改進(jìn)BSDiff算法生成的補(bǔ)丁文件格式，提高了終端打補(bǔ)丁的效率。文獻(xiàn)[11]在文獻(xiàn)[10]改進(jìn)的補(bǔ)丁文件的基礎(chǔ)上，將BSDiff 算法中的并行解壓過程替換為串行解壓，并減小了申請(qǐng)的輔助空間，提出了一種節(jié)約內(nèi)存的增量更新算法。文獻(xiàn)[12]設(shè)計(jì)了一套安全備份和校驗(yàn)機(jī)制，保證遠(yuǎn)程升級(jí)過程中數(shù)據(jù)傳輸完整可靠，并使用差異文件減少升級(jí)的流量消耗。目前，除了軟件升級(jí)方面，增量更新還被廣泛應(yīng)用于數(shù)據(jù)同步、云存儲(chǔ)、蛋白質(zhì)序列比較等場景[13-14]。

以上研究從遠(yuǎn)程更新平臺(tái)設(shè)計(jì)、終端設(shè)備升級(jí)過程以及增量更新的應(yīng)用進(jìn)行了分析。由以上分析可知，通過增量更新的方式可以有效減少傳輸?shù)臄?shù)據(jù)量，提高終端設(shè)備更新的效率。本文以減少需要傳輸?shù)母聰?shù)據(jù)量為核心思想，對(duì)更新服務(wù)端的固件管理方案進(jìn)行優(yōu)化，采用改進(jìn)的BSDiff差分算法即時(shí)生成新舊固件的增量更新文件，減少需要傳輸?shù)母聰?shù)據(jù)量，進(jìn)而提升了終端設(shè)備遠(yuǎn)程更新的效率。

1 算法分析

1.1 BSDiff差分算法

可執(zhí)行文件之間的差異復(fù)雜，源文件中的微小更改可能會(huì)在整個(gè)可執(zhí)行文件中造成重大更改。BSDiff差分算法的提出針對(duì)可執(zhí)行文件更新前后變動(dòng)的兩個(gè)重要規(guī)律[6，15]：(1)在一個(gè)可執(zhí)行文件中，不受修改直接影響的那一部分，差異通常很小，修改后的地址可能僅改變其最低有效的一個(gè)或兩個(gè)字節(jié)；(2)更新后的代碼和數(shù)據(jù)會(huì)有較大的位置變動(dòng)，但這種變動(dòng)大多為整塊的移動(dòng)，即某一塊位置中代碼內(nèi)的指針地址變動(dòng)均會(huì)有相同的位移值。因此相同源代碼對(duì)應(yīng)的兩個(gè)代碼塊中，大部分內(nèi)容字節(jié)差為0，而少部分需要更新的地址位移數(shù)據(jù)又存在大量相同的位移值。如圖1所示，截取的是V3和V4這兩個(gè)功能一致的相鄰版本固件通過Beyond Compare3軟件進(jìn)行差異對(duì)比后的部分內(nèi)容，可以看到大部分的字節(jié)差異為0，這樣的字節(jié)差異字符串就具有高度可壓縮特性。

圖1 Beyond Compare3差異比較結(jié)果

基于以上特性，通過BSDiff差分算法即可生成高度壓縮的補(bǔ)丁包，其具體步驟如下：

步驟1讀取舊文件，使用后綴排序或者哈希算法生成字符串索引；

步驟2使用該索引遍歷新文件，生成差異文件和新增文件；

步驟3將差異文件和新增文件以及必要的索引控制信息進(jìn)行壓縮，生成補(bǔ)丁包。

步驟1是目前增量更新算法的瓶頸部分。BSDiff算法采用了qSufSort后綴數(shù)組算法來進(jìn)行索引的生成。該算法的基本思想是，后綴的后綴是字符串中后綴的前綴，并且已經(jīng)在后綴數(shù)組的另一個(gè)區(qū)域中部分排序。因此，不再使用已經(jīng)比較過的字符，而是使用現(xiàn)有的部分結(jié)果。該算法時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)。算法偽代碼如下[16]：

def qSufSort(T)

Sort suffixes Si according to their first character into SA

Init additional arraysVandL

h:= 1

while(-L[0]!=n):

Sort suffixes Si in unsorted groups in SA byV[i+h]

Mark borders of Aleft，Amiddle and Aright

Calculate new groups

UpdateVandL

h=h·2

1.2 DivSufSort后綴數(shù)組構(gòu)造算法

后綴數(shù)組的有效構(gòu)造是一個(gè)研究熱點(diǎn)，目前已經(jīng)有許多優(yōu)秀的后綴數(shù)組構(gòu)造算法，其中DivSufSort是目前實(shí)踐上速度最快的后綴數(shù)組構(gòu)造算法[16]，其理論時(shí)間復(fù)雜度為O(nlogn)。此外，還有時(shí)間復(fù)雜度為O(n)的SAIS算法。DivSufSort與SAIS算法都是基于誘導(dǎo)排序的后綴數(shù)組構(gòu)造算法，但是DivSufSort更快。其主要原因可以歸為兩點(diǎn)[17-18]：首先，SAIS算法通過遞歸的方式對(duì)初始后綴進(jìn)行排序，而DivSufSort采用了實(shí)際運(yùn)行時(shí)更快的字符串排序和類似前綴倍增的方式，同時(shí)還采用了重復(fù)檢測等方法，進(jìn)一步減少了運(yùn)行時(shí)間；其次，在SAIS算法中，已被初步排序的后綴在之后的誘導(dǎo)過程會(huì)被移動(dòng)，而在DivSufSort算法中則保持不動(dòng)。這使得DivSufSort算法在第一階段的誘導(dǎo)過程中可以更快。Google對(duì)以上后綴數(shù)組構(gòu)造算法進(jìn)行了運(yùn)行時(shí)間以及內(nèi)存空間占用上的對(duì)比，對(duì)比結(jié)果如下表所示。

綜合表1、表2可知，在運(yùn)行時(shí)間上，DivSufSort表現(xiàn)明顯優(yōu)于qSufSort，平均提升了61.10%。而在內(nèi)存空間占用上，DivSufSort的表現(xiàn)僅次于SAIS。相較于qSufSort，DivSufSort平均減少了約35.51%的內(nèi)存空間占用。

表1 運(yùn)行時(shí)間對(duì)比

表2 內(nèi)存空間占用對(duì)比

2 遠(yuǎn)程增量更新方案設(shè)計(jì)

為了提高終端設(shè)備遠(yuǎn)程更新的效率，本文以減少需要傳輸?shù)母聰?shù)據(jù)量為核心思想，采用遠(yuǎn)程下發(fā)增量更新包的方式進(jìn)行終端設(shè)備的更新。遠(yuǎn)程增量更新方案以BSDiff差分算法為核心，可以生成高度壓縮的增量更新包，有效減少傳輸?shù)臅r(shí)間和數(shù)據(jù)量。此外，選用性能更高的DivSufSort后綴數(shù)組構(gòu)造算法還可對(duì)BSDiff差分算法進(jìn)行改進(jìn)，以提高差分算法的運(yùn)行效率。遠(yuǎn)程增量更新系統(tǒng)整體框圖如圖2所示。首先，在增量更新服務(wù)平臺(tái)進(jìn)行終端設(shè)備固件版本號(hào)的比對(duì)；然后在增量更新服務(wù)平臺(tái)運(yùn)行改進(jìn)的BSDiff差分算法，生成新舊版本固件之間的增量更新包；最后，終端設(shè)備通過物聯(lián)網(wǎng)無線傳輸網(wǎng)絡(luò)請(qǐng)求增量更新包數(shù)據(jù)，終端設(shè)備執(zhí)行BSPatch程序構(gòu)造完整的更新包。校驗(yàn)通過后，終端設(shè)備執(zhí)行升級(jí)程序。

圖2 增量更新方案整體框圖

2.1 改進(jìn)的BSDiff差分算法

改進(jìn)BSDiff差分算法生成補(bǔ)丁包的具體步驟與原先的BSDiff差分算法相同，其主要區(qū)別在于使用DivSufSort后綴數(shù)組構(gòu)造算法對(duì)步驟1中生成舊文件的字符串索引的過程進(jìn)行了改進(jìn)。具體分為3個(gè)階段[16]：

(1)對(duì)舊文件進(jìn)行一次掃描，確定所有后綴的類型，并計(jì)算相應(yīng)的c0和(c0，c1)的桶邊界；

(2)對(duì)所有B*后綴進(jìn)行排序，并將它們放置在SA中的正確位置。首先必須對(duì)B*子字符串進(jìn)行排序。然后，使用排序后的B*子字符串的等級(jí)對(duì)相應(yīng)的B*后綴進(jìn)行排序；

(3)對(duì)SA進(jìn)行兩次掃描，以得出所有剩余后綴的正確位置，從而得到字符串索引。首先從右向左掃描以誘導(dǎo)所有B后綴，然后從左向右掃描以誘導(dǎo)所有A后綴。

2.2 遠(yuǎn)程更新服務(wù)平臺(tái)分析

遠(yuǎn)程更新服務(wù)平臺(tái)主要實(shí)現(xiàn)遠(yuǎn)程更新的管理控制功能，包括固件包的管理、版本控制以及更新數(shù)據(jù)下發(fā)等。傳統(tǒng)的全量更新方案一般只需要在更新服務(wù)平臺(tái)保留一個(gè)最新版本的固件包。這種方案使得更新服務(wù)平臺(tái)的控制邏輯變得較為簡單，但是由于每次更新都需要向終端設(shè)備發(fā)送整個(gè)固件包，這就導(dǎo)致終端設(shè)備需要長時(shí)間連續(xù)的與更新服務(wù)平臺(tái)進(jìn)行數(shù)據(jù)通信，終端設(shè)備耗電量大，更新效率低。當(dāng)同一時(shí)段請(qǐng)求更新的設(shè)備過多，還會(huì)對(duì)更新服務(wù)平臺(tái)造成較大的壓力。

傳統(tǒng)的增量更新方案需要在更新服務(wù)平臺(tái)進(jìn)行增量更新包的集中管理，當(dāng)終端設(shè)備進(jìn)行鄰近版本更新時(shí)，只需發(fā)送一個(gè)相應(yīng)的包。由于這些增量更新包通常是高度壓縮的，可以有效減少更新時(shí)傳輸?shù)臄?shù)據(jù)量。但是當(dāng)設(shè)備需要跨越多個(gè)版本進(jìn)行更新時(shí)，更新服務(wù)平臺(tái)則需要多次發(fā)送補(bǔ)丁包，這使得終端設(shè)備的更新效率有所降低。

2.3 改進(jìn)的增量更新服務(wù)平臺(tái)

與傳統(tǒng)遠(yuǎn)程更新服務(wù)平臺(tái)方案不同，本文設(shè)計(jì)的增量更新服務(wù)平臺(tái)需要保留用戶上傳的每一個(gè)版本的固件包，這是因?yàn)闊o法保證所有的終端設(shè)備都已經(jīng)及時(shí)升級(jí)到最新版本，而增量更新包需要通過對(duì)比新舊兩個(gè)版本的固件才能生成。雖然這會(huì)消耗更新服務(wù)平臺(tái)更多的存儲(chǔ)空間，但是這使得終端設(shè)備可以更加方便地進(jìn)行版本回退以及跨版本更新等操作，給終端設(shè)備地更新帶來了更多的靈活性。在增量更新包的生成上，根據(jù)終端設(shè)備的版本查詢請(qǐng)求，在更新服務(wù)平臺(tái)即時(shí)地生成增量更新包。增量更新包的生成基于BSDiff差分算法，并且使用運(yùn)行效率更高的DivSufSort后綴數(shù)組算法對(duì)其進(jìn)行優(yōu)化，提高增量更新包生成的效率。同時(shí)，新生成的增量更新包還需要在更新服務(wù)平臺(tái)保留一段時(shí)間，以便提供給有相同更新需求的終端設(shè)備使用，提高更新服務(wù)平臺(tái)的效率。

3 實(shí)驗(yàn)及結(jié)果分析

本文實(shí)驗(yàn)的終端設(shè)備選用樂鑫科技的ESP8266物聯(lián)網(wǎng)芯片，更新服務(wù)平臺(tái)則搭建在云端，操作系統(tǒng)為Linux，版本為Ubuntu16.04，實(shí)驗(yàn)樣本的具體數(shù)據(jù)如表3所示。其中V1為功能實(shí)現(xiàn)的初始版本，V2在V1的基礎(chǔ)上增加了新功能并在整體上進(jìn)行了完善，V3、V4針對(duì)一些運(yùn)行時(shí)出現(xiàn)的問題進(jìn)行了修復(fù)，其中V4為最終版本。從V1到V4，代碼差異逐版本減小。

表3 增量更新測試文件

3.1 評(píng)價(jià)指標(biāo)

本文以差分過程耗費(fèi)的時(shí)間和傳輸數(shù)據(jù)壓縮率分別作為差分算法和遠(yuǎn)程增量更新系統(tǒng)的主要評(píng)價(jià)指標(biāo)。定義壓縮率Rcmp的計(jì)算方法如下

Rcmp=(Nnew-Ndate)/Nnew×100%

(1)

式中，Nnew為目標(biāo)更新版本固件包的總字節(jié)數(shù)；Ndate為傳輸數(shù)據(jù)的總字節(jié)數(shù)；壓縮率Rcmp表示相較于全量更新，通過增量更新可以減少的傳輸數(shù)據(jù)量的程度。壓縮率越大，表示增量更新系統(tǒng)性能越高，傳輸時(shí)間、設(shè)備功耗以及網(wǎng)絡(luò)流量開銷越少。

3.2 實(shí)驗(yàn)設(shè)計(jì)與分析

實(shí)驗(yàn)通過在Linux命令行運(yùn)行BSDiff差分算法來仿真更新服務(wù)端進(jìn)行差分運(yùn)算并獲取指定更新包的過程，通過運(yùn)行time指令來獲取BSDiff算法運(yùn)行的準(zhǔn)確時(shí)間。

在實(shí)驗(yàn)開始前，先將終端固件手動(dòng)燒寫成V1版本，并根據(jù)實(shí)驗(yàn)場景在服務(wù)端上傳指定的更新包。然后，觸發(fā)終端設(shè)備更新指令，使用http協(xié)議向服務(wù)端請(qǐng)求指定更新包。終端設(shè)備接收完成后，校驗(yàn)更新包，校驗(yàn)通過則進(jìn)入更新流程。最后，通過查看終端設(shè)備日志確認(rèn)版本是否更新。

實(shí)驗(yàn)設(shè)計(jì)了終端設(shè)備鄰近版本更新與跨版本更新兩種場景，分別對(duì)比了全量更新方案、傳統(tǒng)的增量更新方案以及本文設(shè)計(jì)的優(yōu)化增量更新方案在這兩種場景下的表現(xiàn)，實(shí)驗(yàn)結(jié)果如表4和表5所示。

表4 鄰近版本升級(jí)

表5 跨版本升級(jí)

在鄰近版本更新時(shí)，相較于全量更新方案，改進(jìn)的增量更新方案的數(shù)據(jù)壓縮率與傳統(tǒng)的增量更新方案相同，平均能達(dá)到96.80%的壓縮率。但是，改進(jìn)的方案傳輸?shù)臄?shù)據(jù)量平均多了10 Byte。這是由于BSDiff差分算法在處理某些文件時(shí)間過長，因此對(duì)BSDiff差分算法中查找最大相似字符串的過程進(jìn)行了改進(jìn)。

在跨版本升級(jí)的場景下，改進(jìn)的增量更新方案的數(shù)據(jù)壓縮率平均達(dá)到了95.09%。對(duì)比傳統(tǒng)的增量更新方案，改進(jìn)增量更新方案的整體數(shù)據(jù)壓縮率平均提高了2.07%，并且從代碼差異最小到最大的版本變更情景中，提高的壓縮率從1.19%上升到了3.3%，說明改進(jìn)的增量更新方案在跨版本升級(jí)時(shí)，隨著版本之間的代碼差異增大，其優(yōu)勢也隨之增加。這是由于傳統(tǒng)的增量更新方案在跨版本升級(jí)時(shí)需要發(fā)送多次patch包，導(dǎo)致重復(fù)發(fā)送了部分相同的差異字段與索引控制信息，而改進(jìn)方案只需要發(fā)送一次。

此外，實(shí)驗(yàn)針對(duì)不同大小的文件，對(duì)BSDiff與改進(jìn)BSDiff差分算法的差分性能進(jìn)行了比較，結(jié)果如圖3以及表6所示。改進(jìn)BSDiff差分算法在生成增量更新包時(shí)，其平均處理時(shí)間比原先的BSDiff差分算法平均減少了31.19%，同時(shí)，對(duì)于原先導(dǎo)致BSDiff算法長時(shí)間運(yùn)行的特殊測試用例，即最后一組數(shù)據(jù)所示的情況，改進(jìn)BSDiff算法也能進(jìn)行高效處理。

表6 差分算法運(yùn)行時(shí)間

圖3 差分算法性能比較

從實(shí)驗(yàn)結(jié)果與分析可知，本文所提出的改進(jìn)增量更新方案可以高效地對(duì)需要傳輸?shù)母聰?shù)據(jù)進(jìn)行壓縮，從而提高遠(yuǎn)程更新的效率，達(dá)到節(jié)省終端設(shè)備功耗的目的。在跨版本更新時(shí)，也可以有效減少需要傳輸?shù)臄?shù)據(jù)量，并且版本之間代碼差異越大，其效果就越明顯。此外，改進(jìn)BSDiff差分算法在運(yùn)行時(shí)間上，相較于原先的BSDiff差分算法也有較大提升，整體上可以將差分運(yùn)算的時(shí)間控制在秒級(jí)，達(dá)到了預(yù)期結(jié)果。

4 結(jié)束語

本文研究了物聯(lián)網(wǎng)終端設(shè)備的遠(yuǎn)程增量更新方案，綜合考慮了傳統(tǒng)全量更新方案需要傳輸?shù)臄?shù)據(jù)量大但是更新過程簡單，以及傳統(tǒng)增量更新方案傳輸?shù)臄?shù)據(jù)量小但是跨版本更新性能弱的特點(diǎn)，對(duì)兩種方案的優(yōu)缺點(diǎn)進(jìn)行了整合和改進(jìn)，提出以改進(jìn)的BSDiff差分算法來減少更新需要傳輸?shù)臄?shù)據(jù)量，同時(shí)優(yōu)化更新服務(wù)平臺(tái)的固件管理方案，從而達(dá)到節(jié)省傳輸流量，提高終端設(shè)備更新效率的目的。本文對(duì)方案進(jìn)行了仿真驗(yàn)證，并取得了預(yù)期結(jié)果。使用BSDiff差分算法進(jìn)行終端設(shè)備的遠(yuǎn)程增量更新可以有效減少需要數(shù)據(jù)量，提高終端設(shè)備的更新效率。但大量的物聯(lián)網(wǎng)終端設(shè)備內(nèi)存小，資源有限，而運(yùn)行BSPatch構(gòu)建新版本固件時(shí)內(nèi)存消耗大，因此在保持較高壓縮率的同時(shí)減小終端設(shè)備的內(nèi)存消耗也是一個(gè)重要的研究課題。