chunking algorithms

[LaurentBonnaud]

Hi,

this approach for deduplication seems interesting:

https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf

It has led to a x2 speed-up in zstd:

facebook/zstd#2483

How about using it in borg-backup?

[ThomasWaldmann]

Sounds interesting.

Update: some more links:

• https://pypi.org/project/fastcdc/ (Python) https://github.com/iscc/fastcdc-py
• https://github.com/wxiacode/FastCDC-c
• http://ranger.uta.edu/~jiang/publication/Journals/2020/2020-IEEE-TPDS(Wen%20Xia).pdf (newer, updated paper)

[callegar]

One way to speed up chunking could be not chunking at all certain file types. For instance, I think that there is no significant advantage in chunking certain types of compressed files, such as gzipped ones, jpeg, pngs and the like, for which it is extremely improbable to find companions offering a little binary delta, because even a small change in the compressed data can cause large and widespread changes in the compressed file. Other types of compressed files where the compression is practiced on items that are smaller than the whole file (e.g. zips, pdfs, some audio files) may stil benefit from chunking, though.

I wonder if it could make sense to teach borg to follow user indications on a file basis for chunking, similarly to how git can have attributes attached to files. This mechanism could also be used to avoid recompressing stuff that is already compressed.

Incidentally, not chunking files that do not benefit from it would leave a margin for using more aggressive chunking params for files that do benefit from it.

[ThomasWaldmann]

We already had a similar discussion for compression and even had code for file-type-based compression. In the end, we removed that again for a simple "auto" compression decider that does not need a lot of configuration.

For the chunker, IIRC:

• if a file is below the minimum chunk size, it immediately returns 1 chunk with the full file
• for big files, we always need multiple chunks because the borg repo code can not store more than ~8MiB in one piece (this also makes sure we have manageable piece sizes for in-memory processing)
• in 1.2, we'll have also a fixed-chunksize chunker that is very light on the cpu (e.g. for block devices, fixed-recordsize DBs, etc.). even has sparse file / sparse map support.
• KISS (keep it simple & "stupid")

That said, speedups for CDC would be nice, just let us not make it too complicated.

[Glandos]

New kid in town: QuickCDC http://www.cloud-conf.net/ispa2021/proc/pdfs/ISPA-BDCloud-SocialCom-SustainCom2021-3mkuIWCJVSdKJpBYM7KEKW/264600a288/264600a288.pdf

I don't know of any implementation though.

[Glandos]

See also UltraCDC I described in #3026 (comment)

[ThomasWaldmann]

#8803 opens the door for a unique opportunity: re-chunking while doing a borg2 transfer (which will be required anyway for transferring archives from borg1 repos to borg2 repos).

So, if borg2 gets a new chunker, we can use it there.

[ThomasWaldmann]

About fastCDC: isn't the small window size of only up to 64bytes an issue for chunking? borg usually uses 4095 bytes, so it includes way more context into the chunking point decision.

See #8903 for a buzhash64 chunker.

[ThomasWaldmann]

borg2's buzhash64 chunker improved: #9823

[ThomasWaldmann]

fastcdc chunker: #9824 - now merged.