遊戲差異更新—BSDiff演算法解析
更多騰訊海量技術文章，請關注云加社區：https://cloud.tencent.com/developer
作者：騰訊雲遊戲行業資深架構師 張曉愚
為何需要差異更新？
差異更新即在軟體更新時只更新差異化的部分，以達到用最小的下載量完成軟體的更新需求。該思想由來已久，從剛接觸電腦時的操作系統、應用軟體快速更新功能或填補漏洞，到迭代更加頻繁的移動應用時代更多了節省下載流量費用的需求。尤其在移動遊戲領域，隨著手機性能的提升和玩家對遊戲體驗的追求，安裝包亦是越來越大，並且會頻繁的更新以不斷給玩家帶來更新的玩法和更為優化的體驗。然而，這種頻繁的更新也同樣會帶來負面的影響：更新包太大沒流量；更新速度太慢錯過了本該用來玩遊戲的碎片時間；本地空間不足無法更新等問題，這些負面影響都會導致一定程度上的玩家流失。因此，差異化更新能力目前已成為各應用下載渠道的必備能力之一，更小的更新包才能提高更新的成功率。
差異化更新可分為兩種，一種是基於源文件的差異化更新，該種方式成功率高， 演算法簡單，常用於平台相關的差異更新，但在移動端保存巨大的源文件、下載更新文件整合後再編譯的方式顯然是不現實的； 另一種即更為廣泛使用的方法即對可執行文件的二進位更新方式，本文中即將就該方式下的經典演算法BSDiff進行詳細介紹。
普通二進位文件對比
熟悉Linux的同學提到二進位文件對比自然會想到一個命令：cmp。那可執行文件的二進位更新豈不是有了這個對比結果後， 然後拿更新結果修改舊文件的二進位串為新文件不就OK了？用個最簡單的方法測試下，舊文件testDiffUpdate_Old與更新後文件testDiffUpdate_New內容僅差了第一個字元0。
xiaoyzhang$ cat testDiffUpdate_Old
xiaoyzhang$ cat testDiffUpdate_New
通過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
如文件內容可知，通過簡單的二進位對比得出的差異文件用來更新顯然是不靠譜的，差異文件的內容遠遠比新舊兩文件還要大的多。
這個差異更新的問題看起來沒有如此簡單，但上述問題仍然比較好解決，使用經典動態規劃演算法——最長公共子序列即可。上述兩個文件對比可以很輕易的找出最長公共子序列為123456789。這樣，只要在更新差異文件中記錄0和其對應的位置，並在舊文件中插入即可解決問題。這種方式下可以將差異更新轉化為兩個最基本的操作即：複製和插入，文件僅包含差異內容的複製及需要插入位置的索引即可，可以極大的減少更新包的大小，做到我們需要的差異化更新能力。
如上方式已經可以使用，但也僅可以使用在源文件的差異對比中，在可執行文件的二進位對比情況下，每次源碼的輕微變動將會導致可執行文件的巨大變化，如下圖中可執行文件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
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
使用bspatch old new patch命令得到新的可執行文件bspatch_new。
xiaoyzhang$ bspatch bspatch bspatch_new delta.patch
xiaoyzhang$ ls -ll
最後做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 幾種二進位更新演算法效率對比 （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
TAG:雲加社區 |