rsync算法中的滚动校验和

Question

我正在尝试理解rsync算法如何处理滚动校验和和错位匹配的块。

维基百科页面似乎暗示发送方和接收方都会计算并交换所有可能块的滚动校验和。但这意味着每个字节基本上都要发送一个校验和！我一定漏掉了什么。如何使块对齐？

例如，如果S = 16个字节的块，并且发送方有文件A的以下文本：

 

The quick brown fox jumps over the   lazy dogs

而接收方有文件B的以下文本：

 

The quick brown fox jumped over the   lazy dog

那么rsync交换将如何进行？

- Jason S

Answer 1

接收器只对不重叠的块计算并发送滚动校验和。 相反，发送器会为每个可能的块计算它（但保持局部结果）。然后对于发送器来说，只需要检查接收器发送的一个非重叠块是否与任何（重叠的）本地块匹配即可。

你的示例太简单了，看不出有什么有趣的东西，最后两个块根本不匹配，将被发送进行合并。

使用更有趣的示例（大写字母表示一个块）：

发送器：

A B Cabc D

接收者:

A B C D

接收方将发送A、B、C和D的MD5和滚动哈希。 发送方将计算每个（重叠的）块的滚动哈希，它将匹配A、B、C和D。由于“abc”不匹配，因此它将在信息中发送，并指示如何合并它。

- tonfa

---

哦，我可能误读了有关接收器未发送所有校验和的部分。谢谢。 - Jason S

Answer 2

我正在处理一个远程同步问题，@tonfa 给出了一个很好的答案，但我发现他们的例子有点令人困惑。因此，我提供自己的示例，使用 Lorem Ipsum 文本作为被同步数据的示例。_{我注意到可读性良好的文本文件可以提取其句子/段落结构以进行领域特定的同步优化，但我们不这样做：对于 rsync 和滚动哈希算法而言，每个文件都是一个不透明的二进制块而没有任何结构。}

---

假设有一个文件服务器（Alice），有一个大小为641字节的文件：lipsum.txt。

（假设使用ASCII或UTF-8编码。为了易读性，已在第80列添加换行符，实际文件中不会存在换行符。）

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla nisl enim,
consectetur quis quam consequat, pharetra tempus enim. Fusce iaculis libero
vitae ipsum accumsan efficitur. Fusce iaculis est et justo sollicitudin, sed
porttitor augue sagittis. Mauris aliquam nisl nibh, sed tempus magna venenatis
ac. Curabitur molestie nisl elit, suscipit egestas ex aliquam ac. Donec
dignissim, mauris nec malesuada pellentesque, ipsum sem porttitor est, quis
laoreet urna orci a leo. Cras tincidunt porttitor sapien, quis cursus metus
pulvinar id. Pellentesque nec mollis eros. Fusce sagittis vehicula ligula, nec
ullamcorper sapien sagittis non.

假设远程客户端（Bob）有一个稍微修改过的 lipsum.txt 副本：

Proin finibus ullamcorper ante sit amet egestas. Lorem ipsum dolor sit amet,
consectetur adipiscing elit. Nulla nisl enim, consectetur quis quam consequat,
pharetra tempus enim. Fusce iaculis libero vitae ipsum accumsan efficitur.
Fusce iaculis est et justo sollicitudin, sed porttitor augue sagittis. Mauris
aliquam nisl nibh, sed tempus magna venenatis ac. Nulla ex metus, malesuada
eget ultricies vel, fermentum quis nisl. Etiam ac venenatis tellus. Curabitur
molestie nisl elit, suscipit egestas ex aliquam ac. Donec dignissim, mauris nec
malesuada pellentesque, ipsum sem porttitor est, quis laoreet urna orci a leo.
Cras tincidunt porttitor sapien, quis cursus metus pulvinar id. Pellentesque
nec mollis eros.

Here's a visual diff for reference:

---

使用rsync时，服务器或客户端软件运行在哪台主机上并不重要，重要的是谁是发送方和接收方（因为rsync服务器可以发送和接收，rsync客户端也可以发送和接收）。在此演示中，远程客户端（Bob）正在将其修改后的lipsum.txt副本发送到rsync服务器（Alice）。

第1部分：接收方（Alice）将现有文件的固定块哈希发送给发送方（Bob）：

Alice将lipsum.txt分成相等大小的块（对于此演示，让我们使用32字节大小的块），并使用该块的弱滚动哈希计算这些块的弱哈希（校验和）（请注意，滚动哈希算法尚未跨块边界计算）：

block offset     32-byte block bytes (as ASCII)       block weak-hash (as UInt32)
--------------------------------------------------------------------------
  0    |Lorem ipsum dolor sit amet, cons|    3262843843 
 16    |ectetur adipiscing elit. Nulla n|    1213926365 
 32    |isl enim, consectetur quis quam |    3307146210 
 48    |consequat, pharetra tempus enim.|    1702104107 
 64    |Fusce iaculis libero vitae ipsu |     113380311 
 80    |m accumsan efficitur. Fusce iacu|    3788835775 
 96    |lis est et justo sollicitudin, s|    2668366836 
112    |ed porttitor augue sagittis. Mau|     212601872 
128    |ris aliquam nisl nibh, sed tempu|    3149335490 
144    |s magna venenatis ac. Curabitur |    1050020743 
160    |molestie nisl elit, suscipit ege|     726010903 
176    |stas ex aliquam ac. Donec dignis|     169282427 
192    |sim, mauris nec malesuada pellen|    1806109673 
208    |tesque, ipsum sem porttitor est,|    1415646245 
224    | quis laoreet urna orci a leo. C|    1034619651 
240    |ras tincidunt porttitor sapien, |    4085386299 
256    |quis cursus metus pulvinar id. P|    4195748849 
272    |ellentesque nec mollis eros. Fus|    3458665474 
288    |ce sagittis vehicula ligula, nec|    3870297057 
304    | ullamcorper sapien sagittis non|    2035682393 
320    |.|                                      3014702

Alice随后将这些块偏移量和弱哈希发送给Bob。

在这个例子中，块大小为32字节，32位大小的哈希意味着Alice向Bob发送84字节来表示一个641字节大小的文件 - 或者大约是Bob想要发送的文件大小的13％。（请注意，rsync使用以“数百字节”为大小的块大小，因此在现实生活中比例更小，使其非常适用于慢速连接速度）。

第二部分：发送方（Bob）计算其文件的滚动哈希：

首先，Bob接收来自Alice的哈希值，并将其加载到哈希表中进行O(1)查找（是的，这意味着有“哈希的哈希”）。

然后，真正的魔法发生了：Bob计算了通过他们的文件的32字节大小的窗口的滚动哈希。Bob的文件长度为714字节，这意味着将计算682个哈希值。rsync的弱哈希算法专门设计为基于滚动基础工作（这样您可以推送和弹出单个字节值），而不是在每个字节上重新迭代窗口（即rsync使用O(n)时间而不是O(n * m)时间，其中n是文件的大小，m是窗口大小）。

这就是Bob生成的内容（为简洁起见，仅显示前100个块）：

Offset| 32-byte block bytes (as ASCII) | Weak-hash
-------------------------------------------------
    0 |Proin finibus ullamcorper ante s| 3787000889 
    1 |roin finibus ullamcorper ante si| 2983660626 
    2 |oin finibus ullamcorper ante sit| 1966279764 
    3 |in finibus ullamcorper ante sit |  663751685 
    4 |n finibus ullamcorper ante sit a| 3578072061 
    5 | finibus ullamcorper ante sit am|  757926908 
    6 |finibus ullamcorper ante sit ame| 1417546817 
    7 |inibus ullamcorper ante sit amet|  382274639 
    8 |nibus ullamcorper ante sit amet | 2866482182 
    9 |ibus ullamcorper ante sit amet e| 2888829949 
   10 |bus ullamcorper ante sit amet eg| 1780157435 
   11 |us ullamcorper ante sit amet ege|  763694078 
   12 |s ullamcorper ante sit amet eges| 1458113532 
   13 | ullamcorper ante sit amet egest| 2940865533 
   14 |ullamcorper ante sit amet egesta|  206310462 
   15 |llamcorper ante sit amet egestas|  539757628 
   16 |lamcorper ante sit amet egestas.| 1384516606 
   17 |amcorper ante sit amet egestas. | 1941179314 
   18 |mcorper ante sit amet egestas. L| 4284812189 
   19 |corper ante sit amet egestas. Lo| 3270773663 
   20 |orper ante sit amet egestas. Lor| 4045278126 
   21 |rper ante sit amet egestas. Lore| 2546076580 
   22 |per ante sit amet egestas. Lorem| 4200926111 
   23 |er ante sit amet egestas. Lorem | 4163898191 
   24 |r ante sit amet egestas. Lorem i| 2578123603 
   25 | ante sit amet egestas. Lorem ip| 2996308817 
   26 |ante sit amet egestas. Lorem ips| 4092857252 
   27 |nte sit amet egestas. Lorem ipsu| 1856506808 
   28 |te sit amet egestas. Lorem ipsum| 2946436023 
   29 |e sit amet egestas. Lorem ipsum | 1533676387 
   30 | sit amet egestas. Lorem ipsum d|  483134306 
   31 |sit amet egestas. Lorem ipsum do|  476908465 
   32 |it amet egestas. Lorem ipsum dol|  320277418 
   33 |t amet egestas. Lorem ipsum dolo| 3243707312 
   34 | amet egestas. Lorem ipsum dolor| 1496386478 
   35 |amet egestas. Lorem ipsum dolor | 3433761710 
   36 |met egestas. Lorem ipsum dolor s| 1480264640 
   37 |et egestas. Lorem ipsum dolor si| 1083640764 
   38 |t egestas. Lorem ipsum dolor sit|  232393675 
   39 | egestas. Lorem ipsum dolor sit | 3691055991 
   40 |egestas. Lorem ipsum dolor sit a| 4223208376 
   41 |gestas. Lorem ipsum dolor sit am| 1521290176 
   42 |estas. Lorem ipsum dolor sit ame| 4025158590 
   43 |stas. Lorem ipsum dolor sit amet| 1003228109 
   44 |tas. Lorem ipsum dolor sit amet,| 1503267718 
   45 |as. Lorem ipsum dolor sit amet, | 3582200626 
   46 |s. Lorem ipsum dolor sit amet, c| 3172993844 
   47 |. Lorem ipsum dolor sit amet, co| 3615230768 
   48 | Lorem ipsum dolor sit amet, con| 3300133744 
   49 |Lorem ipsum dolor sit amet, cons| 3262843843 
   50 |orem ipsum dolor sit amet, conse| 4056353756 
   51 |rem ipsum dolor sit amet, consec| 2500266960 
   52 |em ipsum dolor sit amet, consect| 2453212114 
   53 |m ipsum dolor sit amet, consecte| 3549891538 
   54 | ipsum dolor sit amet, consectet| 3963358169 
   55 |ipsum dolor sit amet, consectetu|  379456558 
   56 |psum dolor sit amet, consectetur| 3206351927 
   57 |sum dolor sit amet, consectetur | 2648968167 
   58 |um dolor sit amet, consectetur a| 3918072789 
   59 |m dolor sit amet, consectetur ad| 3511225284 
   60 | dolor sit amet, consectetur adi| 2267089856 
   61 |dolor sit amet, consectetur adip| 2145979408 
   62 |olor sit amet, consectetur adipi| 2017070101 
   63 |lor sit amet, consectetur adipis| 1143409689 
   64 |or sit amet, consectetur adipisc| 3407809552 
   65 |r sit amet, consectetur adipisci| 3452242954 
   66 | sit amet, consectetur adipiscin| 1381174278 
   67 |sit amet, consectetur adipiscing| 3012037709 
   68 |it amet, consectetur adipiscing |  863898618 
   69 |t amet, consectetur adipiscing e| 1819020278 
   70 | amet, consectetur adipiscing el| 1786383342 
   71 |amet, consectetur adipiscing eli| 3535604791 
   72 |met, consectetur adipiscing elit| 2849705034 
   73 |et, consectetur adipiscing elit.| 3906866187 
   74 |t, consectetur adipiscing elit. | 3028814790 
   75 |, consectetur adipiscing elit. N| 1042025376 
   76 | consectetur adipiscing elit. Nu| 3860663273 
   77 |consectetur adipiscing elit. Nul| 2577534005 
   78 |onsectetur adipiscing elit. Null| 3386641470 
   79 |nsectetur adipiscing elit. Nulla| 1332743216 
   80 |sectetur adipiscing elit. Nulla | 2328497122 
   81 |ectetur adipiscing elit. Nulla n| 1213926365 
   82 |ctetur adipiscing elit. Nulla ni| 2679376865 
   83 |tetur adipiscing elit. Nulla nis| 1645546481 
   84 |etur adipiscing elit. Nulla nisl| 1719798761 
   84 |etur adipiscing elit. Nulla nisl| 1719798761 
   85 |tur adipiscing elit. Nulla nisl | 3454143396 
   86 |ur adipiscing elit. Nulla nisl e| 3142519701 
   87 |r adipiscing elit. Nulla nisl en| 3224963982 
   88 | adipiscing elit. Nulla nisl eni|  579210117 
   89 |adipiscing elit. Nulla nisl enim|  907021266 
   90 |dipiscing elit. Nulla nisl enim,| 1625361309 
   91 |ipiscing elit. Nulla nisl enim, |  804916057 
   92 |piscing elit. Nulla nisl enim, c| 3002403667 
   93 |iscing elit. Nulla nisl enim, co| 1436224338 
   94 |scing elit. Nulla nisl enim, con| 1020398423 
   95 |cing elit. Nulla nisl enim, cons| 2978286423 
   96 |ing elit. Nulla nisl enim, conse|   62524249 
   97 |ng elit. Nulla nisl enim, consec| 2620984147 
   98 |g elit. Nulla nisl enim, consect| 1986661209 
   99 | elit. Nulla nisl enim, consecte|  460917591 

您可能会注意到Bob的块49有些特别：它与Alice的块0完全匹配（两者都具有“Lorem ipsum dolor sit amet, cons”的ASCII字节，但它们还共享哈希值3262843843！）。

然后Bob继续逐字节地记录哪些块也与Alice的副本匹配（这对于每个块在O(1)时间内是可能的，或者总计为O(n)），因为Bob将Alice的块哈希加载到了散列表中。

还存在一种优化：如果Bob看到他的块匹配之一，他可以跳到下一个整块并查看是否匹配，从而跳过介于的块（因此我们知道偏移量49处的32字节块匹配，因此我们可以跳到块81-块81也匹配（哈希值为1213926365），等等...）。

对于Bob中的所有窗口都这样做，最终您将获得以下输出：

Offset   Bytes (as ASCII text)
----------------------------------------------
   49  |Lorem ipsum dolor sit amet, cons| 
   81  |ectetur adipiscing elit. Nulla n| 
  113  |isl enim, consectetur quis quam | 
  145  |consequat, pharetra tempus enim.| 
  177  | Fusce iaculis libero vitae ipsu| 
  209  |m accumsan efficitur. Fusce iacu| 
  241  |lis est et justo sollicitudin, s| 
  273  |ed porttitor augue sagittis. Mau| 
  305  |ris aliquam nisl nibh, sed tempu| 
  463  |molestie nisl elit, suscipit ege| 
  495  |stas ex aliquam ac. Donec dignis| 
  527  |sim, mauris nec malesuada pellen| 
  559  |tesque, ipsum sem porttitor est,| 
  591  | quis laoreet urna orci a leo. C| 
  623  |ras tincidunt porttitor sapien, | 
  655  |quis cursus metus pulvinar id. P| 

那么这就是16个块（或窗口），每个块32字节，总共512字节，Bob知道他不需要发送给Alice。然后Bob只需要发送上述块未覆盖的非重叠窗口：

Offset   Bytes (as ASCII text)
----------------------------------------------
    0  |Proin finibus ullamcorper ante s| 
   33  |t amet egestas. Lorem ipsum dolo|
  330  |d tempus magna venenatis ac. Nul|
  363  |a ex metus, malesuada eget ultri|
  396  |ies vel, fermentum quis nisl. Et|
  429  |am ac venenatis tellus. Curabitu|

不错，嗯？

- Dai

---

清晰的解释 - smilingpoplar

非常非常令人印象深刻的例子！ - chmin.seo

这个程序相关的内容翻译成中文：33 |t amet egestas. Lorem ipsum dolo|是正确的，而不是32 |it amet egestas. Lorem ipsum dol|。 - chmin.seo

@chmin.seo 你有什么问题？ - Dai