{"thread":{"id":"33877","subject":"Storing refs in the odb (was: Re: [PATCH 00/17] Remove assumptions about refname lifetimes)","startedAt":"2013-05-20T13:48:15Z","lastAt":"2013-05-20T18:44:35Z","messageCount":5,"participants":["Johan Herland","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":17},"messages":[{"id":"217978","messageId":"CALKQrgcBkdoJdJGam=VkE=nXHQ8WB5judY3C3nNQBJCns-_f+A@mail.gmail.com","threadId":"33877","inReplyTo":null,"subject":"Storing refs in the odb (was: Re: [PATCH 00/17] Remove assumptions about refname lifetimes)","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T13:48:15Z","receivedAt":"2013-05-20T13:48:15Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Mon, May 20, 2013 at 2:15 PM, Michael Haggerty wrote:\n> This is a very interesting idea. \"It's turtles all the way down.\"\n\n:)\n\n> On 05/20/2013 12:28 PM, Johan Herland wrote:\n>> For server-class installations we need ref storage that can be read\n>> (and updated?) atomically, and the current system of loose + packed\n>> files won't work since reading (and updating) more than a single file\n>> is not an atomic operation. Trivially, one could resolve this by\n>> dropping loose refs, and always using a single packed-refs file, but\n>> that would make it prohibitively expensive to update refs (the entire\n>> packed-refs file must be rewritten for every update).\n>\n> Correct, or the \"packed-refs\" file would have to be updated in place\n> using some database-style approach for locking/transactions/whatever.\n>\n>> Now, observe that we don't have these race conditions in the object\n>> database, because it is an add-only immutable data store.\n>\n> Except for prune, of course, which can cause race conditions WRT to writers.\n\nYes, but that is a different race, in need of a different solution.\nE.g. that race is concerned with pruning unreachable objects that are\nabout to become reachable by a concurrent operation, which is AFAICS\nindependent from the ref update race that we're discussing here.\n\n>> What if we stored the refs as a tree object in the object database,\n>> referenced by a single (loose) ref? There would be a _single_ (albeit\n>> highly contentious) file outside the object database that represent\n>> the current state of the refs, but hopefully we can guarantee\n>> atomicity when reading (and updating?) that one file. Transactions can\n>> be done by:\n>> 1. Recording the tree id holding the refs before starting manipulation.\n>> 2. Creating a new tree object holding the manipulated state.\n>> 3. Re-checking the tree id before replacing the loose ref. If\n>> unchanged: commit, else: rollback/error out.\n>\n> There are two closely related possibilities and I'm not sure which one\n> you mean:\n>\n> * Effectively treat all of the refs as loose refs, but stored not in the\n> filesystem but rather in a hierarchical tree structure in the object\n> database. E.g., all of the refs directly under \"refs/heads\" would be in\n> one tree object, those in refs/remotes/foo in a second, those for\n> refs/remotes/bar in another etc. and all of them linked up together in a\n> tree object representing \"refs\".\n>\n> * Effectively treat all of the refs as packed refs, but store the single\n> \"packed-refs\" file as a single object in the object database.\n>\n> (The first alternative sounds more practical to me. I also guess that's\n> what you mean, since down below you say that each change would require\n> producing \"a few objects\".)\n\nThe first alternative is what I had in mind.\n\nInitially I thought to record it as if one were to record a new tree\nusing .git/refs as the root of your worktree (having exploded all\npacked-refs into loose refs). I.e. you would have \"heads\", \"tags\",\n\"remotes\" as subtrees of \"reference tree\", and then e.g. in the\n\"heads\" subtree, there would be an entry named \"master\" pointing to a\n_blob_, and the contents of that blob would be the commit id of the\ncurrent tip of the master branch.\n\nObviously the next optimization would be to drop the \"master\" -> blob\n-> commit indirection, and use \"master\" -> commit instead, i.e. the\n\"master\" tree entry corresponds directly to the commit to which it\npoints (symrefs would naturally be recorded as symlinks). This would\nautomatically provide reachability for all refs, but as you correctly\nobserve:\n\n> Of course in either case we couldn't use a tree object directly, because\n> these new \"reference tree\" objects would refer not only to blobs and\n> other trees but also to commits and tags.\n\nIndeed. I don't know if the best solution would be to actually _allow_\nthat (which would complicate the object parsing code somewhat; a tree\nentry pointing to a commit is usually interpreted as a submodule, but\nthat is not what we'd want for the ref tree, and a tree entry pointing\nat a tag has AFAIK not yet been done), or whether it means we need to\ncome up with a different kind of structure.\n\n> [I know this is not what you are suggesting, but I am reminded of\n> Subversion, which stores trunk, branches, and tags in the same \"tree\"\n> space as the contents of the working trees. A Subversion commit\n> references a gigantic tree encompassing all branches of development and\n> all files on all of those branches (with cheap copies to reduce the\n> redundancy):\n>\n> /\n> /trunk/\n> /trunk/Makefile\n> /trunk/src/\n> /trunk/src/foo.c\n> /branches/\n> /branches/next/\n> /branches/next/Makefile\n> /branches/next/src/\n> /branches/next/src/foo.c\n> /branches/pu/\n> /branches/pu/Makefile\n> /branches/pu/src/\n> /branches/pu/src/foo.c\n> /tags/\n> /tags/v1.8.2/\n> /tags/v1.8.2/Makefile\n> /tags/v1.8.2/src/\n> /tags/v1.8.2/src/foo.c\n> etc...\n>\n> A Subversion commit thus describes the state of *every* branch and tag\n> at that moment in time. The model is conceptually very simple (in fact,\n> too simple, and I believe the Subversion developers regret not having\n> distinguished between the branch namespace and the file namespace).]\n\nTrue. Thanks for the added perspective. The crucial difference between\nSubversion and Git in this regard is obviously that Git puts the\ncommit \"between\" the branch namespace and the file namespace, firmly\nseparating the two. My suggestion does not change this in any way, but\nit reuses the same object model to look at the branch namespace as\n\"meta-trees\".\n\n> The main difficulty with this idea will be the extreme contention on\n> that \"last loose reference file\" pointing at the root of the reference\n> tree. Essentially *every* change to the repository will have to create\n> a new reference tree and point this file at the new version.\n\nYes. This is indeed the ultimate problem with this idea. But AFAICS it\nis the same ultimate problem for all filesystem-based solutions: since\natomicity can only be guaranteed for single-file updates, any\nfile-based solution _must_ have the equivalent of a single lock on all\nref updates.\n\nHence, if it can be demonstrated that the contention on a single\n(41-byte) file is sufficiently extreme to make it infeasible in\npractice, then we can conclude that there is _no_ filesystem-based\nsolution that will solve our problem, and we _must_ go for more\nadvanced database solution.\n\n> I doubt\n> that would be a problem for short-lived operations, but I fear that a\n> long-lived operation would *never* get done. By the time it had\n> finished constructing its new reference tree, some other short-lived\n> operation will have changed it, and the long-lived process will have to\n> choose between\n>\n> * Restart from the beginning.\n>\n> * Die with a kind of \"concurrent modification error\".\n>\n> * Resolve the difference between the reference tree at the start of its\n> operation and the reference tree as it exists when it is done with the\n> changes that they want to make. In some cases this might be able to be\n> done automatically as a kind of \"reference tree merge\" but the logic\n> might have to vary from case to case.\n\nAlternatively, it could (when sufficiently miffed) grab a lock that\nwould temporarily refuse/delay anybody else access to update refs.\n\n>> PS: Keeping reflogs is just a matter of wrapping the ref tree in a\n>> commit object using the previous state of the ref tree as its parent.\n>\n> Yes, there are a lot of nice aspects to this idea in that it reuses\n> concepts with which we are already familiar. For example, fetching from\n> a remote would approximately hook the remote's entire reference tree\n> into a subtree of the local \"refs/remotes\" reference subtree.\n\nTrue. Hadn't thought of that...\n\n> But with\n> things like reflogs we would have to be careful not to keep obsolete\n> objects around *forever*--there would have to be some mechanism to prune\n> the old reference history.\n\nYes, pruning reflogs could be done by finding the oldest reflog-commit\nwe want to keep, rewriting it to have zero parents with \"git replace\",\nand then rewriting the reflog-commit history accordingly to make the\nolder reflog-commits unreachable.\n\n(But then, the \"git replace\" mechanism writes its own refs/replace/*\nref, which would cause a new reflog-commit. Fortunately the replace\nref does not make the replaced history reachable, so this should in\nfact work, albeit more than a little complicated...)\n\n...Johan\n\n\n> Altogether a very interesting idea.\n>\n> Michael\n>\n> --\n> Michael Haggerty\n> mhagger@alum.mit.edu\n> http://softwareswirl.blogspot.com/\n\n\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"217986","messageId":"7vbo85wos9.fsf@alter.siamese.dyndns.org","threadId":"33877","inReplyTo":"CALKQrgcBkdoJdJGam=VkE=nXHQ8WB5judY3C3nNQBJCns-_f+A@mail.gmail.com","subject":"Re: Storing refs in the odb","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-20T17:21:10Z","receivedAt":"2013-05-20T17:21:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n>> Of course in either case we couldn't use a tree object directly, because\n>> these new \"reference tree\" objects would refer not only to blobs and\n>> other trees but also to commits and tags.\n>\n> Indeed. I don't know if the best solution would be to actually _allow_\n> that (which would complicate the object parsing code somewhat; a tree\n> entry pointing to a commit is usually interpreted as a submodule, but\n> that is not what we'd want for the ref tree, and a tree entry pointing\n> at a tag has AFAIK not yet been done), or whether it means we need to\n> come up with a different kind of structure.\n\nYou can disallow that only by giving up on being able to express\nLinus's kernel repository, which has an oddball v2.6.11-tree tag.\n\nI do not think that that particular tag in the particular repository\nis too big a show-stopper; if it is only Linus, we can ask him to\ndrop that tag (he has v2.6.11 tag object that points at the tree, so\nthe users do not lose anything) and be done with it.\n\nBut if there are other repositories that tag trees in a similar way,\nthat would be a real regression. We cannot just go ask people to\nchange their workflow that depended on using refs that directly\npoint at trees overnight.\n"},{"id":"217987","messageId":"CALKQrgdWx5mw3NCd4JOr3x9M34c2rNjm_tz_C7fm7g7g-LUJZQ@mail.gmail.com","threadId":"33877","inReplyTo":"7vbo85wos9.fsf@alter.siamese.dyndns.org","subject":"Re: Storing refs in the odb","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T17:37:45Z","receivedAt":"2013-05-20T17:37:45Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Mon, May 20, 2013 at 7:21 PM, Junio C Hamano wrote:\n> Johan Herland writes:\n>\n>>> Of course in either case we couldn't use a tree object directly, because\n>>> these new \"reference tree\" objects would refer not only to blobs and\n>>> other trees but also to commits and tags.\n>>\n>> Indeed. I don't know if the best solution would be to actually _allow_\n>> that (which would complicate the object parsing code somewhat; a tree\n>> entry pointing to a commit is usually interpreted as a submodule, but\n>> that is not what we'd want for the ref tree, and a tree entry pointing\n>> at a tag has AFAIK not yet been done), or whether it means we need to\n>> come up with a different kind of structure.\n>\n> You can disallow that only by giving up on being able to express\n> Linus's kernel repository, which has an oddball v2.6.11-tree tag.\n>\n> I do not think that that particular tag in the particular repository\n> is too big a show-stopper; if it is only Linus, we can ask him to\n> drop that tag (he has v2.6.11 tag object that points at the tree, so\n> the users do not lose anything) and be done with it.\n>\n> But if there are other repositories that tag trees in a similar way,\n> that would be a real regression. We cannot just go ask people to\n> change their workflow that depended on using refs that directly\n> point at trees overnight.\n\nI wasn't considering disallowing _anything_, rather open up to the\nidea that a tree object might refer to tag objects as well as\ncommits/trees/blobs. E.g. in my suggested-but-pretty-much-retracted\nscheme, I was considering whether the tree entry at the \"virtual\" path\n\"refs/tags/v1.0\" should look like this:\n\n 100644 blob 123456... v1.0\n\nwhere the blob at 123456... contains the object id of the v1.0 tag\nobject, or whether we should allow the crazyness that is:\n\n ?????? tag 987654... v1.0\n\nJust a thought experiment...\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"217992","messageId":"7va9npv730.fsf@alter.siamese.dyndns.org","threadId":"33877","inReplyTo":"CALKQrgdWx5mw3NCd4JOr3x9M34c2rNjm_tz_C7fm7g7g-LUJZQ@mail.gmail.com","subject":"Re: Storing refs in the odb","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-20T18:28:51Z","receivedAt":"2013-05-20T18:28:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland writes:\n\n> I wasn't considering disallowing _anything_, rather open up to the\n> idea that a tree object might refer to tag objects as well as\n> commits/trees/blobs. E.g. in my suggested-but-pretty-much-retracted\n> scheme, I was considering whether the tree entry at the \"virtual\" path\n> \"refs/tags/v1.0\" should look like this:\n>\n> 100644 blob 123456... v1.0\n>\n> where the blob at 123456... contains the object id of the v1.0 tag\n> object, or whether we should allow the crazyness that is:\n>\n> ?????? tag 987654... v1.0\n>\n> Just a thought experiment...\n\nI was reacting to this part of your earlier message:\n\n>>> Of course in either case we couldn't use a tree object directly, because\n>>> these new \"reference tree\" objects would refer not only to blobs and\n>>> other trees but also to commits and tags.\n>>\n>> Indeed. I don't know if the best solution would be to actually _allow_\n>> that (which would complicate the object parsing code somewhat; a tree\n\nYou cannot disambiguate, with the thought-experiment in your message\nI am responding to, between these two:\n\n ?????? tree 987654... v2.6.11-tree\n ?????? tree 987654... sub\n\nwhere the former is a light-weight tag for that tree, while the\nlatter is merely a subhierarchy in refs/sub/hier/archy, but if you\ndisallow v2.6.11-tree, and if you know this kind of tree is only to\nexpress the ref hierarchy, then everything is unambiguous (a commit\nis not a submodule but is a ref that points at a commit, a blob is a\nref that points at a blob like refs/tags/junio-gpg-pub, and tag is a\nref that points at the tag).\n\nSo it was \"workable\" alternative implementation of refs (I am not\nsaying it is an \"improvement\", with the atomicity and performance\nimplications we already discussed), if we did not have to worry\nabout a light-weight tag that directly point at a tree.\n"},{"id":"217993","messageId":"CALKQrgeq5xs0ob7=gyYp4nzV3EftOePOPXD4gz6uZBHgmDzD7w@mail.gmail.com","threadId":"33877","inReplyTo":"7va9npv730.fsf@alter.siamese.dyndns.org","subject":"Re: Storing refs in the odb","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T18:44:35Z","receivedAt":"2013-05-20T18:44:35Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Mon, May 20, 2013 at 8:28 PM, Junio C Hamano wrote:\n> Johan Herland writes:\n>\n>> I wasn't considering disallowing _anything_, rather open up to the\n>> idea that a tree object might refer to tag objects as well as\n>> commits/trees/blobs. E.g. in my suggested-but-pretty-much-retracted\n>> scheme, I was considering whether the tree entry at the \"virtual\" path\n>> \"refs/tags/v1.0\" should look like this:\n>>\n>> 100644 blob 123456... v1.0\n>>\n>> where the blob at 123456... contains the object id of the v1.0 tag\n>> object, or whether we should allow the crazyness that is:\n>>\n>> ?????? tag 987654... v1.0\n>>\n>> Just a thought experiment...\n>\n> I was reacting to this part of your earlier message:\n>\n>>>> Of course in either case we couldn't use a tree object directly, because\n>>>> these new \"reference tree\" objects would refer not only to blobs and\n>>>> other trees but also to commits and tags.\n>>>\n>>> Indeed. I don't know if the best solution would be to actually _allow_\n>>> that (which would complicate the object parsing code somewhat; a tree\n>\n> You cannot disambiguate, with the thought-experiment in your message\n> I am responding to, between these two:\n>\n> ?????? tree 987654... v2.6.11-tree\n> ?????? tree 987654... sub\n>\n> where the former is a light-weight tag for that tree, while the\n> latter is merely a subhierarchy in refs/sub/hier/archy, but if you\n> disallow v2.6.11-tree, and if you know this kind of tree is only to\n> express the ref hierarchy, then everything is unambiguous (a commit\n> is not a submodule but is a ref that points at a commit, a blob is a\n> ref that points at a blob like refs/tags/junio-gpg-pub, and tag is a\n> ref that points at the tag).\n>\n> So it was \"workable\" alternative implementation of refs (I am not\n> saying it is an \"improvement\", with the atomicity and performance\n> implications we already discussed), if we did not have to worry\n> about a light-weight tag that directly point at a tree.\n\nTrue, unless we were to abuse the mode bits to differentiate between\nregular-subtree and ref-to-tree cases...\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"}]}