文/張曉愚

為何需要差異更新？

差異更新即在軟件更新時只更新差異化的部分，以達(dá)到用最小的下載量完成軟件的更新需求。該思想由來已久，從剛接觸電腦時的操作系統(tǒng)、應(yīng)用軟件快速更新功能或填補漏洞，到迭代更加頻繁的移動應(yīng)用時代更多了節(jié)省下載流量費用的需求。尤其在移動游戲領(lǐng)域，隨著手機性能的提升和玩家對游戲體驗的追求，安裝包亦是越來越大，并且會頻繁的更新以不斷給玩家?guī)砀碌耐娣ê透鼮閮?yōu)化的體驗。然而，這種頻繁的更新也同樣會帶來負(fù)面的影響：更新包太大沒流量；更新速度太慢錯過了本該用來玩游戲的碎片時間；本地空間不足無法更新等問題，這些負(fù)面影響都會導(dǎo)致一定程度上的玩家流失。因此，差異化更新能力目前已成為各應(yīng)用下載渠道的必備能力之一，更小的更新包才能提高更新的成功率。

差異化更新可分為兩種，一種是基于源文件的差異化更新，該種方式成功率高， 算法簡單，常用于平臺相關(guān)的差異更新，但在移動端保存巨大的源文件、下載更新文件整合后再編譯的方式顯然是不現(xiàn)實的； 另一種即更為廣泛使用的方法即對可執(zhí)行文件的二進(jìn)制更新方式，本文中即將就該方式下的經(jīng)典算法BSDiff進(jìn)行詳細(xì)介紹。

普通二進(jìn)制文件對比

熟悉Linux的同學(xué)提到二進(jìn)制文件對比自然會想到一個命令：cmp。那可執(zhí)行文件的二進(jìn)制更新豈不是有了這個對比結(jié)果后， 然后拿更新結(jié)果修改舊文件的二進(jìn)制串為新文件不就OK了？用個最簡單的方法測試下，舊文件testDiffUpdate_Old與更新后文件testDiffUpdate_New內(nèi)容僅差了第一個字符0。

xiaoyzhang$ cat testDiffUpdate_Old

123456789

xiaoyzhang$ cat testDiffUpdate_New

0123456789

通過CMP做兩文件的對比后輸出文件為testDiffUpdate_Delta，內(nèi)容下：

xiaoyzhang$ cmp -l testDiffUpdate_New testDiffUpdate_Old > testDiffUpdate_Delta

cmp: EOF on testDiffUpdate_Old

xiaoyzhang$ cat testDiffUpdate_Delta

1 60 61

2 61 62

3 62 63

4 63 64

5 64 65

6 65 66

7 66 67

8 67 70

9 70 71

10 71 12

如文件內(nèi)容可知，通過簡單的二進(jìn)制對比得出的差異文件用來更新顯然是不靠譜的，差異文件的內(nèi)容遠(yuǎn)遠(yuǎn)比新舊兩文件還要大的多。

-rw-r--r-- 1 xiaoyzhang 1085706827110 12 23 12:33 testDiffUpdate_Delta

-rw-r--r-- 1 xiaoyzhang 1085706827 11 12 23 12:29 testDiffUpdate_New

-rw-r--r-- 1 xiaoyzhang 1085706827 10 12 23 12:28 testDiffUpdate_Old

這個差異更新的問題看起來沒有如此簡單，但上述問題仍然比較好解決，使用經(jīng)典動態(tài)規(guī)劃算法——最長公共子序列即可。上述兩個文件對比可以很輕易的找出最長公共子序列為123456789。這樣，只要在更新差異文件中記錄0和其對應(yīng)的位置，并在舊文件中插入即可解決問題。這種方式下可以將差異更新轉(zhuǎn)化為兩個最基本的操作即：復(fù)制和插入，文件僅包含差異內(nèi)容的復(fù)制及需要插入位置的索引即可，可以極大的減少更新包的大小，做到我們需要的差異化更新能力。

如上方式已經(jīng)可以使用，但也僅可以使用在源文件的差異對比中，在可執(zhí)行文件的二進(jìn)制對比情況下，每次源碼的輕微變動將會導(dǎo)致可執(zhí)行文件的巨大變化，如下圖中可執(zhí)行文件A與可執(zhí)行文件B僅僅加入了一小段代碼（Inserted Code），但整個程序改動的內(nèi)容遠(yuǎn)不僅如此，如圖1所示：1）跳過插入代碼的程序分支）（branch）位移改變；2）

數(shù)據(jù)段中指向其他位置的絕對指針(pointer)將替換為新的值，所有插入代碼后續(xù)的地址均會后移。

圖1：插入一小段代導(dǎo)致可執(zhí)行文件大量變動（Brenda S. Baker ，Compressing Differences of Executable Code）
如上問題會導(dǎo)致使用簡單的“復(fù)制-插入”方式生成的更新文件遠(yuǎn)遠(yuǎn)大于我們所期望的大小，在可執(zhí)行文件中僅插入一行代碼將會產(chǎn)生近5-10%舊文件大小的更新文件。

為解決如上問題，“差異更新界“專家們做出了很多努力，試圖找出一些規(guī)律來避免這種可執(zhí)行文件更新包過大的問題，如一個指針指向地址A更新后變?yōu)橹赶虻刂稡，那么所有指向地址A的指針也會隨之更新為指向地址B。在仔細(xì)挖掘可執(zhí)行文件的內(nèi)在規(guī)律后，確實有許多更新算法對可執(zhí)行文件的更新文件壓縮效率非常高。但大多高效算法都是與可執(zhí)行文件的類型深度綁定的， 而Colin Percival在2003年即提出了一個優(yōu)秀的算法BSDiff，可在平臺無關(guān)的環(huán)境下做到極高的更新文件壓縮效率。

可執(zhí)行文件二進(jìn)制更新算法—BSDiff

可執(zhí)行文件的更新會產(chǎn)生三類不同的文件變動：

1. 零階變動：指編譯過程中的固有變化，即完全相同的兩段源代碼在編譯后也可能會發(fā)生變化。然而在現(xiàn)代大多數(shù)編譯環(huán)境下，如Unix程序或Windows exe等，相同代碼編譯后并不會產(chǎn)生變化。

2. 一階變動：直接修改源代碼導(dǎo)致的變動，此變動會導(dǎo)致新舊文件大范圍不一致。

3. 二階變動：由于一階變動間接引起的變動，每次插入或修改代碼都會引起其他未修改代碼部分的指針地址或寄存器地址變化，但該變動內(nèi)的大部分其他二進(jìn)制字段內(nèi)容與舊文件保持相同。

在傳統(tǒng)的差異更新算法中，要求新舊兩文件的二進(jìn)制的對比保持完全一致。而由于可執(zhí)行文件中的二階變動特點，完全一致的匹配方式會極大的增加更新包的大小。 類似ExeDiff等平臺相關(guān)的更新算法可以將可執(zhí)行文件反編譯后找到可變部分并剝離出來，再進(jìn)行其余指令的比對，將問題簡化為源代碼的比對問題。但在平臺無關(guān)的可執(zhí)行文件環(huán)境下，需要將問題轉(zhuǎn)化為發(fā)現(xiàn)負(fù)責(zé)操作部分代碼的二進(jìn)制差異而非內(nèi)存或寄存器信息的差異。

BSDiff算法的提出即針對可執(zhí)行文件更新前后二階變動的兩個重要規(guī)律：1）沒有被更新代碼所影響的代碼段，在變?yōu)榭蓤?zhí)行文件后，該區(qū)域的二進(jìn)制內(nèi)容的改變是極為稀疏的，即僅僅有部分指針或寄存器地址會變動，通常不會超過一兩個字節(jié)；2）更新后的代碼和數(shù)據(jù)會有很大的位置變動，但這種變動大多為整塊的移動，即某一塊位置中代碼內(nèi)的指針地址變動均會有相同的位移值。這兩個規(guī)律導(dǎo)致一個重要的事實即：相同源代碼對應(yīng)的兩個代碼塊中，大部分內(nèi)容字節(jié)差為0，而少部分需要更新的地址位移數(shù)據(jù)又存在大量相同位移值，即源代碼相同的代碼塊差異數(shù)據(jù)可以被高效壓縮。

圖2：差異文件包含大量0與相同偏移量2的字符，可被高效壓縮
基于此思想，BSDiff算法使用如下步驟來進(jìn)行生成差異更新包：

1. 將舊文件二進(jìn)制使用后綴排序或哈希算法形成一個字符串索引。

2. 使用該字符串索引對比新文件，生成差異文件(difference file)和新增文件(extra file)。

3. 將差異文件和新增文件及必要的索引控制信息壓縮為差異更新包。
首先是字符串索引的生成，該部分為差量更新算法的瓶頸部分，BSDiff算法里采用基于二分思想的Faster Suffix Sorting(更快的后綴排序)算法來進(jìn)行索引的生成。后綴數(shù)組即一個一維數(shù)組，保存了i(1…n)的某個排列I,并且保證suffix(I)<suffix(I[i+1]), 即將S的n個后綴從小到大進(jìn)行排序之后，把有序的后綴的開頭位置順次放入I中，如下圖3所示, I[0]標(biāo)識了后綴‘$’在原數(shù)組起始位置為13， I[1]表示后綴‘be$’在原數(shù)組起始位置為11，并且‘$’按字典序排序小于‘be$’。


圖3 I即為通過Faster Suffix Sorting排序算法生成的后綴數(shù)組， （Jesper Larsson, Faster Suffix Sorting）

該算法時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)，其中n為舊文件的二進(jìn)制字符串長度。

得到索引后，使用該索引依次查找新舊文件中完全匹配的最長二進(jìn)制段，但并不會像傳統(tǒng)更新算法一樣直接打包，而是從該二進(jìn)制段進(jìn)行前后擴展，來生成范圍更大的“近似匹配”，近似的要求是向前擴展的每個后綴及后向擴展的每個前綴至少有50%字節(jié)與舊字符串可以匹配(通常以8個不匹配字節(jié)作為閾值)。這些近似匹配可以認(rèn)為是二階變動導(dǎo)致的新代碼，而非近似匹配的字段均可以認(rèn)為是一階變動新生成的字段。

在匹配完成后，更新包文件也即按此匹配方案生成，包含三個部分：1）控制文件，包含需要添加和插入二進(jìn)制段的指引信息（”添加指令”指定舊文件中的偏移量和長度，從舊文件讀取適當(dāng)?shù)淖止?jié)數(shù)，并將其添加到差異文件中的相同字節(jié)數(shù)；”插入指令”只是指定一個長度，指定的字節(jié)數(shù)是從額外的文件中讀取的）；2）差異文件，包含近似匹配字段的字節(jié)差異；3）新增文件，包含無法近似匹配的完全不同的字段。這三個文件加一起會比新文件略大，但其中控制文件和差異文件是高度結(jié)構(gòu)化的，意味著其均可被高效壓縮，所以可以使用類似bzip2等壓縮工具將更新包總文件進(jìn)行非常有效的壓縮。

以上便是bsdiff算法的基本思想，并且作者也將該算法實現(xiàn)并開源出來，供所有有二進(jìn)制差異更新需求的同學(xué)使用(下載鏈接：http://www.daemonology.net/bsdiff/)。該工具不僅包含了bsdiff來生成二進(jìn)制更新包，并且提供了bspatch工具可以將更新包與舊文件一起生成新文件,下文簡單對該工具進(jìn)行下測試。

隨意選擇兩個可執(zhí)行文件，這里就選擇bsdiff工具里的bsdiff與bspatch，兩個完全無關(guān)的可執(zhí)行文件，bsdiff作為新文件，bspatch作為舊文件。

xiaoyzhang$ ls -ll

-rwxr-xr-x 1 xiaoyzhang 1085706827 17636 12 23 19:34 bsdiff

-rwxr-xr-x 1 xiaoyzhang 1085706827 13404 12 23 19:37 bspatch

xiaoyzhang$ md5 bsdiff bspatch

MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605

MD5 (bspatch) = cd8b33f3b125f6d7c5883b6322d8a158

使用bsdiff old new patch命令得到差異更新包delta.patch。

xiaoyzhang$ bsdiff bspatch bsdiff delta.patch

xiaoyzhang$ ls -ll

-rw-r--r-- 1 xiaoyzhang 10857068275351 12 23 20:06 delta.patch

使用bspatch old new patch命令得到新的可執(zhí)行文件bspatch_new。

xiaoyzhang$ bspatch bspatch bspatch_new delta.patch

xiaoyzhang$ ls -ll

-rw-r--r-- 1 xiaoyzhang 1085706827 17636 12 23 20:07 bspatch_new

最后做md5校驗看新文件是否與目標(biāo)文件一致。

xiaoyzhang$ md5 bsdiff bspatch_new

MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605

MD5 (bspatch_new) = e775531d35bb8aff34ffd733fdf47605

可以看到，目標(biāo)更新文件bsdiff與剛生成的新文件bspatch_new完全一致，實現(xiàn)了我們差異更新的需求，并且更新包delta.patch僅有5351bit, 可以為我們節(jié)省69%（（17636-5351）/17636）的更新文件大小，并且這二者還是完全無關(guān)的兩個文件，在實際的更新場景中，該方式將會為我們節(jié)約更多的更新文件大小。在一些真實更新場景中測試數(shù)據(jù)如下圖所示，可以看到，bsdiff僅比平臺相關(guān)的Exediff壓縮比例稍高，但其優(yōu)秀的壓縮比例及平臺無關(guān)的特性，使其到目前為止都是一個非常優(yōu)秀的二進(jìn)制更新算法。


圖4 幾種二進(jìn)制更新算法效率對比 （Colin Percival, Naive differences of executable code）

游戲更新還需要哪些能力

有了BSDiff，我們可以很方便的做到二進(jìn)制文件的差異更新，但BSDiff也并非完美，比如其存在一些應(yīng)對移動應(yīng)用時的穩(wěn)定性以及對DEX文件的壓縮效率不高等問題。因此在真正的游戲更新場景中，仍然需要廠商基于各類二進(jìn)制壓縮算法進(jìn)行針對游戲場景的定制化開發(fā)，以達(dá)到更優(yōu)質(zhì)穩(wěn)定的服務(wù)和更高的壓縮效率。并且，在實現(xiàn)了版本二進(jìn)制差異更新以外，仍需要另外一種非常重要的更新能力，即程序內(nèi)的熱更新能力——無需跳轉(zhuǎn)渠道，在游戲啟動時即完成更新。目前AppStore, GooglePlay及國內(nèi)很多如應(yīng)用寶等知名渠道，都對程序內(nèi)熱更新做了很多限制，以避免熱更新帶來渠道無法控制的安全問題，為最終用戶造成損失。因此，我們也需要在遵守渠道熱更新規(guī)范的條件下，進(jìn)行針對游戲內(nèi)資源文件的熱更新。同時，在面對多渠道多版本的管理時，我們也需要一套滿足多種場景的功能強大的更新管理平臺，可以供運維及運營人員更方便的審核并發(fā)布新版本，及時迭代以完善游戲體驗。

via：騰訊云

銳亞教育，游戲開發(fā)論壇|游戲制作人|游戲策劃|游戲開發(fā)|獨立游戲|游戲產(chǎn)業(yè)|游戲研發(fā)|游戲運營| unity|unity3d|unity3d官網(wǎng)|unity3d 教程|金融帝國3|8k8k8k|mcafee8.5i|游戲蠻牛|蠻牛 unity|蠻牛