The Rsync Algorithm
21 July, 2000
Dr. Andrew Tridgell
This paper describes the rsync algorithm, which provides a nice way to
remotely update files over a high latency, low bandwidth link. The
paper itself concentrates on the core algorithm, giving the basic
mathematical justifications and characterising the problem. In my
presentation at OLS I will concentrate on some of the practical
applications of the rsync algorithm, such as the rsync tool and recent
work on getting the rsync algorithm into a variety of everyday
protocols, such as CVS and HTTP.
Notes
Original presentation
The original presentation of this talk occurred in room C of the
Ottawa Linux Symposium, Ottawa Congress Centre, Ottawa, Ontario,
Canada on the 21st of July, 2000 at 15:15 local time. This
presentation was given by Dr. Andrew Tridgell.
Presenter bio
Prior to joining Linuxcare, Andrew held a full-time position as a
researcher and lecturer in the Department of Computer Science at
Australian National University in Canberra. His research interests
include parallel computing, network protocols, automatic speech
recognition, and operating systems. Andrew spends his spare time
working on various bits of free software. He is well known as the
original author and current team leader for the Samba software
package.
In addition to Samba, Andrew is recognized for his work on rsync, a
fast file transfer program; Jitterbug, a Web-based bug tracking
system; Nightcap, a learning chess program; and AP/Linux, a Linux
port to the AP1000+ multicomputer. Andrew is also one of the
privileged few to have witnessed the famous incident where Linus
Torvalds was bitten by a penguin.
Presentation recording details
This transcript was created using the OLS-supplied recording of the
original live presentation. This recording is available from
[1]ftp://ftp.linuxsymposium.org/ols2000/2000-07-21_15-02-49_C_64.mp
3
The recording has a 64 kb/s bitrate, 32KHz sample rate, mono audio
(due to the style of single microphone recording used) and has a
file size of 44925120 bytes. The MD5 sum of this file is:
b790b88d23f2815c823ba958840b72a4
Creation of this transcript
Request for corrections
This transcript was not created by a professional transcriptionist;
it was created by someone with technical skills and an interest in
the presented content. There may be errors found within this
transcript; we ask that you report them to using the bug tracking
interface described at [2]http://olstrans.sourceforge.net/bugs.php3
Tools used in transcript creation
This transcription was made from the MP3 recording of the original
presentation, using XMMS for playback and lyx (with docbook
template) for the transcription.
Format of transcript files
The transcribed data should be available in a number of formats so
as to provide more ready access to this data to a larger audience.
The transcripts will be available in at least HTML, SGML and plain
ASCII text formats; other formats may be provided.
Names of people involved with this transcription
This transcript was created by Jacob Moorman of the Marble Horse
Free Software Group (whose pages live at
http://www.marblehorse.org). He may be reached at
roguemtl@marblehorse.org
The primary quality assurance for this document was performed by
Stephanie Donovan. She may be reached at sdonovan@achilles.net
Notes related to the use of this document
This document is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. While quality
assurance checks on this transcript were performed, it was not
created nor checked by a professional transcriptionist; the
technical accuracy of this transcript is neither guaranteed nor
confirmed. Please refer to the original audio recording of this
talk in the event confirmation of the speaker's actual statements
are needed.
Ownership of the content within this transcript
These transcripts likely contain content owned, under copyright, by
the original presentation speaker; please contact them for
licensing requests, but do so in a polite manner, please. It may
also be useful to contact the coordinator for the Ottawa Linux
Symposium, the original venue for this presentation. All trademarks
are property of their respective owners.
Markup used in this transcript
Time markers
At the end of each paragraph within the body of this transcript, a
time offset is listed, corresponding to that point in the MP3
recording of the presentation. This time marker is emphasized (in
document formats in which emphasis is supported) and is placed
within brackets at the very end of each paragraph. For example,
[05m, 30s] states that this paragraph ends at the five-minute,
thirty-second mark in the MP3 recording.(null)
Questions and comments from the audience
These recordings were created using a bud microphone attached to
the speaker during their presentation. Due to the inherent range
limitations of this type of microphone, some of the comments and
questions from the audience are unintelligible. In cases where the
speaker repeats the audience question, the question shall be
omitted and a marker will be left in its place. Events which happen
in the audience shall be bracketed, such as: [The audience
applauds.]
Further, in cases where the audience comments or questions are not
repeated by the speaker, they shall be included within this
transcript and shall be enclosed within double quotes to delineate
that the statements come from the audience, not from the speaker.
Editorial notes
The editor of this transcript, the transcriptionist (if you will),
and the quality assurance resource who have examined this
transcript may each include editorial notes within this transcript.
These shall be placed within brackets and shall begin with 'ED:'.
For example: [ED: The author is referring to sliced cheese, not
grated cheese.]
Paragraph breaks
The paragraph breaks within this transcript are very much
arbitrary; in many cases they represent pauses or breaks in the
speech of the speaker. In other cases, they have been inserted to
allow for enhanced clarity in the reading of this transcript.
Speech corrections by the speaker
During the course of the talk, the speaker may correct himself or
herself. In these cases, the corrected speech will be placed in
parenthesis. The reader of this transcript may usually ignore the
parenthised sections as they represent corrected speech. For
example: My aunt once had (a dog named Spot, sorry) a cat named
Cleopatra.
Unintelligible speech
In sections where the speech of the author or audience has been
deemed useful, but unintelligible by the transcriptionist or by the
quality assurance resource, a marker will be inserted in their
places, [unintelligible]. Several attempts will be made to correct
words and phrases of this nature. In cases where the unintelligible
words or phrases are clearly not of importance to the meaning and
understanding of the sentence, they may be omitted without marker
insertion.
Transcript
My name's Andrew Tridgell. I'm going to tell you a bit about rsync,
and I'm going to be concentrating on the rsync algorithm for this
talk, as opposed to to the rsync tool. A lot of people are familiar
with the tool itself, but there's actually some interesting
technology underlying the tool, which I'm trying to get a few more
people to know about (the technology), because it has some uses
outside of the tool. And I want to, hopefully, see it used in a far
wider range of applications than what it's currently being used in.
And so I'm hoping that by introducing a few more people to the
ideas underlying the internals of the tool, that it might be
implemented in a few more places. And I'm hoping that, eventually,
the algorithmic part of the tool will become as ubiquitous as QSort
or memcopy or other standard algorithms... standard utility
functions that people use all the time in their programming. [00m,
55s]
So the core of rsync is this algorithm that I call the rsync
algorithm. And it solves this problem, the remote update problem.
Now the remote update problem is basically: you have two computers
connected by a very high latency, very low bandwidth link... a
typical Internet link, at least if you're in Australia. So, a piece
of wet string, a really pathetic link... and you've got two files.
The algorithm actually works on arbitrary lumps of data. You've got
two lumps of data; one sitting on one of the computers and the
other sitting on the other computer, and you want to update one of
the lumps of data to be the same as the other one. So you're trying
to just update a file remotely and you don't know... it's really
like the morning after algorithm. It's an algorithm meant for: when
you didn't have the forethought to, at one end or the other, have a
copy of the old file so you could run a diff, or an Xdelta, or some
other tool like that. So you don't have any way of doing a local
diff between the two files and sending that. [02m, 09s]
The rsync algorithm is a way of solving this problem and much like
neural networks, the last result for people who don't understand
the problem, rsync is a good way of solving this problem when you
don't know exactly what types of changes have been made to the
data. There are always more efficient algorithms than rsync. If you
have structured data, and you know precisely the sorts of updates,
the constraints on the types of updates that can happen to the
data, then you can always craft a better algorithm than rsync. And
that's preferable by saying well you could always craft rsync, but
in fact you'll very likely be able to craft a much better
algorithm. But rsync is useful because it doesn't require any
thinking; and it doesn't require any forethought to organize, to
have particular information about the old file stored beforehand.
So it's like this morning after algorithm for copying data when you
need to update remote data, you don't know the old data, or you
don't have any control over the remote changes. For example, you
may not have any knowledge about what changes we may have made at
the other end of the link because you're not the person who made
those changes. And yet you're the person who has to update from
that file. [03m, 31s]
Okay, so how do you go about doing this? Now prior to these sorts
of algorithms, really there were only two ways of doing this; one
was that you could just throw some compression at it. You could
just compress the file and send the compressed file. That might
gain you a factor of three, a factor of five, a factor of a hundred
if it's a spam file or something. So you might be able to get some
speed-up if the file is reasonably compressible. [04m, 02s]
But that really isn't enough, you know; people want more of a
speed-up than that. Just because there's a lot more data there;
there's a lot more information you're not taking advantage of. You
have the old file. It's likely that the old file has a lot in
common with the new file, because usually in a big file, the
changes are small. Where I'm deliberately being vague here, small
on an undefined scale. As soon as you start defining the scale of
the size of the changes, actually defining those, you immediately
have to get into the area of structured changes and structures to
the file, in which case you probably shouldn't be using rsync
anyway. [04m, 43s]
So the next thing is: you could keep the old file; you could have
some forethought and arrange at one end or the other to always keep
the old file and that way you can always send a diff. That's not
always practical. So the remote update problem is: is there a
better way of doing this, of updating the files remotely, without
all of this prior knowledge, and doing better than just
compression; taking advantage of the data in the old file? [05m,
14s]
First of all, maybe we should actually get you guys to give some
ideas. Those of you that have already read the paper about rsync
maybe shouldn't say what the idea is. Can anyone here suggest how
you might do this; what are some... What I find is that, it's a bit
embarrassing, really. I took several years to work on the rsync
algorithm, but generally when I describe the problem to somebody,
as a fresh problem, most people in the CS Department back at ANU
worked it out in about half an hour. But then again, they knew
there was a solution or I wouldn't have been asking them. So maybe
with a few people, you'll work it out much quicker. Does anyone
have any suggestions? How would you go about doing this? [05m, 53s]
[The speaker calls on an audience member.]
Split the file into half and then try to do a checksum... keep
breaking it up into smaller pieces until the checksum matches...
Indeed you could; the problem is: what if someone has inserted one
byte into the beginning of the file? Then neither half is going to
match the half at the other end. That will only work if you've
modified exactly half of the file or you've kept things aligned. If
the alignments have changed at all, if any of the data has slid in
the file, even by one byte, then any algorithm based on matching
blocks with corresponding blocks in the other file won't work.
Okay, so another idea... [06m, 32s]
[The speaker calls on an audience member.]
You could take sixteen bytes and send that and then have the other
end look for that in their file. Checksum over, say, a kilobyte
after the match.
Okay, you could indeed. Now if you're sending just sixteen bytes at
a time, you've got a lot of round trips. This is another one of the
constraints. I'm going to change the problem on you. And I'm going
to add the additional constraint that I want to do the whole thing
in one round trip. In fact, I want to do it in one round trip for
any number of files, even if you have ten-thousand files, I want
one round trip in total. Just to make it a bit harder. Let's
consider just one file at first, though. [07m, 08s]
There's still another slight problem. Say you sent checksums of
every 16 bytes to the other end. Well first of all, that's going to
be big, it's going to be a large percentage of the file, so 16 is
too small. So lets make it, say, 600 instead. Okay, then the
checksum is going to be 1% or something, of the file, something of
that order. Which is getting more reasonable. [07m, 32s]
Then you've got a slight problem that you've got to checksum it at
every offset at the other end. Now say it's a megabyte file at the
other end. That means you'll be calculating a million checksums.
[07m, 44s]
[The audience member continues.]
Wait, I said just send 16 bytes, not the checksum of 16 bytes. So
then you can just look for that 16 bytes...
Right, and then you're getting very close. The very first version
of rsync used something very similar to this. Rsync actually came
out of some work I did on search algorithms. How many of you know
about the Boyer-Moore-Gosper string searching algorithm? Very, very
common. We have basically a delta table and you jump the length of
the delta table. [08m, 14s]
I was doing some work on searching large text databases and I
wanted to search for multiple alternates... We were looking up in
the thesaurus; somebody was looking for something like apple and
what you do is you look up in the thesaurus for all the synonyms of
apple in different languages; pears and oranges and related
words... and you want to search for any of those in a single pass,
so you can do a thing called a multi-alternate BMG algorithm. And
that is a very fast way of doing that. [08m, 43s]
The very first rsync algorithm did in fact do that. It sent chunks
of data; what it did is divide the file into blocks and it sent the
first few bytes and the last few bytes of each block and the
checksum of the whole block. Then what it did is use this
multi-alternate BMG search algorithm to search for the beginning of
the block or the end of the block in the file. And where it found
that the beginning of the block matched, it checked: does the end
of the block also match and does the whole checksum of the block
match? In which case it says: we've probably got a block match.
[09m, 13s]
So in fact you're close; unfortunately it ends up being rather
slow. It does work, though, and rsync 0.01 did that, but it was
unacceptably slow. Because although multi-alternate search
algorithms are much faster than standard BMG-type algorithms,
they're still far too slow; we actually need a search algorithm
that's linear and about the same speed as a memory copy. [09m, 37s]
Okay... other ideas...
GNU diff takes the file and splits it into chunks after certain
terms and checksums each line and then searches for checksums which
match that line.
First of all, text based; not much good. The other thing is GNU
diff relies on the bandwidth between the two files being very, very
high. It's local. Both files are local. [10m, 04s]
But it could be done in a shifted fashion...
Not using the diff algorithm, no.
How about not using the diff algorithm directly, then...
This is what Xdelta is.
... you can send the checksums...
Yes, you can send checksums; what you'll end up with is basically
something like the rsync algorithm; you're exactly right, but as
soon as you have differing sized blocks, then you'll find that the
bandwidth requirements to get sufficient data to the other end for
the search algorithm will be massive. So those local differencing
algorithms can use differing sized blocks, right, they can use
carriage returns and things, but as soon as you go remote and
you're worried about the cost of sending the signatures, and the
cost of doing the search and things, you really have to go to
even-sized. [10m, 47s]
Okay, other ideas? [10m, 49s]
We combine the first suggestion of progressively doing like a
binary breakup of the file with looking for the blocks that we've
broken up and moving them.
So you could break it up into blocks on one end and on the other
end, you could look for it at different boundaries and not just the
block boundaries. Okay, that's getting closer. Yes, in fact you
want to look on every boundary. You want to look at every single
byte boundary at the other end. [11m, 13s]
Send back offsets, as in we found this, but it was offset this
far...
Right, you could, yes. But the problem there is still... sending it
back is no problem; the data format for sending it back... there's
many, many formats you could use; it's more the fact that it's an
N-squared... If you're doing your checksumming at every single
offset, then you've got a million different offsets in a 1 megabyte
file. You've got to do a million strong checksums; you're going to
be there all day. It's too slow. [11m, 51s]
So how do we make that faster?
How about a rolling checksum?
Right. That's exactly right and that's the core of rsync.
Basically, rsync combines a rolling checksum with a strong
checksum. The rolling checksum is not critical to the algorithm
except for speed. The rolling checksum is a filter on the strong
checksum, to make sure that you only run the strong checksum when
the rolling checksum matches. [12m, 21s]
Now for those of you who don't know what a rolling checksum is,
I'll start explaining that. In fact, I'll explain that now, then
get on with the rest of the talk. A rolling checksum is an
update-able checksum or update-able hash. Say you've got a buffer
here, you know in the middle of the air about there. And you know
the checksum of that buffer and you want to know the checksum of
this buffer, one byte along, where one byte has been added on the
end and one byte has been removed from the beginning. So you've
slid a little window along by one byte in a file. Now a rolling
checksum is a checksum where you can calculate the new checksum
from the old checksum with a very small number of operations. Maybe
three or four adds and a couple of subtracts and a XOR, or
something. A very small number of operations to get from a checksum
in this location to a checksum in that location. And that's called
the rolling property of a checksum. And that is the key to making
rsync efficient. [13m, 21s]
Okay, so let's have a look now, to answer that question: yes there
is a better way and the basic algorithm goes something like this,
although those of you who have been following the little
bit-windowing so far will now already know this and you can go and
look at one of the other talks. [The audience laughs.] [13m, 37s]
First of all, we do signature generation, and what we do is we
generate what I call a signature block for the old file. Okay, in
fact you can invert this whole thing and you can send the
differences in either direction. Either from the receiver to the
sender or from the sender to the receiver. There's two different
ways of doing it; I'm going to explain the one that is in the rsync
tool. The one that is in the rsync library, which is part of some
other applications of rsync, in fact does it everything in the
other direction, for various reasons that I'll get into later.
[14m, 07s]
Signature generation... we generate a signature block. Now the
signature block consists of a checksum; or you take a file of say a
megabyte and divide it into, say, six- or seven-hundred byte chunks
or kilobyte chunks, say, you know, chunks of about that size. And
you take two checksums on each block. One of them has this rolling
property that you mentioned. And the other is a conventional hash.
I use MD4, because I happen to have an MD4 routine laying around
which is nice and fast. [14m, 40s]
So you take these two hashes on each block and you bundle them up
and you put them all together, and that's your signature. The
signature is just the checksums of each of the blocks concatenated
together to be a lump. The overall size of this is about 1% of the
file, of the order of magnitude... there's various maths you can do
to work out the optimal size, depending on various assumptions
which are never valid, but the rule of thumb is about 1%. [15m,
11s]
The next part of the algorithm is the signature search. So you do
this signature generation and you send the signatures to the other
end, to the guy who's got the new file. Right, so you do the
signature generation on the old file, send those across. So you've
used one half of your round trip already. So I said, rather meanly,
to the first suggestion here, that I only wanted one round trip,
right, adding a condition to the problem, which is the classic way
of doing things. [15m, 39s]
So we send that and we've got one half of the round trip gone
already. So we've only got one send left and then we're done. What
we do then is that we now have to search for blocks from the old
file that are present in the new file at any offset. And that's the
trick. You have to find them at any offset at all, any byte offset,
because that way you handle arbitrary insertions and deletions.
Otherwise, you'd only handle block size. It'd be fine for VMS with
record-based filesystems, but it'd be terrible for UNIX, where
things tend to be byte-oriented. [16m, 18s]
Now that search algorithm uses this rolling hash and what it does
is it takes the hash and rolls it along the new file, calculating
the weak rolling hash checksum at each byte offset, looks it up in
a little hash table and if the weak checksum matches, the rolling
checksum matches, then it goes and calculates the strong checksum.
If the strong checksum and the weak checksum match, then you assume
you've got a block match and you've found a common block between
the old and the new file. [16m, 51s]
Then you've got a simple encoding mechanism to encode that
information back to the receiver, the guy with the old file. So we
can reconstruct the new file from this encoded data. Now what does
that look like? Let's have a look. So here's a bit of a diagram of
how this turns out. Now have we got a little pointer here
somewhere? No? I'll just use a finger. [17m, 16s]
What we've got is this is the old file sitting up there, file A,
and that consists of these chunks of data. Now I've just drawn them
with different hashes. So when, see this cross-hash goes this way,
down to the left, assume that this is the same as this one which
also goes down to the left. And this one here, which is a little
brick-like, is the same lump of data as that brick-like one over
there. That's what the little diagram is supposed to mean. It's all
very obvious, I hope. [17m, 55s]
Okay, so here's our new file and here's our old file and this is
the resulting difference, which gets sent over the wire. And the
resulting difference, the first block of the new file doesn't exist
in the old file, so we have to send it as literal data. We have to
send that over the wire, right, because that data does not exist in
the old file, therefore the information is not present on the
receiving computer. You've got to get it there somehow. It's
basically got to go over the wire. [18m, 30s]
There are second order things you can do, you can do things like
compression on this, no problem. Rsync does that if you use the -z
option, it'll compress that. And there's some tricks you can do to
make that compression go especially well and things. But basically
you've got to send it. [18m, 45s]
But this second lump of data in the new file is the same as this
lump over here, which is just in a different position in the old
file. Okay, so the search algorithm will find a match between this
little block here and this block here, and will emit a token. The
token is just an index into the indexing count or whatever you want
to encode it as, it's a RLL-type encoded, RLE-type encoded in
rsync, token which represents the match from the old file, the
location, which is saying to the destination: when you're
reconstructing this new file, shove out this little literal block
of data, then go and fetch token number 0123 from the old file and
shove that out. [19m, 39s]
Then we see, the next lump of data, this hash here, is the same as
that hash over there. So we send another token. Then there's
another token and and this lump of data is another lump of literal
data, that's that lump of literal data which doesn't exist anywhere
in the old file. So what we end up with is; the difference going
over the wire is alternately lumps of literal data and tokens
representing lumps of data from the old file. [20m, 04s]
Okay, so that's our difference. And we can generate that from the
searching for the signature blocks in the file, and that's all
fine. So it's not really that magic when it comes down to it, which
is why people work it out in a few minutes, and why it took me
several years. But it's very easy to code; you can code up the
rsync algorithm in a matter of a few hundred lines of code. You can
make it fast in not much more than that and so you should be using
it in all of your programs. [20m, 40s]
Okay, so let's go into it a little bit more deeply: signature
generation. The file is divided into uniform blocks on the
receiving end. Now it has to be uniform blocks if you want to make
this thing at all efficient. I'll let you think about that
yourselves. I know people here are already thinking: how can I do
it in non-uniform blocks, optimize it? There are ways of doing
non-uniform blocks, but only if you're willing to handle more than
one pass. Or you're willing to increase the amount of signature
data that gets sent over the wire considerably. [21m, 10s]
So, because of latency, those of you that have done that much
network programming will know that latency is at least as important
as bandwidth, if not more important. Particularly if you're in
Australia. And bandwidth really can be quite cheap but latency is
often a killer, and so I really wanted to keep the latency to an
absolute minimum. So I wanted to keep it down to one round trip
total. Of course TCP throws extra, you know with its windowing,
it's ACKs and all that, but at least because of the windowing and
the smarts in TCP, the costs of the extra round trips and things
aren't really that high. Whereas logical round trips up at the
algorithm level would be a killer. [21m, 50s]
A good demonstration of that is: if you look in I think chapter
three of my thesis, I've got a little table where I show the speed
of rsync-ing a thousand small files, like one byte files, versus
FTP, versus RCP. And rsync was like two seconds and FTP, (this is
over a modem) and RCP took up like the order of minutes. It's an
enormous difference. And that wasn't the rsync algorithm doing
anything, because it can't do anything on a two-byte or one-byte
file, it was the fact that it was saving latency; the fact that it
was using one round trip for all thousand files, rather than doing
one round trip per file. So a lot of the time when people find
rsync fast, it's not because of the algorithm underneath it, it's
because it saves latency. [22m, 35s]
Okay, anyway, it's divided into uniform blocks. On each block we
calculate two checksums, one of which has this special rolling
property. Additionally, we also calculate a whole-file strong
checksum. Why do we do that? To make sure we reconstruct the file
properly. Do we actually need that? You could have a bad link, but
we're already doing checksums. The first version of rsync didn't
have this and yet I can assure you that the first version of rsync
will not fail, it won't fail in the lifetime of this universe
anyway, except for bugs, there were plenty of those, but it won't
fail due to the algorithm. Why not? [23m, 22s]
[There is an unintelligible response from the audience.]
Yeah, that they're the same to begin with, the algorithm would be
very, very efficient. The difference would be just a bunch of
tokens and then run-length encode those and it'd be like four
bytes. So that's not a problem. [23m, 36s]
The reason the whole-file strong checksum is needed is so you can
cheat on the block checksums. We can use really short block
checksums. If you use something like a full MD4 for each block, 128
bits per block, then there would be no point at all in having the
whole-file checksum. Because you're already doing a 128-bit
checksum per block. Right, but 128 bits per block, 16 bytes per
block, is very expensive. That's a lot of checksum data. It means
you'd have to have large blocks in order so your checksums don't
swamp the link. So instead, what you do is you trim down the size
of the checksum per block; you make it really small. Which means
there's a probability, there's a small probability that the
algorithm will fail. You have to catch that. [24m, 30s]
And you catch that with the whole-file checksum which you can do at
the same time; you can calculate at the same time with nice caching
properties, etc. as you're doing the individual block checksums.
And that way you know when you've screwed up. [24m, 46s]
In fact, it turns out that it's extremely rare this is needed
anyway, because the rolling checksum is actually quite strong. It
doesn't need to be that strong, but it just turned out that the
algorithm I used, which is a derivative of the Adler checksum,
is... it's a 32-bit checksum, two 16-bit halves. It has an
effective strength of about 28 bits, which isn't bad for a rolling
checksum. There are better ones, though. Somebody at defense in
Australia has one with an effective strength of about 31.5 out of
32, but it's a lot more expensive to calculate. [25m, 19s]
Anyway, so you need this so you can use a small block checksum. The
current versions of rsync use a 16-bit block checksum, plus a
32-bit rolling checksum, giving you a total of 48; effective
strength of about 46. Which is still plenty so that none of you, if
you're running rsync all the time have ever noticed a resend and
using the strong checksum, but it's there because it will happen
once every, you know, hundred years or so. So you do have to make
sure and catch it when it does. [25m, 53s]
Okay, the signatures are sent to the sending side, obviously, and
the optimal size depends on the data. Although the dependency is a
fairly flat one. If you look at a graph of optimal size of the
signature size versus the total data transmitted, the efficiency of
it, it's a relatively flat graph. So you can play with it on the
command line of rsync with the -b option; rsync has got option-itis
quite badly. You can play with that if you want to, but you'll find
that it's a relatively flat graph except in some particular types
of data, when playing with that can give you massive improvements.
[25m, 34s]
Why do you use MD4; why not use something simple like CRC16?
Primarily as a PR stunt. When rsync came out, nobody trusted it.
Everyone said: it can't work; this is going to fail all the time;
the probability for failure is blah and blah. And there were all
these people saying it's not going to work. So me being able to
tell them that rsync failing is equivalent to breaking MD4, gives
them a nice, warm feeling in the tummy. The fact is that no one is
attacking the transfer, right. Because they're not attacking the
transfer, a CRC is ideal. And in fact I would have used a CRC if it
wasn't for the fact that users wouldn't have trusted it. [27m, 15s]
But you're right, from a mathematical point of view, a CRC would be
far more appropriate, but MD4 is actually very fast. It's quite a
bit faster than MD5; I already had one laying around that I'd
written for Samba, because you need it for the encryption stuff in
Samba; and it also meant that I felt very confident that I was
transferring the right data. That was particularly when I wasn't
using the whole-file checksum. I could now, for example, go to a
CRC per block and go to an MD4 for the whole-file checksum and that
would be fine, because then I can still say it's equivalent to
breaking MD4, but why bother? That is not the bottleneck and in
fact the bottleneck, when people use the -z option, 90% of the CPU
is in gzip, you know, the zlib library. [28m, 02s]
[The speaker calls on an audience member for a question.]
You talked about the possibility of failure being maybe one in a
hundred years...
Much, much higher than that. That is if... the probability of it
even needing the strong checksum. The probability of failure is
about one in 10-to-the-11th power years if you... I've got a slide
on that, but basically this universe will be long dead before the
algorithm fails. [28m, 26s]
[The audience member continues.]
How did you test that? How do you know the resend code works?
Oh, I know, exactly... well he's right, you need to test... code
that isn't tested is broken. Everyone knows that. If you haven't
tested your code, then it doesn't work. So what I did was I dropped
it back to a 2-bit weak checksum and I tried like 2-bit and 4-bit
and 5-bit and various ones which meant the probability of the
resend was much, much higher. And I got it to resend every hour or
so and that way I was able to test that the resend code does in
fact work. In fact I even did one of the releases of rsync:
accidentally had a one-byte, I think, because I'd left the constant
wrong from some experimentation. It didn't matter, though, you
know, it's just... anyhow. Yes, so maybe it actually got tested by
someone else, apart from me. Which is good, yes, deliberate, of
course. [29m, 15s]
So that's basically how it works and a failure probability, yes,
you can work out... There was a rather amusing e-mail I got from
one particular person worried about his data. He said: no, no, we
can't do this, the probability of failure is huge; it'll happen all
the time. And he had this great, long page of math; he said: if we
assume this sort of data and blah, blah, blah, math, math, math,
math... long page and at the bottom, it said it will fail at
approximately 10-to-the-49th power years. Oh, I suppose that's
okay. [The audience laughs.] I'm glad he still hit send, because
that was quite cute. He was actually off, his math was a bit off,
but it's a massive number, basically. The universe is thought to be
about 10-to-the-10th power years old and if you assume one million
transfers per second of a one megabyte file, constantly, then you
end up with about one in 10-to-the-11th power years, approximately.
So it's a big number. [30s, 12s]
Yes, there's a question over here?
Yeah, I was just wondering... when you see a failure in one of the
individual checks, what exactly do you do to recover it? Just send
the whole file or...
No, what I do is resend with the full 128-bit per block and I seed
the checksum differently each round, so I use a different seed for
the checksum algorithm. What I do is: with MD4, I put a seed at the
front of the MD4 and MD4 hashes the data plus the extra seed at the
front. Even if there was some particular failure mode of MD4 in the
block algorithm, it's going to be a different seed every time and
the only way you can tell is you see the file name twice. [30m,
55s]
But the filename twice can happen under other circumstances; if
you've seen this happen, it's almost certainly because the file
changed during transfer. Rsync does no locking. Which means that:
if you are modifying a file while it's being transferred, then
probably the checksum will fail and it'll go round again. And if it
goes around twice, and it still fails, then it prints a message
saying; Error, checksum failed, file changed during transfer? And
it's probably a file like a log file that's being constantly
updated and so the checksums didn't match because it's never going
to be able to get it exact; it means that what you've got on the
other end is something which will approximate some snapshot of the
file, but because it's not doing any locking, it can't guarantee
that it's got a particular snapshot of the file, because you can't
have an atomic read of the whole file. [31m, 49s]
Why is there no locking?
Because nobody's submitted a patch for locking yet. It doesn't do
locking for a number of reasons. Locking is cooperative in UNIX and
has to cooperate with some other locking scheme... which locking
scheme? I could flock() it, I could do something like that. What do
I do if it's locked? Do I then block the whole transfer? And then
people use this in cron, etc. What I'm thinking of doing for a
future version is having a locking option, --locking=flock,
--locking=mailbox, --locking=something, you know, various schemes
and you can drop in different locking schemes if you want to. If
you're silly enough to use mandatory locks, you could actually make
it work properly. UNIX doesn't really use much locking and so UNIX
tools don't tend to lock stuff. cp doesn't lock and other tools
don't lock, but you're right that it could be nice in some cases to
do locking, particularly if you're transferring known types of data
when you know the locking-style of that data, like mailboxes. [32m,
54s]
What I tend to do for mailboxes, in fact all of my mail gets
delivered and sent using rsync, I've got an rsync-based mailer;
it's a tiny little shell script. It's in /pub/tridge/misc on
samba.org... about a couple hundred lines of shell and it does
send/receive SSH transferral. It's actually nice stuff, a nice
little mailer. Anyway, plug number... And it uses that, what it
does is inside the rsync, it calls the movemail and that of course
does the right locking stuff, atomic and... you know, wondrous
things. Okay, that's that. [33m, 36s]
Some of you may not realize, you can actually do a lot of things
with the rsync option -i, as I mentioned earlier. One of the cute
things you can do... people get asking about things like: please
can you add an option to rsync to run this command on completion?
Well, no, because you can do that already. There's the rsync path
option which says where to find rsync on the remote end. Now the
thing on the remote end only has to look like rsync, it doesn't
actually have to be rsync. So it can be a shell-script wrapper that
runs rsync in the middle, checks the error code and does various
things at the end. And that's how my mailer works. Therefore you
can run arbitrary commands on (the completion of rsync) the
successful completion of rsyncs, by using the rsync path option to
specify a program other than rsync that happens to call rsync and
send it to standard in/standard out at the other end. So anyway,
those of you that like playing with shell scripts might like that.
[34m, 38s]
The actual rsync program has a bunch of other features that make it
a useful tool, which are completely orthogonal to the algorithm.
Particular things... latency-saving design, I spent eight years
studying from the other end of a modem from where all my data was,
and so I tended to worry about latency and often my stuff was on
the other side of the world as well, so I really cared about
latency; it really cares a lot about latency. Fancy file list
handling, excludes, skipping files, that sort of thing. [35m, 11s]
SSH support, people seem to like that a lot, it's very useful at
getting you secure transfers. And thank god OpenSSH now has finally
got non-blocking I/O. That was a major pain with rsync, the
blocking I/O and various bugs with pipes in kernels of various
operating systems and things. Finally, OpenSSH 2.1 and above does
non-blocking I/O which means rsync works much better. So if any of
you are using rsync over SSH, then grab the latest OpenSSH; things
work a lot better, a lot more smoothly. [35m, 43s]
Daemon mode... rsync is now becoming quite a common distribution
tool for various places. A lot of sites that have FTP sites also
have rsync sites. And it sort of exports shares and that sort of
thing. [35m, 47s]
Incremental backup is one that people aren't aware of. Rsync
actually can be used as an incremental backup tool. Including doing
like rotating backups and all sorts of things like that, using the
--backup-dir option. I should put up some more examples of that on
the rsync site. We use it for all of our backups; we have a backup
server in the office and rsync has built-in the capability to say:
okay, update this remote directory as a backup, but any of the
changed files, deleted files, put them in this incremental
directory. And that way you can have a seven day rotating backup
and that sort of thing, which is quite useful. But a lot of people
aren't aware of that. [36m, 35s]
And in all of this stuff, the significance of the actual underlying
signature algorithm, search algorithm, really has been lost. (Now,
don't know how much power I've got left in this; don't want it to
embarrassingly turn off in the middle of the talk. Oh boy! Power.
Where's the plug? I'm about to lose... I'd better suspend. Great.
Right, saved! I hope. Battery charging... yes. Zero percent. We
just made it. Okay, that was close. There was this light flashing;
I wondered what it meant. [The audience laughs.] I just got this
laptop...) [37m, 31s]
Right, other uses for the algorithm. Rsync is starting to get used
in a few other places, which is really good. I'm hoping that it's
going to be used in a lot more places, though. Perhaps the most
important one is rproxy, which is embedding rsync into the HTTP
algorithm. And I'll talk about that in a second. Then there's also
an effort under way to embed rsync into CVS. Rsync as part of a WAN
filesystem is one of my favorites. And rzip is something I
developed just out of academic interest; it's a very good
compressor. It does much better compression, particularly for large
files, than anything else I've seen. But it's extraordinarily slow;
really, really slow. But if you really need that extra compression
and you've got a few weeks to spare, then you know, it can be
good... hours, anyway. [38m, 26s]
So lets talk about some of these a little bit to give you some idea
of the sort of things you can do with this. Rsync in HTTP is one of
the most important ones. And that's nearing the point where it's
ready for release. It's a thing called rproxy. And it's being
developed by another guy at Linuxcare in Canberra [Australia]. And
what this does is basically, think of the history of the Internet,
the web, you know, of course the Internet is the web. Think of the
history of the web. Basically, we started off uncached; everyone
just had a browser, so you know the old browsers. Then caches were
invented because it made things much faster. And then CGI came
along and everything got slow again. Basically, one of the big
problems is there's massive cache infrastructure worldwide. Right,
people have Squids everywhere and hierarchies of Squids and NetApp
caches and all these sort of things. The problem is that they're
all completely useless for dynamic content. And yet the world is
moving towards dynamic content at a very fast rate. [39m, 26s]
Probably by volume of data transferred, the majority of the data on
the web is already dynamic. Or at least it's getting that way. So
how do we solve this? Well what we can do is you can actually,
there's a couple of proposals to solve this; some people are
proposing to, in the markup, in the HTML or XML itself, you markup
sections that are static and sections that are dynamic, etc. The
problem is web site designers are inherently lazy, or brain dead or
something... something about them. If we can't even convince
website designers not to put four megabyte images on their home
pages, how are we going to convince them to put in the markup
sections for dynamic and non-dynamic and get them right? It's too
much effort. We really have to do it in the tools, so it just
happens. I don't think those markup things are really a practical
solution, for the wide range, really big use. [40m, 23s]
The other types of solutions... there's a solution being proposed
at the moment, HTTP delta. Unfortunately, it really relies on
storing outgoing pages. Having some sort of database or repository
where you store all pages that you send, so that you run a diff,
then they send a tag ID to say which page they've got in their
cache, and then you can generate a difference. The thing is, I run
a fairly large website myself and I just don't like the idea of
every page I send, I have to store on local disk. Because I send a
lot of pages. And you know, storing all of those pages would be a
great pain. [41m, 00s]
So what rsync and HTTP does is it solves the problem by allowing
only the differences to go over the wire, without having to store
the old files. Using this exact same algorithm. So what you do...
it has all of the nice features... it builds on the existing web
infrastructure. You know, sounds like a sales pitch. All of the
content is cacheable, whether it's CGI, whatever. Any content
becomes cacheable and there's no extra round trips. Because extra
round trips would be deadly. We've got enough of them already with
TCP handshakes and all that. [41m, 32s]
So what you can do with rsync and HTTP is... imagine the client has
a cached file. Let's assume we haven't got a chicken and egg, we've
already got a cached file there; we've cached some CGI file, okay.
The client generates the signature from that cached file and adds
it to the request as an rsync signature header. In the request for
the... re-requesting the same page, it adds this header; it's
BASE64 encoded or whatever. Then the server generates the page as
usual, so the server runs its usual CGI generation stuff, then just
before it goes on the wire, it says: oh, did the incoming request
have this rsync signature header? Oh, it did, then I can generate a
diff. Because it can use that signature plus the new page to
generate the diff from the old page. Because it doesn't need access
to the old page to generate the diff. The signature will do the
job. [42m, 34s]
So it generates the page as usual, does the checksum search, and
generates the rsync differences, then it sends the rsync
differences as content-encoded rsync and (decodes it to give the
new page,) sends it back to the client and the client decodes it
and shoves the new page in its cache. And this actually works, it
works very nicely and I get massive speed-ups; I've been running
this for a little while at home, across my modem link. I run it for
the last hop over the modem. Now I've got ISDN, so I haven't
bothered running it for a little while, but it reduced the traffic
over my modem link for web surfing in general over a two-week
period by 90%, which is a fairly large reduction. [43m, 15s]
The fact that I throw gzip over the top of it as well helped, you
know, it got some of that. But a fair bit of it was in fact the
improvements from the algorithm. The rproxy project is a project to
do this properly; I just did a rough prototype. And Martin Pool,
who's been working on Apache for quite a while, is now working on
building this into Apache and doing it as a separate proxy plus
possibly doing patches for Mozilla. Though we haven't started
looking into that yet. And also doing patches for SQUID. And the
idea is that eventually, you have it in your SQUID server, you have
it in your web server, and then you end up just sending differences
for CGI pages between the web server and your local SQUID. [44m,
03s]
The advantages of doing that, of course, is that if your browser
doesn't understand this extension, you still get the benefit.
Because the way we've organized it is that you get the benefit
between the two furthest points in the HTTP chain between the
client and the server that understand the extension. So if the
server and your SQUID both understand it, you get the advantage; if
the second-level SQUID and the first-level SQUID understand it, but
the server and client don't, you get the advantage for the hop
between the two Squids. So if you've got some slow link or
something, you can put one of these over it and reduce the data
going over that section. [44m, 40s]
[There is a comment from an audience member.]
It seems to me that this really only benefits dynamic content, it
seems to me that it benefits transcontinental, transpacific proxy
caching efforts, but really doesn't do anything at all for the...
in fact, it doesn't even for pages that are static or mostly static
and change weekly or something like that. But it doesn't really
even... My impression is that the bottleneck for most of those
dynamic content is that those CGIs are just too slow and they
just... [45m, 15s]
No, no, no. If you have a look at something like... if you go to
something like CNN.com, the page remains exactly the same every
time except for about 8 bytes. They have this little ID that ticks
over on every page, okay. Which means that with current technology,
you're resending that 150KB every time. Now the generation of it...
you can solve the generation problem by just getting a faster CPU.
But it's relatively cheap to get a faster CPU, or just get more of
them, have a farm. But it's harder to get a faster network link.
What this does is it allows you to trade off between CPU speed and
network speed; this costs you some CPU speed... it's actually quite
fast, you can saturate a 10 Mbps network quite happily; with a fast
enough CPU, you could saturate 100 Mbps. But if you've got a bit of
CPU around to spare but you haven't got a particularly fast network
link, then you can use some of that CPU to reduce the amount of
bandwidth you need. [46m, 08s]
Do you see it over a 28.8Kbps modem, or any high latency link?
Come and live in Australia for a while. [The audience laughs.] It's
not for everyone, you don't want to use it on an intranet, it's
just going to be a waste of CPU on your intranet. But there's an
awful lot of places... I've heard that a lot of people in the US
have DSL; something like 30% of households have access to DSL, or
could have DSL if they wanted to in the US. It's like 0% or close
to it in Australia. But the other 70% could benefit from this sort
of thing. You know, getting that last mile to the end-user. This
could actually benefit quite a lot. Okay, so, and of course you
don't have to turn it on, it's just a feature. [46m, 56s]
Rsync and CVS... Ben Elliston is working on that. Hopefully, it's
going to be done any day now for the past several months. It's that
kind of project. [47m, 05s]
Rsync and a WAN filesystem, this is quite interesting. You can
combine rsync with lease-based filesystems to do the... You combine
rsync with a WAN-based filesystem. Now lease filesystems, it's a
bit like the stuff in NFSv4 where basically the client can take a
lease out on the file and do write caching and read caching on the
file. [47m, 39s]
Now imagine you had a WAN filesystem, a global filesystem, where
you're reading your mail from a machine in the US and you're
sitting in Australia. And you load your 10MB mailbox, you subscribe
to Linux Kernel [Mailing List], so you've got this massive mailbox
and you bring it up, then you delete one message out of it, then
you save the mailbox again. [48m, 07s]
Now with normal network filesystems, what you would have to do is
send that whole 10MB file, chug, chug, chug, chug, chug, back to
the server, because you've written a modified file. The length has
changed, everything has changed about it. Right, but if you've got
a lease on the file, then what will happen is those writes will
initially go into the page cache on the client. So in the page
cache on the client, you have the new file. In the page cache on
the server, you will have the old file. So you have two lumps of
data and a low-bandwidth, high-latency link between them. What do
you do? You synchronize the page caches between the client and the
server using the rsync algorithm. What that means is that what goes
over the wire is just a few bytes, because it says: oh, all of this
part of the file is the same, and all of that's the same, and
there's these few bytes that are missing. [48m, 55s]
Notice one of the things, I didn't point this out earlier, about
the rsync algorithm that are very different to diff. Diff only
handles insertions and deletions. Have any of you noticed that if
you move a routine in a file, then you send the diff, what it does
is says minus, minus, minus this one and plus, plus, plus that one;
if you use ed-style diffs it just says edit out this bit and add
that bit. It repeats the whole chunk in its new location. That's
because it can only handle inserts and deletes. It encodes
everything in terms of inserts and deletes. Whereas if what you
actually have is a move of a lump of data in the file, you can't
encode that with a diff-style algorithm. Rsync encodes that as a
move. Because it just says: this token is at that location. So you
can handle arbitrary moves. Which is particularly good for remote
filesystems if you've sorted the file or done something weird to
it, you've moved a chunk of data around and resave the file, it
will encode that. It also handles binary files quite well. The
thing about gzipped files, if I've got a second, I can tell you
about those... Question? [50m, 02s]
[The speaker calls on an audience member for a question.]
The brand new filesystem there...
It doesn't exist yet...
but in theory, though, there's a significant problem. You're saying
updates to the file are maintained in the page cache and I presume
the rsync algorithm updates to the fileserver occur when the file
is closed...
Or when it's flushed. Typically with lease-based filesystems, you
flush every 30 seconds or minute or whatever. [50m, 25s]
Okay, so even if the file is still open...
You're worried about turning off the power and losing it...
No, I was more thinking if you make so many updates between fopen()
and fclose() that you fill up your page cache...
Hang on. But if the data is in memory, right... now it doesn't
record the changes you've made. It's not like... there are other
algorithms; there are other systems and what they do is they record
all the edits, then they send the edits as an edit list, which can
become infinitely large if you made a large number of edits. That's
not how this works; it's when you save the file you've got the
whole file as the new file and you've got the old file at the other
end. You don't have a list of edits available to you. To have the
list of edits, you need to instrument all of your applications; you
don't want to instrument your applications. So you've got this lump
of data on one end, the new file, you've got the old file as a lump
of data on the other and all you're doing is using this as a fast
way of getting the old data to equal the new data. [51m, 26s]
[The speaker calls on an audience member for a question.]
So it sounds like an interesting application would be rsync-diff.
The thing is that contexts are a problem. You can't get contexts.
[51m, 39s]
[There is an unintelligible comment from the audience member.]
That's Xdelta. Have you seen Xdelta? Xdelta is an rsync-inspired
delta algorithm; it's a very nice delta algorithm. It works really
well on binaries. It works really well... and produces very small
differences. It was originally based on the rsync algorithm. The
thing is, since it's a local differencing algorithm, he's got high
bandwidth between the old and the new file. So he was able to tweak
it and tweak it and tweak it and tweak it and now really it's
nothing like the rsync algorithm. It's really just inspired by it.
And if you want a local differencing algorithm, use Xdelta. It's a
hell of a lot better than using a local rsync because he knows that
both are local, he can do all sorts of tricks to make it really
fast. In fact, it will give approximately the same differences as
if you had run rsync with the -b4, block size of 4 bytes. [52m,
31s]
[The same audience member asks another question.]
Well what if I were doing a cvs diff from a remote repository?
Ahh, well that's where we are building it into CVS. Inside CVS
there is a file send operation and the file send operation on the
other end you have the best guess of the old file. It doesn't have
to be the old file; it just has to be your best guess at it; the
last revision or whatever. Then what you do is inside the file send
method, inside CVS, you go file send rsync method; you don't call
out to rsync, you just call the library and that's what Ben's
adding to CVS. [53m, 09s]
I'm surprised the client doesn't diff locally in local mode.
It's got both files then and runs diff.
Yeah, and that's what Ben's adding. He's adding it... it helps
annotate, it helps commit, it helps diff, it helps anywhere inside
CVS, if you do a cvs -t (trace), when you see sending file blah.
Those bits get sped up. [53m, 31s]
[There is a question from an audience member.]
Any special issues in copying directories to directories?
Well the rsync tool has all sorts of options; does recursive and
knows about symlinks and directories and devices and inodes and
rsync is quite commonly used... In fact, I did an install when I
changed hard disks on my laptop, from one hard disk to the other,
with just rsync from / to / and then boot, I just had to run LILO.
So it will handle all of the different properties. It will do
devices and all those sort of things. And it knows about directory
hierarchies and hard links and all that sort of stuff. The hard
link support is optional; you have to add -H, and it's a bit slow;
the algorithm for doing hard links is a bit horrible. But it knows
all about directories and things. [54m, 24s]
Is all of that stuff obvious when you think it through, or...
No, there are some tricks to it. The main thing is latency-saving
tricks. If you've got a whole tree of a million files, you don't
want a million round trips. You don't even want one round trip per
directory. So what it does is, in fact, one logical send for the
whole tree. One logical send of a stream of signatures and in fact
there's three processes; it forms a little triangle of processes.
[54m, 48s]
We've got, at one end of the link, the generator and the receiver;
and the generator is generating signatures on the tree as fast as
it can and stuffing it down the link. The sender at the other end
is receiving those signatures and is generating the differences and
is sending it back to the receiver at the other end. The receiver
is having differences thrown at it as fast as it can and generating
new files. [55m, 07s]
Which means the whole thing is one logical trip pipelined for the
whole tree. Which is why rsync works really well for large trees.
Because of latency saving with small files. Also, the way it
encodes the file list, transferring the file names, it has various
tricks. It ends up encoding them as approximately ten bytes per
file, including all of the various size information and things.
Like it has a bit to say that this is the same device number as the
previous file. It has a byte which says how many bytes are in
common with this filename and the previous filename. [55m, 41s]
That sort of thing, so it packs it and compresses and this sort of
thing. So there's various ticks in there. I went a bit mad,
actually, and tried to save every bit. And it was a mistake.
Because several people have asked about making this an IETF
standard and doing some sort of RFC and that sort of thing. The
format on the wire is too horrible to put in a document. Because I
tried to save every bit. When you save every bit, you end up with a
very specialized format and it was like rebelling against the SMB
protocol. You know, I was doing something completely different. But
instead what I'd like to see, if we're going to make anything a
standard, I'd like to see a new tool developed on top of librsync
which is much, much cleaner, but uses a sensible encoding rather
than this saving every bit encoding. [56m, 27s]
[The speaker calls on an audience member for a question.]
Compressed data, stream compressed and block compressed data; how
does rsync work on those files?
Okay, compressed data. Basically the rsync program works fine on
compressed files, the actual binary works fine, but the rsync
algorithm is not very efficient on compressed files. And the reason
for that... it depends on the type of compression, but most
compression algorithms... if you change the first byte of the file,
then every byte of the compressed file beyond that point gets
changed. Now there's an easy workaround. (You could just send the
whole file.) [57m, 07s]
In fact there's two workarounds, one that everyone tends to
suggest, is why don't you uncompress the file, send the compressed
differences of the uncompressed file then re-compress at the other
end. And the reason I don't do that is: sure you will get the right
uncompressed data at the other end, but you won't end up with an
identical compressed file because you won't necessarily have the
exact same revision of zlib at both ends. A different version of
zlib will decompress the file with no problem, but it'll compress
it differently. It'll have different options; it won't necessarily
produce the same compressed stream. Which means sure you will
transfer the correct compressed data, but the MD5 checksum of the
two files may not be the same. And that is a problem, because if
people started using rsync to distribute RPMs, and they come up
with a different MD5 checksum or tarred gz after the transfer,
everyone would lose faith in rsync. [58m, 02s]
So there's a way you can get around this, but it requires a small
tweak to gzip or bzip or whatever the compression algorithm is. And
the gzip one is easiest to explain. Gzip has a 32K buffer, a
history buffer. Now gzip uses dynamic Huffman encoding, which means
if you change one byte in the file, everything after that point in
the file changes in the compressed data. Problem; that means of
course that rsync will be terrible, unless, of course, the change
is toward the end of the file. [58m, 31s]
But what you can do is inside the gzip algorithm, you keep a
rolling hash... (We've got an earthquake, have we? [The chandelier
in the ceiling is shaking.] A truck, okay.) Inside the gzip
algorithm, you maintain a rolling hash of the last say hundred
bytes or three hundred bytes, or whatever number of kilobytes. In
fact, ten kilobytes would probably be optimal. So the last ten
kilobytes rolling hash and you roll that along while you're doing
the gzip. Now whenever that rolling hash equals a particular
number, and zero is a good number, then you reset the internal
compression tables of gzip. [59m, 11s]
What that means is that the differences don't propagate more than
ten kilobytes on average. So what you end up with... that's if
you're using a ten-bit rolling hash... a ten-bit rolling hash would
mean it's one kilobyte, but whatever... twelve bit, eleven bit,
whatever. So it's a tiny tweak to the gzip algorithm and is one
I've been meaning to submit to the gzip maintainers and the zlib
people to basically make gzip rsync-friendly. And it doesn't affect
the compression ratio much at all. Very, very small difference in
the compression ratio. But it does mean that you've got a fifty
megabyte .tar.gz file and you've got a different version of that
.tar.gz file, then rsync will do very, very well on that. And it
will end up with a very small transfer. So that's a proposed
change. [60m, 06s]
In the case of bzip, you do the same thing, but with a longer...
what you do in bzip is you select a block size; normally you select
on the command-line. Normally, it's 900K. In fact, -9 means 900K,
-n means n times 100K. What you do is you set the... you keep a
rolling hash of about the length of that block size and you
basically... you restart the blocks; you have to do a larger block
in that case, so it would only be useful for really big files. Do a
larger block and you reset the bzip tables when the rolling hash
equals zero in each case. And you don't... when you do that, you
don't keep your dynamic Huffman tables between blocks. [60m, 52s]
[The speaker calls on an audience member for a question.]
You talked earlier about how you were doing the hierarchy, you
treat it as one big thing; does this mean you can actually cope
with when a file gets renamed?
Coping with files that are renamed is partly in there; it's called
the fuzzy option, --fuzzy. It's in the CVS tree partly; it's
broken, it doesn't work yet. I started coding it a few weeks ago.
The idea is to cope with renames so... it's for Debian trees and
that sort of thing. I should call it the --debian option. [The
audience laughs.] Where basically, you put out your .deb files or
your source files or whatever and the filename changes every time
you put it out and so what it does... I've got various heuristics
for finding the closest match filename to use for the signatures.
And it looks first in the current directory for files with at least
six characters in common and various other stupid heuristics. And
the idea is it will find files that are similar named that have
been renamed. [61m, 51s]
If you want to actually handle arbitrary renames, it's very
expensive because you need to be able to search for the signatures
across all of the directories. It's an N-squared problem... and
it's expensive. But handling renames to similarly named files is
easy or doing on the command-line, if you have an option to say
this file equals that file. In fact you can handle renames now if
you want to do it all on the command-line, you can just say rsync
this file to that filename. And it's perfectly happy to have
different filenames on either end. Is that what you were asking
about? [62m, 23s]
[The audience member continues.]
No. I must have misunderstood how you said it works, because I
thought you treated it as if it were one large file...
No, I don't treat it as one large file; it's just that I pipeline
the signatures from each of the individual files. [62m, 36s]
[The speaker calls on another audience member for a question.]
What if when you transferred files reversibly, you made a tar file
of the directory and transferred that?
You could indeed do that, but it wouldn't give you the nice
properties. It would take an awful lot of disk space at the other
end to store the tar file then unpack it. The way rsync works at
the moment, the destination file is created as a temporary file, a
dot file, then it's renamed atomically at the end over the file.
You can rsync tar files. And in fact in my thesis, that's what I
did. If you look in my thesis, all of my results are for rsync-ing
of tar files. And the reason for that is that all I was interested
in was the algorithm, not all of the associated garbage of
directory handling and all that. So to get rid of all that, I just
transferred one file. But I wanted it to be a realistic file, so I
did tar files of the Linux kernel and emacs and things like that.
So in fact, doing tar files is perfectly sensible. Although don't
make the block size 512-bytes; you get various things with tar
files at 512-byte offsets. [63m, 35s]
[The speaker calls on an audience member for a question.]
Another interesting thing you can do in the rename situation is you
can use the inode numbers.
Right, yes. Indeed I could do that; I hadn't thought of that. [63m,
48s]
You could look first at this magic inode table...
Yes, yes. But the, hang on... Which inode number are you going to
match, because you don't have the old inode if you're doing it
between two machines.
The master file on that side.
But if you've got the master file on the same... you would have had
to have cached the... you would have had to have done an ls -li
previously and stored that somewhere. You don't have the old inode
number. [64m, 20s]
You had to scan the tree anyway and look at all of these files.
You have to scan the tree on one machine; you have the new scan
tree on both machines. You don't have the old scan tree on the
destination. Which means you don't have the old inode number.
You would have to be fuzzy on the opposite side...
You would have to have some forethought and the administrator would
have had to do an ls -li and stored the inode numbers somewhere.
[64m, 45s]
You could extend the rsync protocol to send them over...
I do send inode numbers when I'm doing hard links. If you use the
-H option, it sends device and inode numbers, because that's how it
detects hard links. [64m, 58s]
[There is an unintelligible comment from an audience member.]
I'm not... maybe we should talk about it after... I'm not quite
sure that works. [65m, 08s]
[The speaker calls on another audience member for a question.]
How well does the rsync algorithm work for really huge files? Does
it still use about 1% of the file size?
What you do is... the optimal... it works fine for big files.
Optimally you should scale the block size as the square root of the
file size. In practice, I scale it linearly with the file size. And
what happens is as you get a really, really big file, you get a
really, really big block size which means you don't see small
matches between the two files. And the reason I scale it like that
is because I like the fact that rsync with its default options will
never be worse than 1% over sending the whole file, okay, because
the signatures are approximately 1% of the data length. Whereas if
you scale it according to the mathematically optimal, which is
approximately the square root of file length, then the problem is
that the worst case becomes quite bad in the case of large files.
[66m, 08s]
You can end up with quite a large percentage over the case of just
sending the file. But you can tune that on the command-line. There
are some cases where people are doing very large DNS, you know,
millions of machines type stuff zone files and they're doing lots
of updates on them and for example, you might want to set a smaller
block size than the default because... If you know something of the
structure of the file, and you know that there are records in the
file of approximately n-bytes in length, approximately, then
setting the block size a little bit smaller than n is a good idea.
[66m, 41s]
I guess my question was more related to the amount of RAM you
require to do the file send. Does it always require 1% of the file
size?
No, it rolls along the file with a windowing thing; it doesn't
require... it does require storing the signatures, but because it
scales linearly, it has an upper bound on the memory it will use in
that case. The main problem with the memory use of rsync is holding
the file list. Because of the way I designed it... I didn't really
design rsync for being used in the case of hundreds of millions of
files with four megabyte machines, but people are using it that
way. [67m, 14s]
And the problem is that the internal storage... I store the whole
file list and sort it, because it's really convenient, having a
sorted file list for a number of reasons, particularly hard links
and things. I sort the file list, so I have to store it in memory
and because of that... and the internal format uses approximately
100 bytes per file, so if you have a million files you are
transferring, then it requires 100 megabytes of RAM, approximately,
internally. Now that's expensive. On the wire, it only costs about
10 bytes per file, but I use an unpacked format for fast access in
memory. [67m, 52s]
Now I'm planning on fixing that; I posted something about 18 months
ago, a year ago or so, to the rsync mailing list of how I can fix
this and it's a bit involved, but you can have a look on the rsync
mailing list; there's a link to it on the rsync home page. There's
a way around this, but unfortunately, it's fairly involved, which
is partly why I've been avoiding doing it thus far; I've also been
busy with various other things. But yeah, the memory usage is
primarily in the holding of the file list; the size of the files is
basically irrelevant to the memory usage of the program. Your page
cache of course will be hit badly. [68m, 24s]
[The speaker calls on an audience member for a question.]
I'm just curious with the renaming problem again; if you were to
just send a file list at the beginning followed by a huge block of
data corresponding to the contents of all the files... would that
not just automatically solve the problem?
Think about the order of magnitude of the problem of matching
signatures to files. [68m, 47s]
Well it would be equivalent of just sending a large tar file except
you...
No, it's not. You also need a bigger block size to make it
efficient. There are various things you can do, but none of them
are particularly appealing. [69m, 05s]
[There is a comment from another audience member.]
There's a conflict here on the one hand of trying to send millions
of files and do that efficiently in terms of overhead, and on the
other hand, the desire some people have of sending a data
distribution list of RPMs where there's only a thousand files and
handling renames. [69m, 27s]
Yeah, you're right. In the case of a thousand files, you could have
an algorithm that could do much better with renames and yes,
handling renames is something I do want to do, partly because of
the stuff Steven has been doing with his apt-proxy stuff, where
he's actually done an rsync-based apt-proxy system. And look for
it; I think it's called apt-proxy, isn't it Steven? Where are you?
Yeah, he was not listening... [The audience laughs.] Have a look at
freshmeat.net apt-proxy; handling renames and stuff like that would
be cute. [69m, 59s]
The last few minutes, I'll just get on with rzip. Rzip is the
compression algorithm. This is primarily of academic interest. But
it's quite nice as far as the compression ratios it gets. Rzip is
an rsync-inspired compression algorithm, but it's not exactly the
rsync algorithm inside it. But it has a lot in common with the
rsync algorithm. Originally, it shared a lot of code, and then it
didn't for speed. [70m, 20s]
But it does give some very nice results. These are the compression
ratios on various files... a particular version of emacs (you can
get the versions out of my thesis), a particular version of Linux,
my development home directory for Samba (so it's got lots of
different versions of Samba in the same (home) directory), and a
mail archive. I collected spam from a 24-hour period on samba.org
and notice, it's 84 megabytes. [The audience laughs.]
Unfortunately, samba@samba.org made it onto some spammer's CD-ROM
and so every spammer in the world hit us. And it was really quite
awful. So this was the collected spam from a little period. [70m,
57s]
Anyway, it compresses very nicely. People told me that compressing
spam was really easy; rm does it beautifully. [The audience
laughs.] But anyway, if you do want to keep it for various analysis
purposes, then this is great. So these are the compression ratios.
Now notice that rzip wins in all cases. In some cases, rzip wins by
a long, long way. [71m, 16s]
For example, my home directory, my development area, my Samba
development area; gzip gets 3.50 compression ratio, bzip2 gets
4.78, rzip gets 8.93. Now if you know anything about the
compression literature, you'll know that getting like a ten-percent
improvement over something like bzip is considered good, getting a
factor of two better is considered quite extraordinary. [71m, 39s]
The reason is that rzip, taking advantage of the rolling checksums
and things, can use a massive history. gzip uses a 32K history;
bzip, by default, uses a 900K history; rzip, by default, uses a 250
megabyte history. Right, so say you're backing up home directories,
/home on a big system. And two people have got checked-out copies
of the Linux kernel. And you rzip a tar file of /home. Then when it
comes to the second copy of the Linux kernel tree, a hundred
megabytes after the first one, it will say: oh, it's the same as
this one back here with these small differences and a few bytes go
out. [72m, 22s]
So it can find matching chunks of the order of hundreds of
megabytes, going back a quarter gigabyte. And in fact you can make
it more than a quarter gigabytes with some tweaks. And the way it
does this... it's a bit like floating point; normal gzip-like
algorithms... they're basically offset-length algorithms; they're
based on: here's a match at offset this in the history and this
length of match. Well what I do is the offset has a mantissa and
exponent portion. Which means it is offset 2 to the power of this
plus this. The rzip algorithm uses the rsync rolling checksums to
find the matches. [73m, 09s]
And it's very, very, very slow. But if you need to compress really
big files, and you think there's a lot of common data in it, like
/home or spam file or something, then rzip is probably good for
you. And it's available in the rzip CVS here. I've never released
it to the world because it really is of academic interest,
primarily. I've just told a few compression places about it, but it
is available under the GPL if anyone wants to use it. [73m, 34s]
[The speaker calls on an audience member for a question.]
How's the decompression speed?
Better than the compression, but still not good, but primarily
because it's lousy code, it's academic code. [The audience laughs.]
It's written with instrumentation and things in it. As an example
of what I mean by academic code in this particular case; it has
built-in to it a bzip-like, because it uses bzip as its entropy
encoder on the back end. My implementation of bzip is 50-60 times
slower than the one in bzip2. It's that sort of code. It's code
that's clear but not particularly fast. So if anyone wants to speed
it up, they can, but speeding up the compression to be actually
acceptably fast, I think would be a hard task. [74m, 17s]
For more info on rsync, you can get it at rsync.samba.org;
rsync.org isn't my site. I have no idea what it points at...
apparently there is an rsync.org, but anyway, somebody's grabbed
it. [74m, 32s]
linuxcare.com.au/rproxy if you want to hear about the rproxy
accelerator
My home directory has got a copy of my thesis and things. There's a
tech report about rsync as well. Don't read the tech report. Read
the thesis instead. The thesis is clearer and more accurate. The
tech report, we wrote when Paul and I were only just started
working on this stuff. And Paul Mackerras is my supervisor at ANU;
we worked on this stuff a bit together. So the thesis is a far more
readable and accurate description of rsync. [75m, 01s]
And if you want to check out some of the code that isn't released
yet, like rzip and the latest version of rsync, then go to the CVS
area on samba.org. [75m, 11s]
[The speaker calls on an audience member for a question.]
A while ago, I think, you had some musings about problems of
synchronizing many millions of files when there were not too many
changes. I guess you had some plans for some kind of a
hierarchical...
Yes exactly, that's what I described earlier when I said of the
ways of reducing the memory and improving things for certain common
cases. People were starting to do things like rsync export
mirror.arnet.edu.au, this massive FTP site is equivalent of metalab
in Australia, and exporting the whole tree and the load on the
server was quite high when you start an rsync of the whole tree.
And additionally, the memory requirements are far too high. [76m,
01s]
And it can be fixed. I just haven't fixed it yet. Hopefully, I'll
fix it soon. I'm going to be using a little tdb database to store
the cached copies of the directory trees, so I don't have to stat()
all the inodes all the time and bring those pages into memory. And
that will speed things up a lot as far as the launch time for
scanning the file list and then I've got this hierarchical idea
which unfortunately does add one round trip per element in the
hierarchy but that will improve things a lot as far as the size of
the file list in memory. Yeah, but it's not implemented yet, so I
can't promise when it's going to be done. It just depends on what
other things I'm working on. If somebody else wants to do it first,
then submit the patch. [76m, 44s]
[The speaker calls on an audience member for a question.]
Can't the server have precomputed signatures?
No, because the client generates the signatures.
What if you did it the other way around?
You can do server-generated signatures and you could do precomputed
server generated signatures. And there are some other reasons for
doing server-generated signatures. The main ones being a patent
concern. But unfortunately it requires basically a complete rewrite
of rsync and it won't be backwards compatible. Paul and I had been
considering doing that. We may do it at some stage and when we do
go to server-generated signatures, we can start; we do have the
possibility of doing caching of those. But while we're still doing
client-generated signatures within the current infrastructure of
rsync, you can't do it. It would basically be a new program. [77m,
30s]
[The speaker calls on an audience member for a question.]
You told me you may be thinking of using a database of signatures
to do an incremental backup using rsync...
Yeah, I talk about that in my thesis a little bit. That's another
application for rsync. You can do very nice incremental backup...
it's ideal for like tape robots, tape robot backup. Say for
example, you've got a silo, so you've got very, very slow access to
the main data in your tape silo. But typically, you've got a fast
front-end disk, which is, maybe, a tenth of a percent of the total
size of your tape archive. [78m, 10s]
What you can do is: your initial backup you store to the tape, but
then you store the signatures of the files on tape on the front-end
disks. Then, when you do a subsequent backup, you can get just the
differences without actually having to retrieve the old files off
of tape. You just retrieve the signatures, which are small, off of
disk, do the differencing using the rsync algorithm, then store the
differences either to tape or to disk. Probably to tape because
it's only a write; it'll be much faster than reading in all the
data and it'll be small. And that allows you to do very nice
incremental tape backups with very little tape activity. [78m, 47s]
And yeah, that's ideal. It would also be good for WORM drives, CD
drives, where basically you store the original data and you just
add a little bit of data on to the end of the WORM drive for the
differences each time. It allows you to roll back to any version
nicely while storing a minimum amount of data. You could make a
really lovely backup system that way. So I'll expect the patches
shortly. [The audience laughs.] And really it would be very nice.
There was a company that was looking at doing it, I think, but it
would be nice if there was a nice GPL'ed backup program that did
this.
Okay, thanks very much.
[The audience applauds.] [The presentation ends.] [79m, 39s]
Additional resources
rsync
Details regarding the rsync application may be found at
[3]http://rsync.samba.org
A copy of Andrew Tridgell's Ph.D. thesis is available from
[4]http://samba.org/~tridge/
rproxy
Details regarding the rproxy project, protocols and application may
be found at [5]http://linuxcare.com.au/projects/rproxy/
Xdelta
Details regarding the Xdelta project, protocols and application may
be found at [6]http://www.XCF.Berkeley.EDU/~jmacd/xdelta.html
OpenSSH
Details regarding OpenSSH may be found at [7]http://www.openssh.com
rzip
rzip and other unreleased code are available from the samba.org
CVS; details at [8]http://samba.org/cvs.html
mail scripts
The mail scripts mentioned in this talk (which use rsync) may be
found at [9]http://samba.org/pub/tridge/misc/mailscripts
References
1. ftp://ftp.linuxsymposium.org/ols2000/2000-07-21_15-02-49_C_64.mp3
2. http://olstrans.sourceforge.net/bugs.php3
3. http://rsync.samba.org/
4. http://samba.org/~tridge/
5. http://linuxcare.com.au/projects/rproxy/
6. http://www.XCF.Berkeley.EDU/~jmacd/xdelta.html
7. http://www.openssh.com/
8. http://samba.org/cvs.html
9. http://samba.org/pub/tridge/misc/mailscripts