{"thread":{"id":"4982","subject":"Handling very large numbers of symbolic references?","startedAt":"2006-07-25T19:29:46Z","lastAt":"2006-07-25T23:20:58Z","messageCount":6,"participants":["Nix","Rene Scharfe","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"24101","messageId":"87psfteb4l.fsf@hades.wkstn.nix","threadId":"4982","inReplyTo":null,"subject":"Handling very large numbers of symbolic references?","fromName":"Nix","fromEmail":"nix@esperi.org.uk","sentAt":"2006-07-25T19:29:46Z","receivedAt":"2006-07-25T19:29:46Z","isPatch":false,"sender":{"key":"nix@esperi.org.uk","avatar":"https://avatars.githubusercontent.com/u/6503005?v=4"},"body":"I'm about to start writing my first git porcelain (to try to convert my\nworkplace from the world's oldest and cruftiest version control system\nto something not based on the bastard offspring of SCCS and VMS's CMS,\nwith less power than either) and have run into a problem that I'm not\nsure how to solve.\n\nThe biggest problem with git for totally naive users is that they get\nscared by the sha1 IDs used as version numbers (assuming the index is\nporcelained away: but that would confuse them, not scare them). They're\nnot pronounceable, not memorable, and so on. So the porcelain I'm\nwhipping up conceals them in large part by using instead bug IDs, as the\nworkflow of the place I'm doing this for is driven entirely by Bugzilla\nbug numbers.\n\nI'm taking a leaf from the `git for the ignorant' document and arranging\nthat every fix that fixes some Bugzilla bug is on a branch named after\nthat bug, e.g. #2243, #10155, whatever. (I'm going to have to go further\nthan that and track dependency relationships between bugs, i.e. `if you\nmerge bug #1404's branch, you must merge #1306's and #1505's as well'. I\ncould do that by adding a new bug-dependency object, respected by a\nwrapper around git-merge, but I'm not sure how kosher it is to add new\ntypes of objects only used by porcelain. Hell, I'm not even sure if it's\npossible yet.)\n\nHowever, this causes a potential problem. There are tens of thousands of\nthese bugs, and the .git/refs/heads directory gets *enormous* and thus\nthe system gets terribly terribly slow (crappy old Solaris filesystem\nsyndrome).\n\nIt seems to me there are two ways to fix this:\n\n - restructure .git/refs/* in a similar way to .git/objects, i.e. as a\n   one- or two-level tree.\n\n - the vast majority of these bugs are closed. They still need to be got\n   at now and again for branch merges, but they could be got out of\n   .refs/heads at delete_branch time, and pushed into a tree consisting\n   entirely of deleted branches, which would in turn be pointed at from\n   some new place under .refs; perhaps .refs/heads/heavy (by analogy to\n   non-lightweight tags). The problem here is that whenever we delete\n   a tag, we'll leak that tree (at least we will if it's in a pack), and\n   that leakage really could add up in the end.\n\n   (Deleting branches corresponding to closed bugs is good for other\n   reasons: e.g., it cleans up gitweb output. But certain tools *will*\n   need to get at those closed bug branches: I'm inclined to say that\n   all of them will sooner or later, because the users aren't going to\n   tolerate being told that they can't do anything to a closed\n   bug. Except for adding code to it: we can reasonably declare the\n   addition of commits to those branches over. Of course once we have\n   the sha1 id, it's all academic, really.)\n\nI'm not sure which way is preferable. Suggestions? Is the entire idea\nlunatic?\n\n\nAnd, in case this hasn't been said enough: thank you for git, it's the\nnicest version control system I've used in years, and the way it's\nstructured encourages everyone to play :)\n\n-- \n`We're sysadmins. We deal with the inconceivable so often I can clearly \n see the need to define levels of inconceivability.' --- Rik Steenwinkel\n"},{"id":"24105","messageId":"44C68D52.6030107@lsrfire.ath.cx","threadId":"4982","inReplyTo":"87psfteb4l.fsf@hades.wkstn.nix","subject":"Re: Handling very large numbers of symbolic references?","fromName":"Rene Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2006-07-25T21:29:54Z","receivedAt":"2006-07-25T21:29:54Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Nix schrieb:\n> However, this causes a potential problem. There are tens of thousands of\n> these bugs, and the .git/refs/heads directory gets *enormous* and thus\n> the system gets terribly terribly slow (crappy old Solaris filesystem\n> syndrome).\n> \n> It seems to me there are two ways to fix this:\n> \n>  - restructure .git/refs/* in a similar way to .git/objects, i.e. as a\n>    one- or two-level tree.\n\nBranch names are allowed to contain slashes, thus your porcelain is free\nto implement such a tree.  Add a slash after every two bug ID digits and\nyour directories will never contain more than 100 objects.\n\nRené\n"},{"id":"24106","messageId":"87u055bbdb.fsf@hades.wkstn.nix","threadId":"4982","inReplyTo":"44C68D52.6030107@lsrfire.ath.cx","subject":"Re: Handling very large numbers of symbolic references?","fromName":"Nix","fromEmail":"nix@esperi.org.uk","sentAt":"2006-07-25T21:52:48Z","receivedAt":"2006-07-25T21:52:48Z","isPatch":false,"sender":{"key":"nix@esperi.org.uk","avatar":"https://avatars.githubusercontent.com/u/6503005?v=4"},"body":"On Tue, 25 Jul 2006, Rene Scharfe said:\n> Nix schrieb:\n>> However, this causes a potential problem. There are tens of thousands of\n>> these bugs, and the .git/refs/heads directory gets *enormous* and thus\n>> the system gets terribly terribly slow (crappy old Solaris filesystem\n>> syndrome).\n>> \n>> It seems to me there are two ways to fix this:\n>> \n>>  - restructure .git/refs/* in a similar way to .git/objects, i.e. as a\n>>    one- or two-level tree.\n> \n> Branch names are allowed to contain slashes, thus your porcelain is free\n> to implement such a tree.  Add a slash after every two bug ID digits and\n> your directories will never contain more than 100 objects.\n\nOh, lovely! I was *sure* I'd need to make git core changes for this, but\nno, the precognitive powers of the git hackers had anticipated my needs\nbefore I knew what they were!\n\n(Now the only downside is gitweb's treatment of such heads: but looking\nat the code, making it skip suitably formatted heads when displaying the\nheads list is an utterly trivial one-liner.)\n\n-- \n`We're sysadmins. We deal with the inconceivable so often I can clearly \n see the need to define levels of inconceivability.' --- Rik Steenwinkel\n"},{"id":"24108","messageId":"Pine.LNX.4.64.0607251508540.29649@g5.osdl.org","threadId":"4982","inReplyTo":"87psfteb4l.fsf@hades.wkstn.nix","subject":"Re: Handling very large numbers of symbolic references?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-25T22:23:57Z","receivedAt":"2006-07-25T22:23:57Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 25 Jul 2006, Nix wrote:\n> \n> However, this causes a potential problem. There are tens of thousands of\n> these bugs, and the .git/refs/heads directory gets *enormous* and thus\n> the system gets terribly terribly slow (crappy old Solaris filesystem\n> syndrome).\n\nI would really suggest you use some lookup logic of your own to handle \nthis, because having that many refs will slow down a lot of things.\n\nThat said, you can certainly use a hierarchy of refs, and just have them \nas\n\n\t.git/refs/heads/00/000-999\n\t\t\t01/000-999\n\t\t\t02/000-999\n\t\t\t...\n\nif you want to avoid the dreaded filesystem meltdown.\n\nI suspect it would suck, though. You'd still end up with tens of thousands \nof small files, with no good way to pack them together.\n\n> It seems to me there are two ways to fix this:\n> \n>  - restructure .git/refs/* in a similar way to .git/objects, i.e. as a\n>    one- or two-level tree.\n\nSo this work already.\n\n>  - the vast majority of these bugs are closed. They still need to be got\n>    at now and again for branch merges, but they could be got out of\n>    .refs/heads at delete_branch time, and pushed into a tree consisting\n>    entirely of deleted branches, which would in turn be pointed at from\n>    some new place under .refs; perhaps .refs/heads/heavy (by analogy to\n>    non-lightweight tags). The problem here is that whenever we delete\n>    a tag, we'll leak that tree (at least we will if it's in a pack), and\n>    that leakage really could add up in the end.\n\nWell, the problem to some degree is that a number of git routines will \nlook up all heads (eg things like \"git pull\" and \"git ls-remote\" and \"git \npush\", not to mention all the visualizers that want to show all the heads.\n\nSo so if you really en dup doing them as individual heads, I'm afraid that \nperformance will suck big-time. And it wouldn't really help to put them \nunder .git/refs/heads/heavy, you'd still be in trouble.\n\n> I'm not sure which way is preferable. Suggestions? Is the entire idea\n> lunatic?\n\nI think you _can_ use git in the way you propose, but it's going to be \nfundamentally pretty inefficient. The diskspace usage will be inefficient \n(tens of thousands of files, all just 41 characters in size), but even \nmore importantly, as mentioned, you'll have things like cloning or pulling \na repository always havign to get tens of thousands of references, and \nthat's just going to be very very slow.\n\nSo yes, I think it's a bit lunatic.\n\nGit scales much better in _other_ ways. For example, one thing you could \ndo is to have each bug-report be described as a _file_ instead of as a \ntag, and then have just one (or a few branches), and you'd have nice \nnaming of bugs just because the filenames can be nice. That would allow \ngit to shine because it scales well in things git is good at, ie the \ndatabase itself.\n\nYou'd probably want to introduce the notion of a nice specialized \"merge\" \nfor those files (assuming you really want to do _distributed_ reporting, \nand actually merge two different databases that have the same bugs), but \ngit should actually be quite good at supporting something like that, even \nif you might have to do some infrastructure yourself.\n\nOR, you could actually teach git about other ways of looking up names. So \nif you decide that you do want to have one branch per bug, you might want \nto teach git about a new \"ref\" file format that has multiple name/ref \ntranslations in the same file. That would solve the disk usage problem, \neven if it would _not_ solve the ineffiency of tools that might be \nslightly unhappy to see thousands and thousands of refs.\n\nAnyway, whatever approach you select, send patches to Junio. I'm sure that \nwe can try to make git support even some rather strange models.\n\n\t\tLinus\n"},{"id":"24109","messageId":"87psftb7v8.fsf@hades.wkstn.nix","threadId":"4982","inReplyTo":"Pine.LNX.4.64.0607251508540.29649@g5.osdl.org","subject":"Re: Handling very large numbers of symbolic references?","fromName":"Nix","fromEmail":"nix@esperi.org.uk","sentAt":"2006-07-25T23:08:27Z","receivedAt":"2006-07-25T23:08:27Z","isPatch":false,"sender":{"key":"nix@esperi.org.uk","avatar":"https://avatars.githubusercontent.com/u/6503005?v=4"},"body":"On Tue, 25 Jul 2006, Linus Torvalds noted:\n> That said, you can certainly use a hierarchy of refs, and just have them \n> as\n> \n> \t.git/refs/heads/00/000-999\n> \t\t\t01/000-999\n> \t\t\t02/000-999\n> \t\t\t...\n> \n> if you want to avoid the dreaded filesystem meltdown.\n\nThat's what I was hoping would work, but...\n\n> I suspect it would suck, though. You'd still end up with tens of thousands \n> of small files, with no good way to pack them together.\n\n... that is, indeed, the problem.\n\n>>  - the vast majority of these bugs are closed. They still need to be got\n>>    at now and again for branch merges, but they could be got out of\n>>    .refs/heads at delete_branch time, and pushed into a tree consisting\n>>    entirely of deleted branches, which would in turn be pointed at from\n>>    some new place under .refs; perhaps .refs/heads/heavy (by analogy to\n>>    non-lightweight tags). The problem here is that whenever we delete\n>>    a tag, we'll leak that tree (at least we will if it's in a pack), and\n>>    that leakage really could add up in the end.\n> \n> Well, the problem to some degree is that a number of git routines will \n> look up all heads (eg things like \"git pull\" and \"git ls-remote\" and \"git \n> push\", not to mention all the visualizers that want to show all the heads.\n\nIck. Yes, that would be a bit of a sod. git-ls-remote showing >30,000 heads\nis... not ideal. Not at all. (It's growing by ~50 a day...)\n\nIt's a sort of `hidden head' I meant. Hm. I think I see a way: see below.\n\n> So so if you really en dup doing them as individual heads, I'm afraid that \n> performance will suck big-time. And it wouldn't really help to put them \n> under .git/refs/heads/heavy, you'd still be in trouble.\n\nOK, so it has to go somewhere else.\n\n>> I'm not sure which way is preferable. Suggestions? Is the entire idea\n>> lunatic?\n> \n> I think you _can_ use git in the way you propose, but it's going to be \n> fundamentally pretty inefficient. The diskspace usage will be inefficient \n> (tens of thousands of files, all just 41 characters in size), but even \n> more importantly, as mentioned, you'll have things like cloning or pulling \n> a repository always havign to get tens of thousands of references, and \n> that's just going to be very very slow.\n> \n> So yes, I think it's a bit lunatic.\n\nIt's perhaps unusual, but, well, the version control system we're\nswitching from takes over an *hour* just to check out some classes of\nfiles! (SCCS's handling of large binary files is... inefficient if\nnaively kludged by uuencoding everything before committing it; we have\nsome s-files whose size is approaching a gigabyte as a result, being\naccessed over very slow NFS. git, of course, doesn't need such crud,\nalthough I may need to teach the deltifier about xdelta or something of\nthat nature to keep sizes down in the long run.)\n\n> Git scales much better in _other_ ways. For example, one thing you could \n> do is to have each bug-report be described as a _file_ instead of as a \n> tag, and then have just one (or a few branches), and you'd have nice \n> naming of bugs just because the filenames can be nice. That would allow \n> git to shine because it scales well in things git is good at, ie the \n> database itself.\n> \n> You'd probably want to introduce the notion of a nice specialized \"merge\" \n> for those files (assuming you really want to do _distributed_ reporting, \n> and actually merge two different databases that have the same bugs), but \n\nThat's the sort of unlikely thing which is *certain* to happen :) but in\npractice until those database merges actually take place I can't be sure\nhow the renumbering would be done :/ but no, the heaps-of-refs seems\nlike the only practical way, because in practice people treat these bugs\nas little sets of changed files that they can merge all over the place,\nand, well, that's a branch as far as I can see. Of course, the\ndifference between a branch and a `tree of commits which has a ref-like\nthing pointing to it' is minimal: I'd have to teach git-fsck-objects\nabout it anyway to stop it ditching things as unreachable when they\nweren't...\n\n> git should actually be quite good at supporting something like that, even \n> if you might have to do some infrastructure yourself.\n> \n> OR, you could actually teach git about other ways of looking up names. So \n\nThis is what I was thinking of doing.\n\n> if you decide that you do want to have one branch per bug, you might want \n> to teach git about a new \"ref\" file format that has multiple name/ref \n> translations in the same file. That would solve the disk usage problem, \n> even if it would _not_ solve the ineffiency of tools that might be \n> slightly unhappy to see thousands and thousands of refs.\n\nWell, actually I was considering trying a combination of two things:\n\n - a new type of multi-entry ref (as you suggested), perhaps in a file\n   refs/inactive-heads, which is merged with the heads list by lookup\n   operations only (so merge would see them, but ls-remote would not:\n   `invisible heads' if you will); git-branch moves head refs there upon\n   deletion; so even deleted head refs are referenceable by name\n   forever. The merging for lookup would scale as O(n), of course, but\n   that can probably be ignored until we have hundreds of thousands of\n   them (whereupon the right thing to do is probably to change the\n   inactive-heads file format and lookup code and keep the general idea).\n\n   (This might mean rejigging code that assumes that looking up a ref is\n   an open() away, but that shouldn't be all that terribly hard, one new\n   tool, `git-lookup-ref', sort of like git-symbolic-ref only applying\n   to refs that aren't symbolic).\n\n - dependency information could be handled by rebasing the depending\n   branch on the heads of the branches which it depends upon, but, well,\n   that seems extremely icky to me, especially if those branches are\n   still changing: we'd have to re-rebase all the time to stay up to\n   date. I suspect that a new object type, or perhaps a new type of ref,\n   would be right here. The idea is that you express a mapping from one\n   branch ref to another set of branch refs (*not* sha1 id, because there\n   is no fixed sha1 id that corresponds to a given branch in the presence\n   of commit and git-rebase).\n\n   A new object type seems ideal for this (sort of like a commit only\n   with ref names instead of sha1 ids), but I'm under the impression\n   that adding new object types to git is quite tricky and introduces\n   inter-repository incompatibilities, so I might just make it a\n   refs/dependencies directory with one file per depending bug, containing\n   many ref names for the bugs it depends on. (There will likely be many\n   fewer dependencies than inactive bug branches, anyway.)\n\nThis should be fun!\n\n> Anyway, whatever approach you select, send patches to Junio. I'm sure that \n> we can try to make git support even some rather strange models.\n\nYeah, I'm planning to make this general enough that anyone can use it:\nthere'll be an outer layer of glaze around the porcelain which is\nspecifically to change the command-line syntax to be similar to the tool\nthat the poor sods at work are moving from, but I'll maintain that in a\nbranch that nobody sane will pull and that I won't push to anyone, and\nkeep it out of the tree meant for sane people. (I'm not sure if `local\nbranch' is really the right term for it: I mean, this is git, *all*\nbranches are local, or none are...)\n\n-- \n`We're sysadmins. We deal with the inconceivable so often I can clearly \n see the need to define levels of inconceivability.' --- Rik Steenwinkel\n"},{"id":"24110","messageId":"Pine.LNX.4.64.0607251612480.29649@g5.osdl.org","threadId":"4982","inReplyTo":"87psftb7v8.fsf@hades.wkstn.nix","subject":"Re: Handling very large numbers of symbolic references?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-07-25T23:20:58Z","receivedAt":"2006-07-25T23:20:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 26 Jul 2006, Nix wrote:\n> \n> Well, actually I was considering trying a combination of two things:\n> \n>  - a new type of multi-entry ref (as you suggested), perhaps in a file\n>    refs/inactive-heads, which is merged with the heads list by lookup\n>    operations only (so merge would see them, but ls-remote would not:\n>    `invisible heads' if you will)\n\nYes, that should work. Make sure that you tell git-fsck-objects and \ngit-prune that those heads are reachable, though.\n\nOf course, if you end up having one \"master\" head (that is the \"merge\" of \nall branches), that would take care of the reachability issue too: you \ndon't actually need to create a _real_ merge, you can just make sure that \nthere is a commit that points to all new heads you create. It could even \nhave a totally dummy tree node, ie you could do\n\n\toldhead=$(git-rev-parse HEAD^0) || exit\n\tnewhead=$(git commit-tree $oldhead -p $oldhead -p new-bug-head < changelog) || exit\n\tgit update-ref HEAD $newhead $oldhead\n\nwhich would just update the commit list with a fake \"merge\" commit merging \n\"new-bug-head\" into the stream of top commits (using the same tree as the \nprevious \"HEAD\" commit had) so that it's always reachable.\n\nSomething like that, anyway. That way you can do a \"git clone\" and you get \nall the bug commits through a single HEAD.\n\n\t\tLinus\n"}]}