11–20 of 229 posts
FastCDC is the same chunking algorithm used in Got. https://github.com/gotvc/got
They both seem like very cool projects, so may the best Got win!
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 Amazon S3 or Google Drive (we need metadata storage about chunks, and the chunks can be deduplicated).
PS. I don't use this algorithm in ClickHouse, but it always remains tempting.
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…
https://rsync.samba.org/tech_report/node3.html
Your description of content defined chunking is exactly right though. There are a number of techniques for doing it. FastCDC is one of them, although not the one used in rsync.
https://en.wikipedia.org/wiki/Rolling_hash
EDIT: Corrected in the comments below. Fixed sized chunks searched for at any offset with a rolling hash. The rsync algorithm description is here.
Earlier quoted context omitted.
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…
I̶ ̶d̶o̶n̶'̶t̶ ̶t̶h̶i̶n̶k̶ ̶r̶s̶y̶n̶c̶ ̶u̶s̶e̶s̶ ̶f̶i̶x̶e̶d̶ ̶s̶i̶z̶e̶d̶ ̶c̶h̶u̶n̶k̶s̶.̶ The algorithm is described here; it's a rolling hash. https://rsync.samba.org/tech_report/node3.html Your description of content defined chunking is exactly right though. There are a number of techniques for doing it. FastCDC is one of them, although not the one used in rsync. https://en.wikipedia.org/wiki/Rolling_hash EDIT: Corr…
So a change partway through the file doesn't force rsync to actually re-transfer all of the subsequent unmodified chunks, but it does incur a computational cost to find them since it has to search through all possible offsets.
I took a quick glance at the repo, it wasn't totally clear to me if the client is windows only. Anyone know more?
TL;DR they rediscovered the context-dependent variable block size technique that Tarsnap uses: https://www.tarsnap.com/download/EuroBSDCon13.pdf
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_...
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…
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, November, 2019.