Re: [PATCH 12/14] rust: add a new binary loose object map format
- From
brian m. carlson <sandals@crustytoothpaste.net>
- Date
- Oct 29, 2025, 01:37 UTC
- Message-ID
- <aQFv7cJUYaSUipF-@fruit.crustytoothpaste.net>
- In-Reply-To
- <aQCKaK6kTfwoj28O@pks.im>
On 2025-10-28 at 09:18:32, Patrick Steinhardt wrote:
Show 7 quoted lines
> Doesn't this indicate that calling this "loose object map" is kind of a > misnomer? If we want to be able to store arbitrary objects regardless of > the way those are stored (or not stored) in the ODB then I think it's > overall quite confusing to have "loose" in the name. > > This isn't something we can fix for the old loose object map. But > shouldn't we fix this now for the new format you're about to introduce?
Sure. I will admit I'm terrible at naming things. What do you think it should be called.
> s/enabling//
Will fix in v2.
> As far as I understood, this legacy mapping wasn't really used anywhere > as it is basically nonfunctional in the first place. Can we get away > with dropping it altogether?
Sure, I can do that.
> Given that we're talking about multiple different hashes: which hash > function is used for this checksum? I assume it's the main hash, but it > might be sensible to document this.
It is the main hash. I'll update that for v2.
Show 9 quoted lines
> > +`git pack-objects` will repack existing entries into one file, removing any > > +unnecessary objects, such as obsolete shallow entries or loose objects that > > +have been packed. > > Curious that this is put into git-pack-objects(1), as it doesn't quite > feel related to the task. Sure, it generates packfiles, but it doesn't > really handle the logic to manage loose objects/packfiles in the repo. > This feels closer to what git-repack(1) is doing, so would that be a > better place to put it?
I've actually put this into `git gc`, which will come in in a future series, so I'll update this for v2.
> As far as I understand this allows us to even store multiple > compatibility hashes if we were ever to grow a third hash. We would > still be able to binary-search through the file as we can compute the > size of every record with this header.
Exactly. We were discussing BLAKE3 at the contributor summit as a potential option.
The careful reader will note that this format looks suspiciously like pack index v3, which is intentional.
Show 8 quoted lines
> > + * 8-byte offset to the trailer from the beginning of this file. > > + * Zero or more additional key/value pairs (4-byte key, 4-byte value), which > > + may optionally declare one or more chunks. No chunks are currently > > + defined. Readers must ignore unrecognized keys. > > How does the reader identify these key/value pairs and know how many of > those there are? Also, do you already have an idea what those should be > used for?
I'd imagined we could do something like fanout entries for tree structures to help parse large trees better (since trees cannot be binary searched). That's something I wanted to add to multi-pack index as a set of chunks.
They are read until the end of the header section.
> How does one figure out how many NUL bytes there's going to be? I guess > the reader doesn't need to know as it simply uses the length of the > header section to seek to the tables?
Exactly. This is what we do with pack index v3 as well. As a practical matter, every chunk of NUL padding contains 0 to 3 bytes: just enough to align the data for 4-byte access.
Show 33 quoted lines
> > +- Tables for the first object format: > > + * A sorted table of shortened object names. These are prefixes of the names > > + of all objects in this file, packed together without offset values to > > + reduce the cache footprint of the binary search for a specific object name. > > Okay. The length of the shortened object names is encoded in the header, > so all of the objects have the same length. > > Does the reader have a way to disambiguate the shortened object names? > They may be unambiguous at the point in time where the mapping is > written, but when they are being shortened it becomes plausible that the > object names becomes ambiguous at a later point in time. > > > + * A sorted table of full object names. > > Ah, I see! We have a second table further down that encodes full object > names, so yes, we can fully disambiguate. > > > + * A table of 4-byte metadata values. > > + * Zero or more chunks. A chunk starts with a four-byte chunk identifier and > > + a four-byte parameter (which, if unneeded, is all zeros) and an eight-byte > > + size (not including the identifier, parameter, or size), plus the chunk > > + data. > > +- Zero or more NUL bytes. > > +- Tables for subsequent object formats: > > + * A sorted table of shortened object names. These are prefixes of the names > > + of all objects in this file, packed together without offset values to > > + reduce the cache footprint of the binary search for a specific object name. > > + * A table of full object names in the order specified by the first object format. > > Interesting, why are these sorted by the first object format again? > Doesn't that mean that I have to do a linear search now to locate the > entry for the second object format?
No, it doesn't. The full object names are always in the order of the first format. The shortened names for second and subsequent formats point into an offset table that finds the offset in the first format.
Therefore, to look up an OID in the second format knowing its OID in the first format, you use the first format's prefixes to find its offset, verify its OID in the full object names, and then look up that offset in the list of full object names in the second format.
To go the other way, you find the prefix in the second format, find its corresponding offset in the mapping table, verify the full object ID in the second format, and then look up that offset in the full object names in the first format.
> Disclaimer: the following paragraphs go into how I would have > designed this. This is _not_ meant as a "you have to do it this > way", but as a discussion starter to figure out why you have picked > the proposed format and for me to get a better understanding of it.
The answer is that it very much resembles pack index v3, except that instead of having pack order, we just always use the sorted order of the first object format (since we don't have a pack). That also makes the data deterministic so that we always write identical files for identical objects.
> Stepping back a bit, my expectation is that we'd have one lookup table > per object format so that we can map into all directions: SHA1 -> SHA256 > and in reverse. If we had more than two hash functions we'd also need to > have a table for e.g. Blake3 -> SHA1 and Blake3 -> SHA256 and reverse.
Yeah, and then the file gets very large. We mmap these into memory and never free them during the life of the program (except when compacting them and deleting the unused ones), so we want to be quite conservative with our memory.
> One way to do this is to have three tables, one for each object format. > The object formats would be ordered lexicographically by their own > object ID, so that one can perform a binary search for an object ID in > every format.
We have that with the shortened object IDs and we do a binary search over those. This is more cache-friendly and all we need to do is verify that the full object ID matches our value (as opposed to a different object stored elsewhere with an identical shortened prefix).
Show 45 quoted lines
> Each row could then either contain all compatibility hashes directly, > but this would explode quite fast in storage space. An optimization > would thus be to have one table per object format that contains the > shortened object ID plus an offset where the actual record can be found. > You know where to find the tables from the header, and you know the > exact size of each entry, so you can trivially perform a binary search > for the abbreviated object ID in that index. > > Once you've found that index you take the stored offset to look up the > record in the "main" table. This main table contains the full object IDs > for all object hashes. So something like the following simplified > format: > > +---------------------------------+ > | header | > | Format version | > | Number of object IDs | > | SHA1: abbrev, offset | > | SHA256: abbrev, offset | > | Blake3: abbrev, offset | > | Main: offset | > +---------------------------------+ > | table for SHA1 | > | 11111 -> 1 | > | 22222 -> 2 | > +---------------------------------+ > | table for SHA256 | > | aaaaa -> 2 | > | bbbbb -> 1 | > +---------------------------------+ > | table for Blake3 | > | 88888 -> 2 | > | 99999 -> 1 | > +---------------------------------+ > | main table | > | 11111111 -> bbbbbbbb -> 9999999 | > | 22222222 -> aaaaaaaa -> 8888888 | > +---------------------------------+ > | trailer | > | trailer hash | > +---------------------------------+ > > Overall you only have to store the full object ID for each hash exactly > once, and the mappings also only have to be stored once. But you can > look up an ID by each of its formats via its indices.
This is very similar to what we have now, except that it has mapping offsets for each algorithm instead of the second and subsequent algorithms and it re-orders the location of the full object IDs.
I also intentionally wanted to produce completely deterministic output, since in `git verify-pack` we verify that the output is byte-for-byte identical and I wanted to have the ability to do that here as well. (It isn't implemented yet, but that's a goal.) In order to do that, we need to write every part of the data in a fixed order, so we'd have to define the main table as being sorted by the first algorithm.
> With some slight adjustments one could also adapt this format to become > streamable:
I don't think these formats are as streamable as you might like. In order to create the tables, we need to sort the data for each algorithm to find the short name length, which requires knowing all of the data up front in order.
I, too, thought that might be a nice idea, but when I implemented pack index v3, I realized that effectively all of the data has to be computed up front. Once you do that, computing the offsets isn't hard because it's just some addition and multiplication.
I personally like a header with offsets better than a trailer since it makes parsing easier. We can peek at the first 64 bytes of the file to see if it meets our needs or has data we're interested in.
-- brian m. carlson (they/them) Toronto, Ontario, CA