{"thread":{"id":"41034","subject":"RefTree: Alternate ref backend","startedAt":"2015-12-17T21:02:50Z","lastAt":"2015-12-24T01:33:00Z","messageCount":18,"participants":["Shawn Pearce","Junio C Hamano","Jeff King","Mike Hommey","Michael Haggerty","Dave Borowitz","Martin Fick"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"274692","messageId":"CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com","threadId":"41034","inReplyTo":null,"subject":"RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-17T21:02:50Z","receivedAt":"2015-12-17T21:02:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I started playing around with the idea of storing references directly\nin Git. Exploiting the GITLINK tree entry, we can associate a name to\nany SHA-1.\n\nBy storing all references in a single tree, atomic transactions are\npossible. Its a simple compare-and-swap of a single 40 byte SHA-1.\nThis of course leads to a bootstrapping problem, where do we store the\n40 byte SHA-1? For this example its just $GIT_DIR/refs/txn/committed\nas a classical loose reference.\n\n\nI posted code for this to JGit (sorry):\n\n https://git.eclipse.org/r/62970\n\n\nConfiguration:\n\n [core]\n repositoryformatversion = 1\n [extensions]\n refsBackendType = RefTree\n\nFor example, recent git.git has a structure like this:\n\n $ git ls-tree -r refs/txn/committed\n 120000 blob 22e42fc826b437033ca444e09368f53a0b169322 ..HEAD\n 160000 commit 1ff88560c8d22bcdb528a6629239d638f927cb96 heads/maint\n 160000 commit f3adf457e046f92f039353762a78dcb3afb2cb13 heads/master\n 160000 commit 5ee9e94ccfede68f0c386c497dd85c017efa22d6 heads/next\n 160000 commit d3835d54cffb16c4362979a5be3ba9958eab4116 heads/pu\n 160000 commit 68a0f56b615b61afdbd86be01a3ca63dca70edc0 heads/todo\n ...\n 160000 commit 17f9f635c101aef03874e1de1d8d0322187494b3 tags/v2.6.0\n 160000 commit 5bebb9057df8287684c763c59c67f25f16884ef6 tags/v2.6.0-rc0\n 160000 commit 16ffa6443e279a9b3b63d7a2bebeb07833506010 tags/v2.6.0-rc0^{}\n 160000 commit bbdca2a7bd942e1d3ce517b48e6229b99f7d7b2b tags/v2.6.0-rc1\n 160000 commit 689efb737a7b46351850eefdfa57d2ce232011fb tags/v2.6.0-rc1^{}\n 160000 commit 7b269a793392ee3d71ecddac88a8ad63497cbc4d tags/v2.6.0-rc2\n 160000 commit 45733fa93f287fbc04d6a6a3f5a39cc852c5cf50 tags/v2.6.0-rc2^{}\n 160000 commit 27df6e2585060add45b32bbd46f6e92ef79d069b tags/v2.6.0-rc3\n 160000 commit 8d530c4d64ffcc853889f7b385f554d53db375ed tags/v2.6.0-rc3^{}\n 160000 commit be08dee9738eaaa0423885ed189c2b6ad8368cf0 tags/v2.6.0^{}\n\nTags are stored twice, to cache the peel information for network advertisements.\n\nPacking the tree by itself is smaller than packed-refs, which is uncompressed:\n\n -rw-r----- 1 shawn me 60K Dec 17 12:43 packed-refs\n -r--r----- 1 shawn me 1.2K Dec 17 12:56 R-5533*.idx\n -r--r----- 1 shawn me 28K Dec 17 12:56 R-5533*.pack\n\n\nBy exploiting Git to store Git, we get a reflog for free:\n\n $ git log -p refs/txn/committed -1\n commit f7ec5ceeba6ca87fa112b3af70d8ac17364045f7\n Author: anonymous \n Date: Thu Dec 17 12:53:39 2015 -0800\n\n push\n\n diff --git a/heads/tmp2 b/heads/tmp2\n deleted file mode 160000\n index f3adf45..0000000\n --- a/heads/tmp2\n +++ /dev/null\n @@ -1 +0,0 @@\n -Subproject commit f3adf457e046f92f039353762a78dcb3afb2cb13\n\n:)\n"},{"id":"274694","messageId":"xmqqk2ocbuw9.fsf@gitster.mtv.corp.google.com","threadId":"41034","inReplyTo":"CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-17T21:57:42Z","receivedAt":"2015-12-17T21:57:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> For example, recent git.git has a structure like this:\n>\n> $ git ls-tree -r refs/txn/committed\n> 120000 blob 22e42fc826b437033ca444e09368f53a0b169322 ..HEAD\n> 160000 commit 1ff88560c8d22bcdb528a6629239d638f927cb96 heads/maint\n> 160000 commit f3adf457e046f92f039353762a78dcb3afb2cb13 heads/master\n> 160000 commit 5ee9e94ccfede68f0c386c497dd85c017efa22d6 heads/next\n> 160000 commit d3835d54cffb16c4362979a5be3ba9958eab4116 heads/pu\n> 160000 commit 68a0f56b615b61afdbd86be01a3ca63dca70edc0 heads/todo\n> ...\n> 160000 commit 17f9f635c101aef03874e1de1d8d0322187494b3 tags/v2.6.0\n> 160000 commit 5bebb9057df8287684c763c59c67f25f16884ef6 tags/v2.6.0-rc0\n> 160000 commit 16ffa6443e279a9b3b63d7a2bebeb07833506010 tags/v2.6.0-rc0^{}\n> ...\n> 160000 commit be08dee9738eaaa0423885ed189c2b6ad8368cf0 tags/v2.6.0^{}\n>\n> Tags are stored twice, to cache the peel information for network advertisements.\n\nThe object 17f9f635 is not a \"commit\" but is a \"tag\". It is\nsomewhat unfortunate that \"ls-tree -r\" reports it as a commit; as\nthe command (or anything that deals with a gitlink) is not allowed\nto look at the actual object, it is the best it could do, though.\n\nThe \"..HEAD\" hack looks somewhat ugly. I can guess that the\nreasoning went like \"if we stored these in the most natural way, we\nalways need a top-level tree that hold two and only two entries,\nHEAD and heads/, which would require us one level of tree unwrapping\nto get to most of the refs\" and \"HEAD is the only oddball that is\noutside refs/ hierarchy, others like MERGE_HEAD are ephemeral and\nfor the purpose of Gerrit that does not even do working tree\nmanagement, those things that are not necessary in order to manage\nonly the committed state can be omitted.\", but still...\n"},{"id":"274695","messageId":"20151217221045.GA8150@sigill.intra.peff.net","threadId":"41034","inReplyTo":"CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-12-17T22:10:45Z","receivedAt":"2015-12-17T22:10:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 17, 2015 at 01:02:50PM -0800, Shawn Pearce wrote:\n\n> I started playing around with the idea of storing references directly\n> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n> any SHA-1.\n\nGitlink entries don't imply reachability, though. I guess that doesn't\nmatter if your ref backend says \"no, really, these are the ref tips, and\nthey are reachable\". But you could not push the whole thing up to\nanother server and expect it to hold the whole graph.\n\nWhich is not strictly necessary, but to me seems like the real advantage\nof using git objects versus some other system.\n\nOf course, the lack of reachability has advantages, too. You can\ndrop commits pointed to by old reflogs without rewriting the ref\nhistory. Unfortunately you cannot expunge the reflogs at all. That's\ngood if you like audit trails. Bad if you are worried that your reflogs\nwill grow large. :)\n\n> By storing all references in a single tree, atomic transactions are\n> possible. Its a simple compare-and-swap of a single 40 byte SHA-1.\n> This of course leads to a bootstrapping problem, where do we store the\n> 40 byte SHA-1? For this example its just $GIT_DIR/refs/txn/committed\n> as a classical loose reference.\n\nSomehow putting it inside `refs/` seems weird to me, in an infinite\nrecursion kind of way. I would have picked $GIT_DIR/REFSTREE or\nsomething. But that is a minor point.\n\n> Configuration:\n> \n> [core]\n> repositoryformatversion = 1\n> [extensions]\n> refsBackendType = RefTree\n\nThe semantics of extensions config keys are open-ended. The\nformatVersion=1 spec only says \"if there is a key you don't know about,\nthen you may not proceed\". Now we're defining a refsBackendType\nextension. It probably makes sense to write up a few rules (e.g., is\nRefTree case-sensitive?).\n\n-Peff\n"},{"id":"274698","messageId":"CAJo=hJvwwOooPG2XUbhLZqyDMwsOa1Ba7eoA1AFLkF3BHk5V8Q@mail.gmail.com","threadId":"41034","inReplyTo":"xmqqk2ocbuw9.fsf@gitster.mtv.corp.google.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-17T22:15:41Z","receivedAt":"2015-12-17T22:15:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Dec 17, 2015 at 1:57 PM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> For example, recent git.git has a structure like this:\n>>\n>> $ git ls-tree -r refs/txn/committed\n>> 120000 blob 22e42fc826b437033ca444e09368f53a0b169322 ..HEAD\n>> 160000 commit 1ff88560c8d22bcdb528a6629239d638f927cb96 heads/maint\n>> 160000 commit f3adf457e046f92f039353762a78dcb3afb2cb13 heads/master\n>> 160000 commit 5ee9e94ccfede68f0c386c497dd85c017efa22d6 heads/next\n>> 160000 commit d3835d54cffb16c4362979a5be3ba9958eab4116 heads/pu\n>> 160000 commit 68a0f56b615b61afdbd86be01a3ca63dca70edc0 heads/todo\n>> ...\n>> 160000 commit 17f9f635c101aef03874e1de1d8d0322187494b3 tags/v2.6.0\n>> 160000 commit 5bebb9057df8287684c763c59c67f25f16884ef6 tags/v2.6.0-rc0\n>> 160000 commit 16ffa6443e279a9b3b63d7a2bebeb07833506010 tags/v2.6.0-rc0^{}\n>> ...\n>> 160000 commit be08dee9738eaaa0423885ed189c2b6ad8368cf0 tags/v2.6.0^{}\n>>\n>> Tags are stored twice, to cache the peel information for network advertisements.\n>\n> The object 17f9f635 is not a \"commit\" but is a \"tag\". It is\n> somewhat unfortunate that \"ls-tree -r\" reports it as a commit; as\n> the command (or anything that deals with a gitlink) is not allowed\n> to look at the actual object, it is the best it could do, though.\n\nYes; thus far GITLINK is only used for commits in submodules so its\nreasonable for it to just hardcode the text \"commit\".\n\n> The \"..HEAD\" hack looks somewhat ugly. I can guess that the\n> reasoning went like \"if we stored these in the most natural way, we\n> always need a top-level tree that hold two and only two entries,\n> HEAD and heads/, which would require us one level of tree unwrapping\n> to get to most of the refs\" and \"HEAD is the only oddball that is\n> outside refs/ hierarchy,\n\nCorrect.\n\n> others like MERGE_HEAD are ephemeral and\n> for the purpose of Gerrit that does not even do working tree\n> management, those things that are not necessary in order to manage\n> only the committed state can be omitted.\", but still...\n\nYes. I was mostly looking at this from a bare repository server\nperspective, not a user working tree. On a bare repository you\nprobably don't have those special refs like MERGE_HEAD, FETCH_HEAD,\netc.\n\nThey could be stored as \"..MERGE_HEAD\", if you had to. But only HEAD\nreally matters to hint to clients what to checkout by default on\nclone.\n"},{"id":"274699","messageId":"CAJo=hJsSgU6yOFZMac85jkOtw9TXWXh0Ext4-Gb1TsSXqROn4g@mail.gmail.com","threadId":"41034","inReplyTo":"20151217221045.GA8150@sigill.intra.peff.net","subject":"Re: RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-17T22:28:01Z","receivedAt":"2015-12-17T22:28:01Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Dec 17, 2015 at 2:10 PM, Jeff King wrote:\n> On Thu, Dec 17, 2015 at 01:02:50PM -0800, Shawn Pearce wrote:\n>\n>> I started playing around with the idea of storing references directly\n>> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n>> any SHA-1.\n>\n> Gitlink entries don't imply reachability, though. I guess that doesn't\n> matter if your ref backend says \"no, really, these are the ref tips, and\n> they are reachable\".\n\nExactly. This works with existing JGit because it swaps out the ref\nbackend. When GC tries to enumerate the roots (current refs), it gets\nthese through the ref backend by scanning the tree recursively. The\npacker itself doesn't care where those roots came from.\n\nSame would be true for any other pluggable ref backend in git-core. GC\nhas to ask the ref backend, and then trust its reply. How/where that\nref backend tracks that is an implementation detail.\n\n> But you could not push the whole thing up to\n> another server and expect it to hold the whole graph.\n\nCorrect, pushing this to another repository doesn't transmit the\ngraph. If the other repository also used this for its refs backend,\nits now corrupt and confused out of its mind. Just like copying the\npacked-refs file with scp. Don't do that. :)\n\n> Which is not strictly necessary, but to me seems like the real advantage\n> of using git objects versus some other system.\n\nOne advantage is you can edit HEAD symref remotely. Commit a different\nsymlink value and push. :)\n\nI want to say more, but I'm going to hold back right now. There's more\ngoing on in my head than just this.\n\n> Of course, the lack of reachability has advantages, too. You can\n> drop commits pointed to by old reflogs without rewriting the ref\n> history.\n\nYes.\n\n> Unfortunately you cannot expunge the reflogs at all. That's\n> good if you like audit trails. Bad if you are worried that your reflogs\n> will grow large. :)\n\nAt present our servers do not truncate their reflogs. Yes some are... big.\n\nI considered truncating this graph by just using a shallow marker. Add\na shallow entry and repack. The ancient history will eventually be\ngarbage collected and disappear.\n\nOne advantage of this format is deleted branches can retain a reflog\npost deletion. Another is you can trivially copy the reflog using\nnative Git to another system for backup purposes. Or fetch it over the\nnetwork to inspect locally. So a shared group server could be\nexporting its reflog, you can fetch it and review locally what\nhappened to branches without logging into the shared server.\n\nSo long as you remember that copying the reflog doesn't mean you\nactually copied the commit histories, its works nicely.\n\nAnother advantage of this format over LMDB or TDB or whatever is Git\nalready understands it. The tools already understand it. Plumbing can\ninspect and repair things. You can reflog the reflog using traditional\nreflog ($GIT_DIR/reflogs/refs/txn/committed).\n\n>> By storing all references in a single tree, atomic transactions are\n>> possible. Its a simple compare-and-swap of a single 40 byte SHA-1.\n>> This of course leads to a bootstrapping problem, where do we store the\n>> 40 byte SHA-1? For this example its just $GIT_DIR/refs/txn/committed\n>> as a classical loose reference.\n>\n> Somehow putting it inside `refs/` seems weird to me, in an infinite\n> recursion kind of way. I would have picked $GIT_DIR/REFSTREE or\n> something. But that is a minor point.\n\nI had started with $GIT_DIR/REFS, but see above. I have more going on\nin my head. This is only a tiny building block.\n\n>> Configuration:\n>>\n>> [core]\n>> repositoryformatversion = 1\n>> [extensions]\n>> refsBackendType = RefTree\n>\n> The semantics of extensions config keys are open-ended. The\n> formatVersion=1 spec only says \"if there is a key you don't know about,\n> then you may not proceed\". Now we're defining a refsBackendType\n> extension. It probably makes sense to write up a few rules (e.g., is\n> RefTree case-sensitive?).\n\nIn my prototype in JGIt I parse it as case insensitive, but used\nCamelCase because the JavaClassNameIsNamedThatWayBecauseJava.\n"},{"id":"274707","messageId":"20151218013603.GA13717@glandium.org","threadId":"41034","inReplyTo":"CAJo=hJsSgU6yOFZMac85jkOtw9TXWXh0Ext4-Gb1TsSXqROn4g@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-12-18T01:36:03Z","receivedAt":"2015-12-18T01:36:03Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Thu, Dec 17, 2015 at 02:28:01PM -0800, Shawn Pearce wrote:\n> On Thu, Dec 17, 2015 at 2:10 PM, Jeff King wrote:\n> > On Thu, Dec 17, 2015 at 01:02:50PM -0800, Shawn Pearce wrote:\n> >\n> >> I started playing around with the idea of storing references directly\n> >> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n> >> any SHA-1.\n> >\n> > Gitlink entries don't imply reachability, though. I guess that doesn't\n> > matter if your ref backend says \"no, really, these are the ref tips, and\n> > they are reachable\".\n> \n> Exactly. This works with existing JGit because it swaps out the ref\n> backend. When GC tries to enumerate the roots (current refs), it gets\n> these through the ref backend by scanning the tree recursively. The\n> packer itself doesn't care where those roots came from.\n> \n> Same would be true for any other pluggable ref backend in git-core. GC\n> has to ask the ref backend, and then trust its reply. How/where that\n> ref backend tracks that is an implementation detail.\n> \n> > But you could not push the whole thing up to\n> > another server and expect it to hold the whole graph.\n> \n> Correct, pushing this to another repository doesn't transmit the\n> graph. If the other repository also used this for its refs backend,\n> its now corrupt and confused out of its mind. Just like copying the\n> packed-refs file with scp. Don't do that. :)\n> \n> > Which is not strictly necessary, but to me seems like the real advantage\n> > of using git objects versus some other system.\n> \n> One advantage is you can edit HEAD symref remotely. Commit a different\n> symlink value and push. :)\n> \n> I want to say more, but I'm going to hold back right now. There's more\n> going on in my head than just this.\n> \n> > Of course, the lack of reachability has advantages, too. You can\n> > drop commits pointed to by old reflogs without rewriting the ref\n> > history.\n> \n> Yes.\n\nRelated thread: \"Allowing weak references to blobs and strong references\nto commits\" http://marc.info/?l=git&m=142779648816577&w=2\n\nMike\n"},{"id":"274888","messageId":"56796F37.1000600@alum.mit.edu","threadId":"41034","inReplyTo":"CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-12-22T15:41:43Z","receivedAt":"2015-12-22T15:41:43Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/17/2015 10:02 PM, Shawn Pearce wrote:\n> I started playing around with the idea of storing references directly\n> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n> any SHA-1.\n> \n> By storing all references in a single tree, atomic transactions are\n> possible. Its a simple compare-and-swap of a single 40 byte SHA-1.\n> This of course leads to a bootstrapping problem, where do we store the\n> 40 byte SHA-1? For this example its just $GIT_DIR/refs/txn/committed\n> as a classical loose reference.\n\nI like this general idea a lot, even while recognizing some practical\nproblems that other people have pointed out. I especially like the idea\nof having truly atomic multi-reference updates.\n\nI'm curious why you decided to store all of the references in a single\nlist, similar to the packed-refs file. This design means that the whole\nobject has to be rewritten whenever any reference is updated [1].\nCertainly, storing the references in a single tree *object* is not a\nrequirement for having atomic transitions.\n\nI would have expected a design where the layout of the references in\ntrees mimics the layout of loose references in the filesystem; e.g., one\ntree object for \"refs/\", one for \"refs/heads/\" one for \"refs/remotes/\"\netc. This design would reduce the amount of rewriting that is needed\nwhen one or a few references are updated.\n\nAnother reason that I find a hierarchical layout intriguing would be\nthat one could imagine using the SHA-1s of reference namespace subtrees\nto speed up the negotiation phase of \"git fetch\". In the common case\nthat I use the local namespace \"refs/remotes/origin\" to track an\nupstream repo, the SHA-1 of my \"refs/remotes/origin\" tree would usually\nrepresent a complete description of the state of the upstream references\nat the time that I last fetched. My client could tell the server\n\n have-tree $SHA1\n\n, where $SHA1 is the hash of the tree representing\n\"refs/remotes/origin/\". If the server keeps a reflog as you have\ndescribed (but hierarchically), then the server could look up $SHA1 and\nimmediately know the full set of references, and therefore of objects,\nthat I fetched last time. More generally, the negotiation could proceed\ndown the reference namespace tree and stop whenever commonality is found.\n\nThere are a lot of \"if\"s in that last paragraph, and maybe it's not\nworkable. For example, if I'm not pruning on fetch, then my reference\ntree won't be identical to one that was ever present on the server and\nthis technique wouldn't necessarily help. But if, for example, we change\nthe default to pruning, or perhaps record some extra reftree SHA-1's,\nthen in most cases I would expect that this trick could reduce the\neffort of negotiation to negligible in most cases, and reduce the time\nof the whole fetch to negligible in the case that the clone is already\nup-to-date.\n\nMichael\n\n[1] At GitHub, we store public repositories in networks with a shared\nobject store. The central repository in each network can have 10M+\nreferences. So for us, rewriting that many references for every\nreference update would be unworkable.\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"274891","messageId":"CAJo=hJtPSxY1YZgEt1AA_ukgY9cTA=1tdv_F+nCetv_Ux9E=3g@mail.gmail.com","threadId":"41034","inReplyTo":"56796F37.1000600@alum.mit.edu","subject":"Re: RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-22T16:11:30Z","receivedAt":"2015-12-22T16:11:30Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Dec 22, 2015 at 7:41 AM, Michael Haggerty wrote:\n> On 12/17/2015 10:02 PM, Shawn Pearce wrote:\n>> I started playing around with the idea of storing references directly\n>> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n>> any SHA-1.\n>>\n>> By storing all references in a single tree, atomic transactions are\n>> possible. Its a simple compare-and-swap of a single 40 byte SHA-1.\n>> This of course leads to a bootstrapping problem, where do we store the\n>> 40 byte SHA-1? For this example its just $GIT_DIR/refs/txn/committed\n>> as a classical loose reference.\n>\n> I like this general idea a lot, even while recognizing some practical\n> problems that other people have pointed out. I especially like the idea\n> of having truly atomic multi-reference updates.\n>\n> I'm curious why you decided to store all of the references in a single\n> list, similar to the packed-refs file. This design means that the whole\n> object has to be rewritten whenever any reference is updated [1].\n> Certainly, storing the references in a single tree *object* is not a\n> requirement for having atomic transitions.\n>\n> I would have expected a design where the layout of the references in\n> trees mimics the layout of loose references in the filesystem; e.g., one\n> tree object for \"refs/\", one for \"refs/heads/\" one for \"refs/remotes/\"\n> etc. This design would reduce the amount of rewriting that is needed\n> when one or a few references are updated.\n\nI did use tree objects for each directory component. The ls-tree I\nshowed was an ls-tree -r.\n\n\"heads\" is a different subtree from \"tags\". I just skipped over the\n\"refs/\" top level subtree because its useless here. The root tree\nwould always have one child, \"refs\", which normally has two children,\n\"heads\" and \"tags\". Why bother with the root at that point?\n\nSo we do get minimum rewriting, tags tree is unmodified and reuses its\ntree node when you update master.\n\n> Another reason that I find a hierarchical layout intriguing would be\n> that one could imagine using the SHA-1s of reference namespace subtrees\n> to speed up the negotiation phase of \"git fetch\". In the common case\n> that I use the local namespace \"refs/remotes/origin\" to track an\n> upstream repo, the SHA-1 of my \"refs/remotes/origin\" tree would usually\n> represent a complete description of the state of the upstream references\n> at the time that I last fetched. My client could tell the server\n>\n> have-tree $SHA1\n>\n> , where $SHA1 is the hash of the tree representing\n> \"refs/remotes/origin/\". If the server keeps a reflog as you have\n> described (but hierarchically), then the server could look up $SHA1 and\n> immediately know the full set of references, and therefore of objects,\n> that I fetched last time. More generally, the negotiation could proceed\n> down the reference namespace tree and stop whenever commonality is found.\n\nYes. Martin Fick and I were discussing a strategy like this at the\nGerrit User Summit in November. I totally forgot about it when I\nstarted this thread, but I'm glad you independently proposed it. Maybe\nits not a horrible idea! :)\n\nOne problem is clients don't mirror the heads tree exactly; they add\nin HEAD as a symbolic reference in a way that the remote peer doesn't\nhave. Minor detail.\n\n\nMartin and I were really thinking about server-server negotiation more\nthan client-server. Consider a master Git server that Linus pushes\ntoo, and then a small farm of mirror servers that users actually clone\nfrom. If an update hook on the master does a git push to each mirror,\nthe ls-remote advertisements is a non-trivial amount of data to\nexchange. If the mirror servers are supposed to exactly match the\nmaster, they can exchange all of their refs with a single SHA-1\ninstead of a big listing.\n\nThis isn't so important for Linus' repository; its got a relatively\nsmall number of refs. We were thinking more about Gerrit Code Review\nwhere the refs/changes/ namespace is huge and may be causing a\nmulti-megabyte advertisement. Its common in large companies to have\nmany mirror slaves in remote offices mirroring the Gerrit server so\nthat end-users can fetch from their office mirror more quickly.\n\n> There are a lot of \"if\"s in that last paragraph, and maybe it's not\n> workable. For example, if I'm not pruning on fetch, then my reference\n> tree won't be identical to one that was ever present on the server and\n> this technique wouldn't necessarily help. But if, for example, we change\n> the default to pruning, or perhaps record some extra reftree SHA-1's,\n> then in most cases I would expect that this trick could reduce the\n> effort of negotiation to negligible in most cases, and reduce the time\n> of the whole fetch to negligible in the case that the clone is already\n> up-to-date.\n\nRight, maybe the client just remember's the server's reftree SHA-1 and\noffers it back on reconnection. The server can then diff between the\ntwo reftrees and shows the client only refs that were modified that\nthe client cares about.\n\n\n> [1] At GitHub, we store public repositories in networks with a shared\n> object store. The central repository in each network can have 10M+\n> references. So for us, rewriting that many references for every\n> reference update would be unworkable.\n\nYup, and Gerrit Code Review servers often have 100k+ refs per\nrepository. We can't rewrite the entire store every time either. So\nits not a flat list. Its a directory structure using the / separators\nin the ref namespace.\n\nFWIW, JGit is able to scan the canonical trees out of a pack file and\ninflate them in approximately the same time it takes to scan the\npacked-refs file for some 70k references. So we don't really slow down\nmuch to use this. And there's huge gains to be had by taking advantage\nof the tree structure and only inflating the components you need to\nanswer a particular read.\n"},{"id":"274895","messageId":"CAD0k6qT21siw00XMM6fSz2d9dT1yiTMh5ai9_w=fFk9GKin83w@mail.gmail.com","threadId":"41034","inReplyTo":"CAJo=hJtPSxY1YZgEt1AA_ukgY9cTA=1tdv_F+nCetv_Ux9E=3g@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Dave Borowitz","fromEmail":"dborowitz@google.com","sentAt":"2015-12-22T17:04:12Z","receivedAt":"2015-12-22T17:04:12Z","isPatch":false,"sender":{"key":"dborowitz@google.com","avatar":"https://avatars.githubusercontent.com/u/194927?v=4"},"body":"On Tue, Dec 22, 2015 at 8:11 AM, Shawn Pearce wrote:\n> Yup, and Gerrit Code Review servers often have 100k+ refs per\n> repository. We can't rewrite the entire store every time either. So\n> its not a flat list. Its a directory structure using the / separators\n> in the ref namespace.\n\nI wonder if this might be insufficient in some cases, and additional\nsharding might be required (though I haven't thought about how to do\nthat).\n\nChromium, for example, has upwards of 10k tags:\n$ git ls-remote https://chromium.googlesource.com/chromium/src\nrefs/tags/\\* | wc -l\n8733\n\nAnd I doubt it's unique in this regard.\n"},{"id":"274897","messageId":"567985A8.2020301@alum.mit.edu","threadId":"41034","inReplyTo":"CAJo=hJtPSxY1YZgEt1AA_ukgY9cTA=1tdv_F+nCetv_Ux9E=3g@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-12-22T17:17:28Z","receivedAt":"2015-12-22T17:17:28Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/22/2015 05:11 PM, Shawn Pearce wrote:\n> On Tue, Dec 22, 2015 at 7:41 AM, Michael Haggerty wrote:\n>> On 12/17/2015 10:02 PM, Shawn Pearce wrote:\n>>> I started playing around with the idea of storing references directly\n>>> in Git. Exploiting the GITLINK tree entry, we can associate a name to\n>>> any SHA-1.\n>> [...]\n>> I'm curious why you decided to store all of the references in a single\n>> list, similar to the packed-refs file. [...]\n> \n> I did use tree objects for each directory component. The ls-tree I\n> showed was an ls-tree -r.\n\nSilly me. Of course that was clear from your post, and I just overlooked it.\n\n>> Another reason that I find a hierarchical layout intriguing would be\n>> that one could imagine using the SHA-1s of reference namespace subtrees\n>> to speed up the negotiation phase of \"git fetch\". [...]\n> \n> Yes. Martin Fick and I were discussing a strategy like this at the\n> Gerrit User Summit in November. I totally forgot about it when I\n> started this thread, but I'm glad you independently proposed it. Maybe\n> its not a horrible idea! :)\n> \n> One problem is clients don't mirror the heads tree exactly; they add\n> in HEAD as a symbolic reference in a way that the remote peer doesn't\n> have. Minor detail.\n\nYes, and this is a side effect of leaving out a layer of the remote\nreference namespace in the local refs/remotes layout. Naively one would\nexpect\n\n refs/remotes/origin/HEAD\n refs/remotes/origin/refs/heads/master\n\netc. But we store branches into the main \"refs/remotes/origin/\"\nnamespace, leaving no reserved space for the remote \"HEAD\" (not to\nmention other namespaces that might appear on the remote, such as\n\"refs/changes/*\", \"refs/pull/*\", a separate record of the remote's\n\"refs/tags/*\", etc).\n\nMaybe that is why my gut reaction to your proposal to elide the \"refs\"\npart of the reference hierarchy and store \"HEAD\" as (effectively)\n\"refs/..HEAD\" was negative, even though I can't think of any practical\nobjections.\n\nAt a deeper level, the \"refs/\" part of reference names is actually\npretty useless in general. I suppose it originated in the practice of\nstoring loose references under \"refs/\" to keep them separate from other\nmetadata in $GIT_DIR. But really, aside from slightly helping\ndisambiguate references from paths in the command line, what is it good\nfor? Would we really be worse off if references' full names were\n\n HEAD\n heads/master\n tags/v1.0.0\n remotes/origin/master (or remotes/origin/heads/master)\n\netc? This notation is already recognized in most places (though not in\n\"update-ref\"). I think your decision to elide \"refs/\" in the reftree\nhierarchy is a reflection of its uselessness. In any case, your decision\nis much less questionable than the decision to mash \"refs/heads/*\" all\nthe way up to the top level like we do in \"refs/remotes/\".\n\n> Martin and I were really thinking about server-server negotiation more\n> than client-server. [...]\n\nYes, that's also an interesting application.\n\n>> There are a lot of \"if\"s in that last paragraph, and maybe it's not\n>> workable. For example, if I'm not pruning on fetch, then my reference\n>> tree won't be identical to one that was ever present on the server and\n>> this technique wouldn't necessarily help. But if, for example, we change\n>> the default to pruning, or perhaps record some extra reftree SHA-1's,\n>> then in most cases I would expect that this trick could reduce the\n>> effort of negotiation to negligible in most cases, and reduce the time\n>> of the whole fetch to negligible in the case that the clone is already\n>> up-to-date.\n> \n> Right, maybe the client just remember's the server's reftree SHA-1 and\n> offers it back on reconnection. The server can then diff between the\n> two reftrees and shows the client only refs that were modified that\n> the client cares about.\n\nThe client not only has to remember the server's reftree, but also must\nverify that it still has all of the objects implied by that reftree, in\ncase a reference somehow got deleted under \"refs/remotes/origin/*\". At\nthat point, there is no special reason to use a SHA-1 in the\nnegotiation; any unique token generated by the server would suffice if\nthe server can connect it back to a set of references that was sent to\nthe client in the past.\n\nThe advantage of using hierarchical reftree SHA-1s in the negotiation is\nthat they can be used to name part of the reftree. For example, if I\nfetch \"refs/heads/*\" from a remote but not \"refs/changes/*\", then what\ndo I report as my \"have-tree\"? I can't claim to have *all* of the\nreferences that the remote had at the time. But with SHA-1s I can say\nthat I have the reftree that corresponds to my\n\"refs/remotes/origin/heads/\", which the remote can notice is identical\nto an old reftree that it happened to have for \"refs/heads/\" (without\neven caring what path it represented). Bingo, we've just agreed about a\nbig part of the reference namespace without having to agree about the\nwhole namespace.\n\nIn practice, in my first \"haves\" announcement I would probably list a\nfew \"famous\" namespaces in the hope that one or more of them are\nrecognized by the server:\n\n have-tree \n have-tree \n have-tree \n have-tree \n have-tree \n\n> [...]\n> FWIW, JGit is able to scan the canonical trees out of a pack file and\n> inflate them in approximately the same time it takes to scan the\n> packed-refs file for some 70k references. So we don't really slow down\n> much to use this. And there's huge gains to be had by taking advantage\n> of the tree structure and only inflating the components you need to\n> answer a particular read.\n\nYes, that's another nice aspect of the design.\n\nI do worry a bit that the hierarchical storage only helps if people\nshard their reference namespace reasonably. Somebody who stores 100k\nreferences in a single reference \"directory\" (imagine a\n\"refs/ci-tests/*\") is going to suffer from expensive reference update\nperformance. But I guess they will suffer from poor performance within\nGit as well, and that will probably encourage them to improve their\npractices :-) I suppose this is not really much different than people\nwho store 100k files within a single directory of their working tree.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"274906","messageId":"CAJo=hJtgfpZn0OjbQ=BVoO_=03yG0Czjfn9vX4RobWLYpNVENg@mail.gmail.com","threadId":"41034","inReplyTo":"567985A8.2020301@alum.mit.edu","subject":"Re: RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-22T18:50:27Z","receivedAt":"2015-12-22T18:50:27Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Dec 22, 2015 at 9:17 AM, Michael Haggerty wrote:\n>\n> etc. But we store branches into the main \"refs/remotes/origin/\"\n> namespace, leaving no reserved space for the remote \"HEAD\" (not to\n> mention other namespaces that might appear on the remote, such as\n> \"refs/changes/*\", \"refs/pull/*\", a separate record of the remote's\n> \"refs/tags/*\", etc).\n>\n> Maybe that is why my gut reaction to your proposal to elide the \"refs\"\n> part of the reference hierarchy and store \"HEAD\" as (effectively)\n> \"refs/..HEAD\" was negative, even though I can't think of any practical\n> objections.\n\nGood point; if the client's refs/remotes/origin/ namespace more\nclosely mirrored the remote's own namespace\n(refs/remotes/origin/heads/master), this seems a lot less fishy. The\nmapping certainly makes a bit more sense. Etc.\n\nIts a user visible shift however; what was origin/master is now\norigin/heads/master. Which is part of the reason why the mapping works\nthe way it does today. We hardly ever call a branch here heads/master,\nwe just call it master. So we call origin's master, origin/master. :)\n\n> At a deeper level, the \"refs/\" part of reference names is actually\n> pretty useless in general. I suppose it originated in the practice of\n> storing loose references under \"refs/\" to keep them separate from other\n> metadata in $GIT_DIR.\n\nCorrect. In the beginning you used echo $sha1 >.git/HEAD and it was good.\n\nLater more refs came along and they had to go somewhere, and so\n.git/refs was born with .git/refs/heads/master. Existing tools that\nknew how to write to .git/HEAD given the name HEAD could magically\nwork with refs/heads/master too, and it was good. But that was an\nawefully long name to type, so shorthand of \"master\" for maybe\nrefs/heads/master or maybe refs/tags/master or maybe no prefix at all\n(hi HEAD) came along. Basically its the origin story of Git. :)\n\n> But really, aside from slightly helping\n> disambiguate references from paths in the command line, what is it good\n> for?\n\nNothing really; today refs/ prefix is used to encourage to the tools\nthat you really meant refs/heads/master and not\nrefs/heads/heads/master or some other crazy construct. You can thank\nthe DWIMery inside the ref rev parse logic for needing this.\n\n> The client not only has to remember the server's reftree, but also must\n> verify that it still has all of the objects implied by that reftree, in\n> case a reference somehow got deleted under \"refs/remotes/origin/*\". At\n> that point, there is no special reason to use a SHA-1 in the\n> negotiation; any unique token generated by the server would suffice if\n> the server can connect it back to a set of references that was sent to\n> the client in the past.\n\nTrue, but its a nicer implementation if the token exchanged has simple\nmeaning to the server. And its just a diff-tree at the server to\ncompute the modifications the client might need to learn about.\n\nI see your point about the client being able to use that to say \"If I\nnot only have this, I also have all of the objects\". It vastly\nsimplifies the client's negotiation with the server. The client is\nnegotiating the common ancestor of the reftree and that immediately\ngets the main graph ancestor negotiation system very close to a good\nset. The client may still be usefully ahead on other branches, e.g.\nshe has pulled from the upstream and is now pulling from a\nlieutenant's tree, who also recently pulled from the upstream.\n\n> In practice, in my first \"haves\" announcement I would probably list a\n> few \"famous\" namespaces in the hope that one or more of them are\n> recognized by the server:\n>\n> have-tree \n> have-tree \n> have-tree \n> have-tree \n> have-tree \n\nYes, but we also have to be careful about how long we get the \"famous\"\nlist get. :)\n\n>> [...]\n>> FWIW, JGit is able to scan the canonical trees out of a pack file and\n>> inflate them in approximately the same time it takes to scan the\n>> packed-refs file for some 70k references. So we don't really slow down\n>> much to use this. And there's huge gains to be had by taking advantage\n>> of the tree structure and only inflating the components you need to\n>> answer a particular read.\n>\n> Yes, that's another nice aspect of the design.\n>\n> I do worry a bit that the hierarchical storage only helps if people\n> shard their reference namespace reasonably. Somebody who stores 100k\n> references in a single reference \"directory\" (imagine a\n> \"refs/ci-tests/*\") is going to suffer from expensive reference update\n> performance. But I guess they will suffer from poor performance within\n> Git as well, and that will probably encourage them to improve their\n> practices :-) I suppose this is not really much different than people\n> who store 100k files within a single directory of their working tree.\n\nYup. Gerrit Code Review shards refs/changes/ across 100 directories\nfor this reason as local filesystems don't like large numbers of files\nor directories in a directory. But at 100k change entries you are\nstill dealing with 10k subtrees in each shard. The 100-sharding isn't\nquite enough.\n\nI started considering doing a notemap like sharding for reftree. Its\nharder because the names aren't a uniform shape the way object ids are\nin a notemap. But it could be possible to split by prefix, for example\nstart by building a table of all 2 character prefixes in the tree. If\nthis produces too many entries in any single 2 character subtree,\nretry as a 4 character subtree. Continue extending the prefix until\neither the number of unique prefixes in the parent tree is too many,\nor the subtrees are acceptable sizes. If the parent gets to be too\nmany (1000?), freeze the parent prefix length and start splitting the\nsubtrees instead.\n\nFor tags you may wind up with a structure like:\n\n tags/\n v1../\n .0\n .2\n v2../\n .0\n 0.125\n v3../\n 0.98\n\nOr whatever. Here I used \"..\" as a suffix on the splits like \"v1..\" to\nindicate the name isn't itself a directory component, but a sharding\nsplit. Thus we have tags \"v1.0\", \"v2.0\", \"v20.125\", \"v30.98\", etc.\n\nIt doesn't help the scalability of a source code tree having too many\nfiles. But we could do some smarter splitting inside reftree to help\nit scale even if people aren't sharding their ref namespaces. Sadly\nthis has a lot of downsides, its complex to write and its ugly.\n"},{"id":"274908","messageId":"xmqq1taee1w9.fsf@gitster.mtv.corp.google.com","threadId":"41034","inReplyTo":"CAJo=hJtgfpZn0OjbQ=BVoO_=03yG0Czjfn9vX4RobWLYpNVENg@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-22T19:09:26Z","receivedAt":"2015-12-22T19:09:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n>> But really, aside from slightly helping\n>> disambiguate references from paths in the command line, what is it good\n>> for?\n>\n> Nothing really; today refs/ prefix is used to encourage to the tools\n> that you really meant refs/heads/master and not\n> refs/heads/heads/master or some other crazy construct. You can thank\n> the DWIMery inside the ref rev parse logic for needing this.\n\nAren't you two forgetting one minor thing, though?\n\nA layout without refs/, i.e. $GIT_DIR/{heads,tags,...}, will force\nus to keep track of where the tips of histories are anchored for\nreachability purposes, every time you would add a new hierarchy\n(e.g. $GIT_DIR/changes)--and those unfortunate souls who run a\nslightly older version of Git that is unaware of 'changes' hierarchy\nwould weep after running \"git gc\", no?\n"},{"id":"274909","messageId":"CAJo=hJswuPdLT0KtGdf_=UGxD7-5NjGk2mwFjRU=uYb-Su-y+A@mail.gmail.com","threadId":"41034","inReplyTo":"xmqq1taee1w9.fsf@gitster.mtv.corp.google.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-12-22T19:11:06Z","receivedAt":"2015-12-22T19:11:06Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Dec 22, 2015 at 11:09 AM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>>> But really, aside from slightly helping\n>>> disambiguate references from paths in the command line, what is it good\n>>> for?\n>>\n>> Nothing really; today refs/ prefix is used to encourage to the tools\n>> that you really meant refs/heads/master and not\n>> refs/heads/heads/master or some other crazy construct. You can thank\n>> the DWIMery inside the ref rev parse logic for needing this.\n>\n> Aren't you two forgetting one minor thing, though?\n>\n> A layout without refs/, i.e. $GIT_DIR/{heads,tags,...}, will force\n> us to keep track of where the tips of histories are anchored for\n> reachability purposes, every time you would add a new hierarchy\n> (e.g. $GIT_DIR/changes)--and those unfortunate souls who run a\n> slightly older version of Git that is unaware of 'changes' hierarchy\n> would weep after running \"git gc\", no?\n\nYou still store them under refs/\n\nAll of the code that is handed a ref name knows its a ref name and not\na sha-1 object name in the objects directory.\n\nThe catch is a few things accept HEAD, MERGE_HEAD, FETCH_HEAD, etc.\nThose have to be handled even though they aren't in the refs/\ndirectory.\n"},{"id":"274911","messageId":"xmqqsi2ucm60.fsf@gitster.mtv.corp.google.com","threadId":"41034","inReplyTo":"CAJo=hJswuPdLT0KtGdf_=UGxD7-5NjGk2mwFjRU=uYb-Su-y+A@mail.gmail.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-22T19:34:31Z","receivedAt":"2015-12-22T19:34:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> On Tue, Dec 22, 2015 at 11:09 AM, Junio C Hamano wrote:\n>> Shawn Pearce writes:\n>>\n>>>> But really, aside from slightly helping\n>>>> disambiguate references from paths in the command line, what is it good\n>>>> for?\n>>>\n>>> Nothing really; today refs/ prefix is used to encourage to the tools\n>>> that you really meant refs/heads/master and not\n>>> refs/heads/heads/master or some other crazy construct. You can thank\n>>> the DWIMery inside the ref rev parse logic for needing this.\n>>\n>> Aren't you two forgetting one minor thing, though?\n>>\n>> A layout without refs/, i.e. $GIT_DIR/{heads,tags,...}, will force\n>> us to keep track of where the tips of histories are anchored for\n>> reachability purposes, every time you would add a new hierarchy\n>> (e.g. $GIT_DIR/changes)--and those unfortunate souls who run a\n>> slightly older version of Git that is unaware of 'changes' hierarchy\n>> would weep after running \"git gc\", no?\n>\n> You still store them under refs/\n\nWell I know; the comment was merely a reaction to the exchange\nbetween you two, \"What is refs/ good for?\", \"Nothing really\".\n\nYou'd benefit by having \"refs/\" that is known to contain all the\nanchoring points for reachability without knowing what subhierarchy\nit may contain in the future, that is what it is good for.\n"},{"id":"274915","messageId":"6263203.WlZuyGWxlh@mfick1-lnx","threadId":"41034","inReplyTo":"4689734.cEcQ2vR0aQ@mfick1-lnx","subject":"Re: RefTree: Alternate ref backend","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2015-12-22T20:56:50Z","receivedAt":"2015-12-22T20:56:50Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, December 22, 2015 06:17:28 PM you wrote:\n> On Tue, Dec 22, 2015 at 7:41 AM, Michael Haggerty\n wrote:\n>\n> At a deeper level, the \"refs/\" part of reference names is\n> actually pretty useless in general. I suppose it\n> originated in the practice of storing loose references\n> under \"refs/\" to keep them separate from other metadata\n> in $GIT_DIR. But really, aside from slightly helping\n> disambiguate references from paths in the command line,\n> what is it good for? Would we really be worse off if\n> references' full names were\n>\n> HEAD\n> heads/master\n> tags/v1.0.0\n> remotes/origin/master (or remotes/origin/heads/master)\n\nI think this is a bit off, because\n\n HEAD != refs/HEAD\n\nso not quite useless.\n\nBut, I agree that the whole refs notation has always bugged\nme, it is quirky. It makes it hard to disambiguate when\nsomething is meant to be absolute or not. What if we added\na leading slash for absolute references? Then I could do\nsomething like:\n\n/HEAD\n/refs/heads/master\n/refs/tags/v1.0.0\n/refs/remotes/origin/master\n\nI don't like that plumbing has to do a dance to guess at\nexpansions, how many tools get it wrong (do it in different\norders, miss some expansions...). With an absolute\nnotation, plumbing could be built to require absolute\nnotations, giving more predictable interpretations when\ncalled from tools.\n\nThis is a long term idea, but it might make sense to\nconsider it now just for the sake of storing refs, it would\neliminate the need for the \"..\" notation for \"refs/..HEAD\".\n\nNow if we could only figure out a way to tell plumbing that\nsomething is a SHA, not a ref? :)\n\n-Martin\n\n--\nThe Qualcomm Innovation Center, Inc. is a member of Code\nAurora Forum, hosted by The Linux Foundation\n"},{"id":"274917","messageId":"xmqqoadich4x.fsf@gitster.mtv.corp.google.com","threadId":"41034","inReplyTo":"6263203.WlZuyGWxlh@mfick1-lnx","subject":"Re: RefTree: Alternate ref backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-22T21:23:10Z","receivedAt":"2015-12-22T21:23:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick writes:\n\n> ... What if we added\n> a leading slash for absolute references? Then I could do\n> something like:\n>\n> /HEAD\n> /refs/heads/master\n> /refs/tags/v1.0.0\n> /refs/remotes/origin/master\n\nYeah, that is one way to allow a tool to be absolutely certain there\nis no funny DWIMmery going on.\n\n> This is a long term idea, but it might make sense to\n> consider it now just for the sake of storing refs, it would\n> eliminate the need for the \"..\" notation for \"refs/..HEAD\".\n\nI do not see how the absolute notation has anything to do with\neliminating \"the need for the '..' notation\" at all, though.\n\nThe funny \"..HEAD\" was brought up only because Shawn wanted to omit\na single level of dereferencing of a tree object, so that the\ntop-level tree for his ref backend would have \"heads/\", \"tags/\", etc.\nin it, and because \"HEAD\" is not next to \"heads/\" and \"tags/\", it\nneeded some funny notation to avoid squatting on \"HEAD\" that should\nmean \"refs/HEAD\" in the notation.\n\n> Now if we could only figure out a way to tell plumbing that\n> something is a SHA, not a ref? :)\n\nYou do not need :) there; I think we discussed something along that\nline in the past few weeks (see the list archive).\n"},{"id":"274930","messageId":"567A2A44.3050003@alum.mit.edu","threadId":"41034","inReplyTo":"xmqqsi2ucm60.fsf@gitster.mtv.corp.google.com","subject":"Re: RefTree: Alternate ref backend","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-12-23T04:59:48Z","receivedAt":"2015-12-23T04:59:48Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/22/2015 08:34 PM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n>> On Tue, Dec 22, 2015 at 11:09 AM, Junio C Hamano wrote:\n>>> Shawn Pearce writes:\n>>>\n>>>>> But really, aside from slightly helping\n>>>>> disambiguate references from paths in the command line, what is it good\n>>>>> for?\n>>>>\n>>>> Nothing really; today refs/ prefix is used to encourage to the tools\n>>>> that you really meant refs/heads/master and not\n>>>> refs/heads/heads/master or some other crazy construct. You can thank\n>>>> the DWIMery inside the ref rev parse logic for needing this.\n>>>\n>>> Aren't you two forgetting one minor thing, though?\n>>>\n>>> A layout without refs/, i.e. $GIT_DIR/{heads,tags,...}, will force\n>>> us to keep track of where the tips of histories are anchored for\n>>> reachability purposes, every time you would add a new hierarchy\n>>> (e.g. $GIT_DIR/changes)--and those unfortunate souls who run a\n>>> slightly older version of Git that is unaware of 'changes' hierarchy\n>>> would weep after running \"git gc\", no?\n>>\n>> You still store them under refs/\n> \n> Well I know; the comment was merely a reaction to the exchange\n> between you two, \"What is refs/ good for?\", \"Nothing really\".\n> \n> You'd benefit by having \"refs/\" that is known to contain all the\n> anchoring points for reachability without knowing what subhierarchy\n> it may contain in the future, that is what it is good for.\n\nYou are answering \"What is 'refs/' good for in the pathnames of files\nthat store loose references?\" I was asking \"What is 'refs/' good for in\nthe logical names of references?\"\n\nIt would have been totally possible to make the full name of a branch\nbe, for example, \"heads/master\" and nevertheless store its loose\nreference in \"$GIT_DIR/refs/heads/master\". The obvious place to store\nHEAD in such a scheme would have been \"$GIT_DIR/refs/HEAD\" while still\ncalling it \"HEAD\". This could have avoided the problem that we now have\nwith pseudo-references like FETCH_HEAD being stored directly in $GIT_DIR.\n\nOn 12/22/2015 09:56 PM, Martin Fick wrote:\n> On Tuesday, December 22, 2015 06:17:28 PM you wrote:\n>> On Tue, Dec 22, 2015 at 7:41 AM, Michael Haggerty\n> wrote:\n>>\n>> [...] Would we really be worse off if\n>> references' full names were\n>>\n>> HEAD\n>> heads/master\n>> tags/v1.0.0\n>> remotes/origin/master (or remotes/origin/heads/master)\n>\n> I think this is a bit off, because\n>\n> HEAD != refs/HEAD\n>\n> so not quite useless.\n\nA reference called \"refs/HEAD\" is not forbidden today but it's still not\nvery useful, is it? Do you know of some system that uses reference names\nlike this or are you just pointing out that it's theoretically possible?\n\n> But, I agree that the whole refs notation has always bugged\n> me, it is quirky. It makes it hard to disambiguate when\n> something is meant to be absolute or not. What if we added\n> a leading slash for absolute references? Then I could do\n> something like:\n>\n> /HEAD\n> /refs/heads/master\n> /refs/tags/v1.0.0\n> /refs/remotes/origin/master\n\nI like the idea of having a way to express \"absolute\" reference names.\nBut maybe if we do so we could take a step towards deprecating \"refs/\"\nin references' logical names, by instead using the following absolute\nnotation for the above references:\n\n /HEAD\n /heads/master\n /tags/v1.0.0\n /remotes/origin/master\n\nSpecifically:\n\n* Any name of the form \"/$name\" for which is_pseudoref_syntax($name)\n returns true would be mapped to what we today call \"$name\" (e.g.,\n \"/FETCH_HEAD\" would be mapped to today's \"FETCH_HEAD\")\n\n* Any other name of the form \"/$name\" would be mapped to today's\n \"refs/$name\".\n\nNote that all of the absolute reference listed above, with their leading\n\"/\" removed, have the same interpretation under DWIM as they would as\nabsolute names under my proposal (provided of course, that there is no\nDWIM ambiguity with other reference names).\n\nThe only disadvantage that I can see with this scheme is that there\nwould be no \"absolute\" notation for a reference that currently has a\nfull name like \"refs/HEAD\" (or more generally a reference currently\ncalled \"refs/$name\" where is_pseudoref_syntax($name) returns true). I\nthink that is acceptable: (1) such references are probably not in wide\nuse; (2) we wouldn't (yet) have to prohibit such references; even though\nthere would be no absolute notation to represent them, their old-style\nnames would still work.\n\nIf we ever decide to go further in banishing \"refs/\", the next step in\nthe transition would be to disallow names like \"refs/HEAD\", treat the\nabsolute reference names as the \"canonical\" version, and adding DWIM\nrules that treat a prefix \"refs/\" very much like a leading \"/\".\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"274978","messageId":"xmqqsi2sbpgz.fsf@gitster.mtv.corp.google.com","threadId":"41034","inReplyTo":"567A2A44.3050003@alum.mit.edu","subject":"Re: RefTree: Alternate ref backend","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-24T01:33:00Z","receivedAt":"2015-12-24T01:33:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty writes:\n\n> You are answering \"What is 'refs/' good for in the pathnames of files\n> that store loose references?\" I was asking \"What is 'refs/' good for in\n> the logical names of references?\"\n>\n> It would have been totally possible to make the full name of a branch\n> be, for example, \"heads/master\" and nevertheless store its loose\n> reference in \"$GIT_DIR/refs/heads/master\". The obvious place to store\n> HEAD in such a scheme would have been \"$GIT_DIR/refs/HEAD\" while still\n> calling it \"HEAD\". This could have avoided the problem that we now have\n> with pseudo-references like FETCH_HEAD being stored directly in $GIT_DIR.\n\nI see; OK.\n"}]}