Git can't be made consistent

http://bramcohen.livejournal.com/74462.html

by mark_h • 15 years ago

166 36 15 years ago

bramcohen.livejournal.com

jarin• 15 years ago

In short: Don't be a dummy and expect git to be some kind of advanced artificial intelligence.

divtxt3• 15 years ago

Someone who knows this stuff please tell me if I my analysis is correct:

I see smart people pointing out "flaws" in software, not realizing the solution requires strong AI.

(e.g. yesterday's post: http://news.ycombinator.com/item?id=2455793)

dons2• 15 years ago

Merging associativity doesn't require magic AI.

bramcohen2• 15 years ago

The problem is not the intelligence of the merge algorithm. The problem is that in this case there is no right answer.

Matt_Rose• 15 years ago

Nice to see Bram Cohen coming to the same conclusion I did. Having two branches constantly cross-merging is a bad idea, no matter what SCM you use.

apenwarr• 15 years ago

I'm pretty sure the example in this article wouldn't confuse git: weirdness like this is the reason git has the "recursive" merge algorithm instead of just doing a plain three-way merge. A recursive merge basically tries to merge some of the parents together before doing the final merge, which resolves this sort of case.

I do criss-cross merges between git branches all the time with no ill effects. Maybe non-git VCSes can't handle this sort of thing.

ob2• 15 years ago

You need to do criss-cross merges that revert previous commits on one or both sides of the merges. If you're not reverting you're not hitting Bram's corners.

This is a though corner case and I'm pretty sure you can confuse any source control system currently in production with cases like this. BitKeeper has some theoretical solutions, but we haven't gotten around to actually test them in production.

dons2• 15 years ago

Note that darcs implements the "expected" or "naive" semantics, at the cost of edge cases that have exponential time (rather than going ahead with unflagged inconsistent merges).

DannoHung• 15 years ago

Was the Camp project expected to create a non-exponential algorithm at the edges?

pedrocr2• 15 years ago

The really big insight Linus had that Brahm apparently still doesn't want to recognize is that if that if you design what essentially a snapshotted filesystem, the merge algorithm is just a convenience. Any better merge algorithms can be added to git without touching the format. In fact any individual user can pick and choose their merge algorithm that the repository just cares about the recorded content history (which trees are parent to which trees).

DougBTX2• 15 years ago

Git also stores diffs from time to time: http://book.git-scm.com/7_how_git_stores_objects.html

codex2• 15 years ago

I stopped reading after the first sentence. The author takes some liberties with the definition of "eventual consistency.". Either he doesn't know what it means, or he likes to demolish terms which used to be defined precisely.

cdavid• 15 years ago

Or maybe you are expecting one context and the author is using a different one. This is quite likely given the author (a well known hacker, and having worked in particular on this exact problem through his project codeville)

random42• 15 years ago

On a related note, to establish the credential of the author, he is the creator of BitTorrent protocol.

http://en.wikipedia.org/wiki/Bram_Cohen

jacobolus• 15 years ago

And has worked quite a bit on the revision control diff/merge problem, e.g. http://bramcohen.livejournal.com/37690.html

shasta2• 15 years ago

Why do you think he's using the term incorrectly? He just means that, with git, the order in which you apply patches matters. In a scenario where people are distributing patches and applying them as they receive them, this implies a lack of eventual consistency.

codex2• 15 years ago

That's the lack of the associative property. Eventual consistency means that updates will eventually be propagated to all replicas in a distributed system and that all replicas will be consistent. Not the same thing, at all.

decklin• 15 years ago

Another interesting case: http://www.kernel.org/pub/software/scm/git/docs/howto/revert...

I'm not sure if the "forget whatever happened" metaphor works for me. In the "revert a revert" article above, the problem is that merging a topic branch doesn't cause the first few commits on it to be applied if those commits were already merged but then reverted -- the revert has no effect on the merge. This is precisely because every commit object, since it includes it's parent's sha1, uniquely determines a history of changes, and commits in that are in both ancestries don't get re-applied.

In Bram's example, you have the opposite problem -- two commits are semantically the same but were made independently and have different sha1s. If Linus were drawing this diagram he would label them B and B' (and so on... there's a lot). To git, B' is totally different so a merge applies the change "again". If the other person had noticed this and reset their branch to the first B, the merge would be a fast-forward.

IMHO, the Don't Do That should apply to creating those commits (by cherry-picking, or not rebasing duplicated work) rather than merging. Not because such commits are morally wrong or something like that, but because git intentionally ("the stupid content tracker") doesn't handle them well. That's the tradeoff of the nice object model.

Our git workflow at my job is pretty messy and does run into this sort of stuff. I'd love something just a little more darcs-y, like say grafting together the two branches in the second example that arrive at the same content (without having to manage a local grafts file separate from the repository), but that opens many other cans of worms that I'm sure I'm not intelligent enough to deal with.

lysium• 15 years ago

Thanks for mentioning B', I first did not understand what the problem was. Merging B' will turn A to B', which is equivalent to B. This causes confusion if the author of the left branch intended to get rid of B.

someisaac• 15 years ago

I am surprised to see this post from bram cohen, as he himself had a heated argument with linus torvalds on git design.

http://www.gelato.unsw.edu.au/archives/git/0504/2153.html http://news.ycombinator.com/item?id=505876

ob2• 15 years ago

Which he lost... i.e. Linus paid no attention to what Bram said ;)

bramcohen2• 15 years ago

For some context, Git follows the same architecture as Codeville, so Linus didn't invent the idea (although he ripped it off from Monotone, not Codeville) and the argument was essentially about whether a simple three-way merge can be used in all cases, and the answer is no, because of criss-cross cases, and solutions for that have since been put into Git. It is the case that semantics which more closely resemble three way merge are preferred though, as explained in my post which this thread is about, but for reasons which nobody in the flame war you link to appreciated at the time.

mrwhy2k• 15 years ago

Holy crap... someone still uses LiveJournal as their blog.

riffraff• 15 years ago

>I have a little secret for you: Git can't be made to have eventual consistency

David Roundy, the initial author of darcs, seems to disagree on this. From https://github.com/droundy/iolaus : > I realized that the semantics of git are actually not nearly so far from those of darcs as I had previously thought. In particular, if we view each commit as describing a patch in its "primitive context" (to use darcs-speak), then there is basically a one-to-one mapping from darcs' semantics to a git repository.

gwern• 15 years ago

'actually not nearly so far', 'if we view each commit', 'there is basically' - many differences and gotchas can lurk in such qualifiers.

closedbracket• 15 years ago

Mr. Joy is a really ironic name.

Git can't be made consistent

Related Stories