我试图了解rsync 算法在滚动校验和和以交错方式匹配的块方面是如何工作的。
维基百科页面似乎建议发送者和接收者都计算和交换所有可能块的滚动校验和。但这意味着基本上每个字节发送一个校验和！我肯定错过了什么。对齐块是如何工作的？
例如，如果 S = 16 字节块，并且发送方拥有文件 A 的以下文本：
敏捷的棕色狐狸跳过懒惰的狗
并且接收者有文件B的这个文本：
敏捷的棕色狐狸跳过了懒惰的狗
rsync 交换如何工作？
问问题
5634 次
2 回答
18
接收器仅为非重叠块计算和发送滚动校验和。相反，发送者为每个可能的块计算它（但将结果保持在本地）。然后对于发送者，只需检查一个非重叠块（由接收者发送）是否与任何（重叠）本地块匹配。
您的示例太简单了，看不到任何有趣的东西，最后两个块根本不匹配，将被发送以进行合并。
有一个更有趣的例子（大写是一个块）：
发件人：
A B Cabc D
接收者：
A B C D
接收方将发送 A、B、C 和 D 的 MD5 和滚动哈希。发送方将为每个（重叠）块计算滚动哈希，它将匹配 A、B、C 和abcD。 t 匹配它会将它与合并它的信息一起发送。
于 2009-10-08T09:01:33.427 回答
6
（我自己现在正在处理一个远程同步问题，@tonfa 给出了一个很好的答案，但我发现他们的示例有点令人困惑。所以我提供了我自己的示例，使用 Lorem Ipsum 文本作为数据同步的示例.我注意到人类可读的文本文件可以为特定领域的同步优化提取它们的句子/段落结构，我们没有这样做：就rsync滚动哈希算法而言，每个文件都是不透明的二进制文件blob 没有任何结构）
假设一个文件服务器 ( 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.
这是一个diff供参考的视觉效果：
使用 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的块大小，因此该比例在现实生活中甚至更小，这对于慢速连接非常实用）。
第 2 部分：发件人 (Bob)通过他们的文件计算移动窗口的滚动哈希：
首先，Bob 从 Alice 接收哈希并将它们加载到哈希表中进行O(1)查找（是的，这意味着存在“哈希哈希”）。
然后真正的魔法发生了：Bob 通过他们的文件计算 32 字节大小的窗口的滚动散列。Bob 的文件长 714 字节，这意味着将计算 682 个哈希值。rsync的弱哈希算法专门设计用于滚动工作（这样您可以推送和弹出单个字节值），而不是在每个字节上重复窗口（即 rsyncO(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 看到他的一个块匹配，他可以跳转到下一个完整块并查看它是否匹配，如果匹配则跳过中间块（所以我们知道 32 字节块偏移量 49 匹配，所以我们可以跳到块 81 - 块 81 也匹配（使用 hash 1213926365，所以跳转到块 113，等等......）。
继续对 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|
还不错吧？
于 2021-02-19T19:53:46.620 回答