分类：rsync| 发布时间：2020-02-17 22:58:00
本文翻译自 https://rsync.samba.org/how-rsync-works.html
原来的 Rsync technical report 和 Andrew Tridgell 的 Phd thesis (pdf) 都是用于理解 rsync 算法的数学原理的很优秀的文档。 不幸的是他们更多的介绍是关于 rsync 工具的原理而不是实现（接下来简称为 Rsync）。
在这个文档中，我希望描述：
该文档可作为需要源代码入门的程序员的指南，但主要目的是为读者提供一个基础用于理解：
本文档笼统地描述了Rsync的构造和行为。 在某些情况下，为了达到更广泛的目标，牺牲了有助于特定准确性的细节和例外。
当我们谈论Rsync时，我们使用特定术语来指代各种进程及其在实用程序执行的任务中的角色。
为了进行有效的交流，我们所有人都使用同一种语言是很重要的。 同样重要的是，在给定上下文中使用某些术语时，我们要指的是相同的事物。 在 rsync 邮件列表上，关于角色和进程通常会有些混乱。 基于这些原因，我将定义一些在角色和进程上下文中使用的术语，这些术语将在以后使用。
| 术语 | 上下文 | 含义 |
|---|---|---|
| client | 角色 | client 会初始化同步 |
| server | 角色 | client 通过本地的 transfer 或者网络 socket 连接的远程 rsync 进程或者系统。这时一个通用的术语不应该和 daemon 混淆。一旦建立了 client 和 server 之间的连接，sender 和 receiver 角色将取代它们之间的区别。 |
| daemon | 角色和进程 | 用于等待 client 连接的 Rsync 进程。在某些平台上这被称为服务。 |
| remote shell | 角色和一组进程 | 一个或者多个用于提供 Rsync client 和 远程的 Rsync server 连接的进程 |
| sender | 角色和进程 | 用于访问要同步的源文件的 Rsync 进程 |
| receiver | 角色和进程 | 作为角色，receiver 指的是目标系统。作为进程 receiver 指的是用于接收更新数据并写到磁盘的进程 |
| generator | 进程 | generator 进程用于标识变更的文件和管理文件级别的逻辑 |
当 Rsync client 启动的时候它会首先和 server 进程建立连接。 这个连接可能是通过管道或者网络 socket 建立的。
当 Rsync 通过 remote shell 来和远端的非 daemon server 通讯的时候，启动方法是通过 fork remote shell，这会在远端系统启用 Rsync server。 Rsync client 和 server 都是通过 remote shell 管道来通讯的。 就 rsync 进程而言这是不通过网络的。 在这种模式下，server 进程的 rsync 选项在用于启动 remote shell 的命令行上传递。
当 Rsync 与守护进程通信时，它直接与网络 socket 通信。 这是唯一可以称为网络感知的 Rsync 通信。 在这种模式下，rsync 选项必须通过 socket 发送，如下所述。
在 client 和 server 之间进行通信的最开始，它们各自将它们支持的最大协议版本发送给另一端。 然后，每一端都将最小值用作传输的协议级别。 如果这是守护进程模式连接，则 rsync 选项将从 client 发送到 server。 然后，传输排除列表。 从这一点开始，client-server 关系仅区别于错误和日志消息的传递。
本地 Rsync 作业（当源和目标都在本地安装的文件系统上时）与推送完全一样。 成为 sender 的 client 将派生一个 server 进程来履行 receiver 的角色。 client/sender 和 server/receiver 通过管道来通讯。
文件列表不仅包括 pathnames 而且包括 ownership, mode, permissions, size and modtime。 如果提供了 --checksum 选项那么它还包括文件的 checksums。 当启用完成后发生的第一件事是 sender 会生成文件列表。 在构建文件列表时，每个条目都以网络优化的方式传输到 receiver。
完成此操作后，双方将按照相对于传输基础目录的路径，按字典顺序对文件列表进行排序。 （确切的排序算法会根据传输的协议版本而有所不同。） 一旦发生这种情况，所有对文件的引用将通过文件列表中的索引来完成。
如有必要，sender 将在文件列表后面跟随 id→name 的用户名和组名表，receiver 将使用该表对文件列表中的每个文件进行 id→name→id 的转换。
当 receiver 接收完文件列表后，它会 fork 出 generator 和 receiver 并通过 pipeline 来完成配对。
Rsync 是 pipelined 的重度使用者。 这意味着它是一组（主要）以单向方式通信的进程。 当共享文件列表后，管道的行为如下：
generator → sender → receiver
generator 的输出是 sender 的输入，而 sender 的输出是 receiver 的输入。 每个进程独立运行，并且仅在管道停止运行或等待磁盘 I/O 或 CPU 资源时才延迟。
generator 进程将文件列表与其本地目录树进行比较。 在开始其主要功能之前，如果已指定 --delete，它将首先识别不在 sender 上的本地文件，然后在 receiver 上将其删除。
然后，generator 将开始遍历文件列表。 每个文件都会被检查以查看是否可以跳过。 在最普通的操作模式下，如果修改时间或大小不同，则不会跳过文件。 如果指定了--checksum，则将创建并比较文件级校验和。 目录，设备文件和软连接不会被跳过。 缺少的目录将被创建。
如果不跳过文件，则 receiver 的任何现有版本都将成为传输的“基准文件”，并将其作为数据源，以助于消除匹配数据，而不必由 sender 发送。 为了实现数据的远程匹配，将为基础文件创建块校验和，并在文件的索引号之后立即将其发送给 sender。 如果指定了--whole-file，则为新文件发送一个空的块校验和集。
块大小，以及在更高版本中，块校验和的大小是根据该文件的大小在每个文件的基础上计算的。
sender 进程一次从 generator 中读取文件索引号和关联的块校验和集。
对于生成器发送的每个文件 id，它将存储块校验和，并为它们建立哈希索引以快速查找。
然后读取本地文件，并从本地文件的第一个字节开始为该块生成校验和。 在生成器发送的集合中查找此块校验和，如果未找到匹配项，则将不匹配字节附加到不匹配数据中，并对从下一个字节开始的块进行比较。 这就是所谓的 “滚动校验和”。
如果找到了块校验和匹配，则将其视为匹配块，并且任何累积的不匹配数据将被发送到 receiver，然后是匹配块的接收器文件中的偏移量和长度，并且块校验和 generator 将前进到匹配块之后的下一个字节。
即使对块进行了重新排序或处于不同的偏移量，也可以通过这种方式识别匹配的块。 此过程是 rsync 算法的核心。
这样，sender 将向 receiver 提供有关如何将源文件重构为新目标文件的指令。 这些说明详细说明了可以从基本文件中复制的所有匹配数据（如果该传输存在一个匹配数据），并包括本地不可用的任何原始数据。 在每个文件的处理结束时，将发送整个文件的校验和，sender 将继续处理下一个文件。
生成滚动校验和并在sender 发送的校验和集中搜索匹配项需要大量 CPU 能力。 在所有 rsync 进程中，最占用 CPU 的是 sender。
receiver 将从 sender 的数据中读取由文件索引号标识的每个文件。 它将打开本地文件（称为基础文件）并创建一个临时文件。
receiver 将期望读取不匹配的数据和/或匹配记录以按顺序获得最终文件内容。 当读取不匹配的数据时，它将被写入临时文件。 接收到块匹配记录时，receiver 将在基本文件中查找块偏移并将其复制到临时文件中。 这样，便从头到尾构建了临时文件。
在构建临时文件时，将生成文件的校验和。 在文件末尾，将此校验和与来自 sender 的文件校验和进行比较。 如果文件校验和不匹配，则删除临时文件。 如果文件第一次失败，它将在第二阶段中进行重新处理，如果两次失败，则将报告错误。
临时文件完成后，将设置其所有权和权限以及修改时间。 然后将其重命名以替换基本文件。
将数据从基本文件复制到临时文件使 receiver 成为所有 rsync 进程中磁盘占用最大的进程。 对于小文件来说可能其内容仍在磁盘高速缓存中，因此可以减轻这种情况，但对于大文件， 由于 generator 已经转而处理其他文件，并且 sender 会造成了进一步的延迟，因此高速缓存可能会失效。 由于可能从一个文件中随机读取数据并将其写入另一个文件，因此如果工作集大于磁盘缓存， 则可能会发生所谓的 “搜寻风暴”，从而进一步损害性能。
daemon 进程，和其他很多守护进程类似，对每个连接进行 fork 操作。 启动时，它将解析 rsyncd.conf 文件，以确定存在哪些模块并设置全局选项。 当收到已定义模块的连接时，守护进程将派生一个新的子进程来处理该连接。 然后，该子进程读取 rsyncd.conf 文件以设置所请求模块的选项，这可能会使用 chroot 更改为模块路径，并可能会使用 setuid 和 setgid 修改进程的 uid 和 gid。 此后，它将像其他任何采用 sender 或 receiver 角色的 rsync 服务器进程一样运行。
精心设计的通信协议具有许多特征。
除了这些特征之外，协议还具有不同程度的状态性，数据包间的独立性，人类可读性以及重新建立断开连接的会话的能力。
Rsync 的协议没有这些好的特性。 数据作为不间断的字节流传输。 除了不匹配的文件数据外，没有长度说明符或计数。 相反，每个字节的含义取决于协议级别定义的上下文。
例如，sender 发送文件列表时，它仅发送每个文件列表条目，并以空字符终止列表。 在文件列表条目中，一个位字段指示期望结构的哪些字段以及可变长度字符串的那些字段简单地以 null 终止。 generator 发送文件编号和块校验和的方式相同。
这种通信方法在可靠的连接上可以很好地工作，并且它的数据开销肯定比正式协议要少。 不幸的是，这使得协议极其难以记录，调试或扩展。 协议的每个版本都会有细微的差异，只有通过知道确切的协议版本才能预期到这些差异。
本文档是一项正在进行的工作。 作者预期到它有一些明显的疏漏并且对某些读者而言某些部分获得的困惑可能比启迪更多。 希望本文可以成为有用的参考。
欢迎提出具体的改进建议，这将会是一个完全重写的文章。