On 8/13/2025 9:09 PM, brian m. carlson wrote: > TL;DR: We need a different datastore than a flat file for storing > mappings between SHA-1 and SHA-256 in compatibility mode. Advice and > opinions sought. ...> Our approach for mapping object IDs between algorithms uses data in pack > index v3 (outlined in the transition document), plus a flat file called > `loose-object-idx` for loose objects. However, we didn't anticipate > that we'd need to handle mappings long-term for data that is neither a > loose object nor a packed object. I'm generally not a fan of this approach to (ab)use the pack index format for this, especially when the translation needs to expand beyond "objects in the local repo". The requirements, as I see them, are: 1. Given an OID in Hash1, load its mapped OID in Hash2 in O(log N) time. 2. Given an OID in Hash2, load its mapped OID in Hash1 in O(log N) time. 3. As OID pairs are discovered, add them to the data structure in ~O(new) time. > Some rough ideas of what this could look like: > > * We could repurpose the top-bit of the pack order value in pack index > v3 to indicate an object that's not in the pack (this would limit us > to 2^31 items per pack). > * We could put this in new entries in multi-pack index and require that > (although I'm not sure that I love the idea of requiring multi-pack > index in all repositories and I have yet to implement compatibility > mode there). > * We could write some sort of quadratic rollup format like reftable. My thought is that the last option is going to be best. It does require starting a new file format from scratch, but it doesn't need to be complicated: * Header information includes: - file version info. - hash versions in mapping. - the number of OIDs in the format - the previous mapping file(s) in the chain - offsets to the Hash1 and Hash2 tables. - room for expansion to other data being added to the format, as necessary in the future. * Hash1 table has a lex-ordered list of Hash1 OIDs and int IDs to do lookups of the mapped Hash2 OIDs from the second table (by position). * Hash2 table has a lex-ordered list of Hash2 OIDs and int IDs to do lookups of the mapped Hash1 OIDs from the first table (by position). Lookup time would be O(L * log N) where L is the number of layers in the collection of files. Writing time could be as low as the size of a new layer on top, with squashing of layers handled in the background or in the foreground (opportunistically for small layers or as needed if background maintenance is not available). I'm sure that things are more complicated than I'm making it out to be in this email. I haven't looked at your branch to see the subtle details around this. Hopefully this just gives you ideas that you can use as you compare options. Thanks, -Stolee
