4 ms·

https://github.com/google/xi-editor https://github.com/google/xi-editor uses many similar ideas to implement concurrent editing by plugins and other devices. In

https://github.com/google/xi-editor https://github.com/google/xi-editor uses many similar ideas to implement concurrent editing by plugins and other devices. In fact nathansobo, the author of this post, wrote a summary of some of the work Raph Levien (Xi's primary author) has done on CRDTs, so this is probably not a coincidence. Xi also keeps track of changes using a data structure like Patch. It doesn't use a tree to do so, although we may eventually switch some to use Xi's generic Rope tree data structure. One interesting difference is that Xi always creates another "layer" for every edit and never modifies anything. This leads to lots of layers, but instead of working forwards from a "base text" we work backwards from the current text. So accessing the current text is very fast, and accessing a past snapshot may require mapping in reverse past a small number of edits. They both solve the same problems though, although Xi's approach of layers for every edit also enables seamless multi-device concurrent editing via a full CRDT merge implementation. If you're interested in reading in detail about the approach Xi uses, I wrote a big document about it near the end of my internship working on Xi's CRDT: https://github.com/google/xi-editor/blob/master/doc/crdt-details.md https://github.com/google/xi-editor/blob/master/doc/crdt-det...

archagon 9y ago
Thanks for this! Great writeup. I'm guessing xi's CRDT uses ideas from Raph Levien's work on combining OT and CRDTs? I've only given Raph's papers a cursory read, but there seem to be a lot of similarities and it looks like he was mentoring you. Does it have an official name yet? Incidentally, I've also been working on an in-depth article on a particular CRDT: Victor Grishchenko's Causal Trees[1]. The original paper only uses the data structure for text, but I believe it can be extended to a variety of other data types. In brief, the basic convergent structure is a tree of immutable "atoms". This tree is stored in memory as a DFS in-order traversal. I treat each atom as an atomic operation ("insert char" or "delete char" in case of strings), and thus, every user action involves an O(N) mutation of the tree array to insert the new atom in the correct spot, followed by an O(N) re-read of the array to update the user-facing data. This requires the effect of each atom to be O(1) when read in DFS order, but with strings, this follows naturally. A CT string in memory looks a whole lot like your "union string" with explicit delete ops instead of tombstones, e.g. ["ins D","ins O","ins U","del","ins G"] which parses as DOG in O(N), except each atom does in fact have a unique ID and holds a reference to its causal atom — the character intended to be on its immediate left. (So no need for crazy coordinate transforms!) As with xi, you also get a full revision history which can be garbage collected if needed. My implementation is a work-in-progress, but I've already extended it to basic Bézier drawing and I'm really curious to see how it scales compared to a more OT-like CRDT such as yours. My guess is that CT won't work very well with large files on account of the full O(N) read/write requirement as well as the ~10x memory cost vs. C strings, but on the other hand, it seems that very few other CRDTs can be painlessly tweaked for use with other data types, and this would be a worthwhile tradeoff for me. CT also benefits from a mostly O(N) merge and O(N) past revision viewing, provided you keep to the reconstruct-data-in-linear-time-on-DFS-traversal invariant. Anyway, CRDTs are super cool! Interesting to see them being used in local contexts, but it totally makes sense, especially since consistency w/garbage collection isn't a concern. [1]: https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b... [2]: https://github.com/archagon/crdt-playground https://github.com/archagon/crdt-playground
- trishume 9y ago
  Glad you found my writeup useful, and your CT stuff sounds interesting. You may also find https://github.com/google/xi-editor/issues/250 https://github.com/google/xi-editor/issues/250 interesting, especially the TODO list of optimizations. Yes the Xi CRDT (closest we have to a name) is based on Raph's work, plus some discussions we had and about one week of me standing in front of a whiteboard figuring out how to apply the concepts to doing a merge on Xi's specific CRDT structures. Currently Xi also stores many bytes for each character typed, but one of our planned optimizations is to delta-encode chunks of old revisions. The operations are stored with fields that are designed to delta-encode efficiently so for runs of normal insertions we should be able to get down to ~2 bytes per character.

archagon 9y ago

Thanks for this! Great writeup. I'm guessing xi's CRDT uses ideas from Raph Levien's work on combining OT and CRDTs? I've only given Raph's papers a cursory read, but there seem to be a lot of similarities and it looks like he was mentoring you. Does it have an official name yet? Incidentally, I've also been working on an in-depth article on a particular CRDT: Victor Grishchenko's Causal Trees[1]. The original paper only uses the data structure for text, but I believe it can be extended to a variety of other data types. In brief, the basic convergent structure is a tree of immutable "atoms". This tree is stored in memory as a DFS in-order traversal. I treat each atom as an atomic operation ("insert char" or "delete char" in case of strings), and thus, every user action involves an O(N) mutation of the tree array to insert the new atom in the correct spot, followed by an O(N) re-read of the array to update the user-facing data. This requires the effect of each atom to be O(1) when read in DFS order, but with strings, this follows naturally. A CT string in memory looks a whole lot like your "union string" with explicit delete ops instead of tombstones, e.g. ["ins D","ins O","ins U","del","ins G"] which parses as DOG in O(N), except each atom does in fact have a unique ID and holds a reference to its causal atom — the character intended to be on its immediate left. (So no need for crazy coordinate transforms!) As with xi, you also get a full revision history which can be garbage collected if needed. My implementation is a work-in-progress, but I've already extended it to basic Bézier drawing and I'm really curious to see how it scales compared to a more OT-like CRDT such as yours. My guess is that CT won't work very well with large files on account of the full O(N) read/write requirement as well as the ~10x memory cost vs. C strings, but on the other hand, it seems that very few other CRDTs can be painlessly tweaked for use with other data types, and this would be a worthwhile tradeoff for me. CT also benefits from a mostly O(N) merge and O(N) past revision viewing, provided you keep to the reconstruct-data-in-linear-time-on-DFS-traversal invariant. Anyway, CRDTs are super cool! Interesting to see them being used in local contexts, but it totally makes sense, especially since consistency w/garbage collection isn't a concern. [1]: https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b6dc19f4fd529caab43.pdf https://ai2-s2-pdfs.s3.amazonaws.com/6534/c371ef78979d7ed84b... [2]: https://github.com/archagon/crdt-playground https://github.com/archagon/crdt-playground

trishume 9y ago
Glad you found my writeup useful, and your CT stuff sounds interesting. You may also find https://github.com/google/xi-editor/issues/250 https://github.com/google/xi-editor/issues/250 interesting, especially the TODO list of optimizations. Yes the Xi CRDT (closest we have to a name) is based on Raph's work, plus some discussions we had and about one week of me standing in front of a whiteboard figuring out how to apply the concepts to doing a merge on Xi's specific CRDT structures. Currently Xi also stores many bytes for each character typed, but one of our planned optimizations is to delta-encode chunks of old revisions. The operations are stored with fields that are designed to delta-encode efficiently so for runs of normal insertions we should be able to get down to ~2 bytes per character.