Re-include a link to the first pre-release diff.
[rsync-web.git] / how-rsync-works.html
1 <html>
2 <head>
3 <title>How Rsync Works</title>
4 </head>
5 <body>
6 <h1 align="center">How Rsync Works<br>A Practical Overview</h1>
7 <h2 align="center">Foreword</h2>
8 <p>
9 The original
10 <a href="http://rsync.samba.org/tech_report/">Rsync technical report</a>
11 and
12 Andrew Tridgell's
13 <a href="http://samba.org/%7Etridge/phd_thesis.pdf">Phd thesis (pdf)</a>
14 Are both excellent documents for understanding the
15 theoretical mathematics and some of the mechanics of the rsync algorithm.
16 Unfortunately they are more about the theory than the
17 implementation of the rsync utility (hereafter referred to as
18 Rsync).
19 <p>
20 In this document I hope to describe...
21 <ul>
22         <li>A non-mathematical overview of the rsync algorithm.
23         <li>How that algorithm is implemented in the rsync utility.
24         <li>The protocol, in general terms, used by the rsync utility.
25         <li>The identifiable roles the rsync processes play.
26 </ul>
27 <p>
28 This document be able to serve as a guide for programmers
29 needing something of an entr&eacute; into the source code but the
30 primary purpose is to give the reader a foundation from
31 which he may understand
32 <ul>
33         <li>Why rsync behaves as it does.
34         <li>The limitations of rsync.
35         <li>Why a requested feature is unsuited to the code-base.
36 </ul>
37 <p>
38 This document describes in general terms the construction
39 and behaviour of Rsync.  In some cases details and exceptions
40 that would contribute to specific accuracy have
41 been sacrificed for the sake meeting the broader goals.
42 <h2 align="center">Processes and Roles</h2>
43 <p>
44 When we talk about Rsync we use specific terms to refer to
45 various processes and their roles in the task performed by
46 the utility.  For effective communication it is important that we
47 all be speaking the same language; likewise it is important
48 that we mean the same things when we use certain terms in a
49 given context.  On the rsync mailing list there is often
50 some confusion with regards to role and processes.  For
51 these reasons I will define a few terms
52 used in the role and process contexts that will be used henceforth.
53
54 <table cellspacing="20"><tr valign="top">
55 <td>client
56 </td><td>role
57 </td><td>
58         The client initiates the synchronisation.
59 </td></tr><tr valign="top">
60 <td>server
61 </td><td>role
62 </td><td>
63         The remote rsync process or system to which the
64         client connects either within a local transfer, via
65         a remote shell or via a network socket.
66         <p>
67         This is a general term and should not be confused with the daemon.
68 </td></tr><tr valign="top">
69 <td>
70 </td><td>
71 </td><td bgcolor="#dddddd">
72         Once the connection between the client and server is established
73         the distinction between them is superseded by the
74         sender and receiver roles.
75 </td></tr><tr valign="top">
76 <td>daemon
77 </td><td>Role and process
78 </td><td>
79         An Rsync process that awaits connections from
80         clients.  On a certain platform this would be called a
81         service.
82 </td></tr><tr valign="top">
83 <td>remote&nbsp;shell
84 </td><td>role and set of processes
85 </td><td>
86         One or more processes that provide connectivity
87         between an Rsync client and an Rsync server on a
88         remote system.
89 </td></tr><tr valign="top">
90 <td>sender
91 </td><td>role and process
92 </td><td>
93         The Rsync process that has access to the source
94         files being synchronised.
95 </td></tr><tr valign="top">
96 <td>receiver
97 </td><td>role and process
98 </td><td>
99         As a role the receiver is the destination system.
100         As a process the receiver is the process that
101         receives update data and writes it to disk.
102 </td></tr><tr valign="top">
103 <td>generator
104 </td><td>process
105 </td><td>
106         The generator process identifies changed files and
107         manages the file level logic.
108 </td></tr></table>
109 <p>
110 <h2 align="center">Process Startup</h2>
111 <p>
112 When an Rsync client is started it will first establish a
113 connection with a server process.  This connection may be
114 through pipes or over a network socket.
115 <p>
116 When Rsync communicates with a remote non-daemon server via
117 a remote shell the startup method is to fork the remote
118 shell which will start an Rsync server on the remote system.
119 Both the Rsync client and server are communicating via pipes
120 through the remote shell.  As far as the rsync processes are
121 concerned there is no network.
122 In this mode the rsync options for the server process are
123 passed on the command-line that is used to start the remote
124 shell.
125 <p>
126 When Rsync is communicating with a daemon it is
127 communicating directly with a network socket.  This is the
128 only sort of Rsync communication that could be called
129 network aware.
130 In this mode the rsync options must be sent over the socket, as
131 described below.
132 <p>
133 At the very start of the communication between the client
134 and the server, they each send the maximum protocol version
135 they support to the other side.
136 Each side then uses the minimum value as the the protocol
137 level for the transfer.
138 If this is a daemon-mode connection, rsync options are sent
139 from the client to the server.  Then, the exclude list is
140 transmitted.  From this point onward the
141 client-server relationship is relevant only with regards
142 to error and log message delivery.
143 <p>
144 Local Rsync jobs (when the source and destination are both on locally
145 mounted filesystems) are done exactly like a push.  The
146 client, which becomes the sender, forks a server process to
147 fulfill the receiver role.  The client/sender and
148 server/receiver communicate with each other over pipes.
149 <h2 align="center">The File List</h2>
150 The file list includes not only the pathnames but also
151 ownership, mode, permissions, size and modtime.
152 If the --checksum option has been specified it also includes
153 the file checksums.
154 <p>
155 The first thing that happens once the startup has completed
156 is that the sender will create the file list.
157 While it is being built, each entry is transmitted to the
158 receiving side in a network-optimised way.
159 <p>
160 When this is done, each side sorts the file list lexicographically by path
161 relative to the base directory of the transfer.
162 (The exact sorting algorithm varies depending on what protocol
163 version is in effect for the transfer.)
164 Once that has happened all references to files
165 will be done by their index in the file list.
166 <p>
167 If necessary the sender follows the file list with id&rarr;name
168 tables for users and groups which the receiver will use to
169 do a id&rarr;name&rarr;id translation for every file in the file
170 list.
171 <p>
172 After the file list has been received by the receiver, it
173 will fork to become the generator and receiver pair
174 completing the pipeline.
175 <h2 align="center">The Pipeline</h2>
176 Rsync is heavily pipelined.  This means that it is a set of
177 processes that communicate in a (largely) unidirectional
178 way.  Once the file list has been shared the pipeline
179 behaves like this:
180 <blockquote>
181         generator &rarr; sender &rarr; receiver
182 </blockquote>
183 <p>
184 The output of the generator is input for the sender and the
185 output of the sender is input for the receiver.
186 Each process runs independently and is delayed only when the
187 pipelines stall or when waiting for disk I/O or CPU resources.
188 <h2 align="center">The Generator</h2>
189 <p>
190 The generator process compares the file list with its local
191 directory tree.  Prior to beginning its primary function, if
192 --delete has been specified, it will first identify local
193 files not on the sender and delete them on the receiver.
194 <p>
195 The generator will then start walking the file list.  Each
196 file will be checked to see if it can be skipped.  In the
197 most common mode of operation files are not skipped if the
198 modification time or size differs.  If --checksum was
199 specified a file-level checksum will be created and
200 compared.  Directories, device nodes and symlinks are not
201 skipped.  Missing directories will be created.  
202 <p>
203 If a file is not to be skipped, any existing version on the
204 receiving side becomes the "basis file" for the transfer, and is
205 used as a data source that will help to eliminate matching data
206 from having to be sent by the sender.  To effect this remote
207 matching of data, block checksums are created for the basis file
208 and sent to the sender immediately following the file's index
209 number.
210 An empty block checksum set is sent for new files and if
211 --whole-file was specified.
212 <p>
213 The block size and, in later versions, the size of the
214 block checksum are calculated on a per file basis according
215 to the size of that file.
216 <h2 align="center">The Sender</h2>
217 The sender process reads the file index numbers and associated
218 block checksum sets one at a time from the generator.
219 <p>
220 For each file id the generator sends it will store the
221 block checksums and build a hash index of them for rapid lookup.
222 <p>
223 Then the local file is read and a checksum is
224 generated for the block beginning with the first byte of the
225 local file.  This block checksum is looked for in the
226 set that was sent by the generator, and if no match is found,
227 the non-matching byte will be appended to the non-matching data
228 and the block starting at the next byte will be compared.
229 This is what
230 is referred to as the &ldquo;rolling checksum&rdquo;
231 <p>
232 If a block checksum match is found it is considered a
233 matching block and any accumulated non-matching data will be
234 sent to the receiver followed by the offset and length in
235 the receiver's file of the matching block and the block
236 checksum generator will be advanced to the next byte after
237 the matching block.
238 <p>
239 Matching blocks can be identified in this way even if
240 the blocks are reordered or at different offsets.  
241 This process is the very heart of the rsync algorithm.
242 <p>
243 In this way, the sender will give the receiver instructions for
244 how to reconstruct the source file into a new destination file.
245 These instructions detail all the matching data that can be
246 copied from the basis file (if one exists for the transfe),
247 and includes any raw data that was not available locally.
248 At the end of each file's processing a whole-file
249 checksum is sent and the sender proceeds with the next
250 file.
251 <p>
252 Generating the rolling checksums and searching for matches
253 in the checksum set sent by the generator require a good
254 deal of CPU power.  Of all the rsync processes it is the
255 sender that is the most CPU intensive.
256 <h2 align="center">The Receiver</h2>
257 <p>
258 The receiver will read from the sender data for each file
259 identified by the file index number.  It will open the local
260 file (called the basis) and will create a temporary file.
261 <p>
262 The receiver will expect to read non-matched data and/or to match
263 records all in sequence for the final file contents.  When
264 non-matched data is read it will be written to the
265 temp-file.  When a block match record is received the
266 receiver will seek to the block offset in the basis file
267 and copy the block to the temp-file.  In this way the
268 temp-file is built from beginning to end.
269 <p>
270 The file's checksum is generated as the temp-file is built.
271 At the end of the file, this checksum is compared with the
272 file checksum from the sender.  If the file checksums do not
273 match the temp-file is deleted.  If the file fails once it
274 will be reprocessed in a second phase, and if it fails twice
275 an error is reported.
276 <p>
277 After the temp-file has been completed, its ownership and
278 permissions and modification time are set.  It is then
279 renamed to replace the basis file.
280 <p>
281 Copying data from the basis file to the temp-file make the
282 receiver the most disk intensive of all the rsync processes.
283 Small files may still be in disk cache mitigating this but
284 for large files the cache may thrash as the generator has
285 moved on to other files and there is further latency caused
286 by the sender.  As
287 data is read possibly at random from one file and written to
288 another, if the working set is larger than the disk cache,
289 then what is called a seek storm can occur, further
290 hurting performance.
291 <h2 align="center">The Daemon</h2>
292 The daemon process, like many daemons, forks for every
293 connection.  On startup, it parses the rsyncd.conf file
294 to determine what modules exist and to set the global options.
295 <p>
296 When a connection is received for a defined module the
297 daemon forks a new child process to handle the connection.
298 That child process then reads the rsyncd.conf file to set
299 the options for the requested module, which may chroot to the
300 module path and may drop setuid and setgid for the
301 process.  After that it will behave just like any other
302 rsync server process adopting either a sender or receiver
303 role.
304 <h2 align="center">The Rsync Protocol</h2>
305 <p>
306 A well-designed communications protocol has a number of
307 characteristics.
308 <ul>
309         <li>Everything is sent in well defined packets with
310                 a header and an optional body or data payload.
311         <li>In each packet's header a type and or command
312                 specified.
313         <li>Each packet has a definite length.
314 </ul>
315 <p>
316 In addition to these characteristics, protocols have varying degrees of
317 statefulness, inter-packet independence, human readability,
318 and the ability to reestablish a disconnected session.
319 <p>
320 Rsync's protocol has none of these good characteristics.  The data is
321 transferred as an unbroken stream of bytes.  With the
322 exception of the unmatched file-data, there are no length
323 specifiers nor counts.  Instead the meaning of each byte is
324 dependent on its context as defined by the protocol level.
325 <p>
326 As an example, when the sender is sending  the file list it
327 simply sends each file list entry and terminates the list
328 with a null byte.  Within the file list entries, a bitfield
329 indicates which fields of the structure to expect and those
330 that are variable length strings are simply null terminated.
331 The generator sending file numbers and block checksum sets
332 works the same way.
333 <p>
334 This method of communication works quite well on reliable
335 connections and it certainly has less data overhead than the
336 formal protocols.  It unfortunately makes the protocol
337 extremely difficult to document, debug or extend.
338 Each version of the protocol will have subtle differences on
339 the wire that can only be anticipated by knowing the exact
340 protocol version.
341 <h2 align="center">notes</h2>
342 This document is a work in progress.  The author expects
343 that it has some glaring oversights and some portions that may be
344 more confusing than enlightening for some readers.  It is
345 hoped that this could evolve into a useful reference.
346 <p>
347 Specific suggestions for improvement are welcome, as would be a
348 complete rewrite.
349 </body>
350 </html>