1git-bug's reusable entity data model
2====================================
3
4This document explains how git-bug's reusable distributed data structure in git is working. This data structure is capable of:
5- storing an entity (bug, pull-request, config...) and its complete history in git
6- carry signed authorship of editions
7- use git remotes as a medium for synchronisation and collaboration
8- merge conflicts
9- respect the rules you define as to what edition are possible
10- carry attached media
11
12If you are looking for a different writing format or to see how you can easily make your own, checkout [the example code](../entity/dag/example_test.go).
13
14If you are not familiar with [git internals](https://git-scm.com/book/en/v2/Git-Internals-Git-Objects), you might first want to read about them, as the `git-bug` data model is built on top of them.
15
16## Entities (bug, author, ...) are a series of edit operations
17
18As entities are stored and edited in multiple processes at the same time, it's not possible to store the current state like it would be done in a normal application. If two processes change the same entity and later try to merge the states, we wouldn't know which change takes precedence or how to merge those states.
19
20To deal with this problem, you need a way to merge these changes in a meaningful way. Instead of storing the final bug data directly, we store a series of edit `Operation`s. This is a common idea, notably with [Operation-based CRDTs](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#Operation-based_CRDTs).
21
22
23
24To get the final state of an entity, we apply these `Operation`s in the correct order on an empty state, to compute (aka "compile") our view.
25
26## Entities are stored in git objects
27
28An `Operation` is a piece of data, including:
29
30- a type identifier
31- an author (a reference to another entity)
32- a timestamp (there is also one or two [Lamport time](#time-is-unreliable))
33- all the data required by that operation type (a message, a status ...)
34- a random [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) to ensure we have enough entropy, as the operation identifier is a hash of that data (more on that later)
35
36These `Operation`s are aggregated in an `OperationPack`, a simple array. An `OperationPack` represents an edit session of the entity. As the operation's author is the same for all the `OperationPack` we only store it once.
37
38We store this pack in git as a git `Blob`; that consists of a string containing a JSON array of operations. One such pack -- here with two operations -- might look like this:
39
40```json
41{
42 "author": {
43 "id": "04bf6c1a69bb8e9679644874c85f82e337b40d92df9d8d4176f1c5e5c6627058"
44 },
45 "ops": [
46 {
47 "type": 3,
48 "timestamp": 1647377254,
49 "nonce": "SRQwUWTJCXAmQBIS+1ctKgOcbF0=",
50 "message": "Adding a comment",
51 "files": null
52 },
53 {
54 "type": 4,
55 "timestamp": 1647377257,
56 "nonce": "la/HaRPMvD77/cJSJOUzKWuJdY8=",
57 "status": 1
58 }
59 ]
60}
61```
62
63To reference our `OperationPack`, we create a git `Tree`; it references our `OperationPack` `Blob` under `"/ops"`. If any edit operation includes a media (for instance in a text message), we can store that media as a `Blob` and reference it here under `"/media"`.
64
65To complete the picture, we create a git `Commit` that references our `Tree`. Each time we add more `Operation`s to our bug, we add a new `Commit` with the same data-structure to form a chain of `Commit`s.
66
67This chain of `Commit`s is made available as a git `Reference` under `refs/<namespace>/<id>`. We can later use this reference to push our data to a git remote. As git will push any data needed as well, everything will be pushed to the remote, including the media.
68
69Here is the complete picture:
70
71
72
73## Time is unreliable
74
75Before being able to merge conflicts, let's start with some building blocks.
76
77It would be very tempting to use the `Operation`'s timestamp to give us the order to compile the final state. However, you can't rely on the time provided by other people (their clock might be off) for anything other than just display. This is a fundamental limitation of distributed system, and even more so when actors might want to game the system.
78
79Instead, we are going to use [Lamport logical clock](https://en.wikipedia.org/wiki/Lamport_timestamps). A Lamport clock is a simple counter of events. This logical clock gives us a partial ordering:
80
81- if L1 < L2, L1 happened before L2
82- if L1 > L2, L1 happened after L2
83- if L1 == L2, we can't tell which happened first: it's a concurrent edition
84
85
86Each time we are appending something to the data (create an `Entity`, add an `Operation`) a logical time will be attached, with the highest time value we are aware of, plus one. This declares a causality in the events and allows ordering entities and operations.
87
88The first commit of an `Entity` will have both a creation time and edit time clock, while a later commit will only have an edit time clock. These clocks value are serialized directly in the `Tree` entry name (for example: `"create-clock-4"`). As a `Tree` entry needs to reference something, we reference the git `Blob` with an empty content. As all of these entries will reference the same `Blob`, no network transfer is needed as long as you already have any entity in your repository.
89
90Example of a `Tree` of the first commit of an entity:
91```
92100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 create-clock-14
93100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 edit-clock-137
94100644 blob a020a85baa788e12699a4d83dd735578f0d78c75 ops
95```
96
97Example of a `Tree` of a later commit of an entity:
98```
99100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 edit-clock-154
100100644 blob 68383346c1a9503f28eec888efd300e9fc179ca0 ops
101```
102
103## Entities and Operation's ID
104
105`Operation`s can be referenced - in the data model or by users - with an identifier. This identifier is computed from the `Operation`'s data itself, with a hash of that data: `id = hash(json(op))`
106
107For entities, `git-bug` uses as identifier the hash of the first `Operation` of the entity, as serialized on disk.
108
109The same way as git does, this hash is displayed truncated to a 7 characters string to a human user. Note that when specifying a bug id in a command, you can enter as few characters as you want, as long as there is no ambiguity. If multiple entities match your prefix, `git-bug` will complain and display the potential matches.
110
111## Entities support conflict resolution
112
113Now that we have all that, we can finally merge our entities without conflict, and collaborate with other users. Let's start by getting rid of two simple scenarios:
114
115- if we simply pull updates, we move forward our local reference. We get an update of our graph that we read as usual.
116- if we push fast-forward updates, we move forward the remote reference and other users can update their reference as well.
117
118The tricky part happens when we have concurrent editions. If we pull updates while we have local changes (non-straightforward in git term), `git-bug` creates the equivalent of a merge commit to merge both branches into a DAG. This DAG has a single root containing the first operation, but can have branches that get merged back into a single head pointed by the reference.
119
120As we don't have a purely linear series of commits/`Operations`s, we need a deterministic ordering to always apply operations in the same order.
121
122`git-bug` applies the following algorithm:
123
1241. load and read all the commits and the associated `OperationPack`s
1252. make sure that the Lamport clocks respect the DAG structure: a parent commit/`OperationPack` (that is, towards the head) cannot have a clock that is higher or equal than its direct child. If such a problem happens, the commit is refused/discarded.
1263. individual `Operation`s are assembled together and ordered given the following priorities:
127 1. the edition's lamport clock if not concurrent
128 2. the lexicographic order of the `OperationPack`'s identifier
129
130Step 2 is providing and enforcing a constraint over the `Operation`'s logical clocks. What that means, is that **we inherit the implicit ordering given by the DAG**. Later, logical clocks refine that ordering. This - coupled with signed commits - has the nice property of limiting how this data model can be abused.
131
132Here is an example of such an ordering:
133
134
135
136We can see that:
137
138- Lamport clocks respect the DAG structure
139- the final `Operation` order is [A,B,C,D,E,F], according to those clocks
140
141When we have concurrent editions, we apply a secondary ordering, based on the `OperationPack`'s identifier:
142
143
144
145This secondary ordering doesn't carry much meaning, but it's unbiased and hard to abuse.