Multi-device editing/syncing with CRDTs

[trishume]

This is a tracking issue/roadmap/plan for how I'm going to proceed with adding the ability to synchronize documents. The tasks below correspond approximately to PRs I plan on writing and the order I plan on doing them.

Edit 2017/08/04: 📝 👁 I wrote a detailed document describing the CRDT

Edit 2017/05/04: Add more detail.
Edit 2017/05/04: Add ideas for optimizing
Edit 2017/07/12: Heavily refactored list to reflect what actually happened, include links to more PRs, and update plan

cc @raphlinus

xi-rope refactoring

Prior to starting this project, the rope and mini-CRDT data structures were mostly undocumented, lightly tested and used some representations that didn't have good time complexity or didn't fit well with turning the mini-CRDT into a full CRDT. The first step of the project was to refactor and replace some of the existing data structures and algorithms and comment and test them.

• Refactor CRDT code and add more doc comments as part of understanding it. #277
• Change the CRDT representation to make it better and undo faster
  • Change it to store tombstones separately rather than the union #297 #299
  • Compute/store deletions/interleaving/from_union in a multiset so that it can be computed both forward and backwards in the revision history. #304 #312
  • Make undo more efficient by carrying the changes forward in a multiset from the undo point instead of rewriting all of history. #313
• Implement Serde serialize/deserialize for Revision, possibly Engine and transitive dependencies. #316
  • Read code and figure out what exactly the state needing synchronization is. Is it just a Vec<Revision>, I think I may also need a Rope like Engine but I haven't read engine.rs yet so I don't quite know how things fit together.
  • If I need a Rope, might need a custom serializer to make it serialize as a string or something, serializing the tree structure like a derive would do seems unnecessary.

Fuchsia last-write-wins prototype

As an initial use case of this functionality, implement syncing using ledger for fuchsia/xi.

• Hook up a Rust binding for the fidl interface for ledger. Gerrit CL #339
• Use the previously built serialization functions to implement basic syncing using ledger. #339
• Add a way to open a synchronized document for demo purposes so it can be edited from multiple Fuchsia instances.

CRDT Merge operation

Implement the merge function on Engine for histories not involving undo.

• Implement a "merge" operation that merges the changes from one engine into another. #348 #350 #351
• Implement framework for describing and running concurrent CRDT merge scenario tests and implement some complex tests #349
• Generate non-colliding revision IDs on all devices using random session IDs #364
• Use both priority and session ID to determine order of inserts #370

Integrate CRDT into Fuchsia

• Get Xi building in the Fuchsia tree. #338 #354 #355 Gerrit CL
• Write a Ledger conflict resolver using this merge operation on Fuchsia to support concurrent editing. #369
• Improve Rust FIDL bindings using futures-rs and Tokio. Done by pair-programming with @raphlinus. Gerrit CL
• Store page ID in Link instead of hashing a hard-coded file name.
• Switch Ledger integration to use futures-rs based FIDL once that is ready.

You can now open Xi on two Fuchsia devices and type into both of them concurrently and they will synchronize and reach a consistent state shortly afterward.

Documentation

• Write a big document describing the specific CRDT used by Xi and explaining how it works. #378
• Write a small document describing how to integrate a CRDT the with Ledger and Fuchsia #380

Improve CRDT robustness and functionality

• Write randomized tests for the merge operation. Possibly using quickcheck tests or fuzz tests. #300
• Support Undo operations in the CRDT
• Use test generator to generate large tests and characterize performance.

Make it fast

The above will have terrible awful scaling properties and will slow to a crawl in many use cases. The next step is to figure out ways to improve the CRDT representation and operations to have better time and space complexity. Some of these ideas are well thought out and are clear wins, others are more speculative half-baked ideas (marked by a "🤔 ").

• Properly compute the common base for merges, currently it always starts from the very first commit. This should be both easy and a huge improvement to merge performance.
• Optimize merge for common simple cases like no new edits on one side, or no edits in common after the base. These won't be that common with conflicts but will be super frequent in the Ledger PageWatcher update case.
• Talk to Ledger team about having side with more revisions be on the left of the merge.
• Store larger Subsets in a rope with an aggregation on number of inserted and deleted characters so that calculations can do things in the middle of the text without being O(n).
• Switch to a multi-key ledger representation, instead of storing everything in a single key. This will improve both running time due to not loading in large changes from ledger, as well as storage use in Ledger.
  • Refactor to make this possible, for example this requires that new changes be merged into the Ledger instead of the current Engine being put in, that will guarantee things are only appended.
  • Optimize the ledger storage serialization of revision history to store segments of history in separate keys, use changed keys in merge to determine common prefix.
  • Store text in ledger as a doubly-linked list of blocks. If a block grows too large it splits, and if too small it merges, but both of these are local operations affecting a constant small number of keys.
• 🤔 Store the revision history in a rope/tree/skip-list to make computing the coordinate transforms O(log n) instead of O(n) for merges and undos. Where n is the size of the history after the undo/common prefix. This would definitely be useful for undo because it would allow an arbitrarily long undo history without significant performance degradation, and would effectively allow us to remove the garbage collector.
• 🤔 In merge, combine transforms that are spatially separate into one Subset so that there are less Subsets to rebase and transform repeatedly in merge. Like #351 but more extreme.

[trishume]

I discussed this a bunch with @raphlinus today and now have a much better understanding of the whole CRDT model and how to proceed. I've included some (very high-res page-bloaty) pictures of the whiteboard from our discussion along with some quick notes. I've edited the main issue body based on the discussion with new items.

cc @cmyr @rkusa since both of you expressed interest in CRDT stuff

Example of a revision history, right column is the deletion set at every revision, identical concurrent deletions (last two) necessitate multi-set (each deleted index also has a count) for reversibility so that undoing/reversing one doesn't un-delete a multi-deleted character. Things along the bottom are state in the engine for the head revision:

top right is the contents of a revision currently:

example of a non-trivial merge (bot-left) and half of a diagram showing correspondence between ops (which include the inserted or deleted string) and revs (which only include index sets and rely on text and tombstone ropes stored in the engine for the head revision):

other half of diagram, plus drawings of how one might efficiently represent histories and ropes as key-values so that only a limited amount of keys/data are changed on update:

example of correspondence between deletion set and function from index to element, with set of non-primes corresponding to function of nth prime:

[rkusa]

Thanks for the update!

I have a question to the first image. Why is the deletion set at line three (ab ins={1} {1}) {1} and not {2}?

Another question regarding the tombstones. Since they are not part of the revision, we only have the most reason tomstone string, right?

I've added the tombstone state to each line of your first example (and also added an additional starting line for the sake of my following question).

(1) 123   del={0, 1, 2}   {0, 1, 2}
      text = "" tombstones = "123"
(2) a     ins={0}         {1, 2}
      text = "a" tombstones = "23"
(3) ab    ins={1}         {1}
      text = "ab" tombstones = "3"
(4) axb   ins={1}         {}
      text = "axb" tombstones = ""
(5) ab    del={1}         {1}
      text = "ab" tombstones = "x"

Is this the correct way of how tombstones are going to work? If yes, when I undo all of these revision ((5), (4), (3), (2) and (1)), how do we know that we have to restore 123 (because 123 it is not in the tombstone string anymore)?

[trishume]

The leftmost deletion set, also known as from_union or the interleaving, is the characters deleted to get the final string. To be clear in the whiteboard diagram, the rightmost column is things that can be computed at the current time after all the revisions based on information at the bottom rather than stuff stored in a revision or computed at that time. So since the union string at the bottom is "axb", the deletion set to get "ab" is {1}.

Let me rewrite your example to be correct. Below the first line is in the revision, and the next line is the contents of Engine just after that revision is made. I included both the text,tombstones representation and the union representation, but in reality only one would be included. For the union, from_union is just the characters to delete to get text, and for text,tombstones you can get the union by using from_union to determine an interleaving. You also need from_union to figure out indexes to put in revisions since the indexes are based on the union string. The text,tombstones representation is an optimization of union that is more complex but also more efficient. I also included back_computed_deletions_from_6_union which is not something known at each time but something that can be computed at the very end, possibly for undo processing or something, it corresponds to the leftmost column of the drawing, I don't know if it is actually useful, it's just something we talked about to make sure I was understanding it right.

()   before any revisions are made
      text = "" tombstones = "" union="" from_union={}
      back_computed_deletions_from_6_union = {0,1,2,3,4,5}
(1) ins={0, 1, 2}
      text = "123" tombstones = "" union="123" from_union={}
      back_computed_deletions_from_6_union = {0,1,2}
(2)  del={0, 1, 2}
      text = "" tombstones = "123" union="123" from_union={0,1,2}
      back_computed_deletions_from_6_union = {0,1,2,3,4,5}
(3) ins={0}
      text = "a" tombstones = "123" union="a123" from_union={1,2,3}
      back_computed_deletions_from_6_union = {1,2,3,4,5}
(4) ins={1}
      text = "ab" tombstones = "123" union="ab123" from_union={2,3,4}
      back_computed_deletions_from_6_union = {1,3,4,5}
(5) ins={1}
      text = "axb" tombstones = "123" union="axb123" from_union={3,4,5}
      back_computed_deletions_from_6_union = {3,4,5}
(6) del={1}
      text = "ab" tombstones = "x123" union="axb123" from_union={1,3,4,5}

[rkusa]

Now, it makes sense. Thanks a lot for the detailed answer!

[erlend-sh]

Might this become compatible with the CRDT version control system Memo that @as-cii and @nathansobo are working on in xray?

[cmyr]

@erlend-sh These two projects aren't particularly related, so I don't think it makes too much sense to think of compatibility; however my understanding is that Memo is designed to be a standalone system that exposes an API that can be used by any consumer, so supporting it in xi at some point in the future should definitely be possibly. It's certainly an interesting project, and I've been following along with interest. :)