Listing possible chunking algorithm

[DonaldTsang]

Does it have static chunking and dynamic chunking algorithms?

[Stebalien]

Could you explain what you mean by "static" and "dynamic" in this context?

[DonaldTsang]

Static as in uniformal chunk size, dynamic as in Rabin-Karp or other algorithms that chunks using something context aware or uses a "sliding window" technique for chunking

See: https://github.com/YADL/yadl/wiki/Rabin-Karp-for-Variable-Chunking

[Stebalien]

Ah. Yes, we actually have both. You can find the different splitters listed in the godoc: https://godoc.org/github.com/ipfs/go-ipfs-chunker.

[Stebalien]

(closing for tracking purposes, feel free to ask followup questions and/or reopen)

[DonaldTsang]

@Stebalien I have heard from @flyingzumwalt that dynamic chunking does not work, possibly due to the blocks being too large or that there are better algorithms for doing dynamic chunking.

[Stebalien]

Dynamic chunking does work. There are better algorithms but the current algorithm definitely works (well, as long as the data isn't compressed).

[DonaldTsang]

So what is the default chunk size in dynamic chunking? Also, has there been any benchmarks that proves the chunker works? References: ipfs-inactive/archives#134 ipfs-inactive/archives#142 ipfs/notes#183 restic/chunker#19 ipfs-inactive/archives#137

[Stebalien]

So what is the default chunk size in dynamic chunking?

256KiB (same as the static chunker) with a min of 85KiB and a max of 512KiB.

Also, has there been any benchmarks that proves the chunker works?

Published? Not that I know. I've seen several of those threads but both @jbenet and I have tested rabin locally and it seems to work quite well on some workloads (but not others). Specifically, he was able to significantly compress his collection of keynote presentations.

(better chunkers and better benchmarks would, of course, be welcome)

[DonaldTsang]

@Stebalien ipfs-inactive/archives#142 has notes on "content specific chunking"
For general chunking, I have seen a list of material pointing to FastCDC

• https://www.usenix.org/sites/default/files/conference/protected-files/atc16_slides_xia.pdf
• https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf
• https://www.usenix.org/node/196197

Also some alternatives like Asymmetric Extremum exists

• http://9livesdata.com/wp-content/uploads/2017/04/Bimodal-Content-Defined-Chunking-for-Backup-Streams.pdf
• http://ykzhou.hustbackup.cn/papers/AE-TC.pdf
• https://dl.acm.org/citation.cfm?id=3066481
• https://www.researchgate.net/publication/305720121_A_Fast_Asymmetric_Extremum_Content_Defined_Chunking_Algorithm_for_Data_Deduplication_in_Backup_Storage_Systems

And http://www.ijarcsms.com/docs/paper/volume4/issue6/V4I6-0021.pdf gives a lot of good info

[yuanjingsong]

Hi, I found an open source implementation on FastCDC in Golang, maybe it's helpful :) https://github.com/tigerwill90/fastcdc