3 ms·

can we gut rsync and implement this? rsync doesn't even have a great protocol specification... maybe it's a new tool...

progbits 4y ago
> Overall, cdc_rsync syncs files about 3 times faster than Cygwin rsync. Sounds promising.
mjevans 4y ago
I'd like additional info about the Content Defined Chunking part of the specification. How is the content defined? Where I'd try to begin is with a single pass that looks for runs of 'null' ('\0') bytes, even one long, as potential boundary ends. During that pass also look for 'magic signatures' for known stream types like already compressed content streams (all the more so to just not try compressing anyway). The CDC might also be aware of some file structures, zip, 7z, tar, etc; and have a dedicated segment creation algorithm for them. At a low level, the two ends should exchange a list of segment offsets, lengths, checksum (partial?) and maybe some short fragment of bytes to check. (E.G. 4 byte chunks at various powers of 2 offsets or major chunk starts.) Where the two ends have differences in chunks existing they might also expend some minor additional effort to investigate if the chunks that were identified on the other side exist locally; in case the two versions are using different filters or happened to reach different conclusions.
- ljusten 4y ago
  In a nutshell, the algorithm computes uint64_t hash = 0; uint64_t magic_pattern = 0b001000010000100001000...; for (size_t n = 0; n < data.size(); ++n) { hash = (hash << 1) + random_table[data[n]]; if ((hash & magic_pattern) == 0) { SetChunkBoundaryAt(n); } } In practice, there's more bells and whistles, but that's the gist of it. By tweaking the numbers of 1's in magic_pattern you can influence the average chunk size (distance between two boundaries). With every additional 1, your chunk size halves. There's no special handling of compressed file types. You'd probably want to do that at a much higher level, e.g. just check for extensions.

> Overall, cdc_rsync syncs files about 3 times faster than Cygwin rsync. Sounds promising.

I'd like additional info about the Content Defined Chunking part of the specification. How is the content defined? Where I'd try to begin is with a single pass that looks for runs of 'null' ('\0') bytes, even one long, as potential boundary ends. During that pass also look for 'magic signatures' for known stream types like already compressed content streams (all the more so to just not try compressing anyway). The CDC might also be aware of some file structures, zip, 7z, tar, etc; and have a dedicated segment creation algorithm for them. At a low level, the two ends should exchange a list of segment offsets, lengths, checksum (partial?) and maybe some short fragment of bytes to check. (E.G. 4 byte chunks at various powers of 2 offsets or major chunk starts.) Where the two ends have differences in chunks existing they might also expend some minor additional effort to investigate if the chunks that were identified on the other side exist locally; in case the two versions are using different filters or happened to reach different conclusions.

ljusten 4y ago
In a nutshell, the algorithm computes uint64_t hash = 0; uint64_t magic_pattern = 0b001000010000100001000...; for (size_t n = 0; n < data.size(); ++n) { hash = (hash << 1) + random_table[data[n]]; if ((hash & magic_pattern) == 0) { SetChunkBoundaryAt(n); } } In practice, there's more bells and whistles, but that's the gist of it. By tweaking the numbers of 1's in magic_pattern you can influence the average chunk size (distance between two boundaries). With every additional 1, your chunk size halves. There's no special handling of compressed file types. You'd probably want to do that at a much higher level, e.g. just check for extensions.