RFC repack: incremental MIDX/bitmap-based repacking
Get series with b4
b4 am [email protected]Versions newest first
- v1 RFC Latest14 patches 6 repliesIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/14 | midx: use `string_list` for retained MIDX filesmidx.c | +22 | 2 replies | |
| 2/14 | strvec: introduce `strvec_init_alloc()`strvec.c strvec.h | +12 | 3 replies | |
| 3/14 | midx: use `strvec` for `keep_hashes`midx-write.c midx.c | +36 | 0 replies | |
| 4/14 | midx: introduce `--checksum-only` for incremental MIDX writesDocumentation/ builtin/ midx-write.c +3 more | +105 | 0 replies | |
| 5/14 | midx: support custom `--base` for incremental MIDX writesDocumentation/ builtin/ midx-write.c +3 more | +172 | 0 replies | |
| 6/14 | repack: track the ODB source via existing_packsbuiltin/ repack.c repack.h | +5 | 1 reply | |
| 7/14 | midx: expose `midx_layer_contains_pack()`midx.c midx.h | +5 | 0 replies | |
| 8/14 | repack-midx: factor out `repack_prepare_midx_command()`repack-midx.c | +19 | 0 replies | |
| 9/14 | repack-midx: extract `repack_fill_midx_stdin_packs()`repack-midx.c | +24 | 0 replies | |
| 10/14 | repack-geometry: prepare for incremental MIDX repackingrepack-geometry.c repack.h | +41 | 0 replies | |
| 11/14 | builtin/repack.c: convert `--write-midx` to an `OPT_CALLBACK`builtin/ repack-midx.c repack.h | +58 | 0 replies | |
| 12/14 | repack: implement incremental MIDX repackingrepack-midx.c repack.h | +476 | 0 replies | |
| 13/14 | repack: introduce `--write-midx=incremental`Documentation/ Documentation/ builtin/ +8 more | +692 | 0 replies | |
| 14/14 | repack: allow `--write-midx=incremental` without `--geometric`Documentation/ builtin/ repack-midx.c +1 more | +101 | 0 replies |
Reviews trailers per patch
None of the 14 patches has a Reviewed-by or Acked-by.
| Patch | Junio C Hamano |
|---|---|
| 1/14 | |
| 2/14 | Helped-by |
| 3/14 | |
| 4/14 | |
| 5/14 | |
| 6/14 | |
| 7/14 | |
| 8/14 | |
| 9/14 | |
| 10/14 | |
| 11/14 | |
| 12/14 | |
| 13/14 | |
| 14/14 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [RFC PATCH 00/14] repack: incremental MIDX/bitmap-based repacking
[NOTE: this series has not yet been tested thoroughly and is based on the v3 of 'tb/incremental-midx-part-3.2', which is d54da84bd9d (midx:
enable reachability bitmaps during MIDX compaction, 2026-02-24).
I suspect that there will be non-trivial changes to the approach in this series based on feedback, hence the RFC.]
Note to the maintainer:
* This series is based on 'tb/incremental-midx-part-3.2', I suggest queueing as 'tb/incremental-midx-part-3.3'.
OVERVIEW
========
This series implements the third and final major component for an incremental MIDX/bitmap-based repacking strategy. As a refresher, those are:
1. Refactoring code out of builtin/repack.c into individual compilation units outside of the builtin directory.
2. Implementing MIDX layer compaction, i.e., the ability to combine a contiguous sequence of MIDX layers in an existing chain and replace them with a single layer representing the union of objects/packs among the compacted layers.
3. (this series) An incremental repacking strategy that, unlike our current '--geometric' approach, does not rely on periodic all-into-one repacks.
BACKGROUND
==========
Today, a '--geometric' repack with '--write-midx' rewrites the entire MIDX (and, when enabled, its reachability bitmap) on every invocation. For most repositories this is acceptable. In large monorepos, these costs can add up significantly, especially when those repositories are repacked frequently.
The incremental MIDX support introduced in the earlier parts of this effort allows us to append new layers to a MIDX chain without rewriting anything. Combined with the support for MIDX compaction in 3.2, we now have all of the building blocks needed to maintain an incrementally growing and shrinking MIDX chain as part of the repack cycle.
STRATEGY
========
The incremental repacking strategy implemented in this series works (roughly) as follows:
1. Repack non-MIDX'd packs using an ordinary '--geometric' repack, optionally including packs from the tip MIDX layer if and only if it contains more than 'repack.midxNewLayerThreshold' number of packs.
2. Prepare to write a new MIDX layer containing the freshly written pack(s) (and any surviving packs from the tip layer, if it was rewritten).
3. Perform a compaction pass over adjacent MIDX layers to restore a geometric progression on object count among layers in the chain (determined by 'repack.midxSplitFactor').
4. Write the new MIDX chain, link it into place, and remove redundant layers.
In effect, this approach encourages MIDX chains where:
* older layers contain fewer, larger packs, and
* newer layers contain many smaller packs.
As a result of the compaction pass, we prevent the chain itself from ever growing too long.
This roughly matches the description of this algorithm I gave at Git Merge last year, which is covered on slides 80-131 of this presentation:
https://ttaylorr.com/presentations/git-merge-2025.pdf
THIS SERIES
===========
This series is organized roughly as follows:
* The first three patches perform small-ish quality-of-life refactors within the MIDX machinery.
* The next two patches introduce --checksum-only and --base options for git multi-pack-index write and compact, which are needed by the incremental repacking machinery to assemble MIDX chains without prematurely updating the chain file.
* The next six patches prepare the repack infrastructure and pack geometry code for the new repacking strategy.
* The final three patches introduce the new repacking machinery, expose it to users, and then extend it to work with non-geometric repacks in that order. The first two are the substantive patches of this series.
WHERE WE'RE AT
==============
This series delivers the final substantive component of this overall effort to enable the new repacking strategy implemented here. There are a couple of (comparatively much smaller) items that will be useful as follow-on items, including:
* "Reachability-infused" geometric repacking to emit small cruft packs to introduce other ways to update the set of cruft objects beyond a whole-repository traversal.
* Richer bitmap configuration to determine which bitmap(s) to carry forward between adjacent MIDX layers when doing an incremental repack, to prevent an endless accumulation of reachability bitmaps.
Like I mentioned earlier, I think that both of those are significantly smaller challenges than this and the previous series. As a general note, I am going on vacation for two weeks starting this Friday (2026-02-24) and will be away from the list.
I'll plan on picking up any review from this series as well as the two other topics listed above as soon as I get back.
Thanks in advance for your review!
Taylor Blau (14):
midx: use string_list for retained MIDX files
strvec: introduce strvec_init_alloc()
midx: use strvec for keep_hashes
midx: introduce --checksum-only for incremental MIDX writes
midx: support custom --base for incremental MIDX writes
repack: track the ODB source via existing_packs
midx: expose midx_layer_contains_pack()
repack-midx: factor out repack_prepare_midx_command()
repack-midx: extract repack_fill_midx_stdin_packs()
repack-geometry: prepare for incremental MIDX repacking builtin/repack.c: convert --write-midx to an OPT_CALLBACK
repack: implement incremental MIDX repacking
repack: introduce --write-midx=incremental
repack: allow --write-midx=incremental without --geometric
Documentation/config/repack.adoc | 18 + Documentation/git-multi-pack-index.adoc | 19 +- Documentation/git-repack.adoc | 44 +- builtin/multi-pack-index.c | 48 +- builtin/repack.c | 90 ++- midx-write.c | 119 ++-- midx.c | 104 ++-- midx.h | 11 +- repack-geometry.c | 50 +- repack-midx.c | 704 +++++++++++++++++++++++- repack.c | 23 +- repack.h | 25 +- strvec.c | 7 + strvec.h | 5 + t/meson.build | 1 + t/t5334-incremental-multi-pack-index.sh | 47 ++ t/t5335-compact-multi-pack-index.sh | 105 ++++ t/t7705-repack-incremental-midx.sh | 461 ++++++++++++++++ 18 files changed, 1730 insertions(+), 151 deletions(-) create mode 100755 t/t7705-repack-incremental-midx.sh
base-commit: ac6221686db11ba802ced8ea6b8b2fa8388b21b2
Signature · 1 line
2.53.0.185.g29bc4dff628