[發(fā)明專利]一種數(shù)據(jù)增量更新方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510093396.3
• 申請(qǐng)日: 2015-03-02
• 公開（公告）號(hào): CN104834539B
• 公開（公告）日: 2018-03-20
• 發(fā)明（設(shè)計(jì)）人: 倪桂強(qiáng);陳志龍;姜?jiǎng)潘?/a>;羅健欣;馬遙;嚴(yán)英姿
• 申請(qǐng)（專利權(quán)）人: 倪桂強(qiáng);陳志龍;姜?jiǎng)潘?/a>;羅健欣;馬遙;嚴(yán)英姿
• 主分類號(hào): G06F9/445
• 分類號(hào): G06F9/445
• 代理公司: 深圳市威世博知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)44280
• 代理人: 何青瓦

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)、智能設(shè)備、消費(fèi)電子產(chǎn)品等數(shù)據(jù)更新領(lǐng)域，尤其涉及一種數(shù)據(jù)增量更新方法。

背景技術(shù)

隨著智能手機(jī)、穿戴設(shè)備等消費(fèi)電子產(chǎn)品提供的應(yīng)用服務(wù)不斷增多，系統(tǒng)更新、應(yīng)用軟件升級(jí)、安全漏洞修復(fù)等數(shù)據(jù)更新業(yè)務(wù)應(yīng)用范圍越來越廣。其中，代碼或數(shù)據(jù)的變化是軟件新舊版本存在差異的主要原因，并且，新舊版本軟件之間的差異信息往往遠(yuǎn)小于軟件本身的大小。因此，使用數(shù)據(jù)增量方式進(jìn)行更新是非常高效的，通過增量更新找到新舊文件之間的差異，并將該差異信息表述成增量文件，增量文件含有指令和數(shù)據(jù)，進(jìn)行更新的設(shè)備使用增量文件可以將舊文件轉(zhuǎn)化為新文件。

圖1顯示了現(xiàn)有技術(shù)中數(shù)據(jù)增量更新的基本流程：在服務(wù)器端存儲(chǔ)著舊版本文件(軟件或者數(shù)據(jù))和新版文件，當(dāng)某個(gè)新版本要被發(fā)布前，服務(wù)器比較新文件和舊文件，并將二者的差異信息表述為增量包的形式，增量包被壓縮后得到增量壓縮包，再通過通信網(wǎng)絡(luò)傳遞給需要更新軟件的設(shè)備，設(shè)備收到增量壓縮包并解壓，按照增量包中的指令和數(shù)據(jù)將舊文件轉(zhuǎn)化為新文件。

圖1所示的數(shù)據(jù)更新流程在實(shí)際應(yīng)用中，會(huì)存在受限的網(wǎng)絡(luò)帶寬、按流量計(jì)算的費(fèi)用、以及消費(fèi)電子設(shè)備較小的內(nèi)存和有限的電量等實(shí)際限制，而較小的增量壓縮包能夠減少流量費(fèi)用和下載時(shí)間，應(yīng)用增量包時(shí)較小的內(nèi)存耗費(fèi)和較少的CPU時(shí)鐘周期能夠減少生成新文件的時(shí)間、節(jié)省設(shè)備電量、降低對(duì)正在運(yùn)行的其他應(yīng)用程序的影響，最終提升用戶體驗(yàn)。可以看出，消費(fèi)電子設(shè)備數(shù)據(jù)增量更新方法的主要評(píng)價(jià)標(biāo)準(zhǔn)是：增量包、增量壓縮包的大小和應(yīng)用增量包的時(shí)間。因此，減小增量包和增量壓縮包的大小，以及加快應(yīng)用增量包的速度是數(shù)據(jù)更新方法中需要重點(diǎn)解決的問題。

在現(xiàn)有技術(shù)中，數(shù)據(jù)增量更新方法主要包括：T.Andrew在文獻(xiàn)《Efficient Algorithms for Sorting and Synchronization》(Australian National University,1999)提出的RDIFF方法，C.Percival在文獻(xiàn)《Naive differences of executable code》(University of Oxford,2003)提出的BSDIFF方法，以及D.Korn等作者在文獻(xiàn)《The VCDIFF Generic Differencing and Compression Data Format》(RFC 3284(Proposed Standard),June.2002)提出的VCDIFF方法。

RDIFF方法主要將舊文件和新文件分成相同大小的連續(xù)多個(gè)數(shù)據(jù)塊，計(jì)算每個(gè)數(shù)據(jù)塊的哈希值，依據(jù)哈希值在新舊文件之間尋找相同的數(shù)據(jù)塊，增量包中包括對(duì)舊文件某個(gè)數(shù)據(jù)塊的引用，或者是一個(gè)完整的新數(shù)據(jù)塊。該方法結(jié)構(gòu)簡單，計(jì)算速度快并且適用于解決RDC(Remote Differential Compression)問題，缺點(diǎn)是無法全面采集新舊文件之間所有的相似信息，應(yīng)用該方法的軟件有Rsync和rdiff-backup等。

BSDIFF方法是在新文件和舊文件之間尋找完全相同的數(shù)據(jù)段，接著逐字節(jié)延伸該數(shù)據(jù)段的前綴和后綴，嘗試尋找近似但不完全相同的數(shù)據(jù)段，即近似數(shù)據(jù)段。BSDIFF方法中使用了N.S.Larsson和K.Sadakane提出的后綴數(shù)組排序算法，增量包中指令有ADD、INSERT、SEEK，ADD操作的參數(shù)是近似數(shù)據(jù)段長度和修正量，INSERT操作的參數(shù)是插入段長度和插入內(nèi)容，SEEK操作的參數(shù)是舊文件讀取指針的跳躍跨度。ADD操作的修正量參數(shù)是增量包的主要成分，新舊文件的相似程度與修正量中“0”的比例成正比，較高的“0”的比例使得增量壓縮包小于新文件的大小。BSDIFF方法中的增量包較小，但是構(gòu)造增量包和應(yīng)用增量包的計(jì)算量較大，因此費(fèi)時(shí)較多。目前BSDIFF方法是應(yīng)用最廣泛的增量更新算法，Bsdiff工具應(yīng)用了BSDIFF方法。

VCDIFF方法是基于LZ77(Lempel-Ziv 77)壓縮算法進(jìn)行改進(jìn)，實(shí)現(xiàn)增量更新。LZ77壓縮算法主要是基于一個(gè)數(shù)據(jù)流中后面的數(shù)據(jù)段與前面的數(shù)據(jù)段相似或者相關(guān)進(jìn)行數(shù)據(jù)壓縮，借鑒LZ77壓縮算法，VCDIFF方法將舊文件和新文件鏈接成一個(gè)數(shù)據(jù)流，應(yīng)用LZ77壓縮算法進(jìn)行壓縮，截取壓縮流中表達(dá)新文件的部分作為增量包。VCDIFF方法的性能介于在RDIFF方法和BSDIFF方法之間，犧牲了部分壓縮率，加快了執(zhí)行的速度。Xdelta是應(yīng)用VCDIFF方法的軟件之一，并且該軟件還在VCDIFF基礎(chǔ)上進(jìn)行了改進(jìn)，優(yōu)化了其中的指令集，進(jìn)一步減小了增量壓縮包的大小。