本篇為rsync官方推薦文章How Rsync Works的翻譯，主要內容是Rsync術語說明和簡單版的rsync工作原理。本篇沒有通篇都進行翻譯，前言直接跳過了，但為了文章的完整性，前言部分的原文還是保留了。

How Rsync Works
A Practical Overview

Foreword

The original Rsync technical report and Andrew Tridgell's Phd thesis (pdf) Are both excellent documents for understanding the theoretical mathematics and some of the mechanics of the rsync algorithm. Unfortunately they are more about the theory than the implementation of the rsync utility (hereafter referred to as Rsync).

In this document I hope to describe...

• A non-mathematical overview of the rsync algorithm.
• How that algorithm is implemented in the rsync utility.
• The protocol, in general terms, used by the rsync utility.
• The identifiable roles the rsync processes play.

This document be able to serve as a guide for programmers needing something of an entré into the source code but the primary purpose is to give the reader a foundation from which he may understand

• Why rsync behaves as it does.
• The limitations of rsync.
• Why a requested feature is unsuited to the code-base.

This document describes in general terms the construction and behaviour of Rsync. In some cases details and exceptions that would contribute to specific accuracy have been sacrificed for the sake meeting the broader goals.

Processes and Roles

當我們討論rsync時，我們使用了一些特殊的術語來代表不同的進程以及它們在任務執行過程中所扮演的角色。人類為了更方便、更準確地交流，使用同一種語言是非常重要的；同樣地，在特定的上下文環境中，使用固定的術語來描述相同的事情也是非常重要的。在Rsync郵件列表中，經常會有一些人對role和processes產生疑惑。出於這些原因，我將定義一些在未來會使用的關於role和process的術語。

Process Startup

當Rsync client啟動時，將首先和server端建立一個連接，這個連接的兩端可以通過管道，也可以通過網路套接字進行通信。

當Rsync和遠程非daemon模式的server通過遠程shell通信時，進程的啟動方法是fork遠程shell，它會通過此方法在遠程系統上啟動一個Rsync server端進程。Rsync客戶端和服務端都通過遠程shell間的管道進行通信。此過程中，rsync進程未涉及到網路。在這種模式下，服務端的rsync進程的選項是由遠程shell傳遞的。

當rsync與rsync daemon通信時，它直接使用網路套接字進行通信。這是唯一一種可以稱為網路感知的rsync通信方式。這種模式下，rsync的選項必須通過套接字發送，具體內容下文描述。

在客戶端和服務端通信最初，雙方都會發送最大的協議版本號給對方，雙方都會使用較小版本的協議來進行傳輸。如果是daemon模式的連接，rsync的選項將從客戶端發送到服務端，然後再傳輸exclude列表，從這一刻開始，客戶端和服務端的關係僅與錯誤和日誌消息傳遞有關。(譯者註：即從此時開始，將採用sender和receiver這兩個角色來描述rsync連接的兩端)

本地Rsync任務(源和目標都在本地文件系統)的處理方式類似於push。客戶端(譯者註：此時即源文件端)變為sender，並fork一個server進程以履行receiver角色的職責，然後client/sender與server/receiver之間通過管道進行通信。

The File List

file list不僅包含了路徑名，還包含了拷貝模式、所有者、許可權、文件大小、mtime等屬性。如果使用了"--checksum"選項，則還包括文件級的校驗碼。

rsync連接建立完成的第一件事是sender創建它的file list，當file list創建完成後，其內的每一項都會傳遞(共用)到receiver端。

當這件事完成後，兩端都會按照相對於基目錄(base directory)的路徑對file list排序(排序演算法依賴於傳輸的協議版本號)，當排序完成後，以後對所有文件的引用都通過file list中的索引來查找。

當receiver接收到file list後，會fork出generator進程，它和receiver進程一起完成pipeline。

The Pipeline

rsync是高度流水線化的(pipelined)。這意味著進程之間以單方向的方式進行通信。當file list已經傳輸完畢，pipeline的行為如下：

generator --> sender --> receiver

generator的輸出結果是sender的輸入，sender的輸出結果是receiver的輸入。它們每個進程獨立運行，且只有在pipeline被阻塞或等待磁碟IO、CPU資源時才被延遲。

(譯者註：雖然它們是單方向的，但每個進程在處理完相關工作的那一刻都會立即將數據傳輸給它的接收進程，並開始處理下一個工作，接收進程接收到數據後也開始處理這段數據，所以它們雖然是流水線式的工作方式，但它們是獨立、並行工作的，基本上不會出現延遲和阻塞)

The Generator

generator進程將file list與本地目錄樹進行比較。如果指定了"--delete"選項，則在generator主功能開始前，它將首先識別出不在sender端的本地的文件(譯者註：因為此generator為receiver端的進程)，併在recevier端刪除這些文件。

然後generator將開始它的主要工作，它會從file list中一個文件一個文件地向前處理。每個文件都會被檢測以確定它是否需要跳過。如果文件的mtime或大小不同，最常見的文件操作模式不會忽略它。如果指定了"--checksum"選項，則會生成文件級別的checksum並做比較。目錄、塊設備和符號鏈接都不會被忽略。缺失的目錄在目標上也會被創建。

如果文件不被忽略，所有目標路徑下已存在的文件版本將作為基準文件(basis file)(譯者註：請記住這個詞，它貫穿整個rsync工作機制)，這些基準文件將作為數據匹配源，使得sender端可以不用發送能匹配上這些數據源的部分(譯者註：從而實現增量傳輸)。為了實現這種遠程數據匹配，將會為basis file創建塊校驗碼(block checksum)，並放在文件索引號(文件id)之後立即發送給sender端。如果指定了"--whole-file"選項，則對文件列表中的所有文件都將發送空的塊校驗碼，使得rsync強制採用全量傳輸而非增量傳輸。(譯者註：也就是說，generator每計算出一個文件的塊校驗碼集合，就立即發送給sender，而不是將所有文件的塊校驗碼都計算完成後才一次性發送)

每個文件被分割成的塊的大小以及塊校驗和的大小是根據文件大小計算出來的(譯者註：rsync命令支持手動指定block size)。

The Sender

Sender進程讀取來自generator的數據，每次讀取一個文件的id號以及該文件的塊校驗碼集合(譯者註：或稱為校驗碼列表)。

對於generator發送的每個文件，sender會存儲塊校驗碼並生成它們的hash索引以加快查找速度。

然後讀取本地文件，併為從第一個位元組開始的數據塊生成checksum。然後查找generator發送的校驗碼集合，看該checksum是否能匹配集合中的某項，如果沒有匹配項，則無匹配的位元組將作為附加屬性附加在無匹配數據塊上(譯者註：此處，無匹配位元組即表示第一個位元組，它表示無匹配數據塊的偏移量，標識無匹配數據塊是從哪裡開始的)，然後從下一個位元組(即第二個位元組)開始繼續生成校驗碼併進行比較匹配，直到所有的數據塊都匹配完成。這種實現方式就是所謂的滾動校驗"rolling checksum"。

如果源文件的塊校驗碼能匹配上校驗碼集合中的某項，則認為該數據塊是匹配塊，然後所有累積下來的非文件數據(譯者註：如數據塊重組指令、文件id等)將隨同receiver端對應文件的匹配數據塊的偏移量和長度一同發送給receiver端(譯者註：例如匹配塊對應的是receiver端此文件的第8個數據塊，則發送偏移量、匹配的塊號和數據塊的長度值，雖然數據塊的大小都是固定的，但是由於文件分割為固定大小的數據塊的時候，最後一個數據塊的大小可能小於固定大小的值，因此為了保證長度完全匹配，還需要發送數據塊的長度值)，然後generator進程將滾動到匹配塊的下一個位元組繼續計算校驗碼並比較匹配(譯者註：此處能匹配數據塊，滾動的大小是一個數據塊，對於匹配不上的數據塊，滾動的大小是一個位元組)。

通過這種方式，即使兩端文件的數據塊順序或偏移量不同，也可以識別出所有能匹配的數據塊。在rsync演算法中，這個處理過程是非常核心的。

使用這種方式，sender將發送一些指令給receiver端，這些指令告訴receiver如何將源文件重組為一個新的目標文件。並且這些指令詳細說明瞭在重組新目標文件時，所有可從basis file中直接複製的匹配數據塊(當然，前提是它們在receiver端已存在)，還包含了所有receiver端不存在的裸數據(註：即純數據)。在每個文件處理的最後階段，還會發送一個whole-file的校驗碼(譯者註：此為文件級的校驗碼)，之後sender將開始處理下一個文件。

生成滾動校驗碼(rolling checksum)以及從校驗碼集合中搜索是否能匹配的階段需要一個不錯的CPU。在rsync所有的進程中，sender是最消耗CPU的。

The Receiver

receiver將讀取從sender發送過來的數據，並通過其中的文件索引號來識別每個文件，然後它會打開本地文件(即被稱為basis file的文件)並創建一個臨時文件。

之後receiver將從sender發送過來的數據中讀取無匹配數據塊(即純數據)以及匹配上的數據塊的附加信息。如果讀取的是無匹配數據塊，這些純數據將寫入到臨時文件中，如果收到的是一個匹配記錄，receiver將查找basis file中該數據塊的偏移量，然後拷貝這些匹配的數據塊到臨時文件中。通過這種方式，臨時文件將從頭開始組建直到組建完成。

當臨時文件組建完成，將生成此臨時文件的校驗碼。最後，會將此校驗碼與sender發送過來的校驗碼比較，如果比較發現不能匹配，則刪除臨時文件，並將在第二階段重新組建該文件，如果失敗了兩次，則報告失敗。

在臨時文件最終完全組建成功後，將設置它的所有者、許可權、mtime，然後重命名並替換掉basis file。

在rsync所有的進程中，由於receiver會從basis file中拷貝數據到臨時文件，所以它是磁碟消耗最高的進程。由於小文件可能一直處於緩存中，所以可以減輕磁碟IO，但是對於大文件，緩存可能會隨著generator已經轉移到其他文件而被沖刷掉，並且sender會引起進一步的延遲。由於可能從一個文件中隨機讀取數據並寫入到另一個文件中，如果工作集(working set)比磁碟的緩存大，將可能會發生所謂的seek storm，這會再一次降低性能。

The Daemon

和很多其他的daemon類似，會為每個連接都fork一個daemon子進程。在啟動時，它將解析rsyncd.conf文件，以確定存在哪些模塊，並且設置全局選項。
當已定義好的模塊接收到一個連接時，daemon將會fork一個子進程來處理該連接。然後該子進程將讀取rsyncd.conf文件並設置被請求模塊的選項，這可能會chroot到模塊路徑，還可能會刪除進程的setuid/setgid。完成上述過程之後，daemon子進程將和普通的rsync server一樣，扮演的角色可能是sender也可能是receiver。

The Rsync Protocol

一個設計良好的通信協議會有一系列的特點。

• 所有要發送的東西明確定義在數據包中，包括首部，可選的body或數據負載量。
• 每個數據包的首部指定了協議類型或指定了命令行。
• 每個數據包的長度都是明確的。

除了這些特點之外，協議還應該具有不同程度的狀態、數據包之間的獨立性、人類可讀性以及重建斷開連接的會話的能力。

rsync的協議不包括上述任何特性。數據通過不間斷的位元組流進行傳輸。除了非匹配的數據外，既沒有指定長度說明符，也沒有長度計數器。相反，每個位元組的含義取決於由協議層次定義的上下文環境。

例如，當sender正在發送file list，它僅只是簡單地發送每個file list中的條目，並且使用一個空位元組表示終止整個列表。generator以相同的方式發送文件號以及塊校驗碼集合。

在可靠連接中，這種通信方式能非常好地工作，它比正式的協議工作方式具有更少的數據開銷。但很不幸，這也同樣使得幫助文檔、調試過程變得非常晦澀難懂。每個版本的協議可能都會有細微的差異，因此只能通過瞭解確切的協議版本來預知發生了什麼改變。

notes

This document is a work in progress. The author expects that it has some glaring oversights and some portions that may be more confusing than enlightening for some readers. It is hoped that this could evolve into a useful reference.

Specific suggestions for improvement are welcome, as would be a complete rewrite.

以下是rsync系列篇：

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

2.rsync(二)：inotify+rsync詳細說明和sersync

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

4.rsync技術報告(翻譯)

5.rsync工作機制(翻譯)

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

回到系列文章大綱：http://www.cnblogs.com/f-ck-need-u/p/7048359.html

轉載請註明出處：http://www.cnblogs.com/f-ck-need-u/p/7221535.html