6 ms·

Rediscovering the Rsync Algorithm

185 points by nicolast 15y ago

rlpb 15y ago
There is a Better Way. Instead of using fixed sized blocks, use variable sized blocks. Decide the block boundaries using the data in the blocks themselves. This will reduce your search from O(n^2) to O(n). Tarsnap does this. My project (ddar) does the same.
- willvarfar 15y ago
  I've heard that called 'anchored hashing'. Its recently been used by FreeArc: http://encode.ru/threads/43-FreeArc?p=28237&viewfull=1#post28237 http://encode.ru/threads/43-FreeArc?p=28237&viewfull=1#p... How does ddar do it?
  - rlpb 15y ago
    ddar calculates a 32-bit Rabin fingerprint over a sliding 48-byte window (a Rabin fingerprint is a type of checksum which allows quick calculation of a "slide" with just the previous fingerprint, the new byte coming in, and the old byte going away). The fingerprint is compared against a mask which has n bits set, where 2^n is the desired target block size. If there's a match, then the location of the window is taken to be a block boundary. With random data this should lead to a binomial distribution of block sizes centred around the target block size. But minimum and maximum block sizes are also enforced for pathological cases which skews this slightly. Blocks whose boundaries are determined by this algorithm are hashed (SHA256 currently). The hash is used to key each block in a reference-counted key/value store. Then each archive member is just a list of block hashes.
    - huhtenberg 15y ago
      If you were to elaborate on and brush up the description, it would make an excellent HN submission. Good stuff anyways.
  - silentbicycle 15y ago
    I wrote a library that does this. I haven't posted it publicly, because it's part of a much larger project (not yet complete), but could put it on github if anybody is interested. There are implementations in Lua, Java, and C.
    - kragen 15y ago
      This would be really cool.
      - silentbicycle 15y ago
        I'll ping you on twitter when I post it.
omh 15y ago
Don’t walk the folder and ‘rsync’ each file you encounter If I just tell rsync to syncronise between two directories, what does it do internally? I might have assumed that it does the more naive option, but in practice it seems to do a lot of upfront calculation that suggests it's doing something more sophisticated.
- deleted 15y ago
  [deleted]
- pronoiac 15y ago
  Rsync will compare timestamps, to only transfer changed files.
  - paxswill 15y ago
    The default behavior also checks file size in addition to modification time.
    - burgerbrain 15y ago
      Is there a purpose to that?
      - ominous_prime 15y ago
        Modification time can be altered, or incorrect. File size is just another fast check that can be done with the same data return by stat'ing the file. Rsync can also compare hashes if you don't trust the size and time on the files.
mitchty 15y ago
As cool as the rsync algorithm is, i'd much rather we had the dsync utility outlined in this usenix 08 paper. http://www.usenix.org/event/usenix08/tech/full_papers/pucha/pucha.pdf http://www.usenix.org/event/usenix08/tech/full_papers/pucha/... An adaptive protocol that matches to the systems load dynamically whether its cpu/disk/network. Anyone know of what happened to this?
- arethuza 15y ago
  Apologies - downvoted by mistake!
david_a_r_kemp 15y ago
If someone committed any of that code to a repository I was working on, then I'd hang them up. It's 2011 and people are still using one and two letter variable names. An interesting article, but I don't have time nor the inclination to understand the code, which is the core of it.
- RegEx 15y ago
  Many people feel a blend of slight obscurity with succinctness are the core ingredients for an elegant solution. As a math major at university, I find this extremely prevalent in the textbooks of proof courses. I generally find it irritating, and to an extent, patronizing.
  - psykotic 15y ago
    > Many people feel a blend of slight obscurity with succinctness are the core ingredients for an elegant solution. My exemplar for mathematical elegance is page 3 of Serre's A Course in Arithmetic. In a tidy page of text, it proves what takes many textbooks a long and tedious chapter, introducing important concepts like the Frobenius. It's so short and neat I can reproduce it here in full: Let K be a field. The image of Z in K is an integral domain, hence isomorphic to Z or to Z/pZ, where p is a prime; its field of fractions is isomorphic to Q or to Z/pZ = F_p. In the first case, one says that K is of characteristic zero; in the second case, that K is of characteristic p. The characteristic of K is denoted by char(K). If char(K) = p != 0, p is also the smallest integer n > 0 such that n 1 = 0. Lemma. If char(K) = p, the map sigma : x -> x^p is an isomorphism of K onto one of its subfields K^p. We have sigma(xy) = sigma(x) sigma(y). Moreover, the binomial coefficient (p choose k) is congruent to 0 (mod p) if 0 < k < p. From this it follows that sigma(x + y) = sigma(x) + sigma(y); hence sigma is a homomorphism. Furthermore, sigma is clearly injective. Theorem 1. (i) The characteristic of a finite field K is a prime number p != 0; if f = [K:F_p], the number of elements of K is q = p^f. (ii) Let p be a prime number and let q = p^f (f >= 1) be a power of p. Let Omega be an algebraically closed field of characteristic p. There exists a unique subfield F_q of Omega which has q elements. It is the set of roots of the polynomial X^q - X. (iii) All finite fields with q = p^f elements are isomorphic to F_q. If K is finite, it does not contain the field Q. Hence its characteristic is a prime number p. If f is the degree of the extension K/F_p, it is clear that Card(K) = p^f, and (i) follows. On the other hand, if Omega is algebraically closed of characteristic p, the above lemma shows that the map x -> x^q (where q = p^f, f >= 1) is an automorphism of Omega; indeed, this map is the f-th iterate of the automorphism sigma : x -> x^p (note that sigma is surjective since Omega is algebraically closed). Therefore, the elements in Omega invariant under x -> x^q form a subfield F_q of Omega. The derivative of the polynomial X^q - X is q X^(q-1) - 1 = p p^(f-1) X^(q-1) - 1 = -1, and is not zero. This implies (since Omega is algebraically closed) that X^q - X has q distinct roots, hence Card(F_q) = q. Conversely, if K is a subfield of Omega with q elements, the multiplicative group K* of nonzero elements in K has q-1 elements. Then x^(q-1) = 1 if x in K* and x^q = x if x in K. This proves that K is contained in F_q. Since Card(K) = Card(F_q) we have K = F_q which completes the proof of (ii). Assertion (iii) follows from (ii) and from the fact that all fields with p^f elements can be embedded in Omega since Omega is algebraically closed. > proof courses I can't think of a single course I took, starting with the first semester, that wasn't a "proof course".
thibaut_barrere 15y ago
Sidenote but in case it's helpful to someone; if you need to have rsync.exe on Windows, here's one path: https://github.com/thbar/rsync-windows https://github.com/thbar/rsync-windows
Ygor 15y ago
Do you know of any other implementations of the rsync algorithm other than the actual rsync program? And where are they used? Do you know how and where dropbox uses rsync? There have been some tries to port the rsync program to other languages/platforms [1], but they are usually not in sync with the current rsync program. I am talking about ports of the program, not new implementations of the algorithm. [1] https://github.com/MatthewSteeples/rsync.net https://github.com/MatthewSteeples/rsync.net
- sciurus 15y ago
  There's librsync [0], although it's not compatible with the rsync program. Duplicity [1] uses it. [0] http://librsync.sourceforge.net http://librsync.sourceforge.net [1] http://duplicity.nongnu.org http://duplicity.nongnu.org
- zellyn 15y ago
  rsync-ish: https://github.com/apenwarr/bup https://github.com/apenwarr/bup
ajays 15y ago
rsync is great. I use the "-H" and "--link-dest" options to make incremental backups which look like snapshots. Been doing this for the better part of a decade; would be interested to know if there's A Better Solution(tm) out there...
- gnaritas 15y ago
  rsnapshot, which does all that for you with automated rotation, built on top of rsync.
- andrewcooke 15y ago
  rdiff-backup http://rdiff-backup.nongnu.org/ http://rdiff-backup.nongnu.org/ may be what you are looking for?
sciurus 15y ago
The rsync algorithm and program are both great, and I use the program a lot to update directory trees across the network. It's also my default tool for synchronizing two directories on the same system. The rsync program correctly optimizes for this case by skipping the rsync algorithm and completely copying changed files. However, it still uses multiple processes and seemingly still calculates some hashes, making it slower than it needs to be. Joey found [0] that running rsync once in dry-run mode to find what files have been changed, copying them each with cp, then running rsync a second time to handle things like deletions and file permissions resulted in a major speedup. [0] http://kitenet.net/~joey/blog/entry/local_rsync_accelerator/ http://kitenet.net/~joey/blog/entry/local_rsync_accelerator/
jeet-singh 15y ago
cool

185 points by nicolast 15y ago

rlpb 15y ago

There is a Better Way. Instead of using fixed sized blocks, use variable sized blocks. Decide the block boundaries using the data in the blocks themselves. This will reduce your search from O(n^2) to O(n). Tarsnap does this. My project (ddar) does the same.

willvarfar 15y ago
I've heard that called 'anchored hashing'. Its recently been used by FreeArc: http://encode.ru/threads/43-FreeArc?p=28237&viewfull=1#post28237 http://encode.ru/threads/43-FreeArc?p=28237&viewfull=1#p... How does ddar do it?
- rlpb 15y ago
  ddar calculates a 32-bit Rabin fingerprint over a sliding 48-byte window (a Rabin fingerprint is a type of checksum which allows quick calculation of a "slide" with just the previous fingerprint, the new byte coming in, and the old byte going away). The fingerprint is compared against a mask which has n bits set, where 2^n is the desired target block size. If there's a match, then the location of the window is taken to be a block boundary. With random data this should lead to a binomial distribution of block sizes centred around the target block size. But minimum and maximum block sizes are also enforced for pathological cases which skews this slightly. Blocks whose boundaries are determined by this algorithm are hashed (SHA256 currently). The hash is used to key each block in a reference-counted key/value store. Then each archive member is just a list of block hashes.
  - huhtenberg 15y ago
    If you were to elaborate on and brush up the description, it would make an excellent HN submission. Good stuff anyways.
- silentbicycle 15y ago
  I wrote a library that does this. I haven't posted it publicly, because it's part of a much larger project (not yet complete), but could put it on github if anybody is interested. There are implementations in Lua, Java, and C.
  - kragen 15y ago
    This would be really cool.
    - silentbicycle 15y ago
      I'll ping you on twitter when I post it.

omh 15y ago

Don’t walk the folder and ‘rsync’ each file you encounter If I just tell rsync to syncronise between two directories, what does it do internally? I might have assumed that it does the more naive option, but in practice it seems to do a lot of upfront calculation that suggests it's doing something more sophisticated.

deleted 15y ago
[deleted]
pronoiac 15y ago
Rsync will compare timestamps, to only transfer changed files.
- paxswill 15y ago
  The default behavior also checks file size in addition to modification time.
  - burgerbrain 15y ago
    Is there a purpose to that?
    - ominous_prime 15y ago
      Modification time can be altered, or incorrect. File size is just another fast check that can be done with the same data return by stat'ing the file. Rsync can also compare hashes if you don't trust the size and time on the files.

mitchty 15y ago

As cool as the rsync algorithm is, i'd much rather we had the dsync utility outlined in this usenix 08 paper. http://www.usenix.org/event/usenix08/tech/full_papers/pucha/pucha.pdf http://www.usenix.org/event/usenix08/tech/full_papers/pucha/... An adaptive protocol that matches to the systems load dynamically whether its cpu/disk/network. Anyone know of what happened to this?

arethuza 15y ago
Apologies - downvoted by mistake!

david_a_r_kemp 15y ago

If someone committed any of that code to a repository I was working on, then I'd hang them up. It's 2011 and people are still using one and two letter variable names. An interesting article, but I don't have time nor the inclination to understand the code, which is the core of it.

RegEx 15y ago
Many people feel a blend of slight obscurity with succinctness are the core ingredients for an elegant solution. As a math major at university, I find this extremely prevalent in the textbooks of proof courses. I generally find it irritating, and to an extent, patronizing.
- psykotic 15y ago
  > Many people feel a blend of slight obscurity with succinctness are the core ingredients for an elegant solution. My exemplar for mathematical elegance is page 3 of Serre's A Course in Arithmetic. In a tidy page of text, it proves what takes many textbooks a long and tedious chapter, introducing important concepts like the Frobenius. It's so short and neat I can reproduce it here in full: Let K be a field. The image of Z in K is an integral domain, hence isomorphic to Z or to Z/pZ, where p is a prime; its field of fractions is isomorphic to Q or to Z/pZ = F_p. In the first case, one says that K is of characteristic zero; in the second case, that K is of characteristic p. The characteristic of K is denoted by char(K). If char(K) = p != 0, p is also the smallest integer n > 0 such that n 1 = 0. Lemma. If char(K) = p, the map sigma : x -> x^p is an isomorphism of K onto one of its subfields K^p. We have sigma(xy) = sigma(x) sigma(y). Moreover, the binomial coefficient (p choose k) is congruent to 0 (mod p) if 0 < k < p. From this it follows that sigma(x + y) = sigma(x) + sigma(y); hence sigma is a homomorphism. Furthermore, sigma is clearly injective. Theorem 1. (i) The characteristic of a finite field K is a prime number p != 0; if f = [K:F_p], the number of elements of K is q = p^f. (ii) Let p be a prime number and let q = p^f (f >= 1) be a power of p. Let Omega be an algebraically closed field of characteristic p. There exists a unique subfield F_q of Omega which has q elements. It is the set of roots of the polynomial X^q - X. (iii) All finite fields with q = p^f elements are isomorphic to F_q. If K is finite, it does not contain the field Q. Hence its characteristic is a prime number p. If f is the degree of the extension K/F_p, it is clear that Card(K) = p^f, and (i) follows. On the other hand, if Omega is algebraically closed of characteristic p, the above lemma shows that the map x -> x^q (where q = p^f, f >= 1) is an automorphism of Omega; indeed, this map is the f-th iterate of the automorphism sigma : x -> x^p (note that sigma is surjective since Omega is algebraically closed). Therefore, the elements in Omega invariant under x -> x^q form a subfield F_q of Omega. The derivative of the polynomial X^q - X is q X^(q-1) - 1 = p p^(f-1) X^(q-1) - 1 = -1, and is not zero. This implies (since Omega is algebraically closed) that X^q - X has q distinct roots, hence Card(F_q) = q. Conversely, if K is a subfield of Omega with q elements, the multiplicative group K* of nonzero elements in K has q-1 elements. Then x^(q-1) = 1 if x in K* and x^q = x if x in K. This proves that K is contained in F_q. Since Card(K) = Card(F_q) we have K = F_q which completes the proof of (ii). Assertion (iii) follows from (ii) and from the fact that all fields with p^f elements can be embedded in Omega since Omega is algebraically closed. > proof courses I can't think of a single course I took, starting with the first semester, that wasn't a "proof course".

thibaut_barrere 15y ago

Sidenote but in case it's helpful to someone; if you need to have rsync.exe on Windows, here's one path: https://github.com/thbar/rsync-windows https://github.com/thbar/rsync-windows

Ygor 15y ago

Do you know of any other implementations of the rsync algorithm other than the actual rsync program? And where are they used? Do you know how and where dropbox uses rsync? There have been some tries to port the rsync program to other languages/platforms [1], but they are usually not in sync with the current rsync program. I am talking about ports of the program, not new implementations of the algorithm. [1] https://github.com/MatthewSteeples/rsync.net https://github.com/MatthewSteeples/rsync.net

sciurus 15y ago
There's librsync [0], although it's not compatible with the rsync program. Duplicity [1] uses it. [0] http://librsync.sourceforge.net http://librsync.sourceforge.net [1] http://duplicity.nongnu.org http://duplicity.nongnu.org
zellyn 15y ago
rsync-ish: https://github.com/apenwarr/bup https://github.com/apenwarr/bup

ajays 15y ago

rsync is great. I use the "-H" and "--link-dest" options to make incremental backups which look like snapshots. Been doing this for the better part of a decade; would be interested to know if there's A Better Solution(tm) out there...

gnaritas 15y ago
rsnapshot, which does all that for you with automated rotation, built on top of rsync.
andrewcooke 15y ago
rdiff-backup http://rdiff-backup.nongnu.org/ http://rdiff-backup.nongnu.org/ may be what you are looking for?

sciurus 15y ago

The rsync algorithm and program are both great, and I use the program a lot to update directory trees across the network. It's also my default tool for synchronizing two directories on the same system. The rsync program correctly optimizes for this case by skipping the rsync algorithm and completely copying changed files. However, it still uses multiple processes and seemingly still calculates some hashes, making it slower than it needs to be. Joey found [0] that running rsync once in dry-run mode to find what files have been changed, copying them each with cp, then running rsync a second time to handle things like deletions and file permissions resulted in a major speedup. [0] http://kitenet.net/~joey/blog/entry/local_rsync_accelerator/ http://kitenet.net/~joey/blog/entry/local_rsync_accelerator/

jeet-singh 15y ago

cool