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 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?
: I'm avoiding "merge" here to avoid confusion, it's not the git merge.