A maintenance bottleneck
GitHub’s largest repositories grow every day, and last year we started seeing our repacking job hit self-imposed timeouts on those repos. Even relaxing the timeouts didn’t help; failing maintenance was usually the first sign of performance degradation that was hard to fix once it started.
The root cause was architectural. We designed maintenance to repack each repository’s entire contents into one packfile. That choice has real benefits: object lookups only need to search one pack, delta compression can relate any object to any other, and reachability bitmaps—a critical data structure for fast clones and fetches—only work in the context of a single pack. The single-pack model made lookups fast, but it made maintenance slow in a way that scaled badly. Repacking cost grew superlinearly with repository size, and the largest repos were also growing the fastest. The result was a queue that never drained: as soon as one maintenance job finished, another was waiting.
Git’s multi-pack index (multi-pack-index) already solved the first half of the problem by giving all object lookups a single index to consult, even when objects are spread across multiple packs. What it didn’t solve was bitmaps, which were still tied to a single pack. To break that tie, we had to solve a set of related problems: how to order objects in a multi-pack index so bitmaps compress well, how to efficiently map between bit positions and object IDs, and how to design a repacking strategy that scales with the rate of incoming pushes rather than with total repository size. Some of this work also made single-pack repositories faster.
All of it is being contributed back to the open source Git project and will be in an upcoming release.
How Git decides what to send
Git stores every file, tree, commit, and tag as an object. Objects can live individually as loose objects or be gathered into packfiles. Objects reference each other: a tree points to blobs and subtrees, and a commit points to a tree and to zero or more parent commits. These edges form a directed acyclic graph.
That graph is what lets the server figure out what to send during a fetch. The client and server each advertise their reference tips—branch and tag endpoints. The server walks from the requested refs back through the object graph, stopping at anything the client already has, to compute the minimal set of objects to transmit.
In the diagram above, the client’s advertised refs are the darker blue commits; the server’s refs are dark red. The blue region is the reachability closure of the client’s objects, the red region is the server’s closure minus what the client already has, and objects in that red region are what gets sent.
The expensive part is computing that closure on the fly. For a clone, the client has nothing, so the server has to enumerate every object reachable from every ref. The exact set matters: we keep objects in special refs like test-merge results in the same object directory, and those shouldn’t be sent during ordinary fetches. So the server can’t just stream everything it has.
Bitmaps make reachability cheap
Git’s solution is reachability bitmaps. Objects in a pack are assigned positions in some fixed order, and for certain commits Git stores a bitmap whose ith bit is 1 if that commit can reach the ith object, 0 otherwise. Because bitmaps make reachability a matter of bitwise logic, the server avoids parsing objects entirely:
ORthe bitmaps for every ref tip the client wants, givingW.ORthe bitmaps for every ref tip the client already has, givingH.- Compute
W AND NOT Hto get the exact object set to send.
The speed-up is dramatic. Walking all objects in the Linux kernel repository takes more than 33 seconds without bitmaps; with them the same traversal finishes in 1.57 seconds.
The order objects are assigned to bit positions matters a great deal. Lexicographic order by object ID would make reachability look random from bit to bit, because reachability is determined by content hashes, not by names. Git compresses bitmaps with EWAH compression, which requires long runs of identical bits to be effective. Pack order—the physical arrangement of objects as written to the packfile—tends to group reachable objects together and produces such runs.
The catch: because bit positions are defined by pack order, bitmaps are conceptually and practically coupled to a single packfile. Objects that arrive later, outside the bitmapped pack, don’t get bitmap coverage. Our fix was to periodically fold everything back into one pack and regenerate bitmaps. But that repack is quadratic in cost—the large repositories that most needed maintenance were also growing the fastest, so the job kept getting more expensive and more frequent at the same time.
The bottleneck was compressing an entire repository into one file. The question we had to answer was: could we instead get the same performance benefits while spreading a repository across multiple packfiles?
Ordering objects across packfiles
To arrange objects that span several packfiles, Git’s multi-pack index (multi-pack-index) is the natural starting point. It serves the same role for a collection of packs that a pack’s own .idx file serves for a single pack: a binary-searchable list of object locations. The key difference is that each entry in a multi-pack index points to a specific pack and an offset within it.
The multi-pack index only stores a location for each unique object. When the same object appears in multiple packs, the copy in the pack with the earliest modification time wins. Within the index, objects are kept in lexicographic order by name, independent of the order inside any single pack.
Concatenating pack order
The question is how to turn that index into an ordering that compresses well. Packs already store objects in a topological order, so objects reachable from one another tend to sit close together. Lexicographic ordering destroys that locality. The solution is to group objects by pack and then by their position within that pack, with the packs themselves arranged according to the multi-pack index.
That approach effectively concatenates the pack-order of each pack into one overall order. The bitmap example below illustrates the result:
The first three bits represent the red, yellow, and green objects, all from pack xyz, which has the oldest modification time among the three packs. Scanning left to right, those objects appear in the same order they do inside xyz. The purple and blue objects follow, since they live in the next pack. The copies of red and green that also exist in pack abc are absent — the multi-pack index selected the copies in the earlier pack. The orange and pink objects from pack 123 finish the run, and the duplicate purple there is likewise not included.
This ordering gives good locality, but it raises a problem: mapping a bit position back to an object isn’t straightforward. Knowing the total object count per pack is not enough, because the number of unique objects contributed by each pack is unknown, as is which duplicates were culled. Counting past the three bits from xyz and then two more, for instance, would land on the copy of green in abc rather than on the intended object.
Reverse indexes
To resolve that mapping, Git now uses reverse indexes. Where a pack index maps object names to locations, the reverse index does the opposite: it maps a position in pack order back to the object’s position in lexicographic order. The values are stored in a new .rev file alongside the .pack and .idx files.
In the single-pack example above, the .idx lists objects lexicographically: yellow before red before green. In pack order, though, red comes first. The reverse index reconciles the two, recording that red is at lexicographic position 3 and yellow at position 1. That enables a quick answer to questions like “how large is the red object?” Git does not store object sizes directly, so it must compare the offset of an object with that of its adjacent neighbor in pack order. Without the reverse index, there is no way to locate that neighbor. With it, reading the adjacent entry gives an index into the .idx file, which in turn points into the pack.
Previously, Git built this table in memory on the fly. That process allocated an array of pack offset and index position pairs and sorted them with a radix sort, consuming memory and CPU time proportional to pack size. Sorting could be noticeably slow when repeated on every process. On-disk reverse indexes avoid that overhead entirely.
Initial tests on real repositories showed substantial gains for fetch serving. The 50th percentile of CPU time for fetches to Homebrew/homebrew-core dropped dramatically after the change:
That amounted to roughly an 80% reduction in fetch serving time for that repository. The resident set size of the serving process also fell:
After a staged rollout to all replicas and a grace period for generating .rev files, the aggregate CPU time across all repositories showed a clear improvement over three 24-hour cycles:
Per-day peaks dropped from around 10.8 seconds to 7 seconds, a collective savings of about 35%.
Bitmaps that span packs
The same .rev format also fills the missing piece for multi-pack bitmaps. A multi-pack reverse index stores positions relative to the multi-pack-index file rather than to a single pack’s .idx file.
That gives an exact way to rediscover which object each bit represents:
To learn that the fifth bit is the blue object, Git reads the fifth entry of the multi-pack reverse index, which says the bit maps to the eleventh object in the multi-pack index. That object points back to the blue copy in pack abc.
With this in place, a single bitmap can refer to objects across multiple packs. The bitmap’s filename indicates whether it belongs to a specific pack or to a multi-pack index, and object lookups are translated accordingly. Because the object ordering was chosen deliberately, the multi-pack bitmaps compress just as well as single-pack ones. They also decouple bitmaps from individual packfiles, so a repository can keep a single bitmap that covers the entire set of packs it contains.
Repacking by geometric progression
With multi-pack bitmaps in place, the next question is how to repack a repository during maintenance. Previously, the only option was to combine every object into a single, massive pack. That restriction no longer exists, so the repacking strategy needed to balance two goals: keep the average number of packs in a repository relatively small, and focus each maintenance run on objects that arrived since the last run.
The invariant chosen is that the packs in a repository form a geometric progression by object count. If you sort packs from largest to smallest, each pack must contain at least twice as many objects as the next one. A new --geometric= mode for git repack enforces this progression. At the time of writing, these patches are still being submitted and reviewed upstream, but the command will work like this:
$ packsizes() {
find .git/objects/pack -type f -name '*.pack' |
while read pack; do
printf "%7d %s\n" \
"$(git show-index < ${pack%.pack}.idx | wc -l)" "$pack"
done | sort -rn
}
$ packsizes # before
$ git repack --write-midx --write-bitmap-index -d --geometric=2
$ packsizes # after
Selecting the optimal set of packs to combine is NP-hard, so the implementation uses an approximation. The first step is to identify how many packs already satisfy the invariant. Order packs by object count, then walk from largest to smallest, checking each adjacent pair: if the larger pack is at least twice the size of the smaller, every pack from that pair downward already forms a geometric progression.
In the example above, the violation is between the second and third packs (both containing one object). That tells us the second pack and anything below it must be repacked together. But combining just those two packs would still leave a pack with two objects, still too large relative to the single-object pack below it. The set of packs to combine must grow until the invariant is restored.
Here, the first four packs had to be merged to restore the progression. Their combined seven objects are less than half of the next-largest pack (32 objects), and adding any more packs would break the remainder of the progression. A new pack is written with exactly those objects, the redundant packs are discarded, and the remaining packs once again form a geometric progression.
This design keeps the number of packs logarithmic in repository size, so no repository ever accumulates too many packs. It also means older objects tend to settle into larger packs and get repacked less frequently over time. A side effect is that each repack mostly touches recently pushed objects, making repack time proportional to the number of new objects rather than the total repository size. To avoid degrading performance over many geometric repacks, an all-into-one repack is run once for every eight geometric repacks. The slow full repacks are still slow, but they are no longer required on every maintenance cycle.
Rolling out to production
With multi-pack bitmaps, the multi-pack index for fast object-to-position lookups, and the geometric repacking strategy in hand, the pieces were ready to combine. Local testing could only go so far—the real corner cases live in production fetch and clone traffic. The rollout was designed to exercise those paths while guaranteeing that no corruption could ever land on a majority of replicas for any repository.
Testing began on internal repositories in two phases. The first phase wrote multi-pack bitmaps containing only a single pack, exercising the basic bitmap machinery without running the new repack code. After building confidence there, the test was expanded to alternate between geometric and full repacks.
After two weeks with no issues, testing moved to external repositories, first on a single host and then on a full rack of hosts, where every repack alternated between geometric and full. Repack times dropped significantly, both per-repository and in aggregate. The rollout then proceeded for several weeks in only one of three data centers. Because no single data center holds a majority of replicas for any repository, this configuration made it impossible for a corrupting change to affect a majority set, while still exposing the new paths to substantial traffic.
After a week in that configuration, the rollout expanded by enrolling percentages of replicas in the other data centers until every repository was using multi-pack reachability bitmaps.
The new strategy saved on average 5.67 CPU days every hour compared with the old approach. Average time spent repacking a single repository also dropped, from about one minute to 15 seconds. The plot below breaks down repack time per site, showing when single-site testing began and when the deployment expanded to all sites.
Future work
Two open areas stand out for further performance gains.
The first is bitmap computation itself. Git's bitmap generation can reuse existing bitmaps by permuting their bits into a new order, but that operation can still scale with repository size. Writing bitmaps incrementally—walking only objects introduced since the last bitmap—would require not only an incremental bitmap file format but also a stable object ordering, so that new bitmaps don't invalidate existing ones.
The second area is pack structure. Geometric pack sequences are a useful trade-off between full and partial repacks, but some repositories are too large for any full repack to be feasible. A strategy that freezes the packs holding the oldest objects in history would allow support for much larger repositories going forward.
This work depended on extensive review from the upstream Git community and engineering teams across GitHub. Special thanks go to Jeff King, Derrick Stolee, Jonathan Tan, Junio Hamano, and others for making it possible.
