{"thread":{"id":"53730","subject":"[RFC] Metadata vs Generation Data Chunk","startedAt":"2020-06-22T09:36:57Z","lastAt":"2020-06-22T14:46:30Z","messageCount":3,"participants":["Abhishek Kumar","Jakub Narębski","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"400274","messageId":"20200622093451.GA1719@Abhishek-Arch","threadId":"53730","inReplyTo":null,"subject":"[RFC] Metadata vs Generation Data Chunk","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-22T09:34:51Z","receivedAt":"2020-06-22T09:36:57Z","isPatch":false,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"One of the remaining pre-requisites for implementing generation number\nv2 was distinguishing between corrected commit dates with monotonically\nincreasing offsets and topological level without incrementing generation\nnumber version.\n\nTwo approaches were proposed [1]:\n1. New chunk for commit data (generation data chunk, \"GDAT\")\n2. Metadata/versioning chunk\n\nSince both approaches have their advantages and disadvantages, I wrote\nup a prototype [2] to investigate their performance.\n\n[1]: https://lore.kernel.org/git/86mu87qj92.fsf@gmail.com/ \n[2]: https://github.com/abhishekkumar2718/git/pull/1\n\nTL;DR: I recommend we should use generation data chunk approach.\n\nGeneration Data Chunk\n=====================\n\nWe could move the generation number v2 into a separate chunk, storing\ntopological levels in CDAT and the corrected commit date into a new,\n\"GDAT\" chunk.  Thus, old Git would use generation number v1, and\nnew Git would use corrected commit dates from GDAT.\n\nUsing generation data chunk has the advantage that we would no longer\nbe restricted to using 30 bits for generation number. It also works\nwell for commit-graph chains with a mix of v1 and v2 generation numbers.\n\nHowever, it increases the time required for I/O as commit data and\ngeneration numbers are no longer contiguous.\n\nNote: While it also increases disk space required for storing\ncommit-graph files by 8 bytes per commit, I don't consider it relevant,\nespecially on modern systems. A repo of the size of Linux repo would be\nlarger by a mere 7.2 Mb.\n\nMetadata / Versioning Chunk\n===========================\n\nWe could also introduce an optional metadata chunk to store generation\nnumber version and store corrected date offsets in CDAT. Since the\noffsets are backward compatible, Old Git would still yield correct\nresults by assuming the offsets to be topological levels. New Git would\ncorrectly use the offsets to create corrected commit dates.\n\nIt works just as well as generation number v1 in parsing and writing\ncommit-graph files.\n\nHowever, the generation numbers are still restricted to 30 bits in CDAT\nchunk and it does not work well with commit-graph chains with a mix of\nv1 and v2 generation numbers.\n\nPerformance\n===========\n\n| Command                        | Master | Metadata | Generation Data |\n|--------------------------------|--------|----------|-----------------|\n| git commit-graph write         | 14.45s | 14.28s   | 14.63s          |\n| git log --topo-order -10000    | 0.211s | 0.206s   | 0.208s          |\n| git log --topo-order -100 A..B | 0.019s | 0.015s   | 0.015s          |\n| git merge-base A..B            | 0.137s | 0.137s   | 0.137s          |\n\n- Metadata and generation data chunks perform better than master on\n  using commit-graph files since they use corrected commit dates.\n\n- The increased I/O time for parsing GDAT does not affect performance as\n  much as expected.\n\n- Generation data commit-graph takes longer to write since more\n  information is written into the file.\n\nAs using the commit-graph is much more frequent than writing, we can\nconsider both approaches to perform equally well.\n\nI prefer generation data chunk approach as it also removes 30-bit length\nrestriction on generation numbers.\n\nThanks\nAbhishek\n"},{"id":"400279","messageId":"10d99e37-8870-6401-d9aa-21a359b30835@gmail.com","threadId":"53730","inReplyTo":"20200622093451.GA1719@Abhishek-Arch","subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-22T13:40:06Z","receivedAt":"2020-06-22T13:40:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On 22.06.2020 at 11:34, Abhishek Kumar wrote:\n\n> One of the remaining pre-requisites for implementing generation number\n> v2 was distinguishing between corrected commit dates with monotonically\n> increasing offsets and topological level without incrementing generation\n> number version.\n> \n> Two approaches were proposed [1]:\n> 1. New chunk for commit data (generation data chunk, \"GDAT\")\n> 2. Metadata/versioning chunk\n\nActually in [1] there was also proposed another distinct approach,\nnamely to 'rename' the \"CDAT\" chunk to something else, like \"CDA2\"\n(or proposed here \"GDAT\").\n\nIf I read the code correctly, with old Git if one of required chunks\nis missing then Git would continue work as if commit-graph was not\npresent -- as opposed to current handling of unknown commit-graph\nfile format version number, where Git would stop working with an\nerror message.\n\n> \n> Since both approaches have their advantages and disadvantages, I wrote\n> up a prototype [2] to investigate their performance.\n> \n> [1]: https://lore.kernel.org/git/86mu87qj92.fsf@gmail.com/\n> [2]: https://github.com/abhishekkumar2718/git/pull/1\n\nThat's very nice.  Thanks for investigating that.\n\n> \n> TL;DR: I recommend we should use generation data chunk approach.\n> \n> Generation Data Chunk\n> =====================\n> \n> We could move the generation number v2 into a separate chunk, storing\n> topological levels in CDAT and the corrected commit date into a new,\n> \"GDAT\" chunk.  Thus, old Git would use generation number v1, and\n> new Git would use corrected commit dates from GDAT.\n> \n> Using generation data chunk has the advantage that we would no longer\n> be restricted to using 30 bits for generation number. It also works\n> well for commit-graph chains with a mix of v1 and v2 generation numbers.\n> \n> However, it increases the time required for I/O as commit data and\n> generation numbers are no longer contiguous.\n> \n> Note: While it also increases disk space required for storing\n> commit-graph files by 8 bytes per commit, I don't consider it relevant,\n> especially on modern systems. A repo of the size of Linux repo would be\n> larger by a mere 7.2 Mb.\n\nAll right.\n\nAnother advantage: we don't have to store the corrected committer date\n_offset_, we can store the date (as epoch) directly.  This saves some\ncalculation, though a minuscule amount.\n\nYet another advantage: we don't need backward-compatibility for\ngeneration number v2, i.e. corrected commit date.\n\nAnother disadvantage: we need to compute both topological levels and\ncorrected commit date when creating a commit-graph file or a chunk of\nit.  This means that `git commit-graph write` could be slightly more\nexpensive.\n\n> \n> Metadata / Versioning Chunk\n> ===========================\n> \n> We could also introduce an optional metadata chunk to store generation\n> number version and store corrected date offsets in CDAT. Since the\n> offsets are backward compatible, Old Git would still yield correct\n> results by assuming the offsets to be topological levels. New Git would\n> correctly use the offsets to create corrected commit dates.\n\nThis also means that we need to use backward-compatible generation\nnumber v2, that is corrected commit date with strictly monotonic\noffsets.  Which may lead to more cases where 30 bits for label is not\nenough, and thus worse performance (no detailed reachability\ninformation for newest commits).\n\n> \n> It works just as well as generation number v1 in parsing and writing\n> commit-graph files.\n> \n> However, the generation numbers are still restricted to 30 bits in CDAT\n> chunk and it does not work well with commit-graph chains with a mix of\n> v1 and v2 generation numbers.\n\n\nCDAT chunk replaced with another chunk\n======================================\n\nIn this approach the \"CDAT\" chunk is missing from the commit-graph file.\nWe can craft the replacement (\"CDA2\") however we like, but it can also\nlook like the \"CDAT\" chunk, only with the offsets for corrected commit\ndate rather than topological level for generation number part (30 bits).\n\nIf we choose to follow the \"CDAT\" format (modified), then the file\nsize would not change, and neither would change the amount of I/O\nneeded -- there would be the same access structure as in current\nversion.\n\nThere should be no confusion with a mix of v1 and v2 generation numbers.\n\nThe disadvantage is of course that older version of Git would no longer\nbe able to make use of serialized commit-graph if the file was written\nby newer version of Git.\n\n> \n> Performance\n> ===========\n\nWhat is the repository where those benchmarks took place?\n\n> | Command                        | Master | Metadata | Generation Data |\n> |--------------------------------|--------|----------|-----------------|\n> | git commit-graph write         | 14.45s | 14.28s   | 14.63s          |\n> | git log --topo-order -10000    | 0.211s | 0.206s   | 0.208s          |\n> | git log --topo-order -100 A..B | 0.019s | 0.015s   | 0.015s          |\n> | git merge-base A..B            | 0.137s | 0.137s   | 0.137s          |\n\nNice.\n\nHow those two (or three) approaches work on gen-test [3] test cases,\nboth in terms of commits walked (extracted via trace2 mechanism) and\nactual wall-time clock, like in the result above?\n\n[3]: https://github.com/derrickstolee/gen-test\n\n> - Metadata and generation data chunks perform better than master on\n>    using commit-graph files since they use corrected commit dates.\n> \n> - The increased I/O time for parsing GDAT does not affect performance as\n>    much as expected.\n> \n> - Generation data commit-graph takes longer to write since more\n>    information is written into the file.\n> \n> As using the commit-graph is much more frequent than writing, we can\n> consider both approaches to perform equally well.\n> \n> I prefer generation data chunk approach as it also removes 30-bit length\n> restriction on generation numbers.\n\nThank you for your work.\n\nBest,\n\nP.S. I hope I haven't sent it twice...\n-- \nJakub Narębski\n"},{"id":"400282","messageId":"7bd59f07-39e7-82c4-51c4-0ceba9f45999@gmail.com","threadId":"53730","inReplyTo":"20200622093451.GA1719@Abhishek-Arch","subject":"Re: [RFC] Metadata vs Generation Data Chunk","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-22T14:46:27Z","receivedAt":"2020-06-22T14:46:30Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/22/2020 5:34 AM, Abhishek Kumar wrote:\n> One of the remaining pre-requisites for implementing generation number\n> v2 was distinguishing between corrected commit dates with monotonically\n> increasing offsets and topological level without incrementing generation\n> number version.\n> \n> Two approaches were proposed [1]:\n> 1. New chunk for commit data (generation data chunk, \"GDAT\")\n> 2. Metadata/versioning chunk\n> \n> Since both approaches have their advantages and disadvantages, I wrote\n> up a prototype [2] to investigate their performance.\n> \n> [1]: https://lore.kernel.org/git/86mu87qj92.fsf@gmail.com/ \n> [2]: https://github.com/abhishekkumar2718/git/pull/1\n> \n> TL;DR: I recommend we should use generation data chunk approach.\n> \n> Generation Data Chunk\n> =====================\n> \n> We could move the generation number v2 into a separate chunk, storing\n> topological levels in CDAT and the corrected commit date into a new,\n> \"GDAT\" chunk.  Thus, old Git would use generation number v1, and\n> new Git would use corrected commit dates from GDAT.\n> \n> Using generation data chunk has the advantage that we would no longer\n> be restricted to using 30 bits for generation number.\n\nIt will be important to detect these 30-bit overflow and replace the\nvalue with GENERATION_NUMBER_MAX and treat those commits as having\nGENERATION_NUMBER_INFINITY(_V2) when parsing them.\n\nThis 30-bit overflow _is_ more likely in the approach we've considered\nbecause the commit-date offsets will accumulate through the history.\nPlease test a check for this against repos with particularly nasty\ncommit-date problems like the Linux kernel repo. Perhaps it would be\nworthwhile to output the maximum stored offset in the trace2 API so\nwe can see how close we are to overflowing, even if we do not.\n\nIn order to fully commit to this plan, we need to know how problematic\nthis overflow is. Generation number v1 required hundreds of millions\nof commits in a row to overflow, but here we could overflow with a few\nappropriate commit date problems. How common are they in the wild?\n\n> It also works\n> well for commit-graph chains with a mix of v1 and v2 generation numbers.\n\nWe do not want to mix commit-graph chains with v1 and v2 numbers,\nbecause we want the comparison between two commits to be independent\nof which commit-graph layer they came from. This will require us to\nsquash the layers if we are asked to write one version and the existing\nchain does not match that version.\n \n> However, it increases the time required for I/O as commit data and\n> generation numbers are no longer contiguous.\n\nI'm glad you were able to measure this, which makes the locality of\nthe data chunk a valuable feature.\n\n> Note: While it also increases disk space required for storing\n> commit-graph files by 8 bytes per commit, I don't consider it relevant,\n> especially on modern systems. A repo of the size of Linux repo would be\n> larger by a mere 7.2 Mb.\n\n...relative to what? What's the percentage increase? It still is not\ngoing to be too bad. I'm _guessing_ ~10-15%.\n\n> Metadata / Versioning Chunk\n> ===========================\n> \n> We could also introduce an optional metadata chunk to store generation\n> number version and store corrected date offsets in CDAT. Since the\n> offsets are backward compatible, Old Git would still yield correct\n> results by assuming the offsets to be topological levels. New Git would\n> correctly use the offsets to create corrected commit dates.\n> \n> It works just as well as generation number v1 in parsing and writing\n> commit-graph files.\n> \n> However, the generation numbers are still restricted to 30 bits in CDAT\n> chunk and it does not work well with commit-graph chains with a mix of\n> v1 and v2 generation numbers.\n> \n> Performance\n> ===========\n> \n> | Command                        | Master | Metadata | Generation Data |\n> |--------------------------------|--------|----------|-----------------|\n> | git commit-graph write         | 14.45s | 14.28s   | 14.63s          |\n> | git log --topo-order -10000    | 0.211s | 0.206s   | 0.208s          |\n> | git log --topo-order -100 A..B | 0.019s | 0.015s   | 0.015s          |\n> | git merge-base A..B            | 0.137s | 0.137s   | 0.137s          |\n> \n> - Metadata and generation data chunks perform better than master on\n>   using commit-graph files since they use corrected commit dates.\n> \n> - The increased I/O time for parsing GDAT does not affect performance as\n>   much as expected.\n> \n> - Generation data commit-graph takes longer to write since more\n>   information is written into the file.\n>> As using the commit-graph is much more frequent than writing, we can\n> consider both approaches to perform equally well.\n> \n> I prefer generation data chunk approach as it also removes 30-bit length\n> restriction on generation numbers.\n\nThanks for testing these approaches.\n\nThe other thing to keep in mind with the new data chunk is that we will\nprobably still want a 32-bit value, but it no longer needs to be\nbackwards compatible! We would keep generation number v1 in the data\nchunk, but could place _any_ definition in the v2 chunk.\n\nThis means that the \"offset\" from the commit-date does not need to be\nstrictly increasing! This could help with the overflow issue if someone\ndecided to do a nasty commit-date order issue (say, a commit with\nUnix epoch \"0\" pointing to a recent commit with \"real\" date).\n\nRecall that a commit C has a commit-date (date(C)) given by the\ncommit date, and we are storing an additional offset (off(C)) with\nthe following requirement for all parents P:\n\n\tdate(C) + off(C) > date(P) + off(P)\n\nThe backwards-compatible requirement is this:\n\n\t\toff(C) > off(P)\n\nbut we can drop that if we are using the new chunk. That allows\noff(C) to be zero if we already have date(C) > date(P) + off(P),\nwhich will naturally happen as time passes (barring malicious\nusers).\n\nSince you have an initial prototype of these two approaches,\ncould you extend your Generation Data prototype to use this\nnon-backwards-compatible model and report the performance data?\n\nI found that using different pairs of tags in the Linux kernel\nrepo to be particularly fruitful for A..B performance tests.\nIn particular, \"git merge-base v4.8 v4.9\" demonstrated the problems\nwith generation number v1 [1]. Please also update the\npaint_down_to_common() method to use generation numbers so\nwe can see the benefit or drawback there. Perhaps use config or\nan environment variable to change this:\n \n\tif (!min_generation)\n\t\tqueue.compare = compare_commits_by_commit_date;\n\nto this:\n\n\tif (!min_genertion && !git_env(...))\n\t\tqueue.compare = compare_commits_by_commit_date;\n\nWithout comparing commit-date heuristics against your generation\nnumber values, we will not be sure that we are moving in the\nright direction here.\n\n[1] https://lore.kernel.org/git/efa3720fb40638e5d61c6130b55e3348d8e4339e.1535633886.git.gitgitgadget@gmail.com/\n\nThanks,\n-Stolee\n"}]}