前言

之前畢設有用到文件增量同步，于是乎就記錄一下。

場景

在A和B兩個不同端之間有相似度很高的文件，同時這個文件又比較大。如果通過全量傳輸來更新，http傳輸量很大，非常不友好。那么可以通過某些手段，只上傳修改的內容，其余內容復用舊文件。

重復塊檢測技術

• 固定分塊檢測技術：固定分塊檢測的話，如果某一區域發生變化，之后分塊將均無法檢測命中塊，命中率低且局限性大。
• 可變塊檢測技術：可變塊很好解決上面的問題，例如CDC算法。不過好像沒有通用的解決方案，我是沒找到。
• 滑動塊檢測技術：采用固定塊，滑動檢測是否命中，命中率高，但是相似度越低的文件，越耗時，例如：rsync增量傳輸算法，也是本文的講解目標

rsync增量傳輸算法

對于A、B文件進行同步為例，首先對A文件進行分塊，并且對每一塊進行摘要計算（弱摘要&強摘要），并將其摘要數據傳輸給B端。B從第一字節開始，以相同大小的塊滑動下去一一比較。

首先計算當前塊的弱摘要，若弱摘要命中，則計算強摘要是否相同；若均相同，則該區域是相同塊；兩個相同塊之間的區域，則是差異塊。

• 弱摘要采用Adler-32，生成速度快，但是可能出現重復。
• 強摘要采用md5，生成慢，但是有保障。

（圖片來源于網絡）

那么以上的內容，其實對于A、B兩端，均有計算量。其實是不友好的，在單A對多B或者單B對多A的場景，則壓力過大。

同時滑動塊的大小也非常影響結果：若滑動塊過小，可以提高命中率，但是計算量增大；若滑動塊過大，計算量減少，但是可能降低命中率。

優化

對于實際的應用場景，可以大致分成兩種情況：

• 客戶端有新文件，要增量同步給服務端；
• 服務端有新文件，要增量同步給其他端；

無論是第一種情況還是第二種情況，我們都希望將計算量放到客戶端，而服務端僅僅做合并操作或者傳輸數據操作。

那么我們可以在其他端第一次傳輸給服務端新文件的時候，將摘要在本地計算得到，然后一起發給服務端。在之后更新的時候，同時也把新的摘要發給服務端更新。服務端就可以緩存摘要內容，省去計算過程。

同時，對于某些情況，可以緩存新舊文件的差異內容，通過版本號的差異，查詢服務端是否有保存差異內容文件，若保存了，則可以直接傳輸更新。

那么對于第一種情況：客戶端首先向服務端發起獲取摘要請求，服務端返回摘要后，客戶端本地滑動塊檢測摘要，然后，將檢測結果同差異內容文件發送給服務端，服務端做合并操作。

對于第二種情況：客戶端還是向服務端發起獲取摘要請求，服務端返回摘要后，客戶端滑動塊檢測摘要。相同塊內容，則從本地文件獲取，差異塊內容文件則通過http range請求。其實也可以直接請求差異文件，若服務端有保存的話。

同時需要設置闕值，在塊滑動檢測時，若命中率過低，可以省去檢測過程，直接采用全量上傳文件同步操作。因為，相似度低的文件，滑動檢測比較花時間，同時結果也不盡人意。

實際使用

我也寫了個demo在github上，在文章末尾已放鏈接。

以瀏覽器新文件增量同步給服務端為例。

我們可以建立一個webwork，然后將計算摘要的過程和滑塊檢測的過程，都放到webwork上。

由于摘要結果需要三個數據，弱摘要，強摘要以及對應序號。一開始想的是數組，對象包括兩種摘要，下標作為序號。但是，這樣查找效率太低了，每次查找都需要遍歷一遍，效率低下。

后來換了個思路，采用以下數據結構：

弱摘要作為key值，強摘要作為value值，對應的原文件內容序號則以@index放到value的末尾。同時，因為弱摘要是可能出現重復的，所以，在計算時，檢測弱摘要是否存在，若存在則在末尾加@1，若還存在則，繼續@2等等，直到不存在，可以放入對象中。

目的就是為了降低查找復雜度，從O(n)變成O(1)。

同時，對于相似度高的文件，滑動塊檢測，必然出現連續的相同塊。 若連續區域，在原文件上是連續的序號，則可以將其合并，減小傳輸數據大?。?/p>

null是差異塊文件，下標作為文件的標識之一。

num是原文件分塊結果的第num塊區域。

數組是原文件分塊結果的第start至end區域。

然后，對于差異塊文件，就進行正常上傳操作，目前還是以http1.1為主流，還是采用4~5個4~5個同時上傳比較好。

作者：江魚兒呃呃呃
鏈接：https://juejin.im/post/6865562336158023688

本文源碼:https://github.com/cjj281795819/study_rsync