packs: add an encrypted object directory at the end of each pack, for a fast index rebuild

[ThomasWaldmann]

Problem

Rebuilding the chunk index from the packs (build_chunkindex_from_repo in src/borg/cache.py, used when there are no index/ fragments, when cache/chunkindex-invalid is present, by borg check --repair, borg compact, borg repo-compress on a corrupt fragment, ...) walks every pack with PackReader.iter_headers(). That does one store range request per object: a 49-byte header read, or a META_READ_SIZE read with a validator.

With the default 50 MB packs that is:

• ~25 requests per pack for ~2 MiB chunks (default chunker params),
• thousands of requests per pack for small-file data (one chunk per small file).

All of them are sequential. On a high latency backend (sftp, s3/b2, rest over ssh) a rebuild of a 1 TB repository means hundreds of thousands to millions of round trips, i.e. hours, just to read headers.

Reading packs in windows instead of per object (the TODO in iter_headers) would help without any format change, but it still reads a large part of every pack when the objects are small.

Proposal: an encrypted object directory at the end of each pack

Append to every pack:

... objects ... | encrypted_directory | directory_size (uint32le) | DIR_MAGIC (8 bytes)

• encrypted_directory: a list of (chunk_id, obj_offset, obj_size) for all objects in the pack (optionally also the plaintext size, so a rebuilt index does not need size=0 there), stored in the key's store object envelope like the index/ fragments (Repository.key, with its own AAD), so it is encrypted and authenticated.
• directory_size + DIR_MAGIC: a fixed-size trailer, so a reader can find the directory from the end of the pack.

The pack id stays the store hash of all pack bytes, the directory included.

Rebuilding then needs only the pack tails: store_list("packs") already returns every pack's size, so the last N bytes (e.g. 64 KiB, enough for the trailer and most directories) of up to 1000 packs can be read with one store.gather call, plus a second read only for packs with a larger directory. That is a few round trips per thousand packs instead of tens to thousands per pack.

The per-object headers stay as they are. They remain the fallback: a pack whose trailer or directory is missing, damaged or fails authentication is walked as today (including the validating resync of borg check). The directory also defines the objects of a pack exactly, which makes the gap handling in compact_pack / transform_pack simpler.

Writers that need changes

• PackWriter._store_pieces: build the directory from the pieces it already lays out, append it.
• transform_pack (borg repo-compress) and salvage_pack (borg check --repair): build their packs client-side, so they can use the same helper.
• compact_pack and merge_packs (borg compact): build the new pack server side with store.defrag() from byte ranges of the old packs. They must no longer copy the old trailers (merge_packs currently copies whole pack files (pack, 0, pack_size)), and the new pack needs a recomputed directory (offsets rebased, dropped objects removed). merge_packs would build it from the source packs' directories rather than from the chunk index, so the gap objects it carries along stay listed, as a header walk would find them.

Needs: an enhanced Store.defrag in borgstore

Store.defrag(sources, ...) can only concatenate ranges of existing items. borg needs to append the client-computed, encrypted directory, its size and the magic to the defragmented content, so defrag must accept literal bytes, e.g. as a source entry or as a suffix= argument. The target name (algorithm=...) must be computed over the whole new content, suffix included.

• The default backend implementation (gather, then store) can just append the bytes.
• posixfs and the REST backend implement defrag themselves; the REST protocol sends the sources as JSON in the request body, so it needs a way to carry the extra bytes too (e.g. base64 in the JSON, or a binary body part).

Without this, borg compact would have to download and re-upload every pack it rewrites or merges.

Notes

• This changes the pack format, so it needs a new repository version. borg 2 is still in beta, so no compatibility code for packs without a directory is needed.
• This is only about rebuild speed. Moving chunk ids and per-object sizes out of the plaintext headers (they are visible to anyone who can read the storage) is a separate discussion; the directory would be the natural place for them, but that would also need a different resync strategy.

[yashgoyal0110]

Hey @ThomasWaldmann
is it open for contribution?

[ThomasWaldmann]

@yashgoyal0110 Not yet.

First needs discussion and feedback from @mr-raj12 and then timing is important as this will break backwards compatibility again. This is why it is not in b26 milestone, but in b27 (so it stays on the radar).

[mr-raj12]

+1, the one-request-per-object walk is what makes rebuilds slow on remote stores.

Points on the design:

• The directory can not be bound to its pack: the pack id is the (unkeyed) store hash of bytes that include the directory, and compact_pack/merge_packs build the pack server side, so the client can not put a hash of the object region into it either. A valid directory can therefore be copied onto other pack bytes. A plain rebuild can trust it like it trusts the unvalidated header walk today, but borg check should keep the validating walk and compare the directory against it.
• Related: the rebuild is last-pack-wins per chunk id, and borg compact drops gap blobs the index maps elsewhere. A wrong directory entry must not get a good copy dropped that way (compact, repo-compress: superseded duplicate dropped when its indexed copy is in a missing or corrupt pack #10474).
• With pack object header: also authenticate meta_size and data_size (whole header as AAD) #10486, checking a directory entry against its object is one metadata slot read: the tag then covers chunk id and both sizes. So pack object header: also authenticate meta_size and data_size (whole header as AAD) #10486 should go first, and the directory needs no meta_size/data_size split.
• Yes to the plaintext size in the entries.
• merge_packs: a source pack without a valid directory needs a header walk first, or has to be left out of the merge.

Timing: same release as #10486, one repository version bump. The borgstore defrag change comes first, it decides whether both make b27.