Data structures and file formats¶

This page documents the internal data structures and storage mechanisms of Borg. It is partly based on mailing list discussions and also on static code analysis.

Repository¶

Borg stores its data in a Repository, which is a key-value store and has the following structure:

config/

readme: simple text object telling that this is a Borg repository
id: the unique repository ID encoded as hexadecimal number text
version: the repository version encoded as decimal number text
manifest: some data about the repository, binary
space-reserve.N: purely random binary data to reserve space, e.g. for disk-full emergencies

cache/

checked-packs: repository check results (pack id -> timestamp, result), as a hashtable with an appended integrity hash. Records are kept across checks: check --max-age skips packs whose intact record is younger than the given age, and partial checks (--max-duration) verify the least-recently-checked packs first so repeated runs cover the whole repository. Records of corrupt packs are kept for repair and always re-verified. Records of packs no longer listed in packs/ are pruned when a check finishes.

There is a list of pointers to archive objects in this directory:

archives/: 0000… .. ffff…

The actual data is stored into a nested directory structure, using the full object ID as name. Each (encrypted and compressed) object is stored separately.

data/

00/ .. ff/

00/ .. ff/: 0000… .. ffff…

keys/

When using repokey mode, the encrypted, passphrase protected borg keys are stored here as a base64 encoded text. The sha256 content hash of the stored borg key is used for the name.

A repository may contain multiple such borg keys (one per passphrase) to support the multiple borg keys feature. keyfile and repokey borg keys use the same format and naming (only the storage location differs).

locks/

used by the locking system to manage shared and exclusive locks.

Keys¶

Repository object IDs (which are used as key into the key-value store) are byte strings of fixed length (256-bit, 32 bytes), computed like this:

key = id = id_hash(plaintext_data)  # plain = not encrypted, not compressed, not obfuscated

The id_hash function is selected via borg repo-create --id-hash (independently of --encryption). For encrypted repositories it is a keyed MAC over the plaintext (keyed by id_key): sha256 selects HMAC-SHA256, blake3 selects a keyed BLAKE3. The unencrypted none mode uses a plain sha256.

As the id / key is used for deduplication, id_hash must be a cryptographically strong hash or MAC.

Repository objects¶

Each repository object is stored separately, under its ID into data/xx/yy/xxyy…

A repo object has a structure like this:

32-bit meta size
32-bit data size
meta
data

The overall size of repository objects varies from very small (a small source file will be stored as a single repository object) to medium (big source files will be cut into medium-sized chunks of some MB).

Metadata and data are separately encrypted and authenticated (depending on the user’s choices).

See Encryption for a graphic outlining the anatomy of the encryption.

Repo object metadata¶

Metadata is a MessagePack-encoded (and encrypted/authenticated) dict with:

ctype (compression type 0..255)
clevel (compression level, one byte, interpreted depending on ctype - see Compression)
csize (overall compressed (and maybe obfuscated) data size)
psize (only when obfuscated: payload size without the obfuscation trailer)
size (uncompressed size of the data)

Having this separately encrypted metadata makes it more efficient to query the metadata without having to read, transfer and decrypt the (usually much bigger) data part.

The compression ctype and clevel is explained in Compression.

Compaction¶

borg compact is used to free repository space. It will:

list all object IDs present in the repository
read all archives and determine which object IDs are in use
remove all unused objects from the repository
inform / warn about anything remarkable it found:
- warn about IDs used, but not present (data loss!)
- inform about IDs that reappeared that were previously lost
compute statistics about:
- compression and deduplication factors
- repository space usage and space freed

The object graph¶

On top of the simple key-value store offered by the Repository, Borg builds a much more sophisticated data structure that is essentially a completely encrypted object graph. Objects, such as archives, are referenced by their chunk ID, which is cryptographically derived from their contents. More on how this helps security in Structural Authentication.

The manifest¶

Compared to borg 1.x:

the manifest moved from object ID 0 to config/manifest
the archives list has been moved from the manifest to archives/*

The manifest is rewritten each time an archive is created, deleted, or modified. It looks like this:

{
    'version': 1,
    'timestamp': '2017-05-05T12:42:23.042864',
    'item_keys': ['acl_access', 'acl_default', ...],
    'config': {},
    'archives': {
        '2017-05-05-system-backup': {
            'id': b'<32 byte binary object ID>',
            'time': '2017-05-05T12:42:22.942864',
        },
    },
}

The version field can be either 1 or 2. The versions differ in the way feature flags are handled, described below.

The timestamp field is used to avoid logical replay attacks where the server just resets the repository to a previous state.

item_keys is a list containing all Item keys that may be encountered in the repository. It is used by borg check, which verifies that all keys in all items are a subset of these keys. Thus, an older version of borg check supporting this mechanism can correctly detect keys introduced in later versions.

config is a general-purpose location for additional metadata. All versions of Borg preserve its contents.

Feature flags¶

Feature flags are used to add features to data structures without causing corruption if older versions are used to access or modify them. The main issues to consider for a feature flag oriented design are flag granularity, flag storage, and cache invalidation.

Feature flags are divided in approximately three categories, detailed below. Due to the nature of ID-based deduplication, write (i.e. creating archives) and read access are not symmetric; it is possible to create archives referencing chunks that are not readable with the current feature set. The third category are operations that require accurate reference counts, for example archive deletion and check.

As the manifest is always updated and always read, it is the ideal place to store feature flags, comparable to the super-block of a file system. The only problem is to recover from a lost manifest, i.e. how is it possible to detect which feature flags are enabled, if there is no manifest to tell. This issue is left open at this time, but is not expected to be a major hurdle; it doesn’t have to be handled efficiently, it just needs to be handled.

Lastly, cache invalidation is handled by noting which feature flags were and which were not understood while manipulating a cache. This allows borg to detect whether the cache needs to be invalidated, i.e. rebuilt from scratch. See Cache feature flags below.

The config key stores the feature flags enabled on a repository:

config = {
    'feature_flags': {
        'read': {
            'mandatory': ['some_feature'],
        },
        'check': {
            'mandatory': ['other_feature'],
        }
        'write': ...,
        'delete': ...
    },
}

The top-level distinction for feature flags is the operation the client intends to perform,

the read operation includes extraction and listing of archives,
the write operation includes creating new archives,
the delete (archives) operation,
the check operation requires full understanding of everything in the repository.

These are weakly set-ordered; check will include everything required for delete, delete will likely include write and read. However, read may require more features than write (due to ID-based deduplication, write does not necessarily require reading/understanding repository contents).

Each operation can contain several sets of feature flags. Only one set, the mandatory set is currently defined.

Upon reading the manifest, the Borg client has already determined which operation should be performed. If feature flags are found in the manifest, the set of feature flags supported by the client is compared to the mandatory set found in the manifest. If any unsupported flags are found (i.e. the mandatory set is not a subset of the features supported by the Borg client used), the operation is aborted with a MandatoryFeatureUnsupported error:

Unsupported repository feature(s) {‘some_feature’}. A newer version of borg is required to access this repository.

Older Borg releases do not have this concept and do not perform feature flags checks. These can be locked out with manifest version 2. Thus, the only difference between manifest versions 1 and 2 is that the latter is only accepted by Borg releases implementing feature flags.

Therefore, as soon as any mandatory feature flag is enabled in a repository, the manifest version must be switched to version 2 in order to lock out all Borg releases unaware of feature flags.

Cache feature flags

The cache does not have its separate set of feature flags. Instead, Borg stores which flags were used to create or modify a cache.

All mandatory manifest features from all operations are gathered in one set. Then, two sets of features are computed;

those features that are supported by the client and mandated by the manifest are added to the mandatory_features set,
the ignored_features set comprised of those features mandated by the manifest, but not supported by the client.

Because the client previously checked compliance with the mandatory set of features required for the particular operation it is executing, the mandatory_features set will contain all necessary features required for using the cache safely.

Conversely, the ignored_features set contains only those features which were not relevant to operating the cache. Otherwise, the client would not pass the feature set test against the manifest.

When opening a cache and the mandatory_features set is not a subset of the features supported by the client, the cache is wiped out and rebuilt, since a client not supporting a mandatory feature that the cache was built with would be unable to update it correctly. The assumption behind this behaviour is that any of the unsupported features could have been reflected in the cache and there is no way for the client to discern whether that is the case. Meanwhile, it may not be practical for every feature to have clients using it track whether the feature had an impact on the cache. Therefore, the cache is wiped.

When opening a cache and the intersection of ignored_features and the features supported by the client contains any elements, i.e. the client possesses features that the previous client did not have and those new features are enabled in the repository, the cache is wiped out and rebuilt.

While the former condition likely requires no tweaks, the latter condition is formulated in an especially conservative way to play it safe. It seems likely that specific features might be exempted from the latter condition.

Defined feature flags

Currently no feature flags are defined.

From currently planned features, some examples follow, these may/may not be implemented and purely serve as examples.

A mandatory read feature could be using a different encryption scheme (e.g. session keys). This may not be mandatory for the write operation - reading data is not strictly required for creating an archive.
Any additions to the way chunks are referenced (e.g. to support larger archives) would become a mandatory delete and check feature; delete implies knowing correct reference counts, so all object references need to be understood. check must discover the entire object graph as well, otherwise the “orphan chunks check” could delete data still in use.

Archives¶

Each archive is an object referenced by an entry below archives/. The archive object itself does not store any of the data contained in the archive it describes.

Instead, it contains a list of chunks which form a msgpacked stream of items. The archive object itself further contains some metadata:

version
name, which might differ from the name set in the archives/* object. When borg check rebuilds the manifest (e.g. if it was corrupted) and finds more than one archive object with the same name, it adds a counter to the name in archives/, but leaves the *name field of the archives as they were.
item_ptrs, a list of “pointer chunk” IDs. Each “pointer chunk” contains a list of chunk IDs of item metadata.
command_line, the command line which was used to create the archive
hostname
username
time and time_end are the start and end timestamps, respectively
comment, a user-specified archive comment
chunker_params are the chunker-params used for creating the archive. This is used by borg recreate to determine whether a given archive needs rechunking.
Some other pieces of information related to recreate.

Items¶

Each item represents a file, directory or other file system item and is stored as a dictionary created by the Item class that contains:

path
list of data chunks (size: count * ~40B)
user
group
uid
gid
mode (item type + permissions)
source (for symlinks)
hlid (for hardlinks)
rdev (for device files)
mtime, atime, ctime, birthtime in nanoseconds
xattrs
acl (various OS-dependent fields)
flags
digests, hash digests over the full content of a regular file, see Item digests

Item digests¶

If asked to (--digests ALGOS, e.g. --digests=blake3), borg create and borg import-tar compute hash digests over the full content of each regular file and store them in the item’s digests dict, mapping the hash algorithm name to the digest, e.g. {"blake3": b"..."} (32 bytes / 256 bits for blake3). The digest of the content is the same as the one an external tool like b3sum computes - in contrast to the chunk ids, it does not depend on the chunker or on borg’s key.

The same algorithms are available as borg list format keys, and borg list --format "{blake3}" uses a stored digest if the item has one (otherwise it reads the file content to compute it).

Digests are off by default (--digests=none): the content is hashed while it is read and processed anyway, mostly by a background thread (our hash implementations release the GIL), so one hash algorithm usually does not make borg create slower for bigger files - but many small files are hashed by the main thread, and several algorithms are hashed one after the other, which the background thread may not be able to hide.

Digests are not computed if borg does not read the full content of a file:

an unchanged file (the files cache knows it) is not read again - borg takes the digests from the files cache. Files that are already in the files cache without digests only get them when they are read again (that is, when they change), so changing --digests only affects files that borg reads.
the additional hard links to a file are not read again, they get the digests of the first one.
borg create --reuse-from reuses chunks of a reference archive without reading them, so the resulting item does not have digests.

All items are serialized using msgpack and the resulting byte stream is fed into the same chunker algorithm as used for regular file data and turned into deduplicated chunks. The reference to these chunks is then added to the archive metadata. To achieve a finer granularity on this metadata stream, we use different chunker params for this chunker, which result in smaller chunks.

A chunk is stored as an object as well, of course.

Chunks¶

Borg has these chunkers (the default is “fastcdc”):

“fixed”: a simple, low cpu overhead, fixed blocksize chunker, optionally supporting a header block of different size.
“fastcdc”: variable, content-defined blocksize, uses the window-less, keyed Gear rolling hash (FastCDC); faster than buzhash, same deduplication.
“buzhash64”: similar to “buzhash”, but improved 64bit implementation
“buzhash”: variable, content-defined blocksize, uses a rolling hash computed by the Buzhash algorithm.
“toeplitz-aes”: like “rabin-aes”, but the universal hash is a tabulated LFSR/Toeplitz hash (secret 2 KiB table, fixed public polynomial); same speed as “rabin-aes” with the best collision bound of the three.
“rabin-aes”: variable, content-defined blocksize; a rolling Rabin fingerprint (secret polynomial) post-processed with AES-128, so the cut decision only depends on the AES output (“UHF-then-PRF” construction). Strongest available protection against chunk-size fingerprinting attacks.
“goldilocks-aes”: like “rabin-aes”, but the universal hash is a polynomial hash over the Goldilocks prime field (the reference construction of the underlying paper); about half the rabin-aes speed, mainly a comparison baseline.

All chunkers support sparse file processing (borg create --sparse): hole ranges in the input file are then detected (via SEEK_HOLE/SEEK_DATA) and seeked over instead of being read, processing their content as all-zero.

For some more general usage hints see also --chunker-params.

“fixed” chunker¶

The fixed chunker triggers (chunks) at even-spaced offsets, e.g. every 4MiB, producing chunks of same block size (the last chunk is not required to be full-size).

Optionally, it supports processing a differently sized “header” first, before it starts to cut chunks of the desired block size. The default is not to have a differently sized header.

borg create --chunker-params fixed,BLOCK_SIZE[,HEADER_SIZE]

BLOCK_SIZE: no default value, multiple of the system page size (usually 4096 bytes) recommended. E.g.: 4194304 would cut 4MiB sized chunks.
HEADER_SIZE: optional, defaults to 0 (no header).

“fastcdc” chunker¶

FastCDC content-defined chunker using the Gear rolling hash. Unlike buzhash it is window-less (each byte’s influence simply decays out of the hash), so its update is cheaper and it chunks noticeably faster, while producing the same deduplication and (with normalized chunking) the same chunk-size distribution.

Like “buzhash64”, the Gear table is cryptographically derived from secret key material, so chunk cut points are unpredictable without the key.

borg create --chunker-params fastcdc,CHUNK_MIN_EXP,CHUNK_MAX_EXP,HASH_MASK_BITS,NC_LEVEL can be used to tune the chunker parameters, the default is:

CHUNK_MIN_EXP = 19 (minimum chunk size = 2^19 B = 512 kiB)
CHUNK_MAX_EXP = 23 (maximum chunk size = 2^23 B = 8 MiB)
HASH_MASK_BITS = 21 (target chunk size ~= 2^21 B = 2 MiB)
NC_LEVEL = 2 (normalized chunking level, 0 disables it)

There is no window size (Gear is window-less). Normalized chunking varies the cut-point mask around the target size, which tightens the chunk-size distribution and reduces clamping at the min./max. chunk size.

This is the default chunker (fastcdc,19,23,21,2), also used for the item metadata stream (with a finer granularity, fastcdc,15,19,17,2).

“buzhash64” chunker¶

Similar to “buzhash”, but using 64bit wide hash values.

The buzhash table is cryptographically derived from secret key material.

These changes should improve resistance against attacks and also solve some of the issues of the original (32bit / XORed table) implementation.

“buzhash” chunker¶

The buzhash chunker triggers (chunks) when the last HASH_MASK_BITS bits of the hash are zero, producing chunks with a target size of 2^HASH_MASK_BITS bytes.

Buzhash is only used for cutting the chunks at places defined by the content, the buzhash value is not used as the deduplication criteria (we use a cryptographically strong hash/MAC over the chunk contents for this, the id_hash).

The idea of content-defined chunking is assigning every byte where a cut could be placed a hash. The hash is based on some number of bytes (the window size) before the byte in question. Chunks are cut where the hash satisfies some condition (usually “n numbers of trailing/leading zeroes”). This causes chunks to be cut in the same location relative to the file’s contents, even if bytes are inserted or removed before/after a cut, as long as the bytes within the window stay the same. This results in a high chance that a single cluster of changes to a file will only result in 1-2 new chunks, aiding deduplication.

Using normal hash functions this would be extremely slow, requiring hashing approximately window size * file size bytes. A rolling hash is used instead, which allows to add a new input byte and compute a new hash as well as remove a previously added input byte from the computed hash. This makes the cost of computing a hash for each input byte largely independent of the window size.

Borg defines minimum and maximum chunk sizes (CHUNK_MIN_EXP and CHUNK_MAX_EXP, respectively) which narrows down where cuts may be made, greatly reducing the amount of data that is actually hashed for content-defined chunking.

borg create --chunker-params buzhash,CHUNK_MIN_EXP,CHUNK_MAX_EXP,HASH_MASK_BITS,HASH_WINDOW_SIZE can be used to tune the chunker parameters, the usual values are:

CHUNK_MIN_EXP = 19 (minimum chunk size = 2^19 B = 512 kiB)
CHUNK_MAX_EXP = 23 (maximum chunk size = 2^23 B = 8 MiB)
HASH_MASK_BITS = 21 (target chunk size ~= 2^21 B = 2 MiB)
HASH_WINDOW_SIZE = 4095 [B] (0xFFF) (must be an odd number)

The buzhash table is altered by XORing it with a seed randomly generated once for the repository, and stored encrypted in the keyfile. This is to prevent chunk size based fingerprinting attacks on your encrypted repo contents (to guess what files you have based on a specific set of chunk sizes).

“toeplitz-aes” chunker¶

Like “rabin-aes”, but the universal hash is a tabulated LFSR-based Toeplitz hash (Krawczyk, CRYPTO ‘94): the digest of the 64-byte window is sum_j x^(63-j) * T[b_j] over GF(2)[x] mod P, where T is a secret random table of 256 64-bit values (2 KiB of key material) and P is a fixed public irreducible polynomial of degree 64. The AES-128 PRF layer is the same as for “rabin-aes”. Two distinct windows collide with probability exactly 2^-64 over the choice of T - the best possible bound for a 64-bit digest, and unconditional (no secret polynomial sampling). The rolling update contains no secret-dependent memory access. Speed is on par with “rabin-aes”. See Chunkers for a comparison of all chunkers.

borg create --chunker-params toeplitz-aes,CHUNK_MIN_EXP,CHUNK_MAX_EXP,HASH_MASK_BITS,NC_LEVEL

The window size is fixed at 64 bytes. NC_LEVEL is the normalized chunking level (0 disables it); 2 is a good default. E.g.: toeplitz-aes,19,23,21,2.

“rabin-aes” chunker¶

A “UHF-then-PRF” content-defined chunker, following the provably secure construction of Breaking and Fixing Content-Defined Chunking (Truong et al., 2025): a rolling Rabin fingerprint over GF(2)[x]/P(x) - with P a secret, random, irreducible polynomial of degree 64 - compresses the last 64 bytes into a digest (a universal hash), and AES-128 with a secret key is applied to that digest. The cut decision only looks at the AES output, so observed chunk boundaries are pseudo-random and do not provide usable equations about the chunking secrets, unlike chunkers that cut directly on (keyed) rolling hash bits. Both secrets are derived from the repository key material.

This is the recommended chunker when resistance against chunk-size fingerprinting attacks matters most. It is slower than “fastcdc” (one AES block encryption per scanned byte), but still fast in absolute terms: the implementation batches the AES work through OpenSSL or uses AES hardware instructions (arm64 crypto extensions / x86-64 AES-NI) where available.

borg create --chunker-params rabin-aes,CHUNK_MIN_EXP,CHUNK_MAX_EXP,HASH_MASK_BITS,NC_LEVEL

The window size is fixed at 64 bytes. NC_LEVEL is the normalized chunking level (0 disables it); 2 is a good default. E.g.: rabin-aes,19,23,21,2.

“goldilocks-aes” chunker¶

Like “rabin-aes”, but the universal hash is the reference construction of the same paper: a polynomial hash over the Goldilocks prime field GF(p) with p = 2^64 - 2^32 + 1, evaluated at a secret random point K over the same 64-byte window. The AES-128 PRF layer and the security properties are the same as for “rabin-aes” (the two-window collision bound is even slightly better). It is about half as fast as “rabin-aes” - prime-field multiplies instead of table lookups in the rolling hash - and is provided mainly as a well-understood comparison baseline.

borg create --chunker-params goldilocks-aes,CHUNK_MIN_EXP,CHUNK_MAX_EXP,HASH_MASK_BITS,NC_LEVEL

The window size is fixed at 64 bytes. NC_LEVEL is the normalized chunking level (0 disables it); 2 is a good default. E.g.: goldilocks-aes,19,23,21,2.

The files cache¶

The files cache is stored in cache/files.<SUFFIX> and is used at backup time to quickly determine whether a given file is unchanged and we have all its chunks.

In memory, the files cache is a key -> value mapping (a Python dict) and contains:

key: id_hash of the encoded path (same path as seen in archive)
value:
- age (0 [newest], …, BORG_FILES_CACHE_TTL - 1)
- file inode number
- file size
- file ctime_ns
- file mtime_ns
- list of chunk (id, size) tuples representing the file’s contents

To determine whether a file has not changed, cached values are looked up via the key in the mapping and compared to the current file attribute values.

If the file’s size, timestamp and inode number is still the same, it is considered not to have changed. In that case, we check that all file content chunks are (still) present in the repository (we check that via the chunks cache).

If everything is matching and all chunks are present, the file is not read / chunked / hashed again (but still a file metadata item is written to the archive, made from fresh file metadata read from the filesystem). This is what makes borg so fast when processing unchanged files.

If there is a mismatch or a chunk is missing, the file is read / chunked / hashed. Chunks already present in repo won’t be transferred to repo again.

The inode number is stored and compared to make sure we distinguish between different files, as a single path may not be unique across different archives in different setups.

Not all filesystems have stable inode numbers. If that is the case, borg can be told to ignore the inode number in the check via --files-cache.

The age value is used for cache management. If a file is “seen” in a backup run, its age is reset to 0, otherwise its age is incremented by one. If a file was not seen in BORG_FILES_CACHE_TTL backups, its cache entry is removed.

The files cache is a python dictionary. To keep the memory overhead of python objects low, the value is not kept as a python tuple, but in a “compressed” form:

the chunks list is reduced from (256bit chunk id, 32bit size) tuples to bare 32bit indexes into the chunks index (see ChunkIndex.k_to_idx). The chunk id and size are looked up from the chunks index again when the entry is used. This only works while that chunks index is in memory.
the resulting entry is then msgpacked, so one dict value is a single bytes object instead of a nested structure of python objects.

Borg can also work without using the files cache (saves memory if you have a lot of files or not much RAM free), then all files are assumed to have changed. This is usually much slower than with files cache.

The on-disk format of the files cache is a stream of msgpacked tuples (key, value). There, the chunks list is stored in its uncompressed form (chunk id and size), as the chunks index indexes are only valid for one specific in-memory chunks index. Loading the files cache involves reading the file, one msgpack object at a time, unpacking it, and compressing the entry as described above.

The chunks index¶

The chunks index is persisted in the repository as index fragments and loaded in memory. It is used to determine whether we already have a specific chunk.

The chunks index is a key -> value mapping and contains:

key (32 bytes):
- chunk id_hash
value (48 bytes, ChunkIndexEntry in borg.hashindex):
- flags (32bit): F_USED (chunk is used / referenced), F_COMPRESS (chunk shall get re-compressed), F_PENDING (the chunk is still buffered in the pack writer, so its pack location is not resolved yet). The upper 8 bits are reserved for system flags (currently F_NEW) and are not visible to users of the index.
- size (32bit): plaintext chunk size, 0 if not known (see below)
- pack_id (32 bytes): id of the pack file the chunk’s blob is stored in
- obj_offset (32bit): byte offset of the blob inside that pack file
- obj_size (32bit): blob length (header + encrypted_meta + encrypted_data)

The last 3 values are the chunk’s location, see Pack Index Entry: reading a chunk is one ranged read of [obj_offset, obj_offset + obj_size) from packs/<hex(pack_id)>.

So a chunks index entry is 32 + 48 == 80 bytes, and that is also exactly what it needs on disk (the serialized format is just key/value pairs, no padding, plus a small header). In memory, there is some additional overhead, see below.

Not all of that is persisted, though: when an index fragment is written, flags and size are zeroed (only the chunk id and the pack location are of interest there). Thus, a chunks index that was just built from the repository has size == 0 for all its entries, no matter whether it came from the index fragments or from the slow rebuild (which reads the pack headers, where only the stored blob size is known, not the plaintext size).

The plaintext size of an entry is only filled in while borg is running, for the chunks it actually processes: by borg create when it adds or re-uses a chunk, or when the files cache entries of a previous archive are loaded (their chunks lists have the plaintext sizes). So code using the chunks index must be prepared to see size == 0 and must not assume it is the real chunk size.

The chunks index is a HashIndex.

Indexes / Caches memory usage¶

Here is the estimated memory usage of Borg - it’s complicated:

chunk_size ~= 2 ^ HASH_MASK_BITS  (for buzhash chunker, BLOCK_SIZE for fixed chunker)
chunk_count ~= total_file_size / chunk_size

chunks_index_usage = chunk_count * 100

files_cache_usage = total_file_count * 230 + chunk_count * 6

mem_usage ~= chunks_index_usage + files_cache_usage
           = chunk_count * 106 + total_file_count * 230

All units are Bytes.

The 100 Bytes per chunks index entry are the 80 Bytes of the entry itself plus the overhead of the hash table it lives in (see HashIndex): the keys/values arrays are over-allocated by up to 30%, and the bucket table adds another 4 Bytes per bucket at a load factor of 0.25 .. 0.5. So, depending on where between two resizes the index currently is, the real value is somewhere between 88 and 120 Bytes per entry - 100 is a good average.

The files cache numbers are for CPython on a 64bit platform: the ~230 Bytes per file cover the dict slot, the 32 Bytes path hash (as a python bytes object) and the fixed part of the msgpacked value; the ~6 Bytes per chunk are one msgpacked 32bit index into the chunks index.

Both data structures grow by re-allocating and copying, so there are short-time peaks in memory usage while a resize happens (worst case about 2x the values computed above for the structure being resized). Usually this does not happen for all data structures at the same time, though.

It is assuming every chunk is referenced exactly once (if you have a lot of duplicate chunks, you will have fewer chunks than estimated above).

It is also assuming that typical chunk size is 2^HASH_MASK_BITS (if you have a lot of files smaller than this statistical medium chunk size, you will have more chunks than estimated above, because 1 file is at least 1 chunk).

The chunks index and files cache are both implemented as hash tables (the chunks index as a HashIndex, the files cache as a python dict). A hash table must have a significant amount of unused entries to be fast - the so-called load factor gives the used/unused elements ratio.

E.g. backing up a total count of 1 Mi (IEC binary prefix i.e. 2^20) files with a total size of 1TiB.

with create --chunker-params buzhash,10,23,16,4095 (custom):

chunk_count = 16 Mi, chunks_index_usage = 1.56GiB, files_cache_usage = 0.32GiB

mem_usage = 1.9GiB

with create --chunker-params buzhash,19,23,21,4095 (default):

chunk_count = 512 Ki, chunks_index_usage = 0.05GiB, files_cache_usage = 0.23GiB

mem_usage = 0.28GiB

Note

There is also the --files-cache=disabled option to disable the files cache. You’ll save some memory, but it will need to read / chunk all the files as it can not skip unmodified files then.

HashIndex¶

The chunks index is implemented on top of borghash.HashTableNT, which comes from the separate borghash package (Cython). borg.hashindex.ChunkIndex only adds the borg specific parts on top of it: the ChunkIndexEntry namedtuple / struct format and the handling of the system flags.

HashTableNT packs/unpacks the namedtuple value to/from bytes using a struct.Struct and delegates the actual storage to borghash.HashTable, which is a fixed key size / fixed value size bytes -> bytes mapping.

Internally, HashTable is not one, but three arrays:

the bucket table, an array of uint32_t indexes into the keys/values arrays. 0xffffffff marks an empty bucket, 0xfffffffe marks a deleted bucket (tombstone); everything >= 0xffffff00 is reserved, so the usable index range (and thus the maximum number of entries) is a bit below 4Gi.
the keys array, holding key_size (32 for the chunks index) Bytes per entry.
the values array, holding value_size (48 for the chunks index) Bytes per entry.

Keys and values are appended to their arrays in insertion order, so the index of a key in the keys array is stable while the hash table is in memory. The files cache uses that to “compress” chunk ids to 32bit numbers, see ChunkIndex.k_to_idx.

The bucket table has only one slot per bucket, spreading hash collisions to the following buckets. As a consequence the hash is just a start position for a linear search. If a key is looked up that is not in the table, then the bucket table is searched from the start position (the hash) until the first empty bucket is reached.

This particular mode of operation is open addressing with linear probing.

The bucket table is grown (by 2x) when the number of used buckets plus tombstones exceeds 50% of its capacity, and shrunken (to 40%, but never below 1000 buckets) when the number of used buckets drops below 10% of its capacity. So its load factor usually is between 0.25 and 0.5. That is cheap, because a bucket is only 4 Bytes - the bulk of the data is in the keys/values arrays, which are not hash tables and thus do not need any unused space for speed. They are just grown by 1.3x whenever they are full.

If an element is deleted, its bucket is marked with a tombstone (the keys/values array slots are zeroed, but not reclaimed until the next rebuild). Tombstones are only removed by resizing / rebuilding the bucket table. They present the same load to the hash table as a real entry (recall that linear probing for an element not in the index stops at the first empty bucket), which is why they count towards the load factor that triggers the growth.

Data in a HashIndex is stored in little-endian format, which increases efficiency for almost everyone, since basically no one uses big-endian processors any more.

HashIndex does not use a hashing function, because all keys (save manifest) are outputs of a cryptographic hash or MAC and thus already have excellent distribution. Thus, HashIndex simply uses the first 32 bits of the key as its “hash”.

The on-disk format does not mirror the in-memory layout - neither the bucket table nor the unused space of the keys/values arrays are written. A serialized HashIndex is:

First, a header: the eight byte ASCII string “BORGHASH”, an uint32 format version and an uint32 length of the metadata block (all little-endian).
Second, the metadata block, a JSON object with the key size, value size, byte order, the value namedtuple’s name / fields / struct format, the bucket table capacity and the number of entries (“used”).
Third, “used” times a (key, value) pair, without any padding or separators.

So the on-disk size is entries * (key_size + value_size) plus a small header, i.e. exactly 80 Bytes per entry for the chunks index.

Encryption¶

AEAD modes¶

For new repositories, borg only uses modern AEAD ciphers: AES-OCB or CHACHA20-POLY1305.

For each borg invocation, a new sessionkey is derived from the borg key material and the 48bit IV starts from 0 again. The cipher blocks of a chunk do not consume IVs here (CHACHA20-POLY1305 counts them in its internal 32bit block counter, AES-OCB derives the per-block offsets from the IV), so we just count up by 1 per chunk.

The encryption layout is best seen at the bottom of this diagram:

No special IV/counter management is needed here due to the use of session keys.

The 48 bit IV limits the number of messages (chunks and metadata objects) that we encrypt with one session key to 2^48 - borg refuses to encrypt more rather than reusing an IV. That is way more than needed: even if you only backed up 4kiB chunks (2^12B), 2^48 messages would be 2^(12+48)B == 1.2 exabytes of input data, meaning you would run against other limitations (RAM, storage, time) way before that.

How much data we may encrypt with one session key is a different question, which is not answered by the IV size, but by the security bounds of the ciphers, see below.

AEAD usage limits¶

The relevant quantities are the number of encrypted messages (q), the amount of data encrypted with one key and the number of forgery attempts (v, decryptions of tampered data that borg refuses). p is the attacker’s success probability we still consider acceptable. See issue #6501 for the details and for the computations.

Number of messages (both ciphers): limited to 2^48 per session key by the IV size, see above. This is never the binding limit for either cipher.
Data volume (AES-OCB): the attacker’s advantage grows with the square of the amount of data encrypted using one key: about 6 * sigma^2 / 2^128, sigma being the number of 128bit cipher blocks, including the authenticated header. RFC 7253 derives from this bound that one key should encrypt at most 2^48 blocks (4PiB), which corresponds to p == 2^-32. borg aims higher and starts a new session after 2^37 blocks (2TiB), which corresponds to p == 2^-51 per session key.

CHACHA20-POLY1305 does not have such a limit at all: its confidentiality bound does not depend on the amount of data encrypted.
Forgery attempts (CHACHA20-POLY1305): v <= p * 2^103 / (L' + 1), L' being the message length (payload plus authenticated header) in 128bit blocks. For borg’s biggest messages, that is about 2^33 forgery attempts at p == 2^-50, so an attacker would have to make borg read more than 100PiB of tampered data. Note that this is counted over all session keys, so - unlike the data volume limit - it can not be improved by starting more sessions.

For AES-OCB, the corresponding limit is much higher (its 128bit authentication tag gives a term in the order of v * L / 2^128), so the CHACHA20-POLY1305 limit is the one to look at.

We do not count or enforce the forgery attempts limit, we just document it here: a failed decryption means we got tampered or corrupted data and borg refuses it, usually aborting the whole command (borg check and archive listing keep going, but only to report the damage). Getting anywhere near the limit computed above would require feeding borg a lot more tampered data than any real repository will ever hold.

Starting a new session just means computing a new random session id and deriving a new session key from it (and counting the IV from 0 again). That is cheap and it does not need any special handling when reading, because the session id is part of every chunk header. Because the advantages of the individual session keys just add up, frequent session key changes also keep the total advantage low over the lifetime of a borg key.

Modes without encryption¶

The authenticated-* and none-* modes do not encrypt: the payload of a repository object slot (the compressed chunk data resp. the packed metadata, see Repository objects) is stored as-is. Every slot still carries a 32 byte tag:

TYPE(1) + reserved(1) + tag(32) + payload

TYPE is the key type byte (which identifies the mode, see KeyType), reserved is zero. The tag is computed over the envelope header, the AAD and the payload:

aad_full = aad + chunk_id
tag = MAC(tag_key, TYPE || reserved || len16_be(aad_full) || aad_full || payload)

aad is what RepoObj authenticates alongside the payload: the object header prefix (magic, format version, chunk id) and the slot tag (M for meta, D for data), see Pack File Format. Consequently, the tag detects modification of the payload, of the metadata, of the object header, a swap of the meta and the data slot, and an object slice taken from a different object. The length prefix keeps the boundary between the AAD and the payload unambiguous.

There is no nonce, no session and no other state: the tag is deterministic. Two repositories with the same key material therefore store byte-identical objects for identical input, which allows deduplicating them on the filesystem level (e.g. with CoW/dedup tools).

The modes differ in the tag algorithm and in whether they have a key at all:

authenticated-sha256 / authenticated-blake3: the tag is a MAC (HMAC-SHA256 resp. keyed BLAKE3), so only somebody who has the borg key can compute it - this detects malicious tampering, not just accidental corruption. The MAC key is derived from crypt_key:
```
tag_key = sha256(crypt_key + b"borg-repoobj-mac-hmac-sha256")[:32]   # authenticated-sha256
tag_key = sha256(crypt_key + b"borg-repoobj-mac-blake3")[:32]        # authenticated-blake3
```
It is deliberately not derived from id_key: chunk ids are public, and related repositories share the id key (see borg repo-create --other-repo), which must not enable them to forge each other’s objects. --copy-crypt-key shares crypt_key and thus opts into producing byte-identical objects across the related repositories.
none-sha256 / none-blake3: there is no key at all, so the tag is an unkeyed hash (plain SHA-256 resp. BLAKE3 over the same input), i.e. a checksum. It detects accidental corruption and reads that returned the wrong bytes, but anybody who modifies an object can recompute it - it is no protection against malicious tampering. For the same reason, the chunk ids of these modes are unkeyed hashes of the plaintext, which makes all repositories of such a mode dedup identically.

Legacy modes¶

Old repositories (which used AES-CTR mode) are supported read-only to be able to borg transfer their archives to new repositories (which use AEAD modes).

AES-CTR mode is not supported for new repositories and the related code will be removed in a future release.

The same applies to the borg 1.x none and authenticated modes: their envelope is just the type byte followed by the payload, so nothing about an object is verified except the chunk id over the plaintext. They were replaced by the tagged modes described above.

All modes¶

Encryption keys (and other secrets) are kept either in the keys directory on the client (‘keyfile’ mode) or under the keys/ namespace in the repository (‘repokey’ mode) using the sha256 of the borg key content as the name.

In both cases, the secrets are generated from random and then encrypted by a key derived from your passphrase (this happens on the client before the key is stored as keyfile or repokey).

keyfile and repokey borg keys use the same format; only the storage location differs. Borg finds the correct key by trying each key against the supplied passphrase. See Multiple borg keys.

The passphrase is passed through the BORG_PASSPHRASE environment variable or prompted for interactive usage.

Key files¶

Compression¶

Borg supports the following compression methods, each identified by a ctype value in the range between 0 and 255 (and augmented by a one-byte clevel value for the compression level):

none (no compression, pass through data 1:1), identified by 0x00
lz4 (low compression, but super fast), identified by 0x01
zstd (level -128..22 offering a wide range: level 22 is higher compression and lower speed, level 1 is lower compression and high speed, and the negative “fast” levels trade still more compression for still more speed) - identified by 0x03
zlib (level 0-9, level 0 is no compression [but still adding zlib overhead], level 1 is low, level 9 is high compression), identified by 0x05
lzma (level 0-9, level 0 is low, level 9 is high compression), identified by 0x02.

The type byte is followed by a byte indicating the compression level. How that byte is interpreted depends on the compression type: for zstd it is an int8_t, so that the negative levels fit (level -1 is stored as 255, -128 as 128). For all other types it is an unsigned byte, with 255 meaning “no level applies” (as for none and lz4). Levels 1..22 occupy the same byte values either way, so zstd data written by older borg versions keeps its meaning.

Speed: none > lz4 > zlib > lzma, lz4 > zstd Compression: lzma > zlib > lz4 > none, zstd > lz4

Be careful, higher compression levels might use a lot of resources (CPU/memory).

The overall speed of course also depends on the speed of your target storage. If that is slow, using a higher compression level might yield better overall performance. You need to experiment a bit. Maybe just watch your CPU load, if that is relatively low, increase compression until 1 core is 70-100% loaded.

Even if your target storage is rather fast, you might see interesting effects: while doing no compression at all (none) is a operation that takes no time, it likely will need to store more data to the storage compared to using lz4. The time needed to transfer and store the additional data might be much more than if you had used lz4 (which is super fast, but still might compress your data about 2:1). This is assuming your data is compressible (if you back up already compressed data, trying to compress them at backup time is usually pointless).

Compression is applied after deduplication, thus using different compression methods in one repo does not influence deduplication.

See borg create --help about how to specify the compression level and its default.

Lock files (fslocking)¶

Borg uses filesystem locks to get (exclusive or shared) access to the cache.

The locking system is based on renaming a temporary directory to lock.exclusive (for exclusive locks). Inside this directory, there is a file indicating hostname, process id and thread id of the lock holder.

There is also a json file lock.roster that keeps a directory of all shared and exclusive lockers.

If the process is able to rename a temporary directory (with the host/process/thread identifier prepared inside it) in the resource directory to lock.exclusive, it has the lock for it. If renaming fails (because this directory already exists and its host/process/thread identifier denotes a thread on the host which is still alive), lock acquisition fails.

The cache lock is usually in ~/.cache/borg/REPOID/lock.*.

Locks (storelocking)¶

To implement locking based on borgstore, borg stores objects below locks/.

The objects contain:

a timestamp when lock was created (or refreshed), stamped by the clock of the machine writing the lock
host / process / thread information about lock owner
lock type: exclusive or shared

Where the storage backend provides object timestamps (file, sftp, s3 and current rest servers - but not rclone), borg additionally uses the lock object’s store-side mtime, which is stamped by the storage’s clock.

Using that information, borg implements:

lock auto-removal if the owner process is dead. the primary purpose of this is to quickly get rid of stale locks by borg processes on the same machine.
lock auto-expiry: if a lock is old and has not been refreshed in time, it will be automatically ignored and deleted. the primary purpose of this is to get rid of stale locks by borg processes on other machines. to never kill a healthy lock just because its writer’s clock is skewed against ours (see #9870), a lock is only expired by age if it looks stale both by the clients’ clocks (content timestamp) and by the storage’s clock (store-side mtime); store-side timestamps can veto an expiry, but never cause one.
a warning if the clocks of concurrently active clients differ by more than a few minutes.

See the module docstring of src/borg/storelocking.py for the details (clock domains, how store “now” is derived, what happens without store-side mtimes).

Breaking the locks¶

In case you run into troubles with the locks, you can use the borg break-lock command after you first have made sure that no Borg process is running on any machine that accesses this resource. Be very careful, the cache or repository might get damaged if multiple processes use it at the same time.

If there is an issue just with the repository lock, it will usually resolve automatically (see above), just retry later.

Checksumming data structures¶

As detailed in the previous sections, Borg generates and stores various files containing important meta data, such as the files cache.

Data corruption in the files cache could create incorrect archives, e.g. due to wrong object IDs or sizes in the files cache.

Therefore, Borg calculates checksums when writing these files and tests checksums when reading them. Checksums are generally 256-bit sha256 hashes. Checksums are stored as hexadecimal ASCII strings.

For compatibility, checksums are not required and absent checksums do not trigger errors. The mechanisms have been designed to avoid false-positives when various Borg versions are used alternately on the same repositories.

Checksums are a data safety mechanism. They are not a security mechanism.

Choice of algorithm

sha256 has been chosen for its wide availability on all platforms and hw acceleration on some.

Lower layer — file_integrity¶

There is a lower layer (borg.crypto.file_integrity.IntegrityCheckedFile) wrapping a file-like object, performing streaming calculation and comparison of checksums. Checksum errors are signalled by raising an exception at the earliest possible moment (borg.crypto.file_integrity.FileIntegrityError).

Calculating checksums

Before feeding the checksum algorithm any data, the file name (i.e. without any path) is mixed into the checksum, since the name encodes the context of the data for Borg.

The various indices used by Borg have separate header and main data parts. IntegrityCheckedFile allows borg to checksum them independently, which avoids even reading the data when the header is corrupted. When a part is signalled, the length of the part name is mixed into the checksum state first (encoded as an ASCII string via %10d printf format), then the name of the part is mixed in as an UTF-8 string. Lastly, the current position (length) in the file is mixed in as well.

The checksum state is not reset at part boundaries.

A final checksum is always calculated in the same way as the parts described above, after seeking to the end of the file. The final checksum cannot prevent code from processing corrupted data during reading, however, it prevents use of the corrupted data.

Serializing checksums

All checksums are compiled into a simple JSON structure called integrity data:

{
    "algorithm": "SHA256",
    "digests": {
        "HashHeader": "eab6802590ba39e3...",
        "final": "e2a7f132fc2e8b24..."
    }
}

The algorithm key notes the used algorithm. When reading, integrity data containing an unknown algorithm is not inspected further.

The digests key contains a mapping of part names to their digests.

Integrity data is generally stored by the upper layers, introduced below. An exception is the DetachedIntegrityCheckedFile, which automatically writes and reads it from a “.integrity” file next to the data file.

Upper layer¶

Main cache files: chunks and files cache

The integrity data of the files cache is stored in the cache config.

The [integrity] section is used:

[cache]
version = 1
repository = 3c4...e59
manifest = 10e...21c
timestamp = 2017-06-01T21:31:39.699514
key_type = 2
previous_location = /path/to/repo

[integrity]
manifest = 10e...21c
files = {"algorithm": "SHA256", "digests": {"HashHeader": "eab...39e3", "final": "e2a...b24"}}

The manifest ID is duplicated in the integrity section due to the way all Borg versions handle the config file. Instead of creating a “new” config file from an internal representation containing only the data understood by Borg, the config file is read in entirety (using the Python ConfigParser) and modified. This preserves all sections and values not understood by the Borg version modifying it.

Thus, if an older versions uses a cache with integrity data, it would preserve the integrity section and its contents. If a integrity-aware Borg version would read this cache, it would incorrectly report checksum errors, since the older version did not update the checksums.

However, by duplicating the manifest ID in the integrity section, it is easy to tell whether the checksums concern the current state of the cache.

Integrity errors are fatal in these files, terminating the program, and are not automatically corrected at this time.

HardLinkManager and the hlid concept¶

Dealing with hard links needs some extra care, implemented in borg within the HardLinkManager class:

At archive creation time, fs items with st_nlink > 1 indicate that they are a member of a group of hardlinks all pointing to the same inode. For such fs items, the archived item includes a hlid attribute (hardlink id), which is computed like H(st_dev, st_ino). Thus, if archived items have the same hlid value, they pointed to the same inode and form a group of hardlinks. Besides that, nothing special is done for any member of the group of hardlinks, meaning that e.g. for regular files, each archived item will have a chunks list.
At extraction time, the presence of a hlid attribute indicates that there might be more hardlinks coming, pointing to the same content (inode), thus borg will remember the “hlid to extracted path” mapping, so it will know the correct path for extracting (hardlinking) the next hardlink of that group / with the same hlid.
This symmetric approach (each item has all the information, e.g. the chunks list) simplifies dealing with such items a lot, especially for partial extraction, for the FUSE filesystem, etc.
This is different from the asymmetric approach of old borg versions (< 2.0) and also from tar which have the concept of a main item (first hardlink, has the content) and content-less secondary items with by-name back references for each subsequent hardlink, causing lots of complications when dealing with them.