之前在某個產品中使用了Gossip算法進行數據庫數據的同步，但是在新的產品中有個需求，就是當文件變化時，(由于文件比較大，比較多)支持增量推送到文件服務器上。于是想到了Unix下的rsync算法，本文也是拜讀了很多大佬的作品，從自己理解的角度整理出來。關于rsync算法的原文請閱讀

https://rsync.samba.org/tech_report/tech_report.html

1、同步技術

一般除了rsync增量同步外，還有一種scp的同步方式，用于將文件上傳和下載，類似于ftp協議。scp?username@servicename:/path/filename?/var/localdir舉例：比如使用這個命令scp root@192.168.0.1:/path/ClassPath.xml /var/localdir。意思就是將192.168.0.1服務器上面的Classpath.xml文件下載到本地的var/localdir文件夾中。scp?/var/filename?username@servicename:/path舉例：比如使用scp /a.xml root@192.168.0.1:/path ,意思就是將本地的a.xml文件上傳到192.168.0.1 服務器的path路徑下，用戶名root。

? ? ? 當然了，還可以在scp命令的后面加上-r 參數，用于下載和上傳整個文件夾。類似與rmdir 命令遞歸刪除文件夾了。在使用scp的前提是對端服務器開啟文件的寫入權限。

? ? 關于ftp這種應用層的上傳下載協議，我也在項目中用過，這里不再敘述，推薦一個開源組件libcurl，可以支持多種協議，使用也比較簡單。

2、rsync算法原理

? ? ? 一般情況下，如果我們要同步的文件只想傳不同的部分，我們就需要對兩邊的文件做差異對比，但是這兩個問題在兩臺不同的機器上無法做對比。如果我們做對比，就要把一個文件傳到另一臺機器上做對比，但這樣一來，我們就傳了整個文件，這與我們只想傳輸不同部的初衷相背。

? ? rsync的算法是讓這兩邊的文件不見面，但還能知道它們間有什么不同。

? ? rsync的算法如下：(假設我們同步源文件名為fileSrc，同步目的文件叫fileDst)

1)分塊Checksum算法。首先，我們會把fileDst的文件平均切分成若干個小塊，比如每塊512個字節(一般在2的整數次方，比如512，1024，最后一塊會小于這個數)，然后對每塊計算兩個checksum，

• 一個叫rolling checksum，是弱checksum，32位的checksum，其使用的是Mark Adler發明的adler-32算法，

• 另一個是強checksum，128位的，以前用md4，現在用md5 hash算法。

這里使用兩個checksum算法，是因為我們需要一個快算法來鑒別文件塊的不同，但是弱的adler32算法碰撞概率太高了，所以我們還要引入強的checksum算法以保證兩文件塊是相同的。也就是說，弱的checksum是用來區別不同，而強的是用來確認相同。

2)傳輸算法。同步目標端會把fileDst的一個checksum列表傳給同步源，這個列表里包括了三個東西，rolling checksum(4字節，32bits),

md5 checksume(16字節，128bits)，文件塊編號。

3)checksum查找算法。同步源端拿到fileDst的checksum數組后，會把這個數據存到一個hash table中，用rolling checksum做hash，以便獲得O(1)時間復雜度的查找性能。這個hash table是16bits的，所以，hash table的尺寸是2的16次方，對rolling checksum的hash會被散列到0 到 2^16 – 1中的某個整數值。

? ?算法的流程如下所示：

? ?首先從目的文件獲取了文件塊的checksum，然后開始計算源端的文件。

1)取fileSrc的第一個文件塊(我們假設的是512個長度)，也就是從fileSrc的第1個字節到第512個字節，取出來后做rolling checksum計算。計算好的值到hash表中查。

2)如果查到了，說明發現在fileDst中有潛在相同的文件塊，于是就再比較md5的checksum，因為rolling checksume太弱了，可能發生碰撞。于是還要算md5的128bits的checksum，這樣一來，我們就有 2^-(32+128) = 2^-160的概率發生碰撞，這太小了可以忽略。如果rolling checksum和md5 checksum都相同，這說明在fileDst中有相同的塊，我們需要記下這一塊在fileDst下的文件編號。

3)如果fileSrc的rolling checksum 沒有在hash table中找到，那就不用算md5 checksum了。表示這一塊中有不同的信息。總之，只要rolling checksum 或 md5 checksum 其中有一個在fileDst的checksum hash表中找不到匹配項，那么就會觸發算法對fileSrc的rolling動作。于是，算法會住后移動1個字節，取fileSrc中字節2-513的文件塊要做checksum，然后執行step1。

4)這樣，我們就可以找出fileSrc相鄰兩次匹配中的那些文本字符，這些就是我們要往同步目標端傳的文件內容了。

? ? ?經過算法的計算和對比，將不同的文件和文件塊組成一個新的列表發送到fileDst端，fileDst端收到新的文件列表，則進行組裝成新的文件。最終兩個文件同步成功。

3?總結

? ? ? rolling checksum算法給我們提供了一種增量同步的思路。通過循環校驗查找，找到相同的塊。最終將不同的數據同步過去即可，極大的減少了網絡傳輸的帶寬。

總結

以上是生活随笔為你收集整理的rsync文件实时同步_从文件同步rsync算法谈起的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。