Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CDC File Transfer

github.com

Post reply on HN
Print view View original

21–30 of 229 posts

Re: CDC File Transfer

#21

Post by mjevans »

sigmonsays wrote: post #2

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

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.

Re: CDC File Transfer

#22

Post by jyxent »

crazygringo wrote: post #17
teraflop wrote: post #10

TL;DR they rediscovered the context-dependent variable block size technique that Tarsnap uses: https://www.tarsnap.com/download/EuroBSDCon13.pdf

They don't claim to have invented CDC, or FastCDC, they just made and are sharing a useful implementation of it. And if that Tarsnap presentation is from 2013, and FastCDC was published in 2016 [1] according to Wikipedia [2], then presumably Tarsnap didn't invent FastCDC either. [1] https://www.usenix.org/system/files/conference/atc16/atc16-p... [2] https://en.wikipedia.org/wiki/Rolling_hash#Gear_fingerprint_...

Another well-cited predecessor is "A low-bandwidth network file system." (https://dl.acm.org/doi/abs/10.1145/502034.502052), which was published in 2001. It uses Rabin fingerprinting to define chunk boundaries.

Re: CDC File Transfer

#23

Post by windowsworkstoo »

piceas wrote: post #18
zX41ZdbW wrote: post #13

Content Defined Chunking is one of my favorite algorithms because it has some "magic" similar to HyperLogLogs, Bloom filters, etc... This algorithm is good to explain to people, to get them inspired by computer science. I usually explain the simplest variant with rolling hashes. It is interesting what the result will be (average saving on deduplication) if it is applied globally to a large-scale blob storage, such as…

Implementing fastCDC is fun (2016). Do you have a suggestion on what to read on the topic since then? I don't keep up with these things. A quick search came up with the following but I haven't read it yet. Fan Ni and Song Jiang, "RapidCDC: Leveraging Duplicate Locality to Accelerate Chunking in CDC-based Deduplication Systems", in Proceedings of 2019 ACM Symposium on Cloud Computing (ACM SoCC'19), Santa Cruz, CA, Nov…

Microsoft have this for DFS-R and the spec is open https://learn.microsoft.com/en-us/openspecs/windows_protocol... - its pretty straight forward to implement.

Re: CDC File Transfer

#24

Post by kccqzy »

teraflop wrote: post #10

TL;DR they rediscovered the context-dependent variable block size technique that Tarsnap uses: https://www.tarsnap.com/download/EuroBSDCon13.pdf

The Tarsnap technique is interesting but that presentation is a bit hard to follow. What are the examples for values alpha and p?

Re: CDC File Transfer

#25

Post by encryptluks2 »

This is great for syncing, but what about separating courgette from Chromium so that we can finally have a descent delta diff program? I am tired of Windows community relying on SmartVersion to create ISO diff files just because you need to be a master at compiling Chromium just to use courgette.

Re: CDC File Transfer

#27

Post by eps »

jws wrote: post #6
brendoncarroll wrote: post #3

FastCDC is the same chunking algorithm used in Got. https://github.com/gotvc/got

To elaborate, rsync chunks in fixed sizes, so inserting or deleting a few bytes makes all different chunks from that point onward. If instead you chunk based off of local content (conceptually like chunking text into sentences at periods, but its a binary thing on has an upper size limit and lower size limit and I couldn't find the algorithm specification) so that after an insertion or deletion in a small number of b…

The gotcha of "inserting or deleting a few bytes" is not in detection, it's in replicating this discovery to the target copy.

Say, we have 1GB file and we detected an extra byte at the head of our local copy. Great, what next? We can't replicate this on the receiving end without recopying the file, which is exactly what happens - rsync recreates target file from pieces of its old copy and differences received from the source. Every byte is copied, it's just that some of them are copied locally.

In that light, sync tools that operate with fixed-size blocks have one very big advantage - they allow updating target files in-place and limiting per-sync IO to writes of modified blocks only. This works exceptionally well for DBs, VMs, VHDs, file system containers, etc. It doesn't work well for archives (tars, zips), compressed images (jpgs, resource packs in games) and huge executables.

In other words - know your tools and know your data. Then match them appropriately.

Re: CDC File Transfer

#28

Post by dn3500 »

5440 wrote: post #20

I'm currently working on a required CDC (Center for Disease Control) reporting function for a COVID test. For a second I thought this article was going to be extremely helpful.

The first computer I used professionaly was a Control Data Corporation (CDC) 6600. For a second I thought I could use this to transfer some of my old files.

Re: CDC File Transfer

#30

Post by lucb1e »

5440 wrote: post #20

I'm currently working on a required CDC (Center for Disease Control) reporting function for a COVID test. For a second I thought this article was going to be extremely helpful.

I have nothing to do with the CDC and am from another continent but had the same confusion. Not be enough TLAs are available it seems!
Post reply on HN