path: root/docs/internals/data-structures.rst

.. include:: ../global.rst.inc
.. highlight:: none

.. _data-structures:

Data structures and file formats
================================

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

.. todo:: Clarify terms, perhaps create a glossary.
          ID (client?) vs. key (repository?),
          chunks (blob of data in repo?) vs. object (blob of data in repo, referred to from another object?),

.. _repository:

Repository
----------

.. Some parts of this description were taken from the Repository docstring

Borg stores its data in a `Repository`, which is a file system based
transactional key-value store. Thus the repository does not know about
the concept of archives or items.

Each repository has the following file structure:

README
  simple text file telling that this is a Borg repository

config
  repository configuration

data/
  directory where the actual data is stored

hints.%d
  hints for repository compaction

index.%d
  repository index

lock.roster and lock.exclusive/*
  used by the locking system to manage shared and exclusive locks

Transactionality is achieved by using a log (aka journal) to record changes. The log is a series of numbered files
called segments_. Each segment is a series of log entries. The segment number together with the offset of each
entry relative to its segment start establishes an ordering of the log entries. This is the "definition" of
time for the purposes of the log.

.. _config-file:

Config file
~~~~~~~~~~~

Each repository has a ``config`` file which is a ``INI``-style file
and looks like this::

    [repository]
    version = 1
    segments_per_dir = 1000
    max_segment_size = 524288000
    id = 57d6c1d52ce76a836b532b0e42e677dec6af9fca3673db511279358828a21ed6

This is where the ``repository.id`` is stored. It is a unique
identifier for repositories. It will not change if you move the
repository around so you can make a local transfer then decide to move
the repository to another (even remote) location at a later time.

Keys
~~~~

Repository keys are byte-strings of fixed length (32 bytes), they
don't have a particular meaning (except for the Manifest_).

Normally the keys are computed like this::

  key = id = id_hash(unencrypted_data)

The id_hash function depends on the :ref:`encryption mode <borg_init>`.

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

Segments
~~~~~~~~

Objects referenced by a key are stored inline in files (`segments`) of approx.
500 MB size in numbered subdirectories of ``repo/data``. The number of segments
per directory is controlled by the value of ``segments_per_dir``. If you change
this value in a non-empty repository, you may also need to relocate the segment
files manually.

A segment starts with a magic number (``BORG_SEG`` as an eight byte ASCII string),
followed by a number of log entries. Each log entry consists of:

* 32-bit size of the entry
* CRC32 of the entire entry (for a PUT this includes the data)
* entry tag: PUT, DELETE or COMMIT
* PUT and DELETE follow this with the 32 byte key
* PUT follow the key with the data

Those files are strictly append-only and modified only once.

Tag is either ``PUT``, ``DELETE``, or ``COMMIT``.

When an object is written to the repository a ``PUT`` entry is written
to the file containing the object id and data. If an object is deleted
a ``DELETE`` entry is appended with the object id.

A ``COMMIT`` tag is written when a repository transaction is
committed. The segment number of the segment containing
a commit is the **transaction ID**.

When a repository is opened any ``PUT`` or ``DELETE`` operations not
followed by a ``COMMIT`` tag are discarded since they are part of a
partial/uncommitted transaction.

The size of individual segments is limited to 4 GiB, since the offset of entries
within segments is stored in a 32-bit unsigned integer in the repository index.

Index, hints and integrity
~~~~~~~~~~~~~~~~~~~~~~~~~~

The **repository index** is stored in ``index.<TRANSACTION_ID>`` and is used to
determine an object's location in the repository. It is a HashIndex_,
a hash table using open addressing. It maps object keys_ to two
unsigned 32-bit integers; the first integer gives the segment number,
the second indicates the offset of the object's entry within the segment.

The **hints file** is a msgpacked file named ``hints.<TRANSACTION_ID>``.
It contains:

* version
* list of segments
* compact

The **integrity file** is a msgpacked file named ``integrity.<TRANSACTION_ID>``.
It contains checksums of the index and hints files and is described in the
:ref:`Checksumming data structures <integrity_repo>` section below.

If the index or hints are corrupted, they are re-generated automatically.
If they are outdated, segments are replayed from the index state to the currently
committed transaction.

Compaction
~~~~~~~~~~

For a given key only the last entry regarding the key, which is called current (all other entries are called
superseded), is relevant: If there is no entry or the last entry is a DELETE then the key does not exist.
Otherwise the last PUT defines the value of the key.

By superseding a PUT (with either another PUT or a DELETE) the log entry becomes obsolete. A segment containing
such obsolete entries is called sparse, while a segment containing no such entries is called compact.

Since writing a ``DELETE`` tag does not actually delete any data and
thus does not free disk space any log-based data store will need a
compaction strategy (somewhat analogous to a garbage collector).

Borg uses a simple forward compacting algorithm,
which avoids modifying existing segments.
Compaction runs when a commit is issued with ``compact=True`` parameter, e.g.
by the ``borg compact`` command (unless the :ref:`append_only_mode` is active).
One client transaction can manifest as multiple physical transactions,
since compaction is transacted, too, and Borg does not distinguish between the two::

  Perspective| Time -->
  -----------+--------------
  Client     | Begin transaction - Modify Data - Commit | <client waits for repository> (done)
  Repository | Begin transaction - Modify Data - Commit | Compact segments - Commit   | (done)

The compaction algorithm requires two inputs in addition to the segments themselves:

(i) Which segments are sparse, to avoid scanning all segments (impractical).
    Further, Borg uses a conditional compaction strategy: Only those
    segments that exceed a threshold sparsity are compacted.

    To implement the threshold condition efficiently, the sparsity has
    to be stored as well. Therefore, Borg stores a mapping ``(segment
    id,) -> (number of sparse bytes,)``.

    The 1.0.x series used a simpler non-conditional algorithm,
    which only required the list of sparse segments. Thus,
    it only stored a list, not the mapping described above.
(ii) Each segment's reference count, which indicates how many live objects are in a segment.
     This is not strictly required to perform the algorithm. Rather, it is used to validate
     that a segment is unused before deleting it. If the algorithm is incorrect, or the reference
     count was not accounted correctly, then an assertion failure occurs.

These two pieces of information are stored in the hints file (`hints.N`)
next to the index (`index.N`).

When loading a hints file, Borg checks the version contained in the file.
The 1.0.x series writes version 1 of the format (with the segments list instead
of the mapping, mentioned above). Since Borg 1.0.4, version 2 is read as well.
The 1.1.x series writes version 2 of the format and reads either version.
When reading a version 1 hints file, Borg 1.1.x will
read all sparse segments to determine their sparsity.

This process may take some time if a repository has been kept in append-only mode
or ``borg compact`` has not been used for a longer time, which both has caused
the number of sparse segments to grow.

Compaction processes sparse segments from oldest to newest; sparse segments
which don't contain enough deleted data to justify compaction are skipped. This
avoids doing e.g. 500 MB of writing current data to a new segment when only
a couple kB were deleted in a segment.

Segments that are compacted are read in entirety. Current entries are written to
a new segment, while superseded entries are omitted. After each segment an intermediary
commit is written to the new segment. Then, the old segment is deleted
(asserting that the reference count diminished to zero), freeing disk space.

A simplified example (excluding conditional compaction and with simpler
commit logic) showing the principal operation of compaction:

.. figure:: compaction.png
    :figwidth: 100%
    :width: 100%

(The actual algorithm is more complex to avoid various consistency issues, refer to
the ``borg.repository`` module for more comments and documentation on these issues.)

.. _internals_storage_quota:

Storage quotas
~~~~~~~~~~~~~~

Quotas are implemented at the Repository level. The active quota of a repository
is determined by the ``storage_quota`` `config` entry or a run-time override (via :ref:`borg_serve`).
The currently used quota is stored in the hints file. Operations (PUT and DELETE) during
a transaction modify the currently used quota:

- A PUT adds the size of the *log entry* to the quota,
  i.e. the length of the data plus the 41 byte header.
- A DELETE subtracts the size of the deleted log entry from the quota,
  which includes the header.

Thus, PUT and DELETE are symmetric and cancel each other out precisely.

The quota does not track on-disk size overheads (due to conditional compaction
or append-only mode). In normal operation the inclusion of the log entry headers
in the quota act as a faithful proxy for index and hints overheads.

By tracking effective content size, the client can *always* recover from a full quota
by deleting archives. This would not be possible if the quota tracked on-disk size,
since journaling DELETEs requires extra disk space before space is freed.
Tracking effective size on the other hand accounts DELETEs immediately as freeing quota.

.. rubric:: Enforcing the quota

The storage quota is meant as a robust mechanism for service providers, therefore
:ref:`borg_serve` has to enforce it without loopholes (e.g. modified clients).
The following sections refer to using quotas on remotely accessed repositories.
For local access, consider *client* and *serve* the same.
Accordingly, quotas cannot be enforced with local access,
since the quota can be changed in the repository config.

The quota is enforcible only if *all* :ref:`borg_serve` versions
accessible to clients support quotas (see next section). Further, quota is
per repository. Therefore, ensure clients can only access a defined set of repositories
with their quotas set, using ``--restrict-to-repository``.

If the client exceeds the storage quota the ``StorageQuotaExceeded`` exception is
raised. Normally a client could ignore such an exception and just send a ``commit()``
command anyway, circumventing the quota. However, when ``StorageQuotaExceeded`` is raised,
it is stored in the ``transaction_doomed`` attribute of the repository.
If the transaction is doomed, then commit will re-raise this exception, aborting the commit.

The transaction_doomed indicator is reset on a rollback (which erases the quota-exceeding
state).

.. rubric:: Compatibility with older servers and enabling quota after-the-fact

If no quota data is stored in the hints file, Borg assumes zero quota is used.
Thus, if a repository with an enabled quota is written to with an older ``borg serve``
version that does not understand quotas, then the quota usage will be erased.

The client version is irrelevant to the storage quota and has no part in it.
The form of error messages due to exceeding quota varies with client versions.

A similar situation arises when upgrading from a Borg release that did not have quotas.
Borg will start tracking quota use from the time of the upgrade, starting at zero.

If the quota shall be enforced accurately in these cases, either

- delete the ``index.N`` and ``hints.N`` files, forcing Borg to rebuild both,
  re-acquiring quota data in the process, or
-