Annotation of embedaddon/rsync/tech_report.tex, revision 1.1
1.1 ! misho 1: \documentclass[a4paper]{article}
! 2: \begin{document}
! 3:
! 4:
! 5: \title{The rsync algorithm}
! 6:
! 7: \author{Andrew Tridgell \quad\quad Paul Mackerras\\
! 8: Department of Computer Science \\
! 9: Australian National University \\
! 10: Canberra, ACT 0200, Australia}
! 11:
! 12: \maketitle
! 13:
! 14: \begin{abstract}
! 15: This report presents an algorithm for updating a file on one machine
! 16: to be identical to a file on another machine. We assume that the
! 17: two machines are connected by a low-bandwidth high-latency
! 18: bi-directional communications link. The algorithm identifies parts
! 19: of the source file which are identical to some part of the
! 20: destination file, and only sends those parts which cannot be matched
! 21: in this way. Effectively, the algorithm computes a set of
! 22: differences without having both files on the same machine. The
! 23: algorithm works best when the files are similar, but will also
! 24: function correctly and reasonably efficiently when the files are
! 25: quite different.
! 26: \end{abstract}
! 27:
! 28: \section{The problem}
! 29:
! 30: Imagine you have two files, $A$ and $B$, and you wish to update $B$ to be
! 31: the same as $A$. The obvious method is to copy $A$ onto $B$.
! 32:
! 33: Now imagine that the two files are on machines connected by a slow
! 34: communications link, for example a dialup IP link. If $A$ is large,
! 35: copying $A$ onto $B$ will be slow. To make it faster you could
! 36: compress $A$ before sending it, but that will usually only gain a
! 37: factor of 2 to 4.
! 38:
! 39: Now assume that $A$ and $B$ are quite similar, perhaps both derived
! 40: from the same original file. To really speed things up you would need
! 41: to take advantage of this similarity. A common method is to send just
! 42: the differences between $A$ and $B$ down the link and then use this
! 43: list of differences to reconstruct the file.
! 44:
! 45: The problem is that the normal methods for creating a set of
! 46: differences between two files rely on being able to read both files.
! 47: Thus they require that both files are available beforehand at one end
! 48: of the link. If they are not both available on the same machine,
! 49: these algorithms cannot be used (once you had copied the file over,
! 50: you wouldn't need the differences). This is the problem that rsync
! 51: addresses.
! 52:
! 53: The rsync algorithm efficiently computes which parts of a source file
! 54: match some part of an existing destination file. These parts need not
! 55: be sent across the link; all that is needed is a reference to the part
! 56: of the destination file. Only parts of the source file which are not
! 57: matched in this way need to be sent verbatim. The receiver can then
! 58: construct a copy of the source file using the references to parts of
! 59: the existing destination file and the verbatim material.
! 60:
! 61: Trivially, the data sent to the receiver can be compressed using any
! 62: of a range of common compression algorithms, for further speed
! 63: improvements.
! 64:
! 65: \section{The rsync algorithm}
! 66:
! 67: Suppose we have two general purpose computers $\alpha$ and $\beta$.
! 68: Computer $\alpha$ has access to a file $A$ and $\beta$ has access to
! 69: file $B$, where $A$ and $B$ are ``similar''. There is a slow
! 70: communications link between $\alpha$ and $\beta$.
! 71:
! 72: The rsync algorithm consists of the following steps:
! 73:
! 74: \begin{enumerate}
! 75: \item $\beta$ splits the file $B$ into a series of non-overlapping
! 76: fixed-sized blocks of size S bytes\footnote{We have found that
! 77: values of S between 500 and 1000 are quite good for most purposes}.
! 78: The last block may be shorter than $S$ bytes.
! 79:
! 80: \item For each of these blocks $\beta$ calculates two checksums:
! 81: a weak ``rolling'' 32-bit checksum (described below) and a strong
! 82: 128-bit MD4 checksum.
! 83:
! 84: \item $\beta$ sends these checksums to $\alpha$.
! 85:
! 86: \item $\alpha$ searches through $A$ to find all blocks of length $S$
! 87: bytes (at any offset, not just multiples of $S$) that have the same
! 88: weak and strong checksum as one of the blocks of $B$. This can be
! 89: done in a single pass very quickly using a special property of the
! 90: rolling checksum described below.
! 91:
! 92: \item $\alpha$ sends $\beta$ a sequence of instructions for
! 93: constructing a copy of $A$. Each instruction is either a reference
! 94: to a block of $B$, or literal data. Literal data is sent only for
! 95: those sections of $A$ which did not match any of the blocks of $B$.
! 96: \end{enumerate}
! 97:
! 98: The end result is that $\beta$ gets a copy of $A$, but only the pieces
! 99: of $A$ that are not found in $B$ (plus a small amount of data for
! 100: checksums and block indexes) are sent over the link. The algorithm
! 101: also only requires one round trip, which minimises the impact of the
! 102: link latency.
! 103:
! 104: The most important details of the algorithm are the rolling checksum
! 105: and the associated multi-alternate search mechanism which allows the
! 106: all-offsets checksum search to proceed very quickly. These will be
! 107: discussed in greater detail below.
! 108:
! 109: \section{Rolling checksum}
! 110:
! 111: The weak rolling checksum used in the rsync algorithm needs to have
! 112: the property that it is very cheap to calculate the checksum of a
! 113: buffer $X_2 .. X_{n+1}$ given the checksum of buffer $X_1 .. X_n$ and
! 114: the values of the bytes $X_1$ and $X_{n+1}$.
! 115:
! 116: The weak checksum algorithm we used in our implementation was inspired
! 117: by Mark Adler's adler-32 checksum. Our checksum is defined by
! 118: $$ a(k,l) = (\sum_{i=k}^l X_i) \bmod M $$
! 119: $$ b(k,l) = (\sum_{i=k}^l (l-i+1)X_i) \bmod M $$
! 120: $$ s(k,l) = a(k,l) + 2^{16} b(k,l) $$
! 121:
! 122: where $s(k,l)$ is the rolling checksum of the bytes $X_k \ldots X_l$.
! 123: For simplicity and speed, we use $M = 2^{16}$.
! 124:
! 125: The important property of this checksum is that successive values can
! 126: be computed very efficiently using the recurrence relations
! 127:
! 128: $$ a(k+1,l+1) = (a(k,l) - X_k + X_{l+1}) \bmod M $$
! 129: $$ b(k+1,l+1) = (b(k,l) - (l-k+1) X_k + a(k+1,l+1)) \bmod M $$
! 130:
! 131: Thus the checksum can be calculated for blocks of length S at all
! 132: possible offsets within a file in a ``rolling'' fashion, with very
! 133: little computation at each point.
! 134:
! 135: Despite its simplicity, this checksum was found to be quite adequate as
! 136: a first-level check for a match of two file blocks. We have found in
! 137: practice that the probability of this checksum matching when the
! 138: blocks are not equal is quite low. This is important because the much
! 139: more expensive strong checksum must be calculated for each block where
! 140: the weak checksum matches.
! 141:
! 142: \section{Checksum searching}
! 143:
! 144: Once $\alpha$ has received the list of checksums of the blocks of $B$,
! 145: it must search $A$ for any blocks at any offset that match the
! 146: checksum of some block of $B$. The basic strategy is to compute the
! 147: 32-bit rolling checksum for a block of length $S$ starting at each
! 148: byte of $A$ in turn, and for each checksum, search the list for a
! 149: match. To do this our implementation uses a
! 150: simple 3 level searching scheme.
! 151:
! 152: The first level uses a 16-bit hash of the 32-bit rolling checksum and
! 153: a $2^{16}$ entry hash table. The list of checksum values (i.e., the
! 154: checksums from the blocks of $B$) is sorted according to the 16-bit
! 155: hash of the 32-bit rolling checksum. Each entry in the hash table
! 156: points to the first element of the list for that hash value, or
! 157: contains a null value if no element of the list has that hash value.
! 158:
! 159: At each offset in the file the 32-bit rolling checksum and its 16-bit
! 160: hash are calculated. If the hash table entry for that hash value is
! 161: not a null value, the second-level check is invoked.
! 162:
! 163: The second-level check involves scanning the sorted checksum list
! 164: starting with the entry pointed to by the hash table entry, looking
! 165: for an entry whose 32-bit rolling checksum matches the current value.
! 166: The scan terminates when it reaches an entry whose 16-bit hash
! 167: differs. If this search finds a match, the third-level check is
! 168: invoked.
! 169:
! 170: The third-level check involves calculating the strong checksum for the
! 171: current offset in the file and comparing it with the strong checksum
! 172: value in the current list entry. If the two strong checksums match,
! 173: we assume that we have found a block of $A$ which matches a block of
! 174: $B$. In fact the blocks could be different, but the probability of
! 175: this is microscopic, and in practice this is a reasonable assumption.
! 176:
! 177: When a match is found, $\alpha$ sends $\beta$ the data in $A$ between
! 178: the current file offset and the end of the previous match, followed by
! 179: the index of the block in $B$ that matched. This data is sent
! 180: immediately a match is found, which allows us to overlap the
! 181: communication with further computation.
! 182:
! 183: If no match is found at a given offset in the file, the rolling
! 184: checksum is updated to the next offset and the search proceeds. If a
! 185: match is found, the search is restarted at the end of the matched
! 186: block. This strategy saves a considerable amount of computation for
! 187: the common case where the two files are nearly identical. In
! 188: addition, it would be a simple matter to encode the block indexes as
! 189: runs, for the common case where a portion of $A$ matches a series of
! 190: blocks of $B$ in order.
! 191:
! 192: \section{Pipelining}
! 193:
! 194: The above sections describe the process for constructing a copy of one
! 195: file on a remote system. If we have a several files to copy, we can
! 196: gain a considerable latency advantage by pipelining the process.
! 197:
! 198: This involves $\beta$ initiating two independent processes. One of the
! 199: processes generates and sends the checksums to $\alpha$ while the
! 200: other receives the difference information from $\alpha$ and
! 201: reconstructs the files.
! 202:
! 203: If the communications link is buffered then these two processes can
! 204: proceed independently and the link should be kept fully utilised in
! 205: both directions for most of the time.
! 206:
! 207: \section{Results}
! 208:
! 209: To test the algorithm, tar files were created of the Linux kernel
! 210: sources for two versions of the kernel. The two kernel versions were
! 211: 1.99.10 and 2.0.0. These tar files are approximately 24MB in size and
! 212: are separated by 5 released patch levels.
! 213:
! 214: Out of the 2441 files in the 1.99.10 release, 291 files had changed in
! 215: the 2.0.0 release, 19 files had been removed and 25 files had been
! 216: added.
! 217:
! 218: A ``diff'' of the two tar files using the standard GNU diff utility
! 219: produced over 32 thousand lines of output totalling 2.1 MB.
! 220:
! 221: The following table shows the results for rsync between the two files
! 222: with a varying block size.\footnote{All the tests in this section were
! 223: carried out using rsync version 0.5}
! 224:
! 225: \vspace*{5mm}
! 226: \begin{tabular}{|l|l|l|l|l|l|l|} \hline
! 227: {\bf block} & {\bf matches} & {\bf tag} & {\bf false} & {\bf data} & {\bf written} & {\bf read} \\
! 228: {\bf size} & & {\bf hits} & {\bf alarms} & & & \\ \hline \hline
! 229:
! 230: 300 & 64247 & 3817434 & 948 & 5312200 & 5629158 & 1632284 \\ \hline
! 231: 500 & 46989 & 620013 & 64 & 1091900 & 1283906 & 979384 \\ \hline
! 232: 700 & 33255 & 571970 & 22 & 1307800 & 1444346 & 699564 \\ \hline
! 233: 900 & 25686 & 525058 & 24 & 1469500 & 1575438 & 544124 \\ \hline
! 234: 1100 & 20848 & 496844 & 21 & 1654500 & 1740838 & 445204 \\ \hline
! 235: \end{tabular}
! 236: \vspace*{5mm}
! 237:
! 238: In each case, the CPU time taken was less than the
! 239: time it takes to run ``diff'' on the two files.\footnote{The wall
! 240: clock time was approximately 2 minutes per run on a 50 MHz SPARC 10
! 241: running SunOS, using rsh over loopback for communication. GNU diff
! 242: took about 4 minutes.}
! 243:
! 244: The columns in the table are as follows:
! 245:
! 246: \begin{description}
! 247: \item [block size] The size in bytes of the checksummed blocks.
! 248: \item [matches] The number of times a block of $B$ was found in $A$.
! 249: \item [tag hits] The number of times the 16-bit hash of the rolling
! 250: checksum matched a hash of one of the checksums from $B$.
! 251: \item [false alarms] The number of times the 32-bit rolling checksum
! 252: matched but the strong checksum didn't.
! 253: \item [data] The amount of file data transferred verbatim, in bytes.
! 254: \item [written] The total number of bytes written by $\alpha$,
! 255: including protocol overheads. This is almost all file data.
! 256: \item [read] The total number of bytes read by $\alpha$, including
! 257: protocol overheads. This is almost all checksum information.
! 258: \end{description}
! 259:
! 260: The results demonstrate that for block sizes above 300 bytes, only a
! 261: small fraction (around 5\%) of the file was transferred. The amount
! 262: transferred was also considerably less than the size of the diff file
! 263: that would have been transferred if the diff/patch method of updating
! 264: a remote file was used.
! 265:
! 266: The checksums themselves took up a considerable amount of space,
! 267: although much less than the size of the data transferred in each
! 268: case. Each pair of checksums consumes 20 bytes: 4 bytes for the
! 269: rolling checksum plus 16 bytes for the 128-bit MD4 checksum.
! 270:
! 271: The number of false alarms was less than $1/1000$ of the number of
! 272: true matches, indicating that the 32-bit rolling checksum is quite
! 273: good at screening out false matches.
! 274:
! 275: The number of tag hits indicates that the second level of the
! 276: checksum search algorithm was invoked about once every 50
! 277: characters. This is quite high because the total number of blocks in
! 278: the file is a large fraction of the size of the tag hash table. For
! 279: smaller files we would expect the tag hit rate to be much closer to
! 280: the number of matches. For extremely large files, we should probably
! 281: increase the size of the hash table.
! 282:
! 283: The next table shows similar results for a much smaller set of files.
! 284: In this case the files were not packed into a tar file first. Rather,
! 285: rsync was invoked with an option to recursively descend the directory
! 286: tree. The files used were from two source releases of another software
! 287: package called Samba. The total source code size is 1.7 MB and the
! 288: diff between the two releases is 4155 lines long totalling 120 kB.
! 289:
! 290: \vspace*{5mm}
! 291: \begin{tabular}{|l|l|l|l|l|l|l|} \hline
! 292: {\bf block} & {\bf matches} & {\bf tag} & {\bf false} & {\bf data} & {\bf written} & {\bf read} \\
! 293: {\bf size} & & {\bf hits} & {\bf alarms} & & & \\ \hline \hline
! 294:
! 295: 300 & 3727 & 3899 & 0 & 129775 & 153999 & 83948 \\ \hline
! 296: 500 & 2158 & 2325 & 0 & 171574 & 189330 & 50908 \\ \hline
! 297: 700 & 1517 & 1649 & 0 & 195024 & 210144 & 36828 \\ \hline
! 298: 900 & 1156 & 1281 & 0 & 222847 & 236471 & 29048 \\ \hline
! 299: 1100 & 921 & 1049 & 0 & 250073 & 262725 & 23988 \\ \hline
! 300: \end{tabular}
! 301: \vspace*{5mm}
! 302:
! 303:
! 304: \section{Availability}
! 305:
! 306: An implementation of rsync which provides a convenient interface
! 307: similar to the common UNIX command rcp has been written and is
! 308: available for download from http://rsync.samba.org/
! 309:
! 310: \end{document}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to tech_report.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync