|
|
|
|
|
|
by auggierose
630 days ago
|
|
|
Ok, I started reading the paper now, and this seems to be a really cool method.
I didn't understand all the details of apply/retreat/advance yet, though. I am wondering, the EG graph is a very general construct, and the events themselves (Insert(i, c) and Delete(i)) are very natural as well. You say in the paper this should also work for other applications than plain text, but I guess then another CRDT has to be constructed to implement apply/retreat/advance. Would it be possible to formulate all of this independently of the application and particular CRDT, together with corresponding correctness theorems? That would help with constructing versions of this for other applications, and maybe make understanding this particular application for plain text easier. |
|
|
All the complexity comes about because we're trying to convert the insert / delete position from edits (expressed at their original version) to some later current version.
There's lots of ways of solving this problem. For example, we could build a data structure which contains metadata for every inserted item in a text document. For every inserted character, we store when the item was inserted and when (if ever) the item was deleted.
Then you could implement the algorithm in a simpler way. Lets say I'm trying to insert at position 1000, at some version V.
- We scan the list of characters from the start of the document, looking for the 1000th item which was actually in the document at version V.
- For each character in the list, we can tell if that item was inserted at version V by comparing V to the stored inserted / deleted at times.
This algorithm would be correct, and it avoids retreat / advance. The only problem with this approach is that it would be slow - because you're constantly scanning the document to convert insert positions. Inserting N items into a document take O(N^2) time.
The retreat / advance approach described in the paper is an optimization on top of this algorithm which performs the same work in O(N log N) time.
I wish we made this more clear in the paper. In an earlier draft we spent about 5 pages simply talking about version theory. The algorithm was then described using that theory with a stronger theoretical grounding. But I think that description may have been even more confusing.
> You say in the paper this should also work for other applications than plain text, but I guess then another CRDT has to be constructed to implement apply/retreat/advance. Would it be possible to formulate all of this independently of the application and particular CRDT, together with corresponding correctness theorems?
"Independently of the application and particular CRDT"? I don't know, we might have to think through how that would work for every CRDT. Do you have any personal favorites that would be worth thinking through?
For registers (eg in a variable, dictionary, hash map or array where indexes never change), you could implement a similar algorithm incredibly easily by just doing the version comparison operation on the graph. (The current value is the value set in the graph's frontier.) The retreat / advance optimisation isn't needed at all for registers.
For a list - for example, a list of layers in photoshop - we might need something more complex, since layers can be inserted / deleted like text and as a result the index of subsequent items changes. But layers can also be reordered - and that requires some thought. For rich text, there's an approach that I think would work but I haven't implemented it yet.