2
$\begingroup$

Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug

Summary of the current algorithm and shortcomings

git-bug is a distributed bug-tracker that embed in git, the distributed version control system. To do so, bugs are stored in the native git data structure (commits and branches). Each bug has its own branch and adding commits to it will evolve the bug state. This allows using git as both a database and a transport, in the sense that users can push/pull those branches to distributes updates and collaborate with each other.

More details can be found in this document: https://github.com/MichaelMure/git-bug/blob/master/doc/model.md

Now to deal with the distributed nature of this system and allow merges, the state of a bug can't be stored as-is. Instead, it's stored as an ordered series of operations: adding a comment, changing the title ... When reading a bug, the final state is "compiled" by applying those operations in order to an originally empty state.

I believe (but don't quote me on that) that this is a form of Operational Transformation (OT).

In reality, multiple operations can be stored in a single git commit but for the purpose of this conversation, let's assume that one git commit stores exactly one operation.

To make my life a bit easier at the beginning of this project, I reduced the complexity of this problem by imposing that the series of commit holding the operations would have to be linear, which make the ordering of the operations trivial: the order of the commit implies the order of the operations.

This purely linear restriction has a major implication: when fusing[1] together with two git DAG when doing a git pull, the equivalent of a git rebase has to be used. The commits of one diverging branch are reapplied on top of the other, which means that the data structure is not actually immutable. Not only this is problematic if commits are signed, but I'm also suspecting this can prevent the commits to reach a stable ordering when there is no central server acting as "source of truth". If three users A, B, and C are pulling and rebasing commits in a cycle A->B->C->A, I suspect they will never reach a stable ordering.

Another way to do things would be to use the equivalent of git merge: the diverging branches are fused together with a new commit having both branches as parents and we end up with a DAG. Although and this is important, in the normal git behavior this merge commit holds the fused state. For git-bug, each operation is disconnected from the others, so the merge commit would hold no fused state, just that the branches fused.

The actual question

I'm looking for an algorithm capable of doing this ordering of commits in a git DAG using git merge, in the most stable way possible.

  • using git merge: git merges are allowed, possibly rebase as well if necessary
  • most stable way possible: in a perfect world, the operations should be ordered by their real-time creation. Obviously, this is not fully possible in a distributed system, so the goal is to get a logical order as close as possible, despite concurrent editions and merges. Thankfully, bugs in a bug-tracker are slightly malleable and will retain the user's intent even if the ordering is slightly wrong.

As you may have guessed, I'm a bit out of my depth here so, short of an actual algorithm, any pointers for theoretical ground or possible solutions would be helpful.

Things I considered

  • storing in each operation/commit the reference of the ancestor at the time of the creation
  • using some form of logical clock, stored in each commit
  • some sort of topological ordering
  • a combination of those?

[1]: I'm avoiding "merge" here to avoid confusion, it's not the git merge.

$\endgroup$
8
  • $\begingroup$ Can you clarify what you mean by "doing this ordering of commits"? What are the inputs to the algorithm, and what are the desired outputs? I'm confused what you mean by "stable"; given a DAG, surely there is only one possible result of the DAG? I don't understand why you need to find a total linear order if you have a DAG and can do merges, so I probably haven't understood some aspect of the motivation -- sorry. Maybe I don't understand git well enough. $\endgroup$ – D.W. Dec 20 '20 at 6:06
  • $\begingroup$ I may not have a firm grasp as well, hence my question. $\endgroup$ – Michael Muré Dec 20 '20 at 9:50
  • $\begingroup$ I need to order the operations(=commits) to apply them one by one to the state and compute the final state of a bug. So the input of the algorithm is this DAG of commit, the output it the commits ordered the best way possible. Before I was enforcing a linear chain of commit, I now want to allow a DAG with arbitrary topology. $\endgroup$ – Michael Muré Dec 20 '20 at 9:56
  • $\begingroup$ Stable in the sense of, when fusing together two DAG (same "old" section) that diverged independently, the algorithm should produce a similar order for this "old" section. Adding new elements at the root of the DAG (the newest element), should not change the ordering of previous elements. $\endgroup$ – Michael Muré Dec 20 '20 at 9:58
  • $\begingroup$ I'm still lost. If you have the ability to merge/fuse two branches, then I don't understand why you need to put them in a linear order. There's no need to store the full state after the merge; you just need the merge operation to be a deterministic function of the two branches entering the merge. I don't understand what it means to be "stable". I don't understand what is meant by "similar order for this old section"; if the algorithm is deterministic, it'll always give the same result. Can you make it precise with math? Is it possible you are looking for a topological sort? $\endgroup$ – D.W. Dec 20 '20 at 16:43
0
$\begingroup$

What exactly is an operation in your model? If two concurrent operations commute, then any topological sort of your DAG will give the same result (cf. Strong Eventual Consistency). If two concurrent operations are independent of one another it's likely they commute (or can be made to commute); otherwise, if there is a deterministic way to prioritise them, then do that (as in CRDTs). I can't be more specific without understanding what an operation is.

$\endgroup$
3
  • $\begingroup$ Thanks. At the moment, operations are Create, SetTitle, AddComment, SetStatus, LabelChange and EditComment. Each of those will mutate the state of a bug to compute the final snapshot shown to a user at a point in time.I suppose you can guess what each of them do. In a way, they also store the full history. To some extent, they both commute and don't commute, depending on what property you look at. Applying them in the wrong order will not return an error but some operations might not make sense anymore and won't change the state. They get "muted". To be avoided if possible. $\endgroup$ – Michael Muré Dec 23 '20 at 14:43
  • $\begingroup$ There is some value in having the invalid operation not change the state without errors: you get more resilient against broken data and you can have extra operations that not all client understand without breaking everything. $\endgroup$ – Michael Muré Dec 23 '20 at 14:44
  • $\begingroup$ Two examples where operations don't commute: - two SetTitle operations will change the same value. Last one win (but they both get shown in the timeline so the intent is not lost) - EditComment depend on a previous AddComment. If apply in the wrong order, EditComment won't thing its target and no state mutation happen $\endgroup$ – Michael Muré Dec 23 '20 at 14:51
0
$\begingroup$

Assuming I understand the semantics:

  • You cannot concurrently Create the same bug report twice, so that's not a problem
  • Title could be a Last-Writer-Wins (LWW) register. If two users perform SetTitle concurrently, the one with the highest timestamp remains.
  • You could use a CRDT set for comments. This way users can add and remove an arbitrary number of comments. With sets, a comment constitutes an element of the set; comments are unordered; a comment can be deleted. If a deleted comment cannot be revived, use 2Pset; otherwise use AWset.
  • A more interesting approach for comments is to provide relations between comments, e.g., a comment may respond to an earlier comment. In this case a CRDT DAG or tree would work, e.g., WOOT or RGA. (RGA is ostensibly a list, but in fact it's a linearised tree.)
  • If you want to allow concurrent EditComment's, the text of a comment could either be an edit-string CRDT, e.g. RGA, or more simply a multi-value register (MVR).
  • For Tags, attach a CRDT set (AWset would be ideal) to a report, where users can add/remove arbitrary tags.
  • Status: not sure what this means. You might again use AWset, or a custom semi-lattice if status always progresses in the same direction (e.g. from Open to Closed, never re-opened).

Does this help?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.