本文通过示例详细分析rsync算法原理和rsync的工作流程，是对rsync官方技术报告和官方推荐文章的解释。本文不会介绍如何使用rsync命令(见rsync基本用法)，而是详细解释它如何实现高效的增量传输。
以下是rsync系列篇：
2.rsync(二)：inotify+rsync详细说明和sersync
本文目录：
在开始分析算法原理之前，简单说明下rsync的增量传输功能。
假设待传输文件为A，如果目标路径下没有文件A，则rsync会直接传输文件A，如果目标路径下已存在文件A，则发送端视情况决定是否要传输文件A。rsync默认使用"quick check"算法，它会比较源文件和目标文件(如果存在)的文件大小和修改时间mtime，如果两端文件的大小或mtime不同，则发送端会传输该文件，否则将忽略该文件。
如果"quick check"算法决定了要传输文件A，它不会传输整个文件A，而是只传源文件A和目标文件A所不同的部分，这才是真正的增量传输。
也就是说，rsync的增量传输体现在两个方面：文件级的增量传输和数据块级别的增量传输。文件级别的增量传输是指源主机上有，但目标主机上没有将直接传输该文件，数据块级别的增量传输是指只传输两文件所不同的那一部分数据。但从本质上来说，文件级别的增量传输是数据块级别增量传输的特殊情况。通读本文后，很容易理解这一点。
1.1 需要解决的问题
假设主机α上有文件A，主机β上有文件B(实际上这两文件是同名文件，此处为了区分所以命名为A和B)，现在要让B文件和A文件保持同步。
最简单的方法是将A文件直接拷贝到β主机上。但如果文件A很大，且B和A是相似的(意味着两文件实际内容只有少部分不同)，拷贝整个文件A可能会消耗不少时间。如果可以拷贝A和B不同的那一小部分，则传输过程会很快。rsync增量传输算法就充分利用了文件的相似性，解决了远程增量拷贝的问题。
假设文件A的内容为"123xxabc def"，文件B的内容为"123abcdefg"。A与B相比，相同的数据部分有123/abc/def，A中多出的内容为xx和一个空格，但文件B比文件A多出了数据g。最终的目标是让B和A的内容完全相同。
如果采用rsync增量传输算法，α主机将只传输文件A中的xx和空格数据给β主机，对于那些相同内容123/abc/def，β主机会直接从B文件中拷贝。根据这两个来源的数据，β主机就能组建成一个文件A的副本，最后将此副本文件重命名并覆盖掉B文件就保证了同步。
虽然看上去过程很简单，但其中有很多细节需要去深究。例如，α主机如何知道A文件中哪些部分和B文件不同，β主机接收了α主机发送的A、B不同部分的数据，如何组建文件A的副本。
1.2 rsync增量传输算法原理
假设执行的rsync命令是将A文件推到β主机上使得B文件和A文件保持同步，即主机α是源主机，是数据的发送端(sender)，β是目标主机，是数据的接收端(receiver)。在保证B文件和A文件同步时，大致有以下6个过程：
(1).α主机告诉β主机文件A待传输。
(2).β主机收到信息后，将文件B划分为一系列大小固定的数据块(建议大小在500-1000字节之间)，并以chunk号码对数据块进行编号，同时还会记录数据块的起始偏移地址以及数据块长度。显然最后一个数据块的大小可能更小。
对于文件B的内容"123abcdefg"来说，假设划分的数据块大小为3字节，则根据字符数划分成了以下几个数据块：
count=4 n=3 rem=1 这表示划分了4个数据块，数据块大小为3字节，剩余1字节给了最后一个数据块 chunk[0]：offset=0 len=3 该数据块对应的内容为123 chunk[1]：offset=3 len=3 该数据块对应的内容为abc chunk[2]：offset=6 len=3 该数据块对应的内容为def chunk[3]：offset=9 len=1 该数据块对应的内容为g
当然，实际信息中肯定是不会包括文件内容的。
(3).β主机对文件B的每个数据块根据其内容都计算两个校验码：32位的弱滚动校验码(rolling checksum)和128位的MD4强校验码(现在版本的rsync使用的已经是128位的MD5强校验码)。并将文件B计算出的所有rolling checksum和强校验码跟随在对应数据块chunk[N]后形成校验码集合，然后发送给主机α。
也就是说，校验码集合的内容大致如下：其中sum1为rolling checksum，sum2为强校验码。
chunk[0] sum1=3ef2c827 sum2=3efa923f8f2e7 chunk[1] sum1=57ac2aaf sum2=aef2dedba2314 chunk[2] sum1=92d7edb4 sum2=a6sd6a9d67a12 chunk[3] sum1=afe74939 sum2=90a12dfe7485c
需要注意，不同内容的数据块计算出的rolling checksum是有可能相同的，但是概率非常小。
(4).当α主机接收到文件B的校验码集合后，α主机将对此校验码集合中的每个rolling checksum计算16位长度的hash值，并将每216个hash值按照hash顺序放入一个hash table中，hash表中的每一个hash条目都指向校验码集合中它所对应的rolling checksum的chunk号码，然后对校验码集合根据hash值进行排序，这样排序后的校验码集合中的顺序就能和hash表中的顺序对应起来。
所以，hash表和排序后的校验码集合对应关系大致如下：假设hash表中的hash值是根据首个字符按照[0-9a-f]的顺序进行排序的。
同样需要注意，不同rolling checksum计算出的hash值也是有可能会相同的，概率也比较小，但比rolling checksum出现重复的概率要大一些。
(5).随后主机α将对文件A进行处理。处理的过程是从第1个字节开始取相同大小的数据块，并计算它的校验码和校验码集合中的校验码进行匹配。如果能匹配上校验码集合中的某个数据块条目，则表示该数据块和文件B中数据块相同，它不需要传输，于是主机α直接跳转到该数据块的结尾偏移地址，从此偏移处继续取数据块进行匹配。如果不能匹配校验码集合中的数据块条目，则表示该数据块是非匹配数据块，它需要传输给主机β，于是主机α将跳转到下一个字节，从此字节处继续取数据块进行匹配。注意，匹配成功时跳过的是整个匹配数据块，匹配不成功时跳过的仅是一个字节。可以结合下一小节的示例来理解。
上面说的数据块匹配只是一种描述，具体的匹配行为需要进行细化。rsync算法将数据块匹配过程分为3个层次的搜索匹配过程。
首先，主机α会对取得的数据块根据它的内容计算出它的rolling checksum，再根据此rolling checksum计算出hash值。
然后，将此hash值去和hash表中的hash条目进行匹配，这是第一层次的搜索匹配过程，它比较的是hash值。如果在hash表中能找到匹配项，则表示该数据块存在潜在相同的可能性，于是进入第二层次的搜索匹配。
第二层次的搜索匹配是比较rolling checksum。由于第一层次的hash值匹配到了结果，所以将搜索校验码集合中与此hash值对应的rolling checksum。由于校验码集合是按照hash值排序过的，所以它的顺序和hash表中的顺序一致，也就是说只需从此hash值对应的rolling chcksum开始向下扫描即可。扫描过程中，如果A文件数据块的rolling checksum能匹配某项，则表示该数据块存在潜在相同的可能性，于是停止扫描，并进入第三层次的搜索匹配以作最终的确定。或者如果没有扫描到匹配项，则说明该数据块是非匹配块，也将停止扫描，这说明rolling checksum不同，但根据它计算的hash值却发生了小概率重复事件。
第三层次的搜索匹配是比较强校验码。此时将对A文件的数据块新计算一个强校验码(在第三层次之前，只对A文件的数据块计算了rolling checksum和它的hash值)，并将此强校验码与校验码集合中对应强校验码匹配，如果能匹配则说明数据块是完全相同的，不能匹配则说明数据块是不同的，然后开始取下一个数据块进行处理。
之所以要额外计算hash值并放入hash表，是因为比较rolling checksum的性能不及hash值比较，且通过hash搜索的算法性能非常高。由于hash值重复的概率足够小，所以对绝大多数内容不同的数据块都能直接通过第一层次搜索的hash值比较出来，即使发生了小概率hash值重复事件，还能迅速定位并比较更小概率重复的rolling checksum。即使不同内容计算的rolling checksum也可能出现重复，但它的重复概率比hash值重复概率更小，所以通过这两个层次的搜索就能比较出几乎所有不同的数据块。假设不同内容的数据块的rolling checksum还是出现了小概率重复，它将进行第三层次的强校验码比较，它采用的是MD4(现在是MD5)，这种算法具有"雪崩效应"，只要一点点不同，结果都是天翻地覆的不同，所以在现实使用过程中，完全可以假设它能做最终的比较。
数据块大小会影响rsync算法的性能。如果数据块大小太小，则数据块的数量就太多，需要计算和匹配的数据块校验码就太多，性能就差，而且出现hash值重复、rolling checksum重复的可能性也增大；如果数据块大小太大，则可能会出现很多数据块都无法匹配的情况，导致这些数据块都被传输，降低了增量传输的优势。所以划分合适的数据块大小是非常重要的，默认情况下，rsync会根据文件大小自动判断数据块大小，但rsync命令的"-B"(或"--block-size")选项支持手动指定大小，如果手动指定，官方建议大小在500-1000字节之间。
(6).当α主机发现是匹配数据块时，将只发送这个匹配块的附加信息给β主机。同时，如果两个匹配数据块之间有非匹配数据，则还会发送这些非匹配数据。当β主机陆陆续续收到这些数据后，会创建一个临时文件，并通过这些数据重组这个临时文件，使其内容和A文件相同。临时文件重组完成后，修改该临时文件的属性信息(如权限、所有者、mtime等)，然后重命名该临时文件替换掉B文件，这样B文件就和A文件保持了同步。
1.3 通过示例分析rsync算法
前面说了这么多理论，可能已经看的云里雾里，下面通过A和B文件的示例来详细分析上一小节中的增量传输算法原理，由于上一小节中的过程(1)-(4)，已经给出了示例，所以下面将继续分析过程(5)和过程(6)。
先看文件B(内容为"123abcdefg")排序后的校验码集合以及hash表。
当主机α开始处理文件A时，对于文件A的内容"123xxabc def"来说，从第一个字节开始取大小相同的数据块，所以取得的第一个数据块的内容是"123"，由于和文件B的chunk[0]内容完全相同，所以α主机对此数据块计算出的rolling checksum值肯定是"3ef2e827"，对应的hash值为"e827"。于是α主机将此hash值去匹配hash表，匹配过程中发现指向chunk[0]的hash值能匹配上，于是进入第二层次的rolling checksum比较，也即从此hash值指向的chunk[0]的条目处开始向下扫描。扫描过程中发现扫描的第一条信息(即chunk[0]对应的条目)的rollign checksum就能匹配上，所以扫描终止，于是进入第三层次的搜索匹配，这时α主机将对"123"这个数据块新计算一个强校验码，与校验码集合中chunk[0]对应的强校验码做比较，最终发现能匹配上，于是确定了文件A中的"123"数据块是匹配数据块，不需要传输给β主机。
虽然匹配数据块不用传输，但匹配的相关信息需要立即传输给β主机，否则β主机不知道如何重组文件A的副本。匹配块需要传输的信息包括：匹配的是B文件中的chunk[0]数据块，在文件A中偏移该数据块的起始偏移地址为第1个字节，长度为3字节。
数据块"123"的匹配信息传输完成后，α主机将处取第二个数据块进行处理。本来应该是从第2个字节开始取数据块的，但由于数据块"123"中3个字节完全匹配成功，所以可以直接跳过整个数据块"123"，即从第4个字节开始取数据块，所以α主机取得的第2个数据块内容为"xxa"。同样，需要计算它的rolling checksum和hash值，并搜索匹配hash表中的hash条目，发现没有任何一条hash值可以匹配上，于是立即确定该数据块是非匹配数据块。
此时α主机将继续向前取A文件中的第三个数据块进行处理。由于第二个数据块没有匹配上，所以取第三个数据块时只跳过了一个字节的长度，即从第5个字节开始取，取得的数据块内容为"xab"。经过一番计算和匹配，发现这个数据块和第二个数据块一样是无法匹配的数据块。于是继续向前跳过一个字节，即从第6个字节开始取第四个数据块，这次取得的数据块内容为"abc"，这个数据块是匹配数据块，所以和第一个数据块的处理方式是一样的，唯一不同的是第一个数据块到第四个数据块，中间两个数据块是非匹配数据块，于是在确定第四个数据块是匹配数据块后，会将中间的非匹配内容(即123xxabc中间的xx)逐字节发送给β主机。
(前文说过，hash值和rolling checksum是有小概率发生重复，出现重复时匹配如何进行？见本小节的尾部)
依此方式处理完A中所有数据块，最终有3个匹配数据块chunk[0]、chunk[1]和chunk[2]，以及2段非匹配数据"xx"和" "。这样β主机就收到了匹配数据块的匹配信息以及逐字节的非匹配纯数据，这些数据是β主机重组文件A副本的关键信息。它的大致内容如下：
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
为了说明这段信息，首先看文件A和文件B的内容，并标出它们的偏移地址。
对于"chunk[0] of size 3 at 0 offset=0"，这一段表示这是一个匹配数据块，匹配的是文件B中的chunk[0]，数据块大小为3字节，关键词at表示这个匹配块在文件B中的起始偏移地址为0，关键词offset表示这个匹配块在文件A中起始偏移地址也为0，它也可以认为是重组临时文件中的偏移。也就是说，在β主机重组文件时，将从文件B的"at 0"偏移处拷贝长度为3字节的chunk[0]对应的数据块，并将这个数据块内容写入到临时文件中的offset=0偏移处，这样临时文件中就有了第一段数据"123"。
对于"data receive 2 at 3"，这一段表示这是接收的纯数据信息，不是匹配数据块。2表示接收的数据字节数，"at 3"表示在临时文件的起始偏移3处写入这两个字节的数据。这样临时文件就有了包含了数据"123xx"。
对于"chunk[1] of size 3 at 3 offset=5"，这一段表示是匹配数据块，表示从文件B的起始偏移地址at=3处拷贝长度为3字节的chunk[1]对应的数据块，并将此数据块内容写入在临时文件的起始偏移offset=5处，这样临时文件就有了"123xxabc"。
对于"data receive 1 at 8"，这一说明接收了纯数据信息，表示将接收到的1个字节的数据写入到临时文件的起始偏移地址8处，所以临时文件中就有了"123xxabc "。
最后一段"chunk[2] of size 3 at 6 offset=9"，表示从文件B的起始偏移地址at=6处拷贝长度为3字节的chunk[2]对应的数据块，并将此数据块内容写入到临时文件的起始偏移offset=9处，这样临时文件就包含了"123xxabc def"。到此为止，临时文件就重组结束了，它的内容和α主机上A文件的内容是完全一致的，然后只需将此临时文件的属性修改一番，并重命名替换掉文件B即可，这样就将文件B和文件A进行了同步。
整个过程如下图：
需要注意的是，α主机不是搜索完所有数据块之后才将相关数据发送给β主机的，而是每搜索出一个匹配数据块，就会立即将匹配块的相关信息以及当前匹配块和上一个匹配块中间的非匹配数据发送给β主机，并开始处理下一个数据块，当β主机每收到一段数据后会立即将将其重组到临时文件中。因此，α主机和β主机都尽量做到了不浪费任何资源。
1.3.1 hash值和rolling checksum重复时的匹配过程
在上面的示例分析中，没有涉及hash值重复和rolling checksum重复的情况，但它们有可能会重复，虽然重复后的匹配过程是一样的，但可能不那么容易理解。
还是看B文件排序后的校验码集合。
当文件A处理数据块时，假设处理的是第2个数据块，它是非匹配数据块，对此数据块会计算rolling checksum和hash值。假设此数据块的hash值从hash表中匹配成功，例如匹配到了上图中"4939"这个值，于是会将此第二个数据块的rolling checksum与hash值"4939"所指向的chunk[3]的rolling checksum作比较，hash值重复且rolling checksum重复的可能性几乎趋近于0，所以就能确定此数据块是非匹配数据块。
考虑一种极端情况，假如文件B比较大，划分的数据块数量也比较多，那么B文件自身包含的数据块的rolling checksum就有可能会出现重复事件，且hash值也可能会出现重复事件。
例如chunk[0]和chunk[3]的rolling checksum不同，但根据rolling checksum计算的hash值却相同，此时hash表和校验码集合的对应关系大致如下：
如果文件A中正好有数据块的hash值能匹配到"c827"，于是准备比较rolling checksum，此时将从hash值"c827"指向的chunk[0]向下扫描校验码集合。当扫描过程中发现数据块的rolling checksum正好能匹配到某个rolling checksum，如chunk[0]或chunk[3]对应的rolling checksum，则扫描终止，并进入第三层次的搜索匹配。如果向下扫描的过程中发现直到chunk[2]都没有找到能匹配的rolling checksum，则扫描终止，因为chunk[2]的hash值和数据块的hash值已经不同，最终确定该数据块是非匹配数据块，于是α主机继续向前处理下一个数据块。
假如文件B中数据块的rolling checksum出现了重复(这只说明一件事，你太幸运)，将只能通过强校验码来匹配。
1.4 rsync工作流程分析
上面已经把rsync增量传输的核心分析过了，下面将分析rsync对增量传输算法的实现方式以及rsync传输的整个过程。在这之前，有必要先解释下rsync传输过程中涉及的client/server、sender、receiver、generator等相关概念。
1.4.1 几个进程和术语f-ck-need-u/p/7048359.html
转载请注明出处：http://www.cnblogs.com/f-ck-need-u/p/7226781.html
http://www.cnblogs.com/f-ck-need-u/p/7226781.html
延伸阅读
- 知识和经验的重要性 2023-04-15 16:58:17.917
- 严谨和负责 2023-04-15 13:58:12.007
- 快乐工作，快乐生活 2022-09-07 11:26:41.417
- 我的第一份工作 2022-07-13 15:18:25.697
- 码上工作 2022-06-26 09:59:53.367
- 我的第一份工作 2022-02-07 14:05:08.76
- 码上工作招聘网站 2021-06-16 14:02:11.163
- 可贵的劳动成果和坚实的同学情谊 2021-06-01 15:33:12.823
- 学习——工作——再学习 2021-06-01 15:31:45.667
- 远离10种职场负能量 2020-06-19 09:41:34.14
知识和经验的重要性