Ordering of operations in a DAG of git commits

Question

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.

Answer 1

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?

Answer 2

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.