本文通過(guò)示例詳細(xì)分析rsync算法原理和rsync的工作流程，是對(duì)rsync官方技術(shù)報(bào)告和官方推薦文章的解釋。本文不會(huì)介紹如何使用rsync命令(見(jiàn)rsync基本用法)，而是詳細(xì)解釋它如何實(shí)現(xiàn)高效的增量傳輸。

以下是rsync系列篇：

1.rsync(一)：基本命令和用法

2.rsync(二)：inotify+rsync詳細(xì)說(shuō)明和sersync

3.rsync算法原理和工作流程分析

4.rsync技術(shù)報(bào)告(翻譯)

5.rsync工作機(jī)制(翻譯)

6.man rsync翻譯(rsync命令中文手冊(cè))

本文目錄：

1.1 需要解決的問(wèn)題

1.2 rsync增量傳輸算法原理

1.3 通過(guò)示例分析rsync算法

1.4 rsync工作流程分析

1.4.1 幾個(gè)進(jìn)程和術(shù)語(yǔ)

1.4.2 rsync整個(gè)工作流程

1.5 根據(jù)執(zhí)行過(guò)程分析rsync工作流程

1.5.1 全量傳輸執(zhí)行過(guò)程分析

1.5.2 增量傳輸執(zhí)行過(guò)程分析

在開(kāi)始分析算法原理之前，簡(jiǎn)單說(shuō)明下rsync的增量傳輸功能。

假設(shè)待傳輸文件為A，如果目標(biāo)路徑下沒(méi)有文件A，則rsync會(huì)直接傳輸文件A，如果目標(biāo)路徑下已存在文件A，則發(fā)送端視情況決定是否要傳輸文件A。rsync默認(rèn)使用"quick check"算法，它會(huì)比較源文件和目標(biāo)文件(如果存在)的文件大小和修改時(shí)間mtime，如果兩端文件的大小或mtime不同，則發(fā)送端會(huì)傳輸該文件，否則將忽略該文件。

如果"quick check"算法決定了要傳輸文件A，它不會(huì)傳輸整個(gè)文件A，而是只傳源文件A和目標(biāo)文件A所不同的部分，這才是真正的增量傳輸。

也就是說(shuō)，rsync的增量傳輸體現(xiàn)在兩個(gè)方面：文件級(jí)的增量傳輸和數(shù)據(jù)塊級(jí)別的增量傳輸。文件級(jí)別的增量傳輸是指源主機(jī)上有，但目標(biāo)主機(jī)上沒(méi)有將直接傳輸該文件，數(shù)據(jù)塊級(jí)別的增量傳輸是指只傳輸兩文件所不同的那一部分?jǐn)?shù)據(jù)。但從本質(zhì)上來(lái)說(shuō)，文件級(jí)別的增量傳輸是數(shù)據(jù)塊級(jí)別增量傳輸?shù)奶厥馇闆r。通讀本文后，很容易理解這一點(diǎn)。

1.1 需要解決的問(wèn)題

假設(shè)主機(jī)α上有文件A，主機(jī)β上有文件B(實(shí)際上這兩文件是同名文件，此處為了區(qū)分所以命名為A和B)，現(xiàn)在要讓B文件和A文件保持同步。

最簡(jiǎn)單的方法是將A文件直接拷貝到β主機(jī)上。但如果文件A很大，且B和A是相似的(意味著兩文件實(shí)際內(nèi)容只有少部分不同)，拷貝整個(gè)文件A可能會(huì)消耗不少時(shí)間。如果可以拷貝A和B不同的那一小部分，則傳輸過(guò)程會(huì)很快。rsync增量傳輸算法就充分利用了文件的相似性，解決了遠(yuǎn)程增量拷貝的問(wèn)題。

假設(shè)文件A的內(nèi)容為"123xxabc def"，文件B的內(nèi)容為"123abcdefg"。A與B相比，相同的數(shù)據(jù)部分有123/abc/def，A中多出的內(nèi)容為xx和一個(gè)空格，但文件B比文件A多出了數(shù)據(jù)g。最終的目標(biāo)是讓B和A的內(nèi)容完全相同。

如果采用rsync增量傳輸算法，α主機(jī)將只傳輸文件A中的xx和空格數(shù)據(jù)給β主機(jī)，對(duì)于那些相同內(nèi)容123/abc/def，β主機(jī)會(huì)直接從B文件中拷貝。根據(jù)這兩個(gè)來(lái)源的數(shù)據(jù)，β主機(jī)就能組建成一個(gè)文件A的副本，最后將此副本文件重命名并覆蓋掉B文件就保證了同步。

雖然看上去過(guò)程很簡(jiǎn)單，但其中有很多細(xì)節(jié)需要去深究。例如，α主機(jī)如何知道A文件中哪些部分和B文件不同，β主機(jī)接收了α主機(jī)發(fā)送的A、B不同部分的數(shù)據(jù)，如何組建文件A的副本。

1.2 rsync增量傳輸算法原理

假設(shè)執(zhí)行的rsync命令是將A文件推到β主機(jī)上使得B文件和A文件保持同步，即主機(jī)α是源主機(jī)，是數(shù)據(jù)的發(fā)送端(sender)，β是目標(biāo)主機(jī)，是數(shù)據(jù)的接收端(receiver)。在保證B文件和A文件同步時(shí)，大致有以下6個(gè)過(guò)程：

(1).α主機(jī)告訴β主機(jī)文件A待傳輸。

(2).β主機(jī)收到信息后，將文件B劃分為一系列大小固定的數(shù)據(jù)塊(建議大小在500-1000字節(jié)之間)，并以chunk號(hào)碼對(duì)數(shù)據(jù)塊進(jìn)行編號(hào)，同時(shí)還會(huì)記錄數(shù)據(jù)塊的起始偏移地址以及數(shù)據(jù)塊長(zhǎng)度。顯然最后一個(gè)數(shù)據(jù)塊的大小可能更小。

對(duì)于文件B的內(nèi)容"123abcdefg"來(lái)說(shuō)，假設(shè)劃分的數(shù)據(jù)塊大小為3字節(jié)，則根據(jù)字符數(shù)劃分成了以下幾個(gè)數(shù)據(jù)塊：

count=4 n=3 rem=1    這表示劃分了4個(gè)數(shù)據(jù)塊，數(shù)據(jù)塊大小為3字節(jié)，剩余1字節(jié)給了最后一個(gè)數(shù)據(jù)塊
chunk[0]：offset=0 len=3 該數(shù)據(jù)塊對(duì)應(yīng)的內(nèi)容為123
chunk[1]：offset=3 len=3 該數(shù)據(jù)塊對(duì)應(yīng)的內(nèi)容為abc
chunk[2]：offset=6 len=3 該數(shù)據(jù)塊對(duì)應(yīng)的內(nèi)容為def
chunk[3]：offset=9 len=1 該數(shù)據(jù)塊對(duì)應(yīng)的內(nèi)容為g

當(dāng)然，實(shí)際信息中肯定是不會(huì)包括文件內(nèi)容的。

(3).β主機(jī)對(duì)文件B的每個(gè)數(shù)據(jù)塊根據(jù)其內(nèi)容都計(jì)算兩個(gè)校驗(yàn)碼：32位的弱滾動(dòng)校驗(yàn)碼(rolling checksum)和128位的MD4強(qiáng)校驗(yàn)碼(現(xiàn)在版本的rsync使用的已經(jīng)是128位的MD5強(qiáng)校驗(yàn)碼)。并將文件B計(jì)算出的所有rolling checksum和強(qiáng)校驗(yàn)碼跟隨在對(duì)應(yīng)數(shù)據(jù)塊chunk[N]后形成校驗(yàn)碼集合，然后發(fā)送給主機(jī)α。

也就是說(shuō)，校驗(yàn)碼集合的內(nèi)容大致如下：其中sum1為rolling checksum，sum2為強(qiáng)校驗(yàn)碼。

chunk[0] sum1=3ef2c827 sum2=3efa923f8f2e7
chunk[1] sum1=57ac2aaf sum2=aef2dedba2314
chunk[2] sum1=92d7edb4 sum2=a6sd6a9d67a12
chunk[3] sum1=afe74939 sum2=90a12dfe7485c

需要注意，不同內(nèi)容的數(shù)據(jù)塊計(jì)算出的rolling checksum是有可能相同的，但是概率非常小。

(4).當(dāng)α主機(jī)接收到文件B的校驗(yàn)碼集合后，α主機(jī)將對(duì)此校驗(yàn)碼集合中的每個(gè)rolling checksum計(jì)算16位長(zhǎng)度的hash值，并將每216個(gè)hash值按照hash順序放入一個(gè)hash table中，hash表中的每一個(gè)hash條目都指向校驗(yàn)碼集合中它所對(duì)應(yīng)的rolling checksum的chunk號(hào)碼，然后對(duì)校驗(yàn)碼集合根據(jù)hash值進(jìn)行排序，這樣排序后的校驗(yàn)碼集合中的順序就能和hash表中的順序?qū)?yīng)起來(lái)。

所以，hash表和排序后的校驗(yàn)碼集合對(duì)應(yīng)關(guān)系大致如下：假設(shè)hash表中的hash值是根據(jù)首個(gè)字符按照[0-9a-f]的順序進(jìn)行排序的。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

同樣需要注意，不同rolling checksum計(jì)算出的hash值也是有可能會(huì)相同的，概率也比較小，但比rolling checksum出現(xiàn)重復(fù)的概率要大一些。

(5).隨后主機(jī)α將對(duì)文件A進(jìn)行處理。處理的過(guò)程是從第1個(gè)字節(jié)開(kāi)始取相同大小的數(shù)據(jù)塊，并計(jì)算它的校驗(yàn)碼和校驗(yàn)碼集合中的校驗(yàn)碼進(jìn)行匹配。如果能匹配上校驗(yàn)碼集合中的某個(gè)數(shù)據(jù)塊條目，則表示該數(shù)據(jù)塊和文件B中數(shù)據(jù)塊相同，它不需要傳輸，于是主機(jī)α直接跳轉(zhuǎn)到該數(shù)據(jù)塊的結(jié)尾偏移地址，從此偏移處繼續(xù)取數(shù)據(jù)塊進(jìn)行匹配。如果不能匹配校驗(yàn)碼集合中的數(shù)據(jù)塊條目，則表示該數(shù)據(jù)塊是非匹配數(shù)據(jù)塊，它需要傳輸給主機(jī)β，于是主機(jī)α將跳轉(zhuǎn)到下一個(gè)字節(jié)，從此字節(jié)處繼續(xù)取數(shù)據(jù)塊進(jìn)行匹配。注意，匹配成功時(shí)跳過(guò)的是整個(gè)匹配數(shù)據(jù)塊，匹配不成功時(shí)跳過(guò)的僅是一個(gè)字節(jié)?？梢越Y(jié)合下一小節(jié)的示例來(lái)理解。

上面說(shuō)的數(shù)據(jù)塊匹配只是一種描述，具體的匹配行為需要進(jìn)行細(xì)化。rsync算法將數(shù)據(jù)塊匹配過(guò)程分為3個(gè)層次的搜索匹配過(guò)程。

首先，主機(jī)α?xí)?duì)取得的數(shù)據(jù)塊根據(jù)它的內(nèi)容計(jì)算出它的rolling checksum，再根據(jù)此rolling checksum計(jì)算出hash值。

然后，將此hash值去和hash表中的hash條目進(jìn)行匹配，這是第一層次的搜索匹配過(guò)程，它比較的是hash值。如果在hash表中能找到匹配項(xiàng)，則表示該數(shù)據(jù)塊存在潛在相同的可能性，于是進(jìn)入第二層次的搜索匹配。

第二層次的搜索匹配是比較rolling checksum。由于第一層次的hash值匹配到了結(jié)果，所以將搜索校驗(yàn)碼集合中與此hash值對(duì)應(yīng)的rolling checksum。由于校驗(yàn)碼集合是按照hash值排序過(guò)的，所以它的順序和hash表中的順序一致，也就是說(shuō)只需從此hash值對(duì)應(yīng)的rolling chcksum開(kāi)始向下掃描即可。掃描過(guò)程中，如果A文件數(shù)據(jù)塊的rolling checksum能匹配某項(xiàng)，則表示該數(shù)據(jù)塊存在潛在相同的可能性，于是停止掃描，并進(jìn)入第三層次的搜索匹配以作最終的確定?；蛘呷绻麤](méi)有掃描到匹配項(xiàng)，則說(shuō)明該數(shù)據(jù)塊是非匹配塊，也將停止掃描，這說(shuō)明rolling checksum不同，但根據(jù)它計(jì)算的hash值卻發(fā)生了小概率重復(fù)事件。

第三層次的搜索匹配是比較強(qiáng)校驗(yàn)碼。此時(shí)將對(duì)A文件的數(shù)據(jù)塊新計(jì)算一個(gè)強(qiáng)校驗(yàn)碼(在第三層次之前，只對(duì)A文件的數(shù)據(jù)塊計(jì)算了rolling checksum和它的hash值)，并將此強(qiáng)校驗(yàn)碼與校驗(yàn)碼集合中對(duì)應(yīng)強(qiáng)校驗(yàn)碼匹配，如果能匹配則說(shuō)明數(shù)據(jù)塊是完全相同的，不能匹配則說(shuō)明數(shù)據(jù)塊是不同的，然后開(kāi)始取下一個(gè)數(shù)據(jù)塊進(jìn)行處理。

之所以要額外計(jì)算hash值并放入hash表，是因?yàn)楸容^rolling checksum的性能不及hash值比較，且通過(guò)hash搜索的算法性能非常高。由于hash值重復(fù)的概率足夠小，所以對(duì)絕大多數(shù)內(nèi)容不同的數(shù)據(jù)塊都能直接通過(guò)第一層次搜索的hash值比較出來(lái)，即使發(fā)生了小概率hash值重復(fù)事件，還能迅速定位并比較更小概率重復(fù)的rolling checksum。即使不同內(nèi)容計(jì)算的rolling checksum也可能出現(xiàn)重復(fù)，但它的重復(fù)概率比hash值重復(fù)概率更小，所以通過(guò)這兩個(gè)層次的搜索就能比較出幾乎所有不同的數(shù)據(jù)塊。假設(shè)不同內(nèi)容的數(shù)據(jù)塊的rolling checksum還是出現(xiàn)了小概率重復(fù)，它將進(jìn)行第三層次的強(qiáng)校驗(yàn)碼比較，它采用的是MD4(現(xiàn)在是MD5)，這種算法具有"雪崩效應(yīng)"，只要一點(diǎn)點(diǎn)不同，結(jié)果都是天翻地覆的不同，所以在現(xiàn)實(shí)使用過(guò)程中，完全可以假設(shè)它能做最終的比較。

數(shù)據(jù)塊大小會(huì)影響rsync算法的性能。如果數(shù)據(jù)塊大小太小，則數(shù)據(jù)塊的數(shù)量就太多，需要計(jì)算和匹配的數(shù)據(jù)塊校驗(yàn)碼就太多，性能就差，而且出現(xiàn)hash值重復(fù)、rolling checksum重復(fù)的可能性也增大；如果數(shù)據(jù)塊大小太大，則可能會(huì)出現(xiàn)很多數(shù)據(jù)塊都無(wú)法匹配的情況，導(dǎo)致這些數(shù)據(jù)塊都被傳輸，降低了增量傳輸?shù)膬?yōu)勢(shì)。所以劃分合適的數(shù)據(jù)塊大小是非常重要的，默認(rèn)情況下，rsync會(huì)根據(jù)文件大小自動(dòng)判斷數(shù)據(jù)塊大小，但rsync命令的"-B"(或"--block-size")選項(xiàng)支持手動(dòng)指定大小，如果手動(dòng)指定，官方建議大小在500-1000字節(jié)之間。

(6).當(dāng)α主機(jī)發(fā)現(xiàn)是匹配數(shù)據(jù)塊時(shí)，將只發(fā)送這個(gè)匹配塊的附加信息給β主機(jī)。同時(shí)，如果兩個(gè)匹配數(shù)據(jù)塊之間有非匹配數(shù)據(jù)，則還會(huì)發(fā)送這些非匹配數(shù)據(jù)。當(dāng)β主機(jī)陸陸續(xù)續(xù)收到這些數(shù)據(jù)后，會(huì)創(chuàng)建一個(gè)臨時(shí)文件，并通過(guò)這些數(shù)據(jù)重組這個(gè)臨時(shí)文件，使其內(nèi)容和A文件相同。臨時(shí)文件重組完成后，修改該臨時(shí)文件的屬性信息(如權(quán)限、所有者、mtime等)，然后重命名該臨時(shí)文件替換掉B文件，這樣B文件就和A文件保持了同步。

1.3 通過(guò)示例分析rsync算法

前面說(shuō)了這么多理論，可能已經(jīng)看的云里霧里，下面通過(guò)A和B文件的示例來(lái)詳細(xì)分析上一小節(jié)中的增量傳輸算法原理，由于上一小節(jié)中的過(guò)程(1)-(4)，已經(jīng)給出了示例，所以下面將繼續(xù)分析過(guò)程(5)和過(guò)程(6)。

先看文件B(內(nèi)容為"123abcdefg")排序后的校驗(yàn)碼集合以及hash表。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

當(dāng)主機(jī)α開(kāi)始處理文件A時(shí)，對(duì)于文件A的內(nèi)容"123xxabc def"來(lái)說(shuō)，從第一個(gè)字節(jié)開(kāi)始取大小相同的數(shù)據(jù)塊，所以取得的第一個(gè)數(shù)據(jù)塊的內(nèi)容是"123"，由于和文件B的chunk[0]內(nèi)容完全相同，所以α主機(jī)對(duì)此數(shù)據(jù)塊計(jì)算出的rolling checksum值肯定是"3ef2e827"，對(duì)應(yīng)的hash值為"e827"。于是α主機(jī)將此hash值去匹配hash表，匹配過(guò)程中發(fā)現(xiàn)指向chunk[0]的hash值能匹配上，于是進(jìn)入第二層次的rolling checksum比較，也即從此hash值指向的chunk[0]的條目處開(kāi)始向下掃描。掃描過(guò)程中發(fā)現(xiàn)掃描的第一條信息(即chunk[0]對(duì)應(yīng)的條目)的rollign checksum就能匹配上，所以掃描終止，于是進(jìn)入第三層次的搜索匹配，這時(shí)α主機(jī)將對(duì)"123"這個(gè)數(shù)據(jù)塊新計(jì)算一個(gè)強(qiáng)校驗(yàn)碼，與校驗(yàn)碼集合中chunk[0]對(duì)應(yīng)的強(qiáng)校驗(yàn)碼做比較，最終發(fā)現(xiàn)能匹配上，于是確定了文件A中的"123"數(shù)據(jù)塊是匹配數(shù)據(jù)塊，不需要傳輸給β主機(jī)。

雖然匹配數(shù)據(jù)塊不用傳輸，但匹配的相關(guān)信息需要立即傳輸給β主機(jī)，否則β主機(jī)不知道如何重組文件A的副本。匹配塊需要傳輸?shù)男畔ǎ浩ヅ涞氖荁文件中的chunk[0]數(shù)據(jù)塊，在文件A中偏移該數(shù)據(jù)塊的起始偏移地址為第1個(gè)字節(jié)，長(zhǎng)度為3字節(jié)。

數(shù)據(jù)塊"123"的匹配信息傳輸完成后，α主機(jī)將處取第二個(gè)數(shù)據(jù)塊進(jìn)行處理。本來(lái)應(yīng)該是從第2個(gè)字節(jié)開(kāi)始取數(shù)據(jù)塊的，但由于數(shù)據(jù)塊"123"中3個(gè)字節(jié)完全匹配成功，所以可以直接跳過(guò)整個(gè)數(shù)據(jù)塊"123"，即從第4個(gè)字節(jié)開(kāi)始取數(shù)據(jù)塊，所以α主機(jī)取得的第2個(gè)數(shù)據(jù)塊內(nèi)容為"xxa"。同樣，需要計(jì)算它的rolling checksum和hash值，并搜索匹配hash表中的hash條目，發(fā)現(xiàn)沒(méi)有任何一條hash值可以匹配上，于是立即確定該數(shù)據(jù)塊是非匹配數(shù)據(jù)塊。

此時(shí)α主機(jī)將繼續(xù)向前取A文件中的第三個(gè)數(shù)據(jù)塊進(jìn)行處理。由于第二個(gè)數(shù)據(jù)塊沒(méi)有匹配上，所以取第三個(gè)數(shù)據(jù)塊時(shí)只跳過(guò)了一個(gè)字節(jié)的長(zhǎng)度，即從第5個(gè)字節(jié)開(kāi)始取，取得的數(shù)據(jù)塊內(nèi)容為"xab"。經(jīng)過(guò)一番計(jì)算和匹配，發(fā)現(xiàn)這個(gè)數(shù)據(jù)塊和第二個(gè)數(shù)據(jù)塊一樣是無(wú)法匹配的數(shù)據(jù)塊。于是繼續(xù)向前跳過(guò)一個(gè)字節(jié)，即從第6個(gè)字節(jié)開(kāi)始取第四個(gè)數(shù)據(jù)塊，這次取得的數(shù)據(jù)塊內(nèi)容為"abc"，這個(gè)數(shù)據(jù)塊是匹配數(shù)據(jù)塊，所以和第一個(gè)數(shù)據(jù)塊的處理方式是一樣的，唯一不同的是第一個(gè)數(shù)據(jù)塊到第四個(gè)數(shù)據(jù)塊，中間兩個(gè)數(shù)據(jù)塊是非匹配數(shù)據(jù)塊，于是在確定第四個(gè)數(shù)據(jù)塊是匹配數(shù)據(jù)塊后，會(huì)將中間的非匹配內(nèi)容(即123xxabc中間的xx)逐字節(jié)發(fā)送給β主機(jī)。

(前文說(shuō)過(guò)，hash值和rolling checksum是有小概率發(fā)生重復(fù)，出現(xiàn)重復(fù)時(shí)匹配如何進(jìn)行？見(jiàn)本小節(jié)的尾部)

依此方式處理完A中所有數(shù)據(jù)塊，最終有3個(gè)匹配數(shù)據(jù)塊chunk[0]、chunk[1]和chunk[2]，以及2段非匹配數(shù)據(jù)"xx"和" "。這樣β主機(jī)就收到了匹配數(shù)據(jù)塊的匹配信息以及逐字節(jié)的非匹配純數(shù)據(jù)，這些數(shù)據(jù)是β主機(jī)重組文件A副本的關(guān)鍵信息。它的大致內(nèi)容如下：

chunk[0] of size 3 at 0 offset=0data receive 2 at 3chunk[1] of size 3 at 3 offset=5data receive 1 at 8chunk[2] of size 3 at 6 offset=9

為了說(shuō)明這段信息，首先看文件A和文件B的內(nèi)容，并標(biāo)出它們的偏移地址。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

對(duì)于"chunk[0] of size 3 at 0 offset=0"，這一段表示這是一個(gè)匹配數(shù)據(jù)塊，匹配的是文件B中的chunk[0]，數(shù)據(jù)塊大小為3字節(jié)，關(guān)鍵詞at表示這個(gè)匹配塊在文件B中的起始偏移地址為0，關(guān)鍵詞offset表示這個(gè)匹配塊在文件A中起始偏移地址也為0，它也可以認(rèn)為是重組臨時(shí)文件中的偏移。也就是說(shuō)，在β主機(jī)重組文件時(shí)，將從文件B的"at 0"偏移處拷貝長(zhǎng)度為3字節(jié)的chunk[0]對(duì)應(yīng)的數(shù)據(jù)塊，并將這個(gè)數(shù)據(jù)塊內(nèi)容寫(xiě)入到臨時(shí)文件中的offset=0偏移處，這樣臨時(shí)文件中就有了第一段數(shù)據(jù)"123"。

對(duì)于"data receive 2 at 3"，這一段表示這是接收的純數(shù)據(jù)信息，不是匹配數(shù)據(jù)塊。2表示接收的數(shù)據(jù)字節(jié)數(shù)，"at 3"表示在臨時(shí)文件的起始偏移3處寫(xiě)入這兩個(gè)字節(jié)的數(shù)據(jù)。這樣臨時(shí)文件就有了包含了數(shù)據(jù)"123xx"。

對(duì)于"chunk[1] of size 3 at 3 offset=5"，這一段表示是匹配數(shù)據(jù)塊，表示從文件B的起始偏移地址at=3處拷貝長(zhǎng)度為3字節(jié)的chunk[1]對(duì)應(yīng)的數(shù)據(jù)塊，并將此數(shù)據(jù)塊內(nèi)容寫(xiě)入在臨時(shí)文件的起始偏移offset=5處，這樣臨時(shí)文件就有了"123xxabc"。

對(duì)于"data receive 1 at 8"，這一說(shuō)明接收了純數(shù)據(jù)信息，表示將接收到的1個(gè)字節(jié)的數(shù)據(jù)寫(xiě)入到臨時(shí)文件的起始偏移地址8處，所以臨時(shí)文件中就有了"123xxabc "。

最后一段"chunk[2] of size 3 at 6 offset=9"，表示從文件B的起始偏移地址at=6處拷貝長(zhǎng)度為3字節(jié)的chunk[2]對(duì)應(yīng)的數(shù)據(jù)塊，并將此數(shù)據(jù)塊內(nèi)容寫(xiě)入到臨時(shí)文件的起始偏移offset=9處，這樣臨時(shí)文件就包含了"123xxabc def"。到此為止，臨時(shí)文件就重組結(jié)束了，它的內(nèi)容和α主機(jī)上A文件的內(nèi)容是完全一致的，然后只需將此臨時(shí)文件的屬性修改一番，并重命名替換掉文件B即可，這樣就將文件B和文件A進(jìn)行了同步。

整個(gè)過(guò)程如下圖：

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

需要注意的是，α主機(jī)不是搜索完所有數(shù)據(jù)塊之后才將相關(guān)數(shù)據(jù)發(fā)送給β主機(jī)的，而是每搜索出一個(gè)匹配數(shù)據(jù)塊，就會(huì)立即將匹配塊的相關(guān)信息以及當(dāng)前匹配塊和上一個(gè)匹配塊中間的非匹配數(shù)據(jù)發(fā)送給β主機(jī)，并開(kāi)始處理下一個(gè)數(shù)據(jù)塊，當(dāng)β主機(jī)每收到一段數(shù)據(jù)后會(huì)立即將將其重組到臨時(shí)文件中。因此，α主機(jī)和β主機(jī)都盡量做到了不浪費(fèi)任何資源。

1.3.1 hash值和rolling checksum重復(fù)時(shí)的匹配過(guò)程

在上面的示例分析中，沒(méi)有涉及hash值重復(fù)和rolling checksum重復(fù)的情況，但它們有可能會(huì)重復(fù)，雖然重復(fù)后的匹配過(guò)程是一樣的，但可能不那么容易理解。

還是看B文件排序后的校驗(yàn)碼集合。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

當(dāng)文件A處理數(shù)據(jù)塊時(shí)，假設(shè)處理的是第2個(gè)數(shù)據(jù)塊，它是非匹配數(shù)據(jù)塊，對(duì)此數(shù)據(jù)塊會(huì)計(jì)算rolling checksum和hash值。假設(shè)此數(shù)據(jù)塊的hash值從hash表中匹配成功，例如匹配到了上圖中"4939"這個(gè)值，于是會(huì)將此第二個(gè)數(shù)據(jù)塊的rolling checksum與hash值"4939"所指向的chunk[3]的rolling checksum作比較，hash值重復(fù)且rolling checksum重復(fù)的可能性幾乎趨近于0，所以就能確定此數(shù)據(jù)塊是非匹配數(shù)據(jù)塊。

考慮一種極端情況，假如文件B比較大，劃分的數(shù)據(jù)塊數(shù)量也比較多，那么B文件自身包含的數(shù)據(jù)塊的rolling checksum就有可能會(huì)出現(xiàn)重復(fù)事件，且hash值也可能會(huì)出現(xiàn)重復(fù)事件。

例如chunk[0]和chunk[3]的rolling checksum不同，但根據(jù)rolling checksum計(jì)算的hash值卻相同，此時(shí)hash表和校驗(yàn)碼集合的對(duì)應(yīng)關(guān)系大致如下：

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

如果文件A中正好有數(shù)據(jù)塊的hash值能匹配到"c827"，于是準(zhǔn)備比較rolling checksum，此時(shí)將從hash值"c827"指向的chunk[0]向下掃描校驗(yàn)碼集合。當(dāng)掃描過(guò)程中發(fā)現(xiàn)數(shù)據(jù)塊的rolling checksum正好能匹配到某個(gè)rolling checksum，如chunk[0]或chunk[3]對(duì)應(yīng)的rolling checksum，則掃描終止，并進(jìn)入第三層次的搜索匹配。如果向下掃描的過(guò)程中發(fā)現(xiàn)直到chunk[2]都沒(méi)有找到能匹配的rolling checksum，則掃描終止，因?yàn)閏hunk[2]的hash值和數(shù)據(jù)塊的hash值已經(jīng)不同，最終確定該數(shù)據(jù)塊是非匹配數(shù)據(jù)塊，于是α主機(jī)繼續(xù)向前處理下一個(gè)數(shù)據(jù)塊。

seo優(yōu)化培訓(xùn),網(wǎng)絡(luò)推廣培訓(xùn),網(wǎng)絡(luò)營(yíng)銷培訓(xùn),SEM培訓(xùn),網(wǎng)絡(luò)優(yōu)化,在線營(yíng)銷培訓(xùn)

假如文件B中數(shù)據(jù)塊的rolling checksum出現(xiàn)了重復(fù)(這只說(shuō)明一件事，你太幸運(yùn))，將只能通過(guò)強(qiáng)校驗(yàn)碼來(lái)匹配。

1.4 rsync工作流程分析

上面已經(jīng)把rsync增量傳輸?shù)暮诵姆治鲞^(guò)了，下面將分析rsync對(duì)增量傳輸算法的實(shí)現(xiàn)方式以及rsync傳輸?shù)恼麄€(gè)過(guò)程。在這之前，有必要先解釋下rsync傳輸過(guò)程中涉及的client/server、sender、receiver、generator等相關(guān)概念。

1.4.1 幾個(gè)進(jìn)程和術(shù)語(yǔ)f-ck-need-u/p/7048359.html

轉(zhuǎn)載請(qǐng)注明出處：http://www.cnblogs.com/f-ck-need-u/p/7226781.html


http://www.cnblogs.com/f-ck-need-u/p/7226781.html