git/Documentation/gitpacking.txt

gitpacking(7)
=============

NAME
----
gitpacking - Advanced concepts related to packing in Git

SYNOPSIS
--------
gitpacking

DESCRIPTION
-----------

This document aims to describe some advanced concepts related to packing
in Git.

Many concepts are currently described scattered between manual pages of
various Git commands, including linkgit:git-pack-objects[1],
linkgit:git-repack[1], and others, as well as linkgit:gitformat-pack[5],
and parts of the `Documentation/technical` tree.

There are many aspects of packing in Git that are not covered in this
document that instead live in the aforementioned areas. Over time, those
scattered bits may coalesce into this document.

== Pseudo-merge bitmaps

NOTE: Pseudo-merge bitmaps are considered an experimental feature, so
the configuration and many of the ideas are subject to change.

=== Background

Reachability bitmaps are most efficient when we have on-disk stored
bitmaps for one or more of the starting points of a traversal. For this
reason, Git prefers storing bitmaps for commits at the tips of refs,
because traversals tend to start with those points.

But if you have a large number of refs, it's not feasible to store a
bitmap for _every_ ref tip. It takes up space, and just OR-ing all of
those bitmaps together is expensive.

One way we can deal with that is to create bitmaps that represent
_groups_ of refs. When a traversal asks about the entire group, then we
can use this single bitmap instead of considering each ref individually.
Because these bitmaps represent the set of objects which would be
reachable in a hypothetical merge of all of the commits, we call them
pseudo-merge bitmaps.

=== Overview

A "pseudo-merge bitmap" is used to refer to a pair of bitmaps, as
follows:

Commit bitmap::

  A bitmap whose set bits describe the set of commits included in the
  pseudo-merge's "merge" bitmap (as below).

Merge bitmap::

  A bitmap whose set bits describe the reachability closure over the set
  of commits in the pseudo-merge's "commits" bitmap (as above). An
  identical bitmap would be generated for an octopus merge with the same
  set of parents as described in the commits bitmap.

Pseudo-merge bitmaps can accelerate bitmap traversals when all commits
for a given pseudo-merge are listed on either side of the traversal,
either directly (by explicitly asking for them as part of the `HAVES`
or `WANTS`) or indirectly (by encountering them during a fill-in
traversal).

=== Use-cases

For example, suppose there exists a pseudo-merge bitmap with a large
number of commits, all of which are listed in the `WANTS` section of
some bitmap traversal query. When pseudo-merge bitmaps are enabled, the
bitmap machinery can quickly determine there is a pseudo-merge which
satisfies some subset of the wanted objects on either side of the query.
Then, we can inflate the EWAH-compressed bitmap, and `OR` it in to the
resulting bitmap. By contrast, without pseudo-merge bitmaps, we would
have to repeat the decompression and `OR`-ing step over a potentially
large number of individual bitmaps, which can take proportionally more
time.

Another benefit of pseudo-merges arises when there is some combination
of (a) a large number of references, with (b) poor bitmap coverage, and
(c) deep, nested trees, making fill-in traversal relatively expensive.
For example, suppose that there are a large enough number of tags where
bitmapping each of the tags individually is infeasible. Without
pseudo-merge bitmaps, computing the result of, say, `git rev-list
--use-bitmap-index --count --objects --tags` would likely require a
large amount of fill-in traversal. But when a large quantity of those
tags are stored together in a pseudo-merge bitmap, the bitmap machinery
can take advantage of the fact that we only care about the union of
objects reachable from all of those tags, and answer the query much
faster.

=== Configuration

Reference tips are grouped into different pseudo-merge groups according
to two criteria. A reference name matches one or more of the defined
pseudo-merge patterns, and optionally one or more capture groups within
that pattern which further partition the group.

Within a group, commits may be considered "stable", or "unstable"
depending on their age. These are adjusted by setting the
`bitmapPseudoMerge.<name>.stableThreshold` and
`bitmapPseudoMerge.<name>.threshold` configuration values, respectively.

All stable commits are grouped into pseudo-merges of equal size
(`bitmapPseudoMerge.<name>.stableSize`). If the `stableSize`
configuration is set to, say, 100, then the first 100 commits (ordered
by committer date) which are older than the `stableThreshold` value will
form one group, the next 100 commits will form another group, and so on.

Among unstable commits, the pseudo-merge machinery will attempt to
combine older commits into large groups as opposed to newer commits
which will appear in smaller groups. This is based on the heuristic that
references whose tip commit is older are less likely to be modified to
point at a different commit than a reference whose tip commit is newer.

The size of groups is determined by a power-law decay function, and the
decay parameter roughly corresponds to "k" in `f(n) = C*n^(-k/100)`,
where `f(n)` describes the size of the `n`-th pseudo-merge group. The
sample rate controls what percentage of eligible commits are considered
as candidates. The threshold parameter indicates the minimum age (so as
to avoid including too-recent commits in a pseudo-merge group, making it
less likely to be valid). The "maxMerges" parameter sets an upper-bound
on the number of pseudo-merge commits an individual group

The "stable"-related parameters control "stable" pseudo-merge groups,
comprised of a fixed number of commits which are older than the
configured "stable threshold" value and may be grouped together in
chunks of "stableSize" in order of age.

The exact configuration for pseudo-merges is as follows:

include::config/bitmap-pseudo-merge.txt[]

=== Examples

Suppose that you have a repository with a large number of references,
and you want a bare-bones configuration of pseudo-merge bitmaps that
will enhance bitmap coverage of the `refs/` namespace. You may start
with a configuration like so:

----
[bitmapPseudoMerge "all"]
	pattern = "refs/"
	threshold = now
	stableThreshold = never
	sampleRate = 100
	maxMerges = 64
----

This will create pseudo-merge bitmaps for all references, regardless of
their age, and group them into 64 pseudo-merge commits.

If you wanted to separate tags from branches when generating
pseudo-merge commits, you would instead define the pattern with a
capture group, like so:

----
[bitmapPseudoMerge "all"]
	pattern = "refs/(heads/tags)/"
----

Suppose instead that you are working in a fork-network repository, with
each fork specified by some numeric ID, and whose refs reside in
`refs/virtual/NNN/` (where `NNN` is the numeric ID corresponding to some
fork) in the network. In this instance, you may instead write something
like:

----
[bitmapPseudoMerge "all"]
	pattern = "refs/virtual/([0-9]+)/(heads|tags)/"
	threshold = now
	stableThreshold = never
	sampleRate = 100
	maxMerges = 64
----

Which would generate pseudo-merge group identifiers like "1234-heads",
and "5678-tags" (for branches in fork "1234", and tags in remote "5678",
respectively).

SEE ALSO
--------
linkgit:git-pack-objects[1]
linkgit:git-repack[1]

GIT
---
Part of the linkgit:git[1] suite