最終實(shí)現(xiàn)效果:
- 無(wú)版本概念,任何本地文件均可增量升級(jí)到最新.服務(wù)器不用管理多版本
- 內(nèi)存小,100M文件升級(jí)時(shí)只占用500KB內(nèi)存.
使用流程:
- 制作新版本,上傳HTTP File Server.
- Client自動(dòng)計(jì)算差異,下載差異,合并差異.
- done!
0.緣起
目前主流的文件增量更新方案是bs diff/patch著拭，以及google chrome Courgette改進(jìn)方案。
無(wú)盡之劍Android版最初使用該方案，在封測(cè)期間發(fā)現(xiàn)存在問(wèn)題:
多版本運(yùn)營(yíng)繁瑣。
假設(shè)目前先后開發(fā)了5個(gè)版本花盐，1.0～5.0，運(yùn)營(yíng)中需要制作
1-2.patch
2-3.patch
3-4.patch
4-5.patch
n個(gè)版本,n-1個(gè)patch包
或者
1-2.patch
1-3.patch 2-3.patch
1-4.patch 2-4.patch 3-4.patch
1-5.patch 2-5.patch 3-5.patch 4-5.patch
n個(gè)版本,(n-1)階乘個(gè)patch包patch依賴本地版本文件完整性
如果本地文件損壞或被篡改砌些，就無(wú)法增量升級(jí)设江，只能重新下載完整包.bs diff/patch算法性能和內(nèi)存開銷太高
from bsdiff官網(wǎng)
bsdiff is quite memory-hungry. It requires max(17n,9n+m)+O(1) bytes of memory, where n is the size of the old file and m is the size of the new file. bspatch requires n+m+O(1) bytes.
bsdiff runs in O((n+m) log n) time; on a 200MHz Pentium Pro, building a binary patch for a 4MB file takes about 90 seconds.
bspatch runs in O(n+m) time; on the same machine, applying that patch takes about two seconds.
bsdiff執(zhí)行慢,可以,200M文件制作patch包需要運(yùn)行64位版本，可以.
bspatch執(zhí)行慢,可以似袁。需要占用n+m內(nèi)存,這點(diǎn)無(wú)法接受.
無(wú)盡之劍Android版的資源包單個(gè)最大200M洞辣，在游戲運(yùn)行同時(shí)進(jìn)行200M+內(nèi)存開銷的patch操作，非常容易OOM.
那么問(wèn)題來(lái)了：有沒(méi)有一種版本無(wú)關(guān)昙衅，內(nèi)容無(wú)關(guān)扬霜，內(nèi)存開銷小的增量升級(jí)方案呢?
這就是我的crsync:
純C語(yǔ)言實(shí)現(xiàn),基于rsync rolling算法, Client Side計(jì)算diff和執(zhí)行patch，通過(guò)curl進(jìn)行HTTP range增量下載
(同類方案有zsync,用于ubuntu package增量更新)
客戶端計(jì)算本地版本和服務(wù)器最新版本之間的diff而涉，然后通過(guò)http range下載差異部分.
內(nèi)存開銷 = 文件size/分塊size * 40字節(jié) + HashTable開銷.
假設(shè)文件size 100M著瓶，分塊size 16K,那么patch操作最多只需500KB內(nèi)存。版本無(wú)關(guān), 本地文件是否改動(dòng)無(wú)關(guān)啼县，只關(guān)注本地和遠(yuǎn)端之間的內(nèi)容差異.
1.rsync rolling
檢測(cè)2個(gè)文件的差異和重復(fù)數(shù)據(jù)材原，有2種策略:定長(zhǎng)分塊和變長(zhǎng)分塊.
rsync算法屬于前者,RDC算法屬于后者,多輪rsync可以看作是對(duì)定長(zhǎng)分塊的變長(zhǎng)優(yōu)化.
定長(zhǎng)分塊是將A文件按固定塊大小切分,計(jì)算校驗(yàn)值。在B文件中遍歷,計(jì)算所有相同塊大小的校驗(yàn)值,相同即一致谭羔，不同即差異.
以下假設(shè)文件size=100M, 分塊size=1KB,測(cè)試數(shù)據(jù)基于公司開發(fā)機(jī)i7-3770 CPU.
A文件切分,計(jì)算[0]~[1023], [1024][2047],[2048][3071]...的校驗(yàn)值华糖，輸出一張A表.
B文件遍歷,計(jì)算[0]~[1023], [1][1024],[2][1025],...的校驗(yàn)值,在A表中遍歷比對(duì).相同即重復(fù),不同即差異.
不足1KB的數(shù)據(jù),rsync補(bǔ)齊0再計(jì)算校驗(yàn)值，與B文件遍歷計(jì)算比對(duì).
crsync不計(jì)算,直接將之存入A表末尾,當(dāng)作差異.
校驗(yàn)算法很多,常用MD4,MD5,SHA-1,BLAKE2均可.
這樣明顯很慢,如何優(yōu)化?
rsync使用2個(gè)校驗(yàn)值,弱校驗(yàn)和強(qiáng)校驗(yàn).
弱校驗(yàn)是計(jì)算一個(gè)32位的CRC值,優(yōu)點(diǎn): 快; 缺點(diǎn): 沖突率高;校驗(yàn)值相同時(shí)數(shù)據(jù)可能不同.
強(qiáng)校驗(yàn)是上面說(shuō)到的各種算法,優(yōu)點(diǎn): 沖突率低; 缺點(diǎn): 慢.
首先做弱校驗(yàn),值相同再做強(qiáng)校驗(yàn).以此保證快速與準(zhǔn)確.
遍歷文件[0]~[1023], [1][1024],[2][1025],...需計(jì)算104856577次弱校驗(yàn)
這樣依然很慢瘟裸，如何優(yōu)化?
CRC校驗(yàn)算法很多,rsync使用adler32算法,因此有了rolling的特性.
alder32算法由Mark Adler于1995發(fā)明,用于zlib.
一個(gè)32位的adler32值由2個(gè)16位的A和B值構(gòu)成客叉。
A值=buffer中所有byte相加,對(duì)2^16取模(65536).
b值=buffer中所有A相加,對(duì)2^16取模(65536).
公式如下:
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
= n×D1 + (n?1)×D2 + (n?2)×D3 + ... + Dn + n (mod 65521)
Adler-32(D) = B × 65536 + A
65521是65536范圍內(nèi)的最大素?cái)?shù),因此mod=65521即可.
librsync(rdiff)在A和B值計(jì)算時(shí)再偏移31,rsync偏移0,crsync偏移0.
有趣的是,這個(gè)公式等價(jià)于:
A += data[i];
B += A;
rolling是什么?
計(jì)算出[0][1023]的校驗(yàn)值,再計(jì)算[1][1024]的校驗(yàn)值時(shí),只需減去data[0],加上data[1024]即可!不需重新計(jì)算!
A -= data[0];
A += data[1024];
B -= 1024 * data[0];
B += A;
如此滑動(dòng)遍歷,即可得到整個(gè)文件的所有分塊的校驗(yàn)值.(大贊!)
實(shí)測(cè)文件size 100M,分塊size 2K,遍歷計(jì)算僅耗時(shí)275ms.
2.rsync HashTable
rolling計(jì)算足夠快了,用B文件每個(gè)塊的校驗(yàn)值check A文件的校驗(yàn)表,如何優(yōu)化?
A文件的校驗(yàn)表size = 102400,冒泡?快速?折半?
rsync使用二段HashTable來(lái)存儲(chǔ)校驗(yàn)值,即H(A, H(B, MD5))
用adler32的A做key, B+MD5做value, 其中再用alder32的B做key, MD5做value.
表大小2^16,滿足A的值范圍.沖突值用LinkList存儲(chǔ).
首先命中A,再命中B,最后順序遍歷LinkList命中MD5.完成!
直接使用adler32值做key,MD5做value也可以,選擇合適的散列算法即可.
HashTable解決了命中率的問(wèn)題,但是實(shí)際中存在大量的missing查找.如何優(yōu)化?
zsync在此基礎(chǔ)上,使用一個(gè)bitbuffer來(lái)構(gòu)建"缺失表",每個(gè)分塊用3個(gè)bit表示,首先做位運(yùn)算,若存在再訪問(wèn)HashTable,否則直接跳過(guò).
crsync使用2^20的Bloom filter做faster missing. 為什么是2^20? 兼顧速度提升和內(nèi)存開銷(2^20 = 128KB)
3.client-side rsync
rsync是C/S架構(gòu),依賴rsyncd服務(wù)端存在,執(zhí)行流程是:
- client生成本地校驗(yàn)表.發(fā)送給server
- server執(zhí)行rsync rolling,發(fā)送相同塊的index和差異塊的數(shù)據(jù).
- client接受指令,執(zhí)行merge.
是否可以去掉rsyncd server,只依賴HttpServer(CDN)存儲(chǔ)文件和校驗(yàn)表,客戶端執(zhí)行rsync rolling?
crsync和zsync為此而生.
- 制作新版本文件,生成校驗(yàn)表,一并上傳CDN.
- client下載新版本的校驗(yàn)表.
- client根據(jù)本地文件和新校驗(yàn)表,執(zhí)行rsync rolling,得到重復(fù)數(shù)據(jù)index和差異數(shù)據(jù)的塊index.
- client重用本地?cái)?shù)據(jù),下載差異數(shù)據(jù),合并寫入新文件.
- done!
4.crsync VS bs diff/patch
測(cè)試對(duì)比1:
測(cè)試文件: 無(wú)盡之劍Android版資源包, base14009.obb ~ base14012.obb 92MB～93MB
編譯版本: MinGW 32bit release
Bloom filter: 2^20
純本地差異查找與合并,無(wú)網(wǎng)絡(luò)開銷
測(cè)試機(jī): DELL PC, Intel i3 550 (4core 3.2GHz) 4GB RAM
| 分塊大小 | 校驗(yàn)表生成時(shí)間 | 校驗(yàn)塊數(shù)量 | 差異查找時(shí)間 | 重復(fù)塊數(shù)量 | 差異塊大小 |
|---|---|---|---|---|---|
| 2K | 2182 ms | 46328 | 3753 ms | 40418 | 11820 KB |
| 4K | 2156 ms | 23164 | 2914 ms | 18960 | 16816 KB |
| 8K | 2154 ms | 11582 | 2719 ms | 9249 | 18664 KB |
測(cè)試機(jī) HP PC, Intel i7-3770 (8core 3.4GHz) 8GB RAM:
| 分塊大小 | 校驗(yàn)表生成時(shí)間 | 校驗(yàn)塊數(shù)量 | 差異查找時(shí)間 | 重復(fù)塊數(shù)量 | 差異塊大小 |
|---|---|---|---|---|---|
| 2K | 1745 ms | 46328 | 2974 ms | 40418 | 11820 KB |
crsync VS bspatch
| 算法 | 差異量 | 內(nèi)存開銷 |
|---|---|---|
| bsdiff | 16.7MB (diff文件) | 108.7MB (92MB+16.7MB) |
| crsync | 12.36MB(校驗(yàn)表835KB + 差異數(shù)據(jù)11820KB) | 1.76MB |
測(cè)試對(duì)比2:
測(cè)試文件: 我叫MT online Android標(biāo)準(zhǔn)版 90.7MB ~ 我叫MT online Android高清版 102MB
(測(cè)試版本基于2015.4.4官網(wǎng)下載,目前已變更)
測(cè)試機(jī) HP PC, Intel i7-3770 (8core 3.4GHz) 8GB RAM:
| 分塊大小 | 校驗(yàn)表生成時(shí)間 | 差異查找時(shí)間 | merge時(shí)間 |
|---|---|---|---|
| 2K | 1379 ms | 2950 ms | 90ms |
crsync VS bs diff/patch
| 算法 | 差異量 | 內(nèi)存開銷 |
|---|---|---|
| bsdiff | 29.5MB (diff文件) | 120.2MB (90.7MB+29.5MB) |
| crsync | 40.8MB | 1.7MB |
這里發(fā)現(xiàn), 為什么無(wú)盡之劍資源包使用crsync得到的差異量更小?
那么問(wèn)題來(lái)了, 如何設(shè)計(jì)出適合差異更新的文件格式
幾種格式對(duì)比:
- 整個(gè)文件不壓縮,完整下載量大,更新量小,bsdiff更優(yōu),因?yàn)閐iff文件使用bzip2壓縮格式.crsync使用原始數(shù)據(jù)http range下載.
- 整個(gè)文件zip壓縮,完整下載量大,更新量更大,這時(shí)bsdiff和crsync都無(wú)效.因?yàn)樯倭扛膭?dòng)就會(huì)造成整個(gè)文件的大量差異.
- 文件內(nèi)容用zip壓縮,再序列化到一起,完整下載量小,更新量小.這時(shí)crsync更優(yōu),因?yàn)閎sdiff對(duì)zip壓縮過(guò)的數(shù)據(jù)處理會(huì)生成額外數(shù)據(jù)量.
UnrealEngine3 Android使用的obb格式為:文件頭(貼圖原始大小, 壓縮大小,文件體偏移位置)+文件體(貼圖內(nèi)容zip壓縮).
資源更改只影響zip壓縮部分和文件頭索引內(nèi)容.對(duì)其他未更改資源無(wú)影響.
Android APK是zip壓縮格式,但是特定后綴名的文件不壓縮,常見(jiàn)圖片音視頻文件為了支持流式read保持原始格式.
因此crsync對(duì)比bsdiff的差異量大些.
5.源碼
https://github.com/9468305/crsync
純C語(yǔ)言實(shí)現(xiàn), 遵循C99。
核心部分僅2個(gè)文件 crsync.h crsync.c 880行代碼.static-link libcurl.
release版Android so 166KB, Windows mingw32 exe 299KB.
API實(shí)現(xiàn)參考curl設(shè)計(jì)(v0.1.0)
CRSYNCcode crsync_global_init();
crsync_handle_t* crsync_easy_init();
CRSYNCcode crsync_easy_setopt(crsync_handle_t *handle, CRSYNCoption opt, ...);
CRSYNCcode crsync_easy_perform_match(crsync_handle_t *handle);
CRSYNCcode crsync_easy_perform_patch(crsync_handle_t *handle);
void crsync_easy_cleanup(crsync_handle_t *handle);
void crsync_global_cleanup();
