tar export / import tuning ideas

[ThomasWaldmann]

idea from DiVOC borg session: speed-optimize tar pipe

Problem: for big repos, the tar-pipe could take rather long:

• tar-export would read content chunks again and again via relatively slow connection from a remote repo
  • maybe use borg.remote.cache_if_remote and a big local persistent cache to avoid repeated remote transfer of same chunks.
• the tar-pipe should be between 2 borg processes on same machine, lots of data flowing here!
• tar-import would do lots of chunking and hashing, but would be faster for content of 2nd+ archives due to dedup
  • could additionally use a files cache like create does (for already "seen" and unmodified tarstream items)

Note: an optimisation sending chunkid lists over the tar pipe requires the id hash algorithm+secret and the chunker secret to be identical in both repos.

[ThomasWaldmann]

tuning source repo for export-tar

Thinking about my post above:

• source repo: likely there are multiple archives in there with a lot of overlap in referenced chunks
• if we want to copy all these archives using the tar pipe, the local cache for tar-export would need to cover all or most of these overlapping chunks (ideally all non-unique chunks), which I guess are frequently a high percentage of the overall volume of the repo (50-99%?). if we use a smaller cache, stuff we would still need for the next archive would be kicked out of the cache due to the insufficient size.

using the cache_if_remote code

• the cache code we have in cache_if_remote is made for smaller caches of a few GBs, not for TBs. uses temp dir, erases all temp stuff at the end, simple flat file storage. good: can use a decrypted storage saving some decryption effort.
• it seems that just making a local copy of the remote repo might be easier and faster. just create a local repo and transfer all the chunks and then work with the local repo for doing the tar export. IF we want to export all archives, this is the most efficient way considering all stuff is deduplicated already and transferred exactly once.
• not sure if we want to optimise for not transferring all archives but just some:
  • gets way more complicated, we need to read these archives and only fetch the referenced chunks
  • due to the likely high overlap, we would still transfer a high percentage of the overall volume

using a full blown local temp REPO as cache

• using a full blown Repository as cache while doing the export-tar
• just try local first before fetching from remote
• maybe the best approach. will only fetch what it needs, will only fetch once.
• unencrypted local repo is faster as a cache
• either keep existing compression of remote repo chunks or decompress once, locally compress with lz4. considering export-tar will need to decompress the chunks and also expand all the duplicated chunks to their full volume for each archive to create the tar stream, having something with fast decompression (== lz4) is likely more efficient.
• a full blown repo is obviously made for that amount of data, unlike that cache_if_remote code.

using a manual local repo copy

• let the user just copy the remote repo to a local fs (e.g. rsync or similar tools)
• similar properties as previous section, except that encryption and compression stays the same
• decryption and decompression will cause some overhead, but decompression in general is relatively fast and decryption might be as well (AES is often hw accelerated), thus maybe not that bad overall.
• borg recreate (recompress) could be used to transform to faster lz4
• no code to write for this :-)

[ThomasWaldmann]

tuning import-tar

• the point of the files cache we use for the filesystem is not having to read/chunk/hash the files' content IF they did not change and we already have all the chunks in the repo.
• thinking about the tar pipe: the files' content is incoming anyway over the tar pipe, because that's what export-tar does. we have no way to not read it.
• thus, a files cache here would not save us from reading the content, we only could optimize for not chunking and not id hashing it multiple times.
• chunker: the default buzhash chunker is a bit slow / cpu intensive
• id hashing: for the target repo we likely will have either blake3 or hw accelerated hmac-sha256, both is super fast.

[elho]

A couple of thoughts on/sparked by above ideas:

• (copied) Manually transferring the remote repo onto the machine that does the export/import work does eliminate the network bottleneck, but still leaves decompression and local storage as bottlenecks. Luckily decompression is much faster than compression even for slow algorithms, but its still quite slow when thinking 5 years of daily archives of multiple TBs of size of which 98% has not changed at all in that time and comparing that to how a perfect in-place transformation of the repo that only ever touches any chunk once could perform.
• The local (uncompressed) temporary repo as cache stored on a fast NVMe (suitable for permanent read load) still means for above example 5*365*5 TB ~ 9 PB need to be read, (decrypted unless very desperate 😉) and chunked to basically transfer what is a repo that deduplicates to just a bit more than 5 TB.
• Another hackish approach (kinda best one could do without code change) would be to transfer (e.g. rsync) the source repo to fast local storage, recreate recompress it to none compressor (ie. efficiently decompress it, any chunk only being decompressed once), compact it, create some temporary fs on the local storage, extract the oldest archive reading and decrypting all data once, create a new archive in the target repo from that, which yields a file cache, next stating to iterate over all archives by doing a borg diff --json of the last archive done to the next, parsing out the path names and writing those in the format of a borg pattern file of pf type (fixed paths) that is used to then extract only those files that are affected by any changes over those in the temporary fs, finally borg creating on it again to the target for the new archive, which will make use of the files cache for the unchanged files. With borg diff using the chunk ids that make up a file to determine content change this saves a lot of reading from the local cache repo and with leveraging the files cache also a lot of rechunking (also reading, but can not count that twice 😉). The disadvantage is requiring more than twice the amount of storage of the repo (the better compressed that is, the worse) and that file-metadata only changes result in the content to not only still be read and rechunked, but in this case read twice and written in between. Things like adding a option for extract to only apply meta-data changes, ie. "bring permissions, ACLs, xattrs, ....) of all files in the target fs to the state of the same paths in this archive" that could help in other cases (new admins failed usage of chown/chmod -R 😉) could help further optimizing this.
• All the approaches using local storage as means of optimization are problematic - the highest need of users to optimize the process is for the huge repos with TB sizes. This means providing the required amount of available local storage more demanding for the users and also lessens the chance of that storage being e.g. a fast NVMe (or array thereof) and more likely e.g. some slow external USB drive. This gives reading from that local storage as bottleneck a higher impact.

Taking back a step and trying to think of ways to get closer to the theoretic ideal point where any chunk only needed to be brought over once leads to these ideas:

Preserve Chunking

• Would keeping the old chunker seed (and of course params) be bad (assuming the repo has never been compromised)?
• Have some sort of "expert" init parameter that allows for creating the target repo with the seed of the source (related: initialise a borg repo reusing existing key material #6554)
• Have export/import make some use of this.
  • It could be some a format to stream the whole repo (could still be abused tar, but chunkid as filename and the chunk contents thereafter) in both a leave chunk as is variant (for non-migration use-cases) and one that has the chunks decrypted for upgrades that break crypto. (Upgrade breaking compression right now could be handled by recreate recompress with the old borg version)
  • It could be a format that is kind of like a sequence of borg PAX format archives, that include an extra custom header listing the chunkids a given file is made of (saving the import side to do the chunking and use it) and, with a temporary cache of already exported chunkids, allow to only write into the stream chunks that have not been in it before (saving to read and pipe any chunk more than once). Ie. a file in an archive that has not been changed would in the PAX archive look like an empty file, but have that extra header indicating which chunks it should refer when imported into a repo with the chunker params and seed as would be given in some header at the very beginning. Attempt to import that to any repo that does not have the same parameters would fail with an error.
• This would not be suitable for a breaking change that e.g. changes the chunking algorithm, but very useful in scenarios like carrying history over into an additional remote at a different location.
• I wonder, given 2 repos with identical chunker params and seeds, how much of this could already be done in a shell script using the various borg debug commands. 😜

Chunk ID Linking Cache

• When not keeping chunker seed, params or hash the same, but still desiring to achieve similar optimization, one would face the question "is this version of the file already in the target repo my merits of another archive that already has been imported or is it a new version as seen by the target?"
• A file (content) "version" would be identified within the scope of a repository by the chunkids of the chunks that make up its content
• To answer above question, one (a cache) would need to correlate ("link") these chunkid based file version identifiers of the source repo to the target repo.
• For the source repo, export would store in the cache for each unique file content encountered the chunkids the file entry in the archive meta-data references, the path and the name(s) of the archive(s) that have referenced it.
• Export/import being done by two different borg processes and maybe even versions requires things to be less bullet-proof at this point and rely on the user not dooing foolish things (e.g not renaming archives in between of export/import sessions).
• Export/import could still handle single archives, but like in the "preserve chunking" idea, custom headers would transprot the file version identity and file versions that had been exported before have their content omitted, those that have not are (that is the difference) stored with their entire content, just like current export does.
• The file version identity information included by export could be the chunkids as per source repo, the importing side for the target repo would then have a sort of "import session cache" that during import records the chunkids of the source repo as found in the custom PAX header, the path, the name(s) of the archive(s) created by import that contained these and the chunkids used in the created archive.
• Import encountering file content not in the cache, it will be sent through the chunker (resulting chunkids added to the cache) and those chunks that are not in the normal repo chunk cache yet will be compressed, encrypted, transferred and written as usual, for content found in the import session cache, the cache entry will have the new archive name added and the known target repo chunkids from that cache entry will be used to create a file entry in the meta-data of the new archive referencing these and carrying all the other meta-data from the PAX headers without the need of any chunking.
• This only optimizes entirely unchanged files, but with different chunking one can not do better. For use cases like backups of huge VM images changing by small amounts between every archive, it will not bring any benefits. However for typical use cases where most of the deduplication is files not being touched for a long time (system files when running stable distro releases, collections of media files, ...), it would be a big step up from fully processing each archive.

[ThomasWaldmann]

@elho thanks for your thoughts!

• i updated my plan above with the item marked as (copied)
• preserve chunking:
  • this sounds very good for performance and keeping (some parts of) the borg key is planned anyway (I linked the issue).
  • for the transfer itself, we do not need to consider chunker seed, params and algorithm, we just transfer chunks and chunkids as they are.
  • but later in the destination repo we of course should use same chunker seed, algorithm, params plus the same id hash/mac and id key to not break the dedup by creating differently cut or id'ed chunks.
  • i guess i would rather always decrypt and decompress at the source - the plaintext chunk can then be compressed within the tar stream (.tar.gz or whatever) - decoupling is good, this is for migrations.
• chunkid linking:
  • gets a bit complicated for that case
  • but there is an easier case also: only changing the id hash / key, but keeping the chunking (for that, a simple old-id <-> new-id map would suffice). that way we e.g. could drop e.g. blake2b as id-hash (and use blake3).

[elho]

• for the transfer itself, we do not need to consider chunker seed, params and algorithm, we just transfer chunks and chunkids as they are.

The sole reason for my suggestion to include the parameters in the export-tar header was as a safeguard allowing the "later" import-tar to give an error message preventing users from accidentally stuffing the as-is chunks into the wrong or a wrongly initalized target repo that does not use matching parameters.

• i guess i would rather always decrypt and decompress at the source - the plaintext chunk can then be compressed within the tar stream (.tar.gz or whatever) - decoupling is good, this is for migrations.

My main motivation to suggest (and if implemented use) chunk preserving in a migration is the use case of migrating a large repo using strong compression (LZMA, high ZSTD level) to newer crypto (e.g. nonce-free) or as a means of rekeying and being able to have that done in a matter of hours to days instead of weeks to months thanks to keeping chunks in their compressed state.
(And what would amount to weeks and months in theoriy, would in many cases in practice mean users not migrating, sticking to lesser crypto and some older borg version).

Side-note: As we kinda agreed that the tar stream basically should only ever be transferred through a local pipe between two borg processes on the same system, compressing that makes no sense. 🙂

[ThomasWaldmann]

there were some tuning attempts in #6643, but i gave up on that because borg transfer (which just works with 2 repos) can work much more efficiently than transferring stuff over the tar pipe.

so guess we can close this one also and just use that.