更多騰訊海量技術文章， 請關注雲加社區：https://cloud.tencent.com/developer
作者：騰訊雲遊戲行業資深架構師 張曉愚
為何需要差異更新？差異更新即在軟體更新時只更新差異化的部分， 以達到用最小的下載量完成軟體的更新需求。 該思想由來已久， 從剛接觸電腦時的作業系統、應用軟體快速更新功能或填補漏洞， 到反覆運算更加頻繁的移動應用時代更多了節省下載流量費用的需求。 尤其在移動遊戲領域， 隨著手機性能的提升和玩家對遊戲體驗的追求， 安裝包亦是越來越大， 並且會頻繁的更新以不斷給玩家帶來更新的玩法和更為優化的體驗。
差異化更新可分為兩種， 一種是基於原始檔案的差異化更新， 該種方式成功率高， 演算法簡單， 常用於平臺相關的差異更新， 但在移動端保存巨大的原始檔案、下載更新檔整合後再編譯的方式顯然是不現實的； 另一種即更為廣泛使用的方法即對可執行檔的二進位更新方式，
熟悉Linux的同學提到二進位檔案對比自然會想到一個命令：cmp。 那可執行檔的二進位更新豈不是有了這個對比結果後， 然後拿更新結果修改舊檔的二進位串為新檔不就OK了？用個最簡單的方法測試下， 舊檔testDiffUpdate_Old與更新後檔testDiffUpdate_New內容僅差了第一個字元0。
xiaoyzhang$ cat testDiffUpdate_Old
123456789
xiaoyzhang$ cat testDiffUpdate_New
0123456789
通過CMP做兩檔的對比後輸出檔為testDiffUpdate_Delta， 內容下：
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
如檔內容可知， 通過簡單的二進位對比得出的差異檔用來更新顯然是不靠譜的， 差異檔的內容遠遠比新舊兩檔還要大的多。
-rw-r--r-- 1 xiaoyzhang 1085706827 110 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
這個差異更新的問題看起來沒有如此簡單， 但上述問題仍然比較好解決， 使用經典動態規劃演算法——最長公共子序列即可。 上述兩個檔對比可以很輕易的找出最長公共子序列為123456789。
如上方式已經可以使用， 但也僅可以使用在原始檔案的差異對比中， 在可執行檔的二進位對比情況下， 每次源碼的輕微變動將會導致可執行檔的巨大變化， 如下圖中可執行檔A與可執行檔B僅僅加入了一小段代碼（Inserted Code）， 但整個程式改動的內容遠不僅如此， 如圖1所示：1）跳過插入代碼的程式分支）（branch）位移改變；2）
資料段中指向其他位置的絕對指標(pointer)將替換為新的值， 所有插入代碼後續的位址均會後移。
圖1：插入一小段代碼會導致可執行檔大量變動 （Brenda S. Baker ， Compressing Differences of Executable Code）
如上問題會導致使用簡單的“複製-插入”方式生成的更新檔遠遠大於我們所期望的大小， 在可執行檔中僅插入一行代碼將會產生近5-10%舊檔大小的更新檔。
為解決如上問題， “差異更新界“專家們做出了很多努力， 試圖找出一些規律來避免這種可執行檔更新包過大的問題， 如一個指標指向位址A更新後變為指向位址B， 那麼所有指向位址A的指標也會隨之更新為指向位址B。 在仔細挖掘可執行檔的內在規律後， 確實有許多更新演算法對可執行檔的更新檔案壓縮效率非常高。 但大多高效演算法都是與可執行檔的類型深度綁定的， 而Colin Percival在2003年即提出了一個優秀的演算法BSDiff， 可在平臺無關的環境下做到極高的更新檔案壓縮效率。
可執行檔二進位更新演算法—BSDiff可執行檔的更新會產生三類不同的檔變動：
1. 零階變動：指編譯過程中的固有變化， 即完全相同的兩段原始程式碼在編譯後也可能會發生變化。然而在現代大多數編譯環境下，如Unix程式或Windows exe等，相同代碼編譯後並不會產生變化。
2. 一階變動：直接修改原始程式碼導致的變動，此變動會導致新舊檔大範圍不一致。
3. 二階變動：由於一階變動間接引起的變動，每次插入或修改代碼都會引起其他未修改代碼部分的指標位址或寄存器位址變化，但該變動內的大部分其他二進位欄位內容與舊檔保持相同。
在傳統的差異更新演算法中，要求新舊兩檔的二進位的對比保持完全一致。而由於可執行檔中的二階變動特點，完全一致的匹配方式會極大的增加更新包的大小。 類似ExeDiff等平臺相關的更新演算法可以將可執行檔反編譯後找到可變部分並剝離出來，再進行其餘指令的比對，將問題簡化為原始程式碼的比對問題。但在平臺無關的可執行檔環境下，需要將問題轉化為發現負責操作部分代碼的二進位差異而非記憶體或寄存器資訊的差異。
BSDiff演算法的提出即針對可執行檔更新前後二階變動的兩個重要規律：1）沒有被更新代碼所影響的程式碼片段，在變為可執行檔後，該區域的二進位內容的改變是極為稀疏的，即僅僅有部分指標或寄存器位址會變動，通常不會超過一兩個位元組；2）更新後的代碼和資料會有很大的位置變動，但這種變動大多為整塊的移動，即某一塊位置中代碼內的指標位址變動均會有相同的位移值。這兩個規律導致一個重要的事實即：相同源代碼對應的兩個代碼塊中，大部分內容位元組差為0，而少部分需要更新的位址位移資料又存在大量相同位移值，即原始程式碼相同的代碼塊差異資料可以被高效壓縮。
圖2：差異檔包含大量0與相同偏移量2的字元，可被高效壓縮
基於此思想，BSDiff演算法使用如下步驟來進行生成差異更新包：
1. 將舊檔二進位使用尾碼排序或雜湊演算法形成一個字串索引。
2. 使用該字串索引對比新檔，生成差異檔(difference file)和新增檔(extra file)。
3. 將差異檔和新增檔及必要的索引控制資訊壓縮為差異更新包。
首先是字串索引的生成，該部分為差量更新演算法的瓶頸部分，BSDiff演算法裡採用基於二分思想的Faster Suffix Sorting(更快的尾碼排序)演算法來進行索引的生成。尾碼陣列即一個一維陣列，保存了i(1…n)的某個排列I[i],並且保證suffix(I[i]) 圖3 I[i]即為通過Faster Suffix Sorting排序演算法生成的尾碼陣列， （Jesper Larsson, Faster Suffix Sorting） 該演算法時間複雜度為O(nlogn)，空間複雜度為O(n)，其中n為舊檔的二進位字元串長度。 得到索引後，使用該索引依次查找新舊檔中完全匹配的最長二進位段，但並不會像傳統更新演算法一樣直接打包，而是從該二進位段進行前後擴展，來生成範圍更大的“近似匹配”，近似的要求是向前擴展的每個尾碼及後向擴展的每個首碼至少有50%位元組與舊字串可以匹配(通常以8個不匹配位元組作為閾值)。這些近似匹配可以認為是二階變動導致的新代碼，而非近似匹配的欄位均可以認為是一階變動新生成的欄位。 在匹配完成後，更新包檔也即按此匹配方案生成，包含三個部分：1）控制檔，包含需要添加和插入二進位段的指引資訊（”添加指令”指定舊檔中的偏移量和長度，從舊檔讀取適當的位元組數，並將其添加到差異檔中的相同位元組數；”插入指令”只是指定一個長度，指定的位元組數是從額外的檔中讀取的）；2）差異檔，包含近似匹配欄位的位元組差異；3）新增檔，包含無法近似匹配的完全不同的欄位。這三個檔加一起會比新檔略大，但其中控制檔和差異檔是高度結構化的，意味著其均可被高效壓縮，所以可以使用類似bzip2等壓縮工具將更新包總檔進行非常有效的壓縮。 以上便是bsdiff演算法的基本思想，並且作者也將該演算法實現並開源出來，供所有有二進位差異更新需求的同學使用(下載連結：http://www.daemonology.net/bsdiff/ )。該工具不僅包含了bsdiff來生成二進位更新包，並且提供了bspatch工具可以將更新包與舊檔一起生成新檔,下文簡單對該工具進行下測試。 隨意選擇兩個可執行檔，這裡就選擇bsdiff工具裡的bsdiff與bspatch，兩個完全無關的可執行檔，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 1085706827 5351 12 23 20:06 delta.patch 使用bspatch old new patch命令得到新的可執行檔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校驗看新檔是否與目的檔案一致。 xiaoyzhang$ md5 bsdiff bspatch_new MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605 MD5 (bspatch_new) = e775531d35bb8aff34ffd733fdf47605 可以看到，目標更新檔bsdiff與剛生成的新檔bspatch_new完全一致，實現了我們差異更新的需求，並且更新包delta.patch僅有5351bit, 可以為我們節省69%（（17636-5351）/17636）的更新檔大小，並且這二者還是完全無關的兩個檔，在實際的更新場景中，該方式將會為我們節約更多的更新檔大小。在一些真實更新場景中測試資料如下圖所示，可以看到，bsdiff僅比平臺相關的Exediff壓縮比例稍高，但其優秀的壓縮比例及平臺無關的特性，使其到目前為止都是一個非常優秀的二進位更新演算法。 圖4 圖4 幾種二進位更新演算法效率對比 （Colin Percival, Naive differences of executable code） 有了BSDiff，我們可以很方便的做到二進位檔案的差異更新，但BSDiff也並非完美，比如其存在一些應對移動應用時的穩定性以及對DEX檔的壓縮效率不高等問題。因此在真正的遊戲更新場景中，仍然需要廠商基於各類二進位壓縮演算法進行針對遊戲場景的定制化開發，以達到更優質穩定的服務和更高的壓縮效率。並且，在實現了版本二進位差異更新以外，仍需要另外一種非常重要的更新能力，即程式內的熱更新能力——無需跳轉管道，在遊戲啟動時即完成更新。目前AppStore, GooglePlay及國內很多如應用寶等知名管道，都對程式內熱更新做了很多限制，以避免熱更新帶來管道無法控制的安全問題，為最終用戶造成損失。因此，我們也需要在遵守管道熱更新規範的條件下，進行針對遊戲內資源檔的熱更新。同時，在面對多管道多版本的管理時，我們也需要一套滿足多種場景的功能強大的更新管理平臺，可以供運維及運營人員更方便的審核並發佈新版本，及時反覆運算以完善遊戲體驗。 以上需求都是一個想要長期運營的優質遊戲所必不可少的，但又需要遊戲廠商花費大量時間與精力去實現，有沒有現成的解決方案可以隨插即用呢？騰訊遊戲雲遊戲更新Dolphin產品即可完美根治所有遊戲更新中的疑難雜症：針對移動遊戲應用結構定制研發的高效穩定的二進位差異更新演算法，產品化後天然支援Unity等遊戲引擎；只需簡單的接入SDK，即可使用差異更新、資源熱更新及多管道多版本管理的全部功能；並且可以直接借助騰訊雲全球部署的基礎設施和CDN資源，一次接入全球使用，使玩家可以更快速的體驗到遊戲新版本。據不完全統計，騰訊內部手遊在使用了該遊戲更新方案後，更新的成功率高達99.7%，極大的減少了更新帶來的玩家流失，為遊戲的長久運營提供了堅實的技術支撐。目前遊戲更新Dolphin已在騰訊雲全量開放，希望可以幫助到各遊戲廠商和開發者，為玩家帶來“多快好省”的遊戲更新體驗。立即註冊，每月專享100M免費體驗流量： https://cloud.tencent.com/product/Dolphin 想瞭解更多騰訊雲遊戲行業解決方案和案例，立即報名1月19日騰訊雲GAME-TECH沙龍杭州站，我們一起探討：https://cloud.tencent.com/act/event/game-tech-hz.html 直播預約：http://www.itdks.com/eventlist/detail/1885
2. 一階變動：直接修改原始程式碼導致的變動，此變動會導致新舊檔大範圍不一致。
3. 二階變動：由於一階變動間接引起的變動，每次插入或修改代碼都會引起其他未修改代碼部分的指標位址或寄存器位址變化，但該變動內的大部分其他二進位欄位內容與舊檔保持相同。
在傳統的差異更新演算法中，要求新舊兩檔的二進位的對比保持完全一致。而由於可執行檔中的二階變動特點，完全一致的匹配方式會極大的增加更新包的大小。 類似ExeDiff等平臺相關的更新演算法可以將可執行檔反編譯後找到可變部分並剝離出來，再進行其餘指令的比對，將問題簡化為原始程式碼的比對問題。但在平臺無關的可執行檔環境下，需要將問題轉化為發現負責操作部分代碼的二進位差異而非記憶體或寄存器資訊的差異。
BSDiff演算法的提出即針對可執行檔更新前後二階變動的兩個重要規律：1）沒有被更新代碼所影響的程式碼片段，在變為可執行檔後，該區域的二進位內容的改變是極為稀疏的，即僅僅有部分指標或寄存器位址會變動，通常不會超過一兩個位元組；2）更新後的代碼和資料會有很大的位置變動，但這種變動大多為整塊的移動，即某一塊位置中代碼內的指標位址變動均會有相同的位移值。這兩個規律導致一個重要的事實即：相同源代碼對應的兩個代碼塊中，大部分內容位元組差為0，而少部分需要更新的位址位移資料又存在大量相同位移值，即原始程式碼相同的代碼塊差異資料可以被高效壓縮。
圖2：差異檔包含大量0與相同偏移量2的字元，可被高效壓縮
基於此思想，BSDiff演算法使用如下步驟來進行生成差異更新包：
1. 將舊檔二進位使用尾碼排序或雜湊演算法形成一個字串索引。
2. 使用該字串索引對比新檔，生成差異檔(difference file)和新增檔(extra file)。
3. 將差異檔和新增檔及必要的索引控制資訊壓縮為差異更新包。
首先是字串索引的生成，該部分為差量更新演算法的瓶頸部分，BSDiff演算法裡採用基於二分思想的Faster Suffix Sorting(更快的尾碼排序)演算法來進行索引的生成。尾碼陣列即一個一維陣列，保存了i(1…n)的某個排列I[i],並且保證suffix(I[i]) 圖3 I[i]即為通過Faster Suffix Sorting排序演算法生成的尾碼陣列， （Jesper Larsson, Faster Suffix Sorting） 該演算法時間複雜度為O(nlogn)，空間複雜度為O(n)，其中n為舊檔的二進位字元串長度。 得到索引後，使用該索引依次查找新舊檔中完全匹配的最長二進位段，但並不會像傳統更新演算法一樣直接打包，而是從該二進位段進行前後擴展，來生成範圍更大的“近似匹配”，近似的要求是向前擴展的每個尾碼及後向擴展的每個首碼至少有50%位元組與舊字串可以匹配(通常以8個不匹配位元組作為閾值)。這些近似匹配可以認為是二階變動導致的新代碼，而非近似匹配的欄位均可以認為是一階變動新生成的欄位。 在匹配完成後，更新包檔也即按此匹配方案生成，包含三個部分：1）控制檔，包含需要添加和插入二進位段的指引資訊（”添加指令”指定舊檔中的偏移量和長度，從舊檔讀取適當的位元組數，並將其添加到差異檔中的相同位元組數；”插入指令”只是指定一個長度，指定的位元組數是從額外的檔中讀取的）；2）差異檔，包含近似匹配欄位的位元組差異；3）新增檔，包含無法近似匹配的完全不同的欄位。這三個檔加一起會比新檔略大，但其中控制檔和差異檔是高度結構化的，意味著其均可被高效壓縮，所以可以使用類似bzip2等壓縮工具將更新包總檔進行非常有效的壓縮。 以上便是bsdiff演算法的基本思想，並且作者也將該演算法實現並開源出來，供所有有二進位差異更新需求的同學使用(下載連結：http://www.daemonology.net/bsdiff/ )。該工具不僅包含了bsdiff來生成二進位更新包，並且提供了bspatch工具可以將更新包與舊檔一起生成新檔,下文簡單對該工具進行下測試。 隨意選擇兩個可執行檔，這裡就選擇bsdiff工具裡的bsdiff與bspatch，兩個完全無關的可執行檔，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 1085706827 5351 12 23 20:06 delta.patch 使用bspatch old new patch命令得到新的可執行檔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校驗看新檔是否與目的檔案一致。 xiaoyzhang$ md5 bsdiff bspatch_new MD5 (bsdiff) = e775531d35bb8aff34ffd733fdf47605 MD5 (bspatch_new) = e775531d35bb8aff34ffd733fdf47605 可以看到，目標更新檔bsdiff與剛生成的新檔bspatch_new完全一致，實現了我們差異更新的需求，並且更新包delta.patch僅有5351bit, 可以為我們節省69%（（17636-5351）/17636）的更新檔大小，並且這二者還是完全無關的兩個檔，在實際的更新場景中，該方式將會為我們節約更多的更新檔大小。在一些真實更新場景中測試資料如下圖所示，可以看到，bsdiff僅比平臺相關的Exediff壓縮比例稍高，但其優秀的壓縮比例及平臺無關的特性，使其到目前為止都是一個非常優秀的二進位更新演算法。 圖4 圖4 幾種二進位更新演算法效率對比 （Colin Percival, Naive differences of executable code） 有了BSDiff，我們可以很方便的做到二進位檔案的差異更新，但BSDiff也並非完美，比如其存在一些應對移動應用時的穩定性以及對DEX檔的壓縮效率不高等問題。因此在真正的遊戲更新場景中，仍然需要廠商基於各類二進位壓縮演算法進行針對遊戲場景的定制化開發，以達到更優質穩定的服務和更高的壓縮效率。並且，在實現了版本二進位差異更新以外，仍需要另外一種非常重要的更新能力，即程式內的熱更新能力——無需跳轉管道，在遊戲啟動時即完成更新。目前AppStore, GooglePlay及國內很多如應用寶等知名管道，都對程式內熱更新做了很多限制，以避免熱更新帶來管道無法控制的安全問題，為最終用戶造成損失。因此，我們也需要在遵守管道熱更新規範的條件下，進行針對遊戲內資源檔的熱更新。同時，在面對多管道多版本的管理時，我們也需要一套滿足多種場景的功能強大的更新管理平臺，可以供運維及運營人員更方便的審核並發佈新版本，及時反覆運算以完善遊戲體驗。 以上需求都是一個想要長期運營的優質遊戲所必不可少的，但又需要遊戲廠商花費大量時間與精力去實現，有沒有現成的解決方案可以隨插即用呢？騰訊遊戲雲遊戲更新Dolphin產品即可完美根治所有遊戲更新中的疑難雜症：針對移動遊戲應用結構定制研發的高效穩定的二進位差異更新演算法，產品化後天然支援Unity等遊戲引擎；只需簡單的接入SDK，即可使用差異更新、資源熱更新及多管道多版本管理的全部功能；並且可以直接借助騰訊雲全球部署的基礎設施和CDN資源，一次接入全球使用，使玩家可以更快速的體驗到遊戲新版本。據不完全統計，騰訊內部手遊在使用了該遊戲更新方案後，更新的成功率高達99.7%，極大的減少了更新帶來的玩家流失，為遊戲的長久運營提供了堅實的技術支撐。目前遊戲更新Dolphin已在騰訊雲全量開放，希望可以幫助到各遊戲廠商和開發者，為玩家帶來“多快好省”的遊戲更新體驗。立即註冊，每月專享100M免費體驗流量： https://cloud.tencent.com/product/Dolphin 想瞭解更多騰訊雲遊戲行業解決方案和案例，立即報名1月19日騰訊雲GAME-TECH沙龍杭州站，我們一起探討：https://cloud.tencent.com/act/event/game-tech-hz.html 直播預約：http://www.itdks.com/eventlist/detail/1885