{"thread":{"id":"63960","subject":"Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","startedAt":"2025-08-14T01:09:28Z","lastAt":"2025-09-03T06:43:45Z","messageCount":10,"participants":["brian m. carlson","Junio C Hamano","Derrick Stolee","Eric Wong","Patrick Steinhardt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"524165","messageId":"aJ03RTHaE_JvHA1t@fruit.crustytoothpaste.net","threadId":"63960","inReplyTo":null,"subject":"Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-08-14T01:09:25Z","receivedAt":"2025-08-14T01:09:28Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"TL;DR: We need a different datastore than a flat file for storing\nmappings between SHA-1 and SHA-256 in compatibility mode.  Advice and\nopinions sought.\n\nAs I've mentioned earlier on the list, I'm working on some of the code\nfor interoperability between SHA-1 and SHA-256.  The good news is that\nit's relatively advanced so far.\n\nRight now, we have pack index v3 (so we can store both loose and packed\nobjects) and it's possible to clone and fetch from and push to a\nsingle-algorithm server if the client repository supports both\nalgorithms and there are no shallow clones, partial clones, or\nsubmodules involved.  Those who are interested can look at my\n`sha256-interop` branch[0], learn more at my talk at Git Merge (which\nI'll be giving remotely), or talk to me at the Contributor Summit.\n\nOur approach for mapping object IDs between algorithms uses data in pack\nindex v3 (outlined in the transition document), plus a flat file called\n`loose-object-idx` for loose objects.  However, we didn't anticipate\nthat we'd need to handle mappings long-term for data that is neither a\nloose object nor a packed object.\n\nFor instance, with shallow clones, we must store a mapping for the\nshallows the server has sent us[1], since we lack the history to convert\nobjects otherwise.  Similarly, if there are submodules or we're using a\npartial clone, we must store those mappings as well, since we cannot\nconvert trees without them.  We can store them in the\n`loose-object-idx`, but since it's not sorted or easily searchable, it's\ngoing to perform really terribly when we store enough of them.  Right\nnow, we read the entire file into two hashmaps (one in each direction)\nand we sometimes need to re-read it when other processes add items, so\nit won't take much to make it be slow and take a lot of memory.\n\nFor these reasons, I think we need a different datastore for this and\nI'd like to solicit opinions on what that should look like.  Here are\nsome things that come to mind:\n\n* The format should be fast to read and relatively fast to write.\n* We need to efficiently read and map objects in both directions.  This\n  is required for many reasons, including efficient fetches and pushes.\n* We still require an in-memory store because we stuff entries in their\n  without writing them during pack indexing and other operations, but\n  that doesn't mean we need to load data from the data files into the\n  in-memory structure (in fact, we probably should try to avoid it).\n* We want to be able to write small updates to the data without having\n  to re-write the entire thing (e.g., `git add`).  We often know that\n  we'll be writing a whole batch at once, such as with shallows or\n  submodules from a clone or fetch, so many places in the code will be\n  able to start a batch and then write, but we shouldn't assume that\n  will always be the case.  (In other words, we will write more\n  frequently than we do packs or indexes.)\n* It would be helpful if we can determine the type of object being\n  stored.  For instance, if we've stored an object mapping because of a\n  shallow, `git gc` could remove that mapping if the shallows have been\n  updated and the mapping is no longer useful.\n* We should try not to assume only two hash algorithms.  Pack index v3\n  allows for effectively an arbitrary number and while much of the\n  compatibility code assumes one main and one compatibility algorithm,\n  we should try to minimize that if possible.[2]\n* Being able to mmap it would be convenient, so if we can make it\n  relatively small, that's nice.\n\nSome rough ideas of what this could look like:\n\n* We could repurpose the top-bit of the pack order value in pack index\n  v3 to indicate an object that's not in the pack (this would limit us\n  to 2^31 items per pack).\n* We could put this in new entries in multi-pack index and require that\n  (although I'm not sure that I love the idea of requiring multi-pack\n  index in all repositories and I have yet to implement compatibility\n  mode there).\n* We could write some sort of quadratic rollup format like reftable.\n\nI would recommend reading the pack index v3 format documentation in\n`Documentation/technical/hash-function-transition.adoc`, since I think\nit's helpful to understand what we have now.  I have implemented a small\nvariant on it (documented in my branch) and will send some documentation\nupdates before code, although the differences are minor and not relevant\nhere.\n\nI've taken the liberty of CCing some people who have worked deeply with\nour existing formats (packs, indexes, reftable, and so on), but I've\nalmost certainly missed some people and I'd love thoughts from anyone\nabout this.  Once we have an approach that we think is useful, I'm happy\nto write up a document for it and send it out.\n\n[0] Available from https://github.com/bk2204/git.git.\n[1] This assumes that the server also supports both algorithms to\ngenerate and send the mapping.  I am implementing that work now and it\nhas yet to be pushed to the branch (because it presently doesn't work).\n[2] We might find that SHA-256 becomes weak well before SHA-1 is\ncompletely dead and we need to deal with a third algorithm suddenly, so\nwe should not mortgage our future unnecessarily.  Cryptographic attacks\nonly ever get better.\n-- \nbrian m. carlson (they/them)\nToronto, Ontario, CA\n"},{"id":"524173","messageId":"xmqq1ppe9e5h.fsf@gitster.g","threadId":"63960","inReplyTo":"aJ03RTHaE_JvHA1t@fruit.crustytoothpaste.net","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-14T14:22:18Z","receivedAt":"2025-08-14T14:22:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n\nI do not know if you want my input (as I wasn't CC'ed), but anyway...\n\n> ...  We can store them in the\n> `loose-object-idx`, but since it's not sorted or easily searchable, it's\n> going to perform really terribly when we store enough of them.  Right\n> now, we read the entire file into two hashmaps (one in each direction)\n> and we sometimes need to re-read it when other processes add items, so\n> it won't take much to make it be slow and take a lot of memory.\n>\n> For these reasons, I think we need a different datastore for this and\n> I'd like to solicit opinions on what that should look like.  Here are\n> some things that come to mind:\n\nI do not see why loose-object-idx is not sorted in the first place,\nbut to account for new objects getting into the object store, it\nwould not be a viable way forward to maintain a single sorted file.\nWe obviously do not want to keep rewriting it in its entirety all\nthe time,\n\n> Some rough ideas of what this could look like:\n>\n> * We could repurpose the top-bit of the pack order value in pack index\n>   v3 to indicate an object that's not in the pack (this would limit us\n>   to 2^31 items per pack).\n\nNice to see an effort to see if we can do with a small incremental\nchange, but would a single bit be sufficient to cover all the needs?\n\nI suspect that the answer is no, in which case the v3 pack .idx\nformat would need to be further tweaked, but in that case we do not\nhave to resort to such a trick of stealing a single bit from here\nand abusing it for other purposes.  We should just make sure that\nthe new .idx file format can have extensions, unlike older format\nthat has fixed sections in fixed order.\n\nIf there aren't any radically novel idea, I would imagine that our\ndesign would default to have a big base file that is optimized for\nreading and searching, plus another format that is easier and\nquicker to write that would overlay, possibly in a way similar to\npacked and loose refs work?\n\n> * We could write some sort of quadratic rollup format like reftable.\n\nThe mapping between two hash formats is stable and once computed can\nbe cast in stone.  Other attributes like the type of each object may\nfall into the same category.  Multi-level roll-up may be overkill\nfor such static data items, especially if consolidation would be a\nsimple \"merge two sorted files into one sorted file\" operation.\n\nAs there are some objects for which we need to carry dynamic\ninformation, e.g. \"we expect not to have this in our object store\nand that is fine\", which may be set for objects immediately behind\nthe shallow-clone boundary, may need to be cleared when the depth of\nshallowness changes.  Would it make sense to store these auxiliary\npieces of information in separate place(s)?  I suspect that the\nobjects that need these extra bits of information form a small\nsubset of all objects that we need to have the conversion data, so a\nseparate table that is indexed into using the order in the main\ntable may not be a bad way to go.\n"},{"id":"524190","messageId":"aJ5d3tvrm2S1ZTR9@fruit.crustytoothpaste.net","threadId":"63960","inReplyTo":"xmqq1ppe9e5h.fsf@gitster.g","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-08-14T22:06:22Z","receivedAt":"2025-08-14T22:06:30Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2025-08-14 at 14:22:18, Junio C Hamano wrote:\n> \"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n> \n> I do not know if you want my input (as I wasn't CC'ed), but anyway...\n> \n> > ...  We can store them in the\n> > `loose-object-idx`, but since it's not sorted or easily searchable, it's\n> > going to perform really terribly when we store enough of them.  Right\n> > now, we read the entire file into two hashmaps (one in each direction)\n> > and we sometimes need to re-read it when other processes add items, so\n> > it won't take much to make it be slow and take a lot of memory.\n> >\n> > For these reasons, I think we need a different datastore for this and\n> > I'd like to solicit opinions on what that should look like.  Here are\n> > some things that come to mind:\n> \n> I do not see why loose-object-idx is not sorted in the first place,\n> but to account for new objects getting into the object store, it\n> would not be a viable way forward to maintain a single sorted file.\n> We obviously do not want to keep rewriting it in its entirety all\n> the time,\n\nIt's not sorted because there's no way to do so and efficiently handle\nboth lookups.  If we sorted it in SHA-256 order, then we would still\nhave to look up items in SHA-1 order with a linear search, and vice\nversa.\n\nWhat we do for pack index v3 is a sorted table of abbreviated names, a\nmapping of that order to pack order, and then full object names in pack\norder, with a set for each algorithm.  The abbreviated names all use the\nsame prefix size, which is just long enough to be unambiguous.  This\nmeans that we can easily look up an object, find its index into pack\norder, and then find the full object ID in any algorithm.\n\nWe could probably write some sort of data file that contains these\nsame mappings except that since we don't have a pack order, we could\njust use a sorted order in the main algorithm and omit the main\nalgorithm's mapping table.  We could then have a single table for the\nnecessary object metadata.\n\n> If there aren't any radically novel idea, I would imagine that our\n> design would default to have a big base file that is optimized for\n> reading and searching, plus another format that is easier and\n> quicker to write that would overlay, possibly in a way similar to\n> packed and loose refs work?\n\nYeah, that could be an option.  Or we could have a base file and some\nincrementals, with a `git gc` when we hit 50 items, just like when we\nhit 50 packfiles.\n\n> As there are some objects for which we need to carry dynamic\n> information, e.g. \"we expect not to have this in our object store\n> and that is fine\", which may be set for objects immediately behind\n> the shallow-clone boundary, may need to be cleared when the depth of\n> shallowness changes.  Would it make sense to store these auxiliary\n> pieces of information in separate place(s)?  I suspect that the\n> objects that need these extra bits of information form a small\n> subset of all objects that we need to have the conversion data, so a\n> separate table that is indexed into using the order in the main\n> table may not be a bad way to go.\n\nMy plan is to just wire this up to `git gc`.  We'd know what entries are\npotentially disposable (such as shallows) and omit the unneeded entries\nwhen repacking.\n-- \nbrian m. carlson (they/them)\nToronto, Ontario, CA\n"},{"id":"524196","messageId":"xmqqh5y9wm8f.fsf@gitster.g","threadId":"63960","inReplyTo":"aJ5d3tvrm2S1ZTR9@fruit.crustytoothpaste.net","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-14T22:51:28Z","receivedAt":"2025-08-14T22:51:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> writes:\n\n>> As there are some objects for which we need to carry dynamic\n>> information, e.g. \"we expect not to have this in our object store\n>> and that is fine\", which may be set for objects immediately behind\n>> the shallow-clone boundary, may need to be cleared when the depth of\n>> shallowness changes.  Would it make sense to store these auxiliary\n>> pieces of information in separate place(s)?  I suspect that the\n>> objects that need these extra bits of information form a small\n>> subset of all objects that we need to have the conversion data, so a\n>> separate table that is indexed into using the order in the main\n>> table may not be a bad way to go.\n>\n> My plan is to just wire this up to `git gc`.  We'd know what entries are\n> potentially disposable (such as shallows) and omit the unneeded entries\n> when repacking.\n\nI wasn't talking about when the information is (gathered|consumed),\nthough.  In response to the request for comments on file format, I\nwas suggesting to have at least two separte files, one for static\npart, and the other for dynamic part, so that the former does not\nhave to be rewritten all the time.\n"},{"id":"524244","messageId":"f61c4070-3d29-465e-8dbf-55c4562c0342@gmail.com","threadId":"63960","inReplyTo":"aJ03RTHaE_JvHA1t@fruit.crustytoothpaste.net","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2025-08-15T15:27:45Z","receivedAt":"2025-08-15T15:27:48Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/13/2025 9:09 PM, brian m. carlson wrote:\n> TL;DR: We need a different datastore than a flat file for storing\n> mappings between SHA-1 and SHA-256 in compatibility mode.  Advice and\n> opinions sought.\n...> Our approach for mapping object IDs between algorithms uses data in pack\n> index v3 (outlined in the transition document), plus a flat file called\n> `loose-object-idx` for loose objects.  However, we didn't anticipate\n> that we'd need to handle mappings long-term for data that is neither a\n> loose object nor a packed object.\n\nI'm generally not a fan of this approach to (ab)use the pack index format\nfor this, especially when the translation needs to expand beyond \"objects\nin the local repo\".\n\nThe requirements, as I see them, are:\n\n1. Given an OID in Hash1, load its mapped OID in Hash2 in O(log N) time.\n2. Given an OID in Hash2, load its mapped OID in Hash1 in O(log N) time.\n3. As OID pairs are discovered, add them to the data structure in ~O(new)\n   time.\n\n> Some rough ideas of what this could look like:\n> \n> * We could repurpose the top-bit of the pack order value in pack index\n>   v3 to indicate an object that's not in the pack (this would limit us\n>   to 2^31 items per pack).\n> * We could put this in new entries in multi-pack index and require that\n>   (although I'm not sure that I love the idea of requiring multi-pack\n>   index in all repositories and I have yet to implement compatibility\n>   mode there).\n> * We could write some sort of quadratic rollup format like reftable.\n\nMy thought is that the last option is going to be best. It does require\nstarting a new file format from scratch, but it doesn't need to be\ncomplicated:\n\n* Header information includes:\n\t- file version info.\n\t- hash versions in mapping.\n\t- the number of OIDs in the format\n\t- the previous mapping file(s) in the chain\n\t- offsets to the Hash1 and Hash2 tables.\n\t- room for expansion to other data being added to the format,\n\t  as necessary in the future.\n* Hash1 table has a lex-ordered list of Hash1 OIDs and int IDs to do\n  lookups of the mapped Hash2 OIDs from the second table (by position).\n* Hash2 table has a lex-ordered list of Hash2 OIDs and int IDs to do\n  lookups of the mapped Hash1 OIDs from the first table (by position).\n\nLookup time would be O(L * log N) where L is the number of layers in\nthe collection of files. Writing time could be as low as the size of\na new layer on top, with squashing of layers handled in the background\nor in the foreground (opportunistically for small layers or as needed\nif background maintenance is not available).\n\nI'm sure that things are more complicated than I'm making it out to\nbe in this email. I haven't looked at your branch to see the subtle\ndetails around this. Hopefully this just gives you ideas that you\ncan use as you compare options.\n\nThanks,\n-Stolee\n\n"},{"id":"525069","messageId":"20250827190817.M36986@dcvr","threadId":"63960","inReplyTo":"aJ03RTHaE_JvHA1t@fruit.crustytoothpaste.net","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2025-08-27T19:08:16Z","receivedAt":"2025-08-27T19:13:55Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> wrote:\n> TL;DR: We need a different datastore than a flat file for storing\n> mappings between SHA-1 and SHA-256 in compatibility mode.  Advice and\n> opinions sought.\n\n<snip>\n\n> Our approach for mapping object IDs between algorithms uses data in pack\n> index v3 (outlined in the transition document), plus a flat file called\n> `loose-object-idx` for loose objects.  However, we didn't anticipate\n> that we'd need to handle mappings long-term for data that is neither a\n> loose object nor a packed object.\n> \n> For instance, with shallow clones, we must store a mapping for the\n> shallows the server has sent us[1], since we lack the history to convert\n> objects otherwise.  Similarly, if there are submodules or we're using a\n> partial clone, we must store those mappings as well, since we cannot\n> convert trees without them.  We can store them in the\n> `loose-object-idx`, but since it's not sorted or easily searchable, it's\n> going to perform really terribly when we store enough of them.  Right\n> now, we read the entire file into two hashmaps (one in each direction)\n> and we sometimes need to re-read it when other processes add items, so\n> it won't take much to make it be slow and take a lot of memory.\n\nThis really seems ideal for SQLite, which has come a long way\nsince 2005 when git started.\n\nI really wish git would've relied on more on existing formats\n(e.g. LMDB refs) rather than introducing more one-off data\nformats that require more cognitive overhead to document and\nlearn[1], especially when SQLite is extremely portable and works\non tiny devices.\n\n> For these reasons, I think we need a different datastore for this and\n> I'd like to solicit opinions on what that should look like.  Here are\n> some things that come to mind:\n> \n> * The format should be fast to read and relatively fast to write.\n> * We need to efficiently read and map objects in both directions.  This\n>   is required for many reasons, including efficient fetches and pushes.\n\nSQLite seems to do these well, in my experience.  It's not the\nfastest possible data store, but it's no slouch, either.\n\n> * We still require an in-memory store because we stuff entries in their\n>   without writing them during pack indexing and other operations, but\n>   that doesn't mean we need to load data from the data files into the\n>   in-memory structure (in fact, we probably should try to avoid it).\n\nSQLite supports in-memory DBs, and also mmap.  I always prefer\nto always put larger structures on TMPDIR and rely on page\ncache; because sometimes code ends up running on machines with\ntoo little memory/swap (but git has never been great w.r.t.\nmemory use :<).\n\n> * We want to be able to write small updates to the data without having\n>   to re-write the entire thing (e.g., `git add`).  We often know that\n>   we'll be writing a whole batch at once, such as with shallows or\n>   submodules from a clone or fetch, so many places in the code will be\n>   able to start a batch and then write, but we shouldn't assume that\n>   will always be the case.  (In other words, we will write more\n>   frequently than we do packs or indexes.)\n\nTransactions and atomicity are included, of course.\n\n> * It would be helpful if we can determine the type of object being\n>   stored.  For instance, if we've stored an object mapping because of a\n>   shallow, `git gc` could remove that mapping if the shallows have been\n>   updated and the mapping is no longer useful.\n\nColumn names should be enough.\n\n> * We should try not to assume only two hash algorithms.  Pack index v3\n>   allows for effectively an arbitrary number and while much of the\n>   compatibility code assumes one main and one compatibility algorithm,\n>   we should try to minimize that if possible.[2]\n\nI haven't used it much, but ALTER TABLE should work well nowadays\nfor adding (maybe not removing) columns.\n\n> * Being able to mmap it would be convenient, so if we can make it\n>   relatively small, that's nice.\n\nmmap is possible, but default builds of SQLite defaults to a\nrelatively small mmap limit (2G?).  I don't know why and never\nbothered to deal sign up for their Fossil (JS required :<, last\nI checked) to ask about the small default limit.\n\n\nI don't like SQLite's approach to rejecting outside\ncontributions; but otherwise it's served me well with various\nbits of Perl code for the last 15 years or so.  Yeah, the SQLite\ndeveloper doesn't have the highest opinion of git, but we\nshouldn't let that affect our decision making.\n\n\n[1] Fwiw, I enjoyed working on git a lot more when it used more\n    high-level scripting glue.  I'm disappointed in the overall\n    movement towards AOT languages (C, now Rust) due to large\n    toolchains, slow builds + linkers.  Hacking was much more\n    discoverable when I could just edit installed scripts like\n    config files and not have to deal with builds at all :>\n"},{"id":"525112","messageId":"xmqqtt1rxzts.fsf@gitster.g","threadId":"63960","inReplyTo":"20250827190817.M36986@dcvr","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T14:53:19Z","receivedAt":"2025-08-28T14:53:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Wong <e@80x24.org> writes:\n\n> I don't like SQLite's approach to rejecting outside\n> contributions; but otherwise it's served me well with various\n> bits of Perl code for the last 15 years or so.  Yeah, the SQLite\n> developer doesn't have the highest opinion of git, but we\n> shouldn't let that affect our decision making.\n\nThey're in \"public domain\", IIRC.  And portable than we are ;-)\n\n> [1] Fwiw, I enjoyed working on git a lot more when it used more\n>     high-level scripting glue.  I'm disappointed in the overall\n>     movement towards AOT languages (C, now Rust) due to large\n>     toolchains, slow builds + linkers.  Hacking was much more\n>     discoverable when I could just edit installed scripts like\n>     config files and not have to deal with builds at all :>\n\nAhh, the halcyon days...\n"},{"id":"525159","messageId":"aLDNj5GPYA9nR3xR@fruit.crustytoothpaste.net","threadId":"63960","inReplyTo":"20250827190817.M36986@dcvr","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-08-28T21:43:43Z","receivedAt":"2025-08-28T21:43:45Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2025-08-27 at 19:08:16, Eric Wong wrote:\n> \"brian m. carlson\" <sandals@crustytoothpaste.net> wrote:\n> > TL;DR: We need a different datastore than a flat file for storing\n> > mappings between SHA-1 and SHA-256 in compatibility mode.  Advice and\n> > opinions sought.\n> \n> <snip>\n> \n> > Our approach for mapping object IDs between algorithms uses data in pack\n> > index v3 (outlined in the transition document), plus a flat file called\n> > `loose-object-idx` for loose objects.  However, we didn't anticipate\n> > that we'd need to handle mappings long-term for data that is neither a\n> > loose object nor a packed object.\n> > \n> > For instance, with shallow clones, we must store a mapping for the\n> > shallows the server has sent us[1], since we lack the history to convert\n> > objects otherwise.  Similarly, if there are submodules or we're using a\n> > partial clone, we must store those mappings as well, since we cannot\n> > convert trees without them.  We can store them in the\n> > `loose-object-idx`, but since it's not sorted or easily searchable, it's\n> > going to perform really terribly when we store enough of them.  Right\n> > now, we read the entire file into two hashmaps (one in each direction)\n> > and we sometimes need to re-read it when other processes add items, so\n> > it won't take much to make it be slow and take a lot of memory.\n> \n> This really seems ideal for SQLite, which has come a long way\n> since 2005 when git started.\n> \n> I really wish git would've relied on more on existing formats\n> (e.g. LMDB refs) rather than introducing more one-off data\n> formats that require more cognitive overhead to document and\n> learn[1], especially when SQLite is extremely portable and works\n> on tiny devices.\n\nSQLite is not an option because it performs poorly with Java and we want\nour formats to work with other implementations, like JGit.  That's why\nwe created reftable instead of using SQLite.\n\nAlso, in general, I'm not interested in being tied to a single\nimplementation.  If the developers of SQLite decide to dramatically\nchange the license of all their code like Oracle did with Berkeley DB,\nwe're going to have a problem.  Yes, we can use the older versions, but\nwe'd still need people to maintain the library and update it.\n-- \nbrian m. carlson (they/them)\nToronto, Ontario, CA\n"},{"id":"525239","messageId":"20250829195109.M344703@dcvr","threadId":"63960","inReplyTo":"aLDNj5GPYA9nR3xR@fruit.crustytoothpaste.net","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2025-08-29T19:51:09Z","receivedAt":"2025-08-29T19:51:16Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"\"brian m. carlson\" <sandals@crustytoothpaste.net> wrote:\n> SQLite is not an option because it performs poorly with Java and we want\n> our formats to work with other implementations, like JGit.  That's why\n> we created reftable instead of using SQLite.\n\nInteresting.  I would've thought it'd be a solved problem by now\ngiven the popularity of both SQLite and Java.  I actually\nexpected choosing a more common/standard file format would make\nlife easier for hackers of alternative git implementations.\n\nSearching for `pure java sqlite' reveals some projects, but\nI'm not a Java user at all so can't comment on the quality of\nimplementations:\nhttps://html.duckduckgo.com/html/?q=pure+java+sqlite\n\nFwiw, the US Library of Congress has SQLite as a recommended\ndata format for several years, now:\nhttps://www.loc.gov/preservation/digital/formats/fdd/fdd000461.shtml\nNowadays I'm more concerned about the continued relevance or\neven existence of the LoC than SQLite.\n\n> Also, in general, I'm not interested in being tied to a single\n> implementation.  If the developers of SQLite decide to dramatically\n> change the license of all their code like Oracle did with Berkeley DB,\n> we're going to have a problem.  Yes, we can use the older versions, but\n> we'd still need people to maintain the library and update it.\n\nWhereas we'd be implementing and maintaining yet another one-off\ndata format from day one instead of waiting for an eventuality\nwhich may never come.  SQLite 3 has far surpassed the stability\nand use of Berkeley DB; there's not a lot of similar formats\nthat might replace it (e.g. GDBM, LMDB).  So I'd expect there'd\nbe no shortage of hackers able to maintain a usable fork if push\ncomes to shove.\n\n\nFwiw, I consider the proliferation of data formats and protocols\nthe biggest threat to digital freedom and security.  Even when\nthe implementations are open source it feels like a huge drain\nto have to constantly deal reviewing/porting code to deal with\nmore formats.\n"},{"id":"525399","messageId":"aLfjk7FalA1A0o6M@pks.im","threadId":"63960","inReplyTo":"f61c4070-3d29-465e-8dbf-55c4562c0342@gmail.com","subject":"Re: Efficiently storing SHA-1 ↔ SHA-256 mappings in compatibility mode","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-09-03T06:43:31Z","receivedAt":"2025-09-03T06:43:45Z","isPatch":false,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Aug 15, 2025 at 11:27:45AM -0400, Derrick Stolee wrote:\n\nSorry, a bit late to the party due to various things going on that\ndistracted me for the last couple weeks.\n\n> On 8/13/2025 9:09 PM, brian m. carlson wrote:\n> > TL;DR: We need a different datastore than a flat file for storing\n> > mappings between SHA-1 and SHA-256 in compatibility mode.  Advice and\n> > opinions sought.\n> ...> Our approach for mapping object IDs between algorithms uses data in pack\n> > index v3 (outlined in the transition document), plus a flat file called\n> > `loose-object-idx` for loose objects.  However, we didn't anticipate\n> > that we'd need to handle mappings long-term for data that is neither a\n> > loose object nor a packed object.\n> \n> I'm generally not a fan of this approach to (ab)use the pack index format\n> for this, especially when the translation needs to expand beyond \"objects\n> in the local repo\".\n> \n> The requirements, as I see them, are:\n> \n> 1. Given an OID in Hash1, load its mapped OID in Hash2 in O(log N) time.\n> 2. Given an OID in Hash2, load its mapped OID in Hash1 in O(log N) time.\n> 3. As OID pairs are discovered, add them to the data structure in ~O(new)\n>    time.\n> \n> > Some rough ideas of what this could look like:\n> > \n> > * We could repurpose the top-bit of the pack order value in pack index\n> >   v3 to indicate an object that's not in the pack (this would limit us\n> >   to 2^31 items per pack).\n> > * We could put this in new entries in multi-pack index and require that\n> >   (although I'm not sure that I love the idea of requiring multi-pack\n> >   index in all repositories and I have yet to implement compatibility\n> >   mode there).\n> > * We could write some sort of quadratic rollup format like reftable.\n> \n> My thought is that the last option is going to be best.\n\nYeah, agreed. One thing that we tend to always end up with eventually is\nusing geometric sequences for repacking data structures. Because\nultimately, the bigger a repository grows the more expensive it'll\nbecome over time to rewrite the base file. And furthermore, there's\nalways going to be use cases where rewriting the base file needs to\nhappen a whole lot more frequently than one would reasonably expect.\n\n> It does require starting a new file format from scratch, but it\n> doesn't need to be complicated:\n> \n> * Header information includes:\n> \t- file version info.\n> \t- hash versions in mapping.\n> \t- the number of OIDs in the format\n> \t- the previous mapping file(s) in the chain\n> \t- offsets to the Hash1 and Hash2 tables.\n> \t- room for expansion to other data being added to the format,\n> \t  as necessary in the future.\n> * Hash1 table has a lex-ordered list of Hash1 OIDs and int IDs to do\n>   lookups of the mapped Hash2 OIDs from the second table (by position).\n> * Hash2 table has a lex-ordered list of Hash2 OIDs and int IDs to do\n>   lookups of the mapped Hash1 OIDs from the first table (by position).\n\nI was wondering whether we need to fully reinvent the wheel here. We\nalready use our chunk format for multiple different data formats (commit\ngraphs, MIDX), so maybe we can also reuse it for this type of mapping?\n\n> Lookup time would be O(L * log N) where L is the number of layers in\n> the collection of files. Writing time could be as low as the size of\n> a new layer on top, with squashing of layers handled in the background\n> or in the foreground (opportunistically for small layers or as needed\n> if background maintenance is not available).\n> \n> I'm sure that things are more complicated than I'm making it out to\n> be in this email. I haven't looked at your branch to see the subtle\n> details around this. Hopefully this just gives you ideas that you\n> can use as you compare options.\n\nLikewise, and I'm very sure that due to me being late the ship has\nalready sailed :)\n\nPatrick\n"}]}