Git’s database internals IV: distributed synchronization

Git’s database internals IV: distributed synchronization

Git’s decentralized design means every repository is an independent store, and connectivity is the exception rather than the rule. Under the CAP theorem, Git chooses partitions as the default: each copy can diverge arbitrarily, and users decide when and how much to reconcile. The git fetch and git push commands are the synchronization primitives; they do not aim for whole-repository consistency. Instead, they transfer only the minimal set of objects needed to update selected references, exploiting the object store’s structure—commit graphs, tree traversal, and specialized data structures—to keep the exchange small.

Client repositories typically reach out only when a user triggers a command manually. To model that, consider a git fetch from a client repo to a remote, pulling all objects reachable from the remote’s refs/heads/ branches and storing those refs locally under refs/remotes/<remote>. The process begins with a ref advertisement: the client asks for the remote’s reference list, and the server responds with every branch under refs/heads/ and refs/tags/ along with its current object ID. Subtleties exist, for instance with Git’s protocol v2; for this discussion, assume the client filters that list and proceeds using only object IDs.

You can inspect the advertisement directly without transferring any objects via git ls-remote, which requests the ref list but stops there.

$ git ls-remote --heads origin
4af7188bc97f70277d0f10d56d5373022b1fa385        refs/heads/main
00d12607a27e387ad78b5957afa05e89c87e83a5        refs/heads/maint
718a3a8f04800cd0805e8fba0be8862924e20718        refs/heads/next
b8d67d57febde72ace37d40301a429cd64f3593f        refs/heads/seen

Frequent synchronization reduces transfer size

In practice, a client repo only talks to a remote when a developer runs git fetch or git pull. The cost of that exchange scales with the number of new objects—that is, objects the client does not already have. A straightforward way to keep that cost down is to synchronize more often, so fewer objects are missing on each connection.

Git’s background maintenance feature automates this. Running git maintenance start schedules regular upkeep, including an hourly “prefetch” task that downloads the latest objects from all remotes. Instead of updating refs/remotes/, the prefetch writes remote refs into the hidden refs/prefetch/ namespace. Foreground git fetch commands then only update refs/remotes/ when explicitly requested.

That separation keeps interactive fetches fast: often all the needed Git objects already reside in the client, and the only remaining operation is a ref update inside refs/remotes/. The background fetches themselves stay cheap because they happen frequently, but understanding why requires examining the actual fetch mechanics underneath.

Computing the reachable set difference

At the core of any fetch operation is a question of set arithmetic: which objects are reachable from the commits the client wants, but not reachable from the commits the client already has? Git frames this as a reachable set difference query, not a simple object-store difference. Unreachable objects are irrelevant, and a full scan of the object database would be wasteful even if it were correct.

The query is anchored by two sets of starting points, known as wants and haves:

• A want is an object ID the client requests, taken from the server’s ref advertisement.
• A have is an object ID the client already possesses, typically taken from its own refs in refs/heads/ and refs/remotes/<remote>/.

There is a wrinkle: the server may not actually have the objects the client lists as haves. Those refs are a heuristic for shared history, not a guarantee. Consequently, Git performs a fetch negotiation step, exchanging rounds of wants and haves so that each side can confirm which objects are known. Once the sets are agreed upon, the server can compute what the client needs.

Walking the object graph

The most direct approach to a reachable set difference is a pair of graph walks. First, mark every object reachable from the haves by walking commits, their root trees, and all subtrees. Then walk from the wants, skipping anything already marked, and the result is the set difference.

This strategy works but carries two significant costs. Parsing trees is expensive, as noted in part III, and tree entries frequently reference the same object. For example, a license file that never changes is still pointed to by the root tree of nearly every commit during the walk, forcing repeated checks against the marked set. Worse, the walk must visit essentially the entire reachable history, even if the actual set difference is a single commit that edits one file. The cost does not shrink as repositories stay in sync.

Finding a frontier instead

Git exploits the structure of commit history to avoid a full-object walk. Because source code is typically extended rather than reverted to exact prior states, Git can stop walking the full history and instead identify a frontier of commits: those reachable from the haves that sit at the boundary of the unreachable-from-haves set. A commit A is on the frontier if it is a parent of a commit B that is reachable from the wants but not from the haves.

$ git log --graph --oneline --boundary 3d8e3dc4fc..d02cc45c7a
*   acdb1e1053 Merge branch 'mt/checkout-count-fix'
|\
| * 611c7785e8 checkout: fix two bugs on the final count of updated entries
| * 11d14dee43 checkout: show bug about failed entries being included in final report
| * ed602c3f44 checkout: document bug where delayed checkout counts entries twice
* |   f0f9a033ed Merge branch 'cl/rerere-train-with-no-sign'
|\ \
| * | cc391fc886 contrib/rerere-train: avoid useless gpg sign in training
| o | bbea4dcf42 Git 2.37.1
|  /
o / 3d8e3dc4fc Merge branch 'ds/rebase-update-ref'
 /
o e4a4b31577 Git 2.37

Once the frontier is identified, Git walks the root trees of those frontier commits and marks everything they reach as “have.” The subsequent walk from the haves then terminates when it hits those marked objects. The cost now scales with the size of a few root trees plus the new objects in the result, rather than the entire history. There is a trade-off: if a commit in the set difference is a genuine revert, it may reintroduce older objects into the result, slightly increasing the transferred set. In practice, that is rare enough to be an acceptable cost.

For a monorepo, however, walking the frontier’s root trees can still be substantial. Advancing further requires not just algorithmic refinement, but a new on-disk data structure.

Reachability bitmaps

Bitmaps are a natural fit for set operations: if every object has a fixed bit position, the reachable set from any commit can be represented as a bit array. The reachable set difference is then the logical AND NOT of two such arrays.

Precomputation is what makes the approach viable. Since each commit could theoretically need a bitmap proportional to the repository size, Git does not compute them on request. Instead, git repack --write-bitmap-index generates these bitmaps when creating a packfile. Object positions in the bitmap correspond to their order in the packfile, and the resulting data is stored in a .bitmap file alongside the .pack and .idx. Multi-pack-index support extends this across multiple packfiles.

In an ideal world, every commit would carry a reachability bitmap, and the algorithm would be:

1. Union the bitmaps for every have commit.
2. Union the bitmaps for every want commit.
3. Perform the bitwise set difference.

That ideal is unreachable. Storing a bitmap per commit would lead to quadratic growth in repository size, even with compression, and new commits can be requested before a bitmap is generated for them. Git therefore falls back on the commit walk. Starting from the haves, Git walks until it finds a commit with a precomputed bitmap, then uses that bitmap as the initial set, halting further exploration when it finds another bitmap or sees that a commit’s bit is already set. Any remaining commits are resolved by walking their root trees and ignoring any trees already present in the bitmap. The same process is repeated for the wants.

With well-maintained bitmaps and a carefully chosen object order to aid compression, these queries execute with a tiny fraction of the object walk required by the frontier method. The result is also more precise, because the bitmap method avoids the false positives that the frontier’s root-tree traversal can introduce in rare revert cases.

The packfile serves double duty here: the same format used to store objects on disk in part I is used to transmit them over the network. The one concession is that reference deltas can point to objects the client already possesses. This shared representation keeps both the algorithmic and the storage layers of the system cohesive.

Push-side synchronization and the sparse walk

git push is the mirror image of git fetch: the client has new objects and wants the server to accept them. In principle, the same reachable set difference algorithm applies, with the roles of haves and wants reversed. In practice, though, the client does not run a negotiation phase by default. It instead assumes the remote already has everything reachable from the local refs/remotes/<remote> references. If those references are stale — because you haven’t fetched recently — the client may send more objects than necessary. The push.negotiate config option enables a real negotiation up front, which is most useful when background maintenance keeps the local object store close to the remote’s state.

Even with negotiation enabled, the two commands have different usage patterns. A typical fetch pulls in work from many contributors and touches many files. A typical push involves a single topic branch and a much smaller set of changes. Git exploits this asymmetry rather than treating push as a pure reversal of fetch.

Sparse reachable set difference

Clients rarely run the expensive background maintenance needed to maintain reachability bitmaps. Most pushes involve few objects, and the cost of building bitmaps is hard to justify for a single contributor. Servers, by contrast, see many fetches and benefit greatly from precomputed bitmaps. When a client lacks bitmaps, Git falls back to the frontier algorithm, which walks every object reachable from the root trees of the haves. On a large repository, that is needlessly expensive for the small set of objects a typical push introduces.

The sparse reachable set difference algorithm, enabled by default via the pack.useSparse config option (default since Git 2.27.0; introduced in Git 2.21.0), avoids this cost. Instead of first walking the full tree structure reachable from the commit frontier and then walking the new commits’ trees, it combines both walks into a single traversal based on directory paths.

The walk starts with the empty path and the root trees of the commit frontier and the pushed commits. Each tree is marked interesting (from the new commits) or uninteresting (from the frontier). When Git visits a node — a path and its associated set of trees — it checks each entry. Blobs are marked accordingly. Tree entries are added to a new node for that path component. Uninteresting trees propagate their status to child trees. If all trees in a node are uninteresting, the node is skipped entirely. Most directories in a large repository fall into this category, so Git only walks the paths where new objects actually exist.

Query planning in Git

Viewing synchronization as a database query reveals both parallels and gaps. Unlike a declarative query language, Git’s "query planner" is fixed and simple. When a repository performs a reachable set difference, it chooses an algorithm based solely on what is available:

1. If reachability bitmaps exist, use the bitmap algorithm.
2. Otherwise, if pack.useSparse is enabled, use the sparse algorithm.
3. If neither case holds, use the frontier algorithm.

This selection does not consider the shape of the history or the likely cost of each approach. A stale bitmap may require more dynamic computation than a frontier walk. A repository with a few new commits and a large shared history might be served better by the sparse algorithm than by a full bitmap computation, even when bitmaps exist. There is room for experiments on adaptive planning, but no such dynamic strategy is in place today.

Git does offer manual control. You can choose whether to build bitmaps, and the pack.useSparse option lets your opt out of the sparse algorithm. A forthcoming push.useBitmaps config option will go further: it allows a client to maintain reachability bitmaps for their own fetches while disabling them during pushes, letting the sparse algorithm handle the typical small object set instead. That change is expected in Git 2.38.0.