1.寫(xiě)在前面
文件同步的核心問(wèn)題是新舊版本的對(duì)比問(wèn)題匠题。這里所說(shuō)的版本是指用于區(qū)分文件變更的一種狀態(tài)標(biāo)記拯坟，它可以是我們通常所說(shuō)的版本號(hào)，也可以是時(shí)間戳韭山，如修改時(shí)間郁季。本文介紹一種基于diff的文件同步算法，共分為兩篇钱磅，上篇介紹diff算法的服務(wù)端實(shí)現(xiàn)梦裂，下篇介紹diff算法的客戶端實(shí)現(xiàn)。
2.算法概述
從客戶端的角度來(lái)看盖淡，文件同步的本質(zhì)是本地文件集合與云端文件集合的對(duì)比年柠。從實(shí)現(xiàn)角度來(lái)講，客戶端會(huì)保存一份云端文件集合的快照褪迟，通過(guò)將快照和云端集合對(duì)比可以計(jì)算出云端文件變更冗恨，通過(guò)將快照和本地集合對(duì)比則可以計(jì)算出本地文件變更答憔。對(duì)于本地文件的變更，需要將文件提交至云端掀抹；對(duì)于云端文件的變更攀唯，需要將文件同步至本地。對(duì)于文件同步在云端和本地都有修改的情況下渴丸，就需要進(jìn)行沖突處理侯嘀。
如果每個(gè)同步周期需要獲取云端文件集合，文件量小還可以接受谱轨，文件量一大戒幔，對(duì)帶寬和服務(wù)器壓力都會(huì)存在瓶頸，而且很多文件可能根本就沒(méi)有變更土童，這會(huì)造成很多無(wú)效的對(duì)比诗茎，浪費(fèi)計(jì)算資源。所以需要一種增量機(jī)制献汗，用于增量拉取云端變更的文件敢订。
diff算法是利用修改時(shí)間作為增量機(jī)制，其核心是每次diff時(shí)會(huì)記錄下當(dāng)前diff的時(shí)間戳罢吃，客戶端下次diff時(shí)楚午，帶上上次diff時(shí)返回的時(shí)間戳（通常將時(shí)間戳編碼到cursor中），這樣就能增量獲取到一段時(shí)間內(nèi)的變更記錄了尿招。由于每次diff的變更文件集合可能非常大矾柜，所以需要進(jìn)行分頁(yè)操作，有兩個(gè)主要的問(wèn)題需要解決：
- 首次diff問(wèn)題
- 用時(shí)間維度獲取變更記錄時(shí)就谜，如(t1, t2]之間的文件變更怪蔑，由于t1、t2通常是使用秒作為精度丧荐，每次分頁(yè)diff出的文件記錄時(shí)缆瓣，如果存在閉區(qū)間t2時(shí)刻文件記錄，則無(wú)法判斷t2時(shí)刻是否存在更多的記錄虹统。
3.全量同步
首次diff通常發(fā)生在客戶端本地快照沒(méi)有數(shù)據(jù)且第一次請(qǐng)求時(shí)弓坞，這種情況通常指全量同步。服務(wù)器在處理全量同步時(shí)是希望盡量將當(dāng)時(shí)請(qǐng)求時(shí)刻以內(nèi)的所有文件數(shù)據(jù)都分頁(yè)吐給客戶端窟却。由于時(shí)間戳存在增量同步的問(wèn)題昼丑，可以使用文件惟一標(biāo)識(shí)迭代出全量數(shù)據(jù)。如果記文件的惟一標(biāo)識(shí)為fid夸赫，修改時(shí)間為mtime，分頁(yè)大小為pagesize咖城，SQL查詢具體做法為：
select fields from file_meta where fid>last_fid and mtime<=stime sort by fid ASC limit pagesize茬腿；
其中：
- stime是第一次全量同步時(shí)呼奢，記錄下當(dāng)前請(qǐng)求的時(shí)間戳，主要是明確一個(gè)時(shí)間限界內(nèi)的全量數(shù)據(jù)切平，防止在全量同步過(guò)程中又出現(xiàn)新的變更握础；
- last_fid為最近一次查詢結(jié)果中最后一條記錄的fid，首次查詢last_fid為0悴品；
- 判斷是否有更多數(shù)據(jù)通常采用多取一條記錄進(jìn)行判斷禀综；
- 由于并不知道全量同步過(guò)程中是否有新的文件變更，需要進(jìn)行一次增量同步苔严；
4.增量同步
前面說(shuō)到在按時(shí)間維度進(jìn)行增量同步時(shí)定枷，由于需要分頁(yè)，并不知道閉區(qū)間內(nèi)是否有更多文件變更記錄届氢。舉個(gè)粟子欠窒，當(dāng)我們查詢出(t1, t2]的文件集合時(shí)，如果恰好有幾個(gè)文件的修改時(shí)間等于t2退子，而且本次分頁(yè)并沒(méi)有拉取完岖妄。下次diff時(shí)會(huì)查詢(t3, t4]時(shí)間區(qū)間內(nèi)的文件（t3>t2)，由于上次并沒(méi)有拉取完寂祥，即t2時(shí)間可能還有更多數(shù)據(jù)荐虐，如果直接查詢(t3, t4]時(shí)間區(qū)間的文件，那么可能會(huì)丟失t2時(shí)間的文件記錄丸凭。
對(duì)于以上情況衙传，當(dāng)查詢(t1, t2]時(shí)間區(qū)間內(nèi)的文件時(shí)，針對(duì)返回的文件遵班，我們需要對(duì)最后一秒的文件進(jìn)行單獨(dú)處理瘾婿。如果返回的文件的修改時(shí)間均是在一秒內(nèi)，那么稱為單秒增量同步向拆，其它情況稱為正常增量同步亚茬。
4.1.正常增量同步
對(duì)于正常增量同步雖然所有文件的mtime不是在同一秒內(nèi)，但需要處理最后一秒問(wèn)題浓恳，就像前面的例子刹缝，當(dāng)分頁(yè)未完成時(shí)，我們沒(méi)辦判斷最后一秒是否還有更多數(shù)據(jù)颈将，所以一個(gè)簡(jiǎn)單的做法是從本次查詢的文件記錄中梢夯，從最后一個(gè)文件開(kāi)始，移除mtime相同的文件晴圾，即把最后一秒的文件留到下次進(jìn)行查詢颂砸。當(dāng)最后一秒的文件足夠多，比如超過(guò)一個(gè)分頁(yè)時(shí)，就會(huì)觸發(fā)單秒增量同步人乓。正常增量同步查詢SQL表示：
select fields from file_meta where mtime>t1 and mtime<=t2 sort by mtime DESC limit pagesize;
4.2.單秒增量同步
單秒增量同步是指查詢一秒內(nèi)的文件記錄勤篮，這種查詢比較簡(jiǎn)單，如果用SQL表示如下：
select fields from file_meta where mtime=xxx sort limit pagesize;
5.其它工程問(wèn)題
在工程實(shí)現(xiàn)上還需要注意很多問(wèn)題色罚，比如主從同步碰缔、頻率控制、數(shù)據(jù)重置等戳护。
5.1.主從同步
對(duì)服務(wù)器來(lái)講金抡，文件數(shù)據(jù)的存儲(chǔ)量通常都比較大，不可能采用單機(jī)就能搞定腌且，一般都會(huì)采用分布式進(jìn)行存儲(chǔ)梗肝，對(duì)于分布存儲(chǔ)就會(huì)存儲(chǔ)主從同步問(wèn)題。當(dāng)寫(xiě)操作完成后切蟋，馬上讀取统捶，如果主從同步未完成，并不能讀取出數(shù)據(jù)柄粹。所以在diff的時(shí)間滑動(dòng)窗口中喘鸟，需要做一定的延遲處理，延遲時(shí)間肯定需要大于主從同步的時(shí)間驻右。
5.2.頻率控制
對(duì)于diff接口什黑，可能會(huì)調(diào)用的比較頻繁，如果不進(jìn)行頻率控制堪夭，高峰期時(shí)可能會(huì)造成雪崩效率愕把，diff接口需要有降級(jí)和頻控處理。diff接口一般來(lái)說(shuō)是一種后臺(tái)行為森爽，并不需要進(jìn)行實(shí)時(shí)調(diào)用恨豁，當(dāng)客戶端進(jìn)行增量同步時(shí)，如果在一段很短的時(shí)間內(nèi)連續(xù)調(diào)用爬迟，應(yīng)觸發(fā)頻控策略橘蜜。
5.3.數(shù)據(jù)重置
由于客戶端會(huì)緩存云端數(shù)據(jù)快照，如果客戶端存在臟數(shù)據(jù)付呕，將導(dǎo)致同步算法失敗计福。服務(wù)器應(yīng)該和客戶端約定一種數(shù)據(jù)重置機(jī)制，當(dāng)服務(wù)器端數(shù)據(jù)升級(jí)或出現(xiàn)臟數(shù)據(jù)時(shí)徽职，服務(wù)端可以下發(fā)數(shù)據(jù)重置命令象颖，客戶端收到數(shù)據(jù)重置命令后應(yīng)該清空本地緩存，重新進(jìn)行全量同步姆钉。
6.總結(jié)
diff算法需要處理全量同步和增量同步的情況说订。全量同步按照文件id維度排序分頁(yè)下發(fā)抄瓦；增量同步按照時(shí)間維度分頁(yè)下發(fā)，由于分頁(yè)原因以及時(shí)間精度問(wèn)題克蚂，不能判斷最后一秒內(nèi)是否存在更多的數(shù)據(jù)需要查詢闺鲸，因?yàn)榘炎詈笠幻氲臄?shù)據(jù)進(jìn)行單獨(dú)查詢筋讨。最后就是需要考慮一些工程上的問(wèn)題埃叭，如主從同步、頻率控制悉罕、接口降級(jí)赤屋、數(shù)據(jù)重置等問(wèn)題。
--- 上篇完 ---
