Moved the doc resources into an include file.
[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/~tridge/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 rolls 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 antre 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 in
53 henceforth.
54 <table valign="top" cellspacing="20"><tr>
55 <td>client
56 <td>role
57 <td>
58         The client initiates the synchronisation.
59 </tr><tr>
60 <td>server
61 <td>role
62 <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 </tr><tr>
69 <td>
70 <td>
71 <td bgcolor="EFEFEF">
72         Once the connection between the client and server is established
73         the distinction between them is superceded by the
74         sender and receiver roles.
75 </tr><tr>
76 <td>daemon
77 <td>Role and process
78 <td>
79         An Rsync process that awaits connections from
80         clients.  On a certain platform this would be called a
81         service.
82 </tr><tr>
83 <td>remote&nbsp;shell
84 <td>role and set of processes
85 <td>
86         One or more processes that provide connectivity
87         between an Rsync client and an Rsync server on a
88         remote system.
89 </tr><tr>
90 <td>sender
91 <td>role and process
92 <td>
93         The Rsync process that has access to the source
94         files being synchronised.
95 </tr><tr>
96 <td>receiver
97 <td>role and process
98 <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 </tr><tr>
103 <td>generator
104 <td>process
105 <td>
106         The generator process identifies changed files and
107         manages the file level logic.
108 </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 <p>
123 When Rsync is communicating with a daemon it is
124 communicating directly with a network socket.  This is the
125 only sort of Rsync communication that could be called
126 network aware.
127 <p>
128 Once the client has communications with the server they
129 agree upon the protocol level and each determine whether
130 they are sender or receiver and the exclude list may be
131 transmitted.  From this point onward the
132 client-server relationship is only irrelevant with regards
133 to error and log message delivery.
134 <p>
135 Local Rsync jobs (both source and destination on locally
136 mounted filesystems) are done exactly like a push.  The
137 client, which becomes the sender, forks a server process to
138 fulfil the receiver role.  The client/sender and
139 server/receiver communicate with each other over pipes.
140 <h2 align="center">The File List</h2>
141 The file list includes not only the pathnames but also
142 ownership, mode, permissions, size and modtime.
143 If the --checksum option has been specified it also includes
144 the file checksums.
145 <p>
146 The first thing that happens once the startup has completed
147 is that the sender will create the file list.
148 While it is being built, each entry is transmitted to the
149 receiving side in a network optimised way.
150 <p>
151 The file list is then sorted lexicographically by path
152 relative to the base directories on both the sender and the
153 receiver.  Once that has happened all references to files
154 will be done by their index in the file list.
155 <p>
156 If necessary the sender follows the file list with id-&gt;name
157 tables for users and groups which the receiver will use to
158 do a id-&gt;name-&gt;id translation for every file in the file
159 list.
160 <p>
161 After the file list has been received by the receiver it
162 will fork again to become the generator and receiver pair
163 completing the pipeline.
164 <h2 align="center">The Pipeline</h2>
165 Rsync is heavily pipelined.  This means that it is a set of
166 processes that communicate in a (largely) unidirectional
167 way.  Once the file list has been shared the pipeline
168 behaves like this:
169 <blockquote>
170         generator -&gt; sender -&gt; receiver
171 </blockquote>
172 <p>
173 The output of the generator is input for the sender and the
174 output of the sender is input for the receiver.  Each
175 process runs independently and is only delayed when the
176 pipelines stall or for disk I/O.
177 <h2 align="center">The Generator</h2>
178 <p>
179 The generator process compares the file list with it's local
180 directory tree.  Prior to beginning its primary function if
181 --delete has been specified it will first identify local
182 files not on the sender and delete them.
183 <p>
184 The generator will then start walking the file list.  Each
185 file will be checked to see if it can be skipped.  In the
186 most common mode of operation files are not skipped if the
187 modification time or size differ.  If --checksum was
188 specified a file-level checksum will be created and
189 compared.  Directories, device nodes and symlinks are not
190 skipped.  Missing directories will be created.  
191 <p>
192 If a file is not to be skipped block checksums are created
193 for it and sent with the file index number to the sender.
194 An empty block checksum set is sent for new files and if
195 --whole-file was specified.
196 <p>
197 The block size and, in later versions, the size of the
198 block checksum are calculated on a per file basis according
199 to the size of that file.
200 <h2 align="center">The Sender</h2>
201 The sender process reads the file index numbers and associated
202 block checksum sets one at a time from the generator.
203 <p>
204 For each file id the generator sends it will store the
205 block checksums and build a hash index of them for rapid lookup.
206 <p>
207 Then the local file is read and a checksum is
208 generated for the block beginning with the first byte of the
209 local file.  This block checksum is looked for in the
210 set that was sent by the generator if no match is found the
211 block starting at the next byte will be compared and the
212 byte will be added to the non-matching data.  This is what
213 is referred to as the "rolling checksum"
214 <p>
215 If a block checksum match is found it is considered a
216 matching block and any accumulated non-matching data will be
217 sent to the receiver followed by the offset and length in
218 the receiver's file of the matching block and the block
219 checksum generator will be advanced to the next byte after
220 the matching block.
221 <p>
222 Matching blocks can be identified in this way even if
223 the blocks are reordered or at different offsets.  
224 This process is the very heart of the rsync algorithm.
225 <p>
226 In this way the generator will send to the receiver a
227 sequence of non-matched data interspersed with matching block
228 information.  At the end of each file's processing a whole
229 file checksum is sent and the sender proceeds with the next
230 file.
231 <p>
232 Generating the rolling checksums and searching for matches
233 in the checksum set sent by the generator require a good
234 deal of CPU power.  Of all the rsync processes it is the
235 sender that is the most CPU intensive.
236 <h2 align="center">The Receiver</h2>
237 <p>
238 The receiver will read from the sender data for each file
239 identified by the file index number.  It will open the local
240 file (called the basis) and will create a temporary file.
241 <p>
242 The receiver will expect to read non-matched data and/or match
243 records all in sequence for the final file contents.  When
244 non-matched data is read it will be written to the
245 temp-file.  When a block match record is received the
246 receiver will seek to the block offset in the basis file
247 and copy the block to the temp-file.  In this way the
248 temp-file is built from beginning to end.
249 <p>
250 As the temp-file was built the a file checksum was
251 generated.  At the end of the file it is compared with the
252 file checksum from the sender.  If the file checksums do not
253 match the temp-file is deleted.  If the file fails once it
254 will be reprocessed in a second phase and if it fails twice
255 and error is reported.
256 <p>
257 After the temp-file has been completed it's ownership and
258 permissions and modification time are set.  It is then
259 renamed to replace the basis file.
260 <p>
261 Copying data from the basis file to the temp-file make the
262 receiver the most disk intensive of all the rsync processes.
263 Small files may still be in disk cache mitigating this but
264 for large files the cache may thrash as the generator has
265 moved on to other files and there is further latency caused
266 by the sender.  For files exceeding cache capacity as
267 data is read possibly at random from one file and written to
268 another it can produce what is called a seek storm further
269 hurting performance.
270 <h2 align="center">The Daemon</h2>
271 The daemon process like many daemons forks for every
272 connection.  On startup it reads the rsyncd.conf file in
273 order to know what modules exist and set the global options.
274 <p>
275 When a connection is received for a defined module the
276 daemon forks a new child process to handle the connection.
277 That child process then reads the rsyncd.conf file to set
278 the options for the requested module it may chroot to the
279 module path and may drop change user and group id for the
280 process.  After that it will behave just like any other
281 rsync server process adopting either a sender or receiver
282 role.
283 <h2 align="center">The Rsync Protocol</h2>
284 <p>
285 A well designed communications protocol has a number of
286 characteristics.
287 <ul>
288         <li>Everything is sent in well defined packets with
289                 a header and an optional body or data payload.
290         <li>In each packet's header a type and or command
291                 specified.
292         <li>Each packet has a definite length.
293 </ul>
294 In addition to these, protocols have varying degrees of
295 statefulness, inter-packet independence, human readability,
296 and the ability to reestablish a disconnected session.
297 <p>
298 Rsync has none of these characteristics.  The data is
299 transfered as an unbroken stream of bytes.  With the
300 exception of the unmatched file-data there are no length
301 specifiers nor counts.  Instead the meaning of each byte is
302 dependent on its context as defined by the protocol level.
303 <p>
304 As an example, when the sender is sending  the file list it
305 simply sends each file list entry and terminates the list
306 with a NUL byte.  Within the file list entries a bitfield
307 indicates which fields of the structure to expect and those
308 that are variable length strings are simply NUL terminated.
309 The generator sending file numbers and block checksum sets
310 works the same way.
311 <p>
312 This method of communication works quite well on reliable
313 connections and it certainly has less data overhead than the
314 formal protocols.  It unfortunately make the protocol
315 extremely difficult to document, debug or extend.
316 Each version of the protocol will have subtle differences on
317 the wire that can only be anticipated by knowing the exact
318 protocol version.
319 <h2 align="center">notes</h2>
320 This document is a work in progress.  The author expects
321 that it has some glaring oversights and portions that may be
322 more confusing than enlightening for some readers.  It is
323 hoped that this could evolve into a useful reference.
324 <p>
325 Specific suggestions for improvement are welcome, as would a
326 complete rewrite.
327 </body>
328 </html>