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...
This document be able to serve as a guide for programmers needing something of an antre into the source code but the primary purpose is to give the reader a foundation from which he may understand
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.
When we talk about Rsync we use specific terms to refer to various processes and their roles in the task performed by the utility. For effective communication it is important that we all be speaking the same language; likewise it is important that we mean the same things when we use certain terms in a given context. On the rsync mailing list there is often some confusion with regards to role and processes. For these reasons i will define a few terms used in the role and process contexts that will be used in henceforth.
| client | role | The client initiates the synchronisation. |
| server | role |
The remote rsync process or system to which the
client connects either within a local transfer, via
a remote shell or via a network socket.
This is a general term and should not be confused with the daemon. |
| Once the connection between the client and server is established the distinction between them is superceded by the sender and receiver roles. | ||
| daemon | Role and process | An Rsync process that awaits connections from clients. On a certain platform this would be called a service. |
| remote shell | role and set of processes | One or more processes that provide connectivity between an Rsync client and an Rsync server on a remote system. |
| sender | role and process | The Rsync process that has access to the source files being synchronised. |
| receiver | role and process | As a role the receiver is the destination system. As a process the receiver is the process that receives update data and writes it to disk. |
| generator | process | The generator process identifies changed files and manages the file level logic. |
When an Rsync client is started it will first establish a connection with a server process. This connection may be through pipes or over a network socket.
When Rsync communicates with a remote non-daemon server via a remote shell the startup method is to fork the remote shell which will start an Rsync server on the remote system. Both the Rsync client and server are communicating via pipes through the remote shell. As far as the rsync processes are concerned there is no network.
When Rsync is communicating with a daemon it is communicating directly with a network socket. This is the only sort of Rsync communication that could be called network aware.
Once the client has communications with the server they agree upon the protocol level and each determine whether they are sender or receiver and the exclude list may be transmitted. From this point onward the client-server relationship is only irrelevant with regards to error and log message delivery.
Local Rsync jobs (both source and destination on locally mounted filesystems) are done exactly like a push. The client, which becomes the sender, forks a server process to fulfil the receiver role. The client/sender and server/receiver communicate with each other over pipes.
The first thing that happens once the startup has completed is that the sender will create the file list. While it is being built, each entry is transmitted to the receiving side in a network optimised way.
The file list is then sorted lexicographically by path relative to the base directories on both the sender and the receiver. Once that has happened all references to files will be done by their index in the file list.
If necessary the sender follows the file list with id->name tables for users and groups which the receiver will use to do a id->name->id translation for every file in the file list.
After the file list has been received by the receiver it will fork again to become the generator and receiver pair completing the pipeline.
generator -> sender -> receiver
The output of the generator is input for the sender and the output of the sender is input for the receiver. Each process runs independently and is only delayed when the pipelines stall or for disk I/O.
The generator process compares the file list with it's local directory tree. Prior to beginning its primary function if --delete has been specified it will first identify local files not on the sender and delete them.
The generator will then start walking the file list. Each file will be checked to see if it can be skipped. In the most common mode of operation files are not skipped if the modification time or size differ. If --checksum was specified a file-level checksum will be created and compared. Directories, device nodes and symlinks are not skipped. Missing directories will be created.
If a file is not to be skipped block checksums are created for it and sent with the file index number to the sender. An empty block checksum set is sent for new files and if --whole-file was specified.
The block size and, in later versions, the size of the block checksum are calculated on a per file basis according to the size of that file.
For each file id the generator sends it will store the block checksums and build a hash index of them for rapid lookup.
Then the local file is read and a checksum is generated for the block beginning with the first byte of the local file. This block checksum is looked for in the set that was sent by the generator if no match is found the block starting at the next byte will be compared and the byte will be added to the non-matching data. This is what is referred to as the "rolling checksum"
If a block checksum match is found it is considered a matching block and any accumulated non-matching data will be sent to the receiver followed by the offset and length in the receiver's file of the matching block and the block checksum generator will be advanced to the next byte after the matching block.
Matching blocks can be identified in this way even if the blocks are reordered or at different offsets. This process is the very heart of the rsync algorithm.
In this way the generator will send to the receiver a sequence of non-matched data interspersed with matching block information. At the end of each file's processing a whole file checksum is sent and the sender proceeds with the next file.
Generating the rolling checksums and searching for matches in the checksum set sent by the generator require a good deal of CPU power. Of all the rsync processes it is the sender that is the most CPU intensive.
The receiver will read from the sender data for each file identified by the file index number. It will open the local file (called the basis) and will create a temporary file.
The receiver will expect to read non-matched data and/or match records all in sequence for the final file contents. When non-matched data is read it will be written to the temp-file. When a block match record is received the receiver will seek to the block offset in the basis file and copy the block to the temp-file. In this way the temp-file is built from beginning to end.
As the temp-file was built the a file checksum was generated. At the end of the file it is compared with the file checksum from the sender. If the file checksums do not match the temp-file is deleted. If the file fails once it will be reprocessed in a second phase and if it fails twice and error is reported.
After the temp-file has been completed it's ownership and permissions and modification time are set. It is then renamed to replace the basis file.
Copying data from the basis file to the temp-file make the receiver the most disk intensive of all the rsync processes. Small files may still be in disk cache mitigating this but for large files the cache may thrash as the generator has moved on to other files and there is further latency caused by the sender. For files exceeding cache capacity as data is read possibly at random from one file and written to another it can produce what is called a seek storm further hurting performance.
When a connection is received for a defined module the daemon forks a new child process to handle the connection. That child process then reads the rsyncd.conf file to set the options for the requested module it may chroot to the module path and may drop change user and group id for the process. After that it will behave just like any other rsync server process adopting either a sender or receiver role.
A well designed communications protocol has a number of characteristics.
Rsync has none of these characteristics. The data is transfered as an unbroken stream of bytes. With the exception of the unmatched file-data there are no length specifiers nor counts. Instead the meaning of each byte is dependent on its context as defined by the protocol level.
As an example, when the sender is sending the file list it simply sends each file list entry and terminates the list with a NUL byte. Within the file list entries a bitfield indicates which fields of the structure to expect and those that are variable length strings are simply NUL terminated. The generator sending file numbers and block checksum sets works the same way.
This method of communication works quite well on reliable connections and it certainly has less data overhead than the formal protocols. It unfortunately make the protocol extremely difficult to document, debug or extend. Each version of the protocol will have subtle differences on the wire that can only be anticipated by knowing the exact protocol version.
Specific suggestions for improvement are welcome, as would a complete rewrite.