4 ms·

If anyone’s interested, I wrote a long article a few months ago on (what I believe to be) the ultimate string CRDT, among other things: http://archagon.net/blog

If anyone’s interested, I wrote a long article a few months ago on (what I believe to be) the ultimate string CRDT, among other things: http://archagon.net/blog/2018/03/24/data-laced-with-history/ http://archagon.net/blog/2018/03/24/data-laced-with-history/ I really, really love the work that Levien and Hume have put into the Xi CRDT, and how open they’ve been with their research. IMHO, though, it’s a bit too “academic” and clever for any sort of general purpose use, though it may well be ideally suited for its stated purpose. There even appears to be a limit to the amount of rewinding you can do, which points to O(n^2) complexity for conflict resolution: a huge problem for offline-first development, where concurrent timelines don’t really have any limit on the length of their diverging histories. (I might be mistaken about this—please correct me if I’m wrong.) Still a very satisfying algorithm, though! You can see more of Raph Levien’s thinking here: https://medium.com/@raphlinus/towards-a-unified-theory-of-operational-transformation-and-crdt-70485876f72f https://medium.com/@raphlinus/towards-a-unified-theory-of-op...

trishume 8y ago
The current implementation definitely has some parts with suboptimal complexity, but at the time of design we had plans to address all of them. I just didn't have sufficient time (or productivity?) in my internship to implement them all. For example a lot of the things that are currently lists can be replaced with ropes of the same type Xi uses for text.
- wenc 8y ago
  This is pretty impressive work for an undergrad internship.
  - raphlinus 8y ago
    Word.
repsilat 8y ago
> offline-first development, where concurrent timelines don’t really have any limit on the length of their diverging histories Is there really great utility in automatically merging wildly divergent documents? Being able to send your queued changes and agree on a new state of the world is lovely, but for most of the circumstances I can imagine the ideal new "state of the world" is "please fix this merge conflict", not "here's my best guess at a reasonable state based on the semantics of some data structure." Maybe it's domain specific. Maybe in code you want merge conflicts and in some kinds of rich text docs you just want a best-guess auto-merge. Even then, though, I think it would depend a lot on what the document is for. Maybe blog posts and company culture docs should get auto-merge and legal contracts should get merge conflicts.
- deleted 8y ago
  [deleted]
- kybernetikos 8y ago
  I agree with this. The correct way of resolving conflicts is different depending on both the semantics of the document and the context in which the conflict arose. For example, I think the CRDT approach is probably applicable to most examples of interactive editing, where incorrect conflict resolutions will happen near a point of focus for one of the editors and can be quickly and easily resolved. If you have wildly divergent documents however (again depending on the document type itself), this is not really the same case, and it's much more likely that a human will need to create a resolved document by consulting the two parent documents.
- kd5bjo 8y ago
  Lots of people collaborate by emailing files to each other, and do version control by saving under a different filename every time. Using CRDTs as an on-disk file format can make these workflows less annoying, by working with changes instead of differences: the same advantage that Git's 3-way merge algorithm has over Subversion's 2-way merge.
- archagon 8y ago
  Yes, there is great utility in this approach! For one, most concurrent text editing, rich or not, is actually quite easy to merge in 99% of cases. But even that aside, when you have data structures or document formats that don't ever have to resolve conflicts—or, more accurately, when conflict resolution becomes something that's naturally done in app-space, on the edges, and not as part of the network layer—then you open up the possibility of offline-capable, collaborative apps that require zero coordination between nodes. A node with changes only has to deliver their content to interested servers and peers, not engage in lengthy conversations about who has the definitive version, whether somebody has to revert, etc. You could build a Google Docs clone that synced entirely over Dropbox! And in any case, the "merge" part would still be up to the app. The data structures will always be able to merge, sure, but the app could still throw up a dialog box on wildly divergent changes saying, "Hey, some crazy stuff happened here—want to look it over and commit manually?" (Where "commit" means generating new changes to overwrite any undesired changes, since it's not possible to literally undo.) You could argue that we've simply implemented ad-hoc coordination protocols in the app layer at that point, but IMO, that's exactly where they belong in cases where there's no authoritative store for your data. (Which is really the case with mobile, offline-first development.)
xtagon 8y ago
Hey I just wanted to say thanks for this article. I'm interested in CRDTs but the papers are a little over my head, so it's nice to be able to step through your examples in detail.
- archagon 8y ago
  Glad you found it useful!
lewisjoe 8y ago
> IMHO, though, it’s a bit too “academic” and clever for any sort of general purpose use, though it may well be ideally suited for its stated purpose Exactly my thoughts. Looks like all the improvements in the OT/CRDT academics - is only useful to make plain string editors (like code editors and plain text editors). I maybe wrong or in a completely different page even. I'd like to see these improved algorithms applied to full featured rich text editors, with styles, tables, TOC sections, etc. They have a completely different set of challenges and I'd like to see how these improvements cater to those. For example the non-code editors like Google Docs & Zoho Writer still use a decade old OT algorithms and seem to do just fine. Not a skepticist here. Just curious how CRDT and the latest collaboration techniques will improve making rich text editors (I'm in the business of making one)
- dunham 8y ago
  Apple’s Notes.app uses CvRDTs (I know this from figuring out the data format). For attributed text, they’re using something homegrown that they’re calling “topotext”. It’s somewhat similar to RGA/Causal tree, but they’re maintaining a digraph (unnecessarily?) and I suspect the conflict resolution isn’t quite right (doesn’t seem to do newest first). But for the sake of discussion, it’s a list of characters with lamport timestamps and a tombstone flag. On top of this each character has a separate lamport time stamp for the attributes. This appears to act as a LWW register, per character. (So a conflicting attribute mutation would pick one users state and an insert conflicting with a embolding a range would not pick up the bold, but close enough?) (On disk, runs of increasing clock are stored as one node, with a length, and the resulting text and attribute runs are stored separately from the CRDT data.) A table is treated as an attachment in the main text (attributes on a placeholder character point to it). It is also encoded as a CRDT. (They compose CRDTs for maps, registers, etc here.) It is modeled as an ordered set of row ids, an ordered set of column ids, and a map of column id -> row id -> topotext. This is needed to preserve the semantics of adding/removing/ordering columns and rows in the face of conflicts. Drawings are also stored as a CRDT. (Sorry if this is terse or confusing, I’m typing on mobile.)
  - archagon 8y ago
jxub 8y ago
Another explanation on CRDTs with a broader scope, can be found here: https://github.com/ljwagerfield/crdt https://github.com/ljwagerfield/crdt. There's also this conference talk by Arnout Engelen: https://www.youtube.com/watch?v=9xFfOhasiOE https://www.youtube.com/watch?v=9xFfOhasiOE

trishume 8y ago

The current implementation definitely has some parts with suboptimal complexity, but at the time of design we had plans to address all of them. I just didn't have sufficient time (or productivity?) in my internship to implement them all. For example a lot of the things that are currently lists can be replaced with ropes of the same type Xi uses for text.

wenc 8y ago
This is pretty impressive work for an undergrad internship.
- raphlinus 8y ago
  Word.

repsilat 8y ago

> offline-first development, where concurrent timelines don’t really have any limit on the length of their diverging histories Is there really great utility in automatically merging wildly divergent documents? Being able to send your queued changes and agree on a new state of the world is lovely, but for most of the circumstances I can imagine the ideal new "state of the world" is "please fix this merge conflict", not "here's my best guess at a reasonable state based on the semantics of some data structure." Maybe it's domain specific. Maybe in code you want merge conflicts and in some kinds of rich text docs you just want a best-guess auto-merge. Even then, though, I think it would depend a lot on what the document is for. Maybe blog posts and company culture docs should get auto-merge and legal contracts should get merge conflicts.

deleted 8y ago
[deleted]
kybernetikos 8y ago
I agree with this. The correct way of resolving conflicts is different depending on both the semantics of the document and the context in which the conflict arose. For example, I think the CRDT approach is probably applicable to most examples of interactive editing, where incorrect conflict resolutions will happen near a point of focus for one of the editors and can be quickly and easily resolved. If you have wildly divergent documents however (again depending on the document type itself), this is not really the same case, and it's much more likely that a human will need to create a resolved document by consulting the two parent documents.
kd5bjo 8y ago
Lots of people collaborate by emailing files to each other, and do version control by saving under a different filename every time. Using CRDTs as an on-disk file format can make these workflows less annoying, by working with changes instead of differences: the same advantage that Git's 3-way merge algorithm has over Subversion's 2-way merge.
archagon 8y ago
Yes, there is great utility in this approach! For one, most concurrent text editing, rich or not, is actually quite easy to merge in 99% of cases. But even that aside, when you have data structures or document formats that don't ever have to resolve conflicts—or, more accurately, when conflict resolution becomes something that's naturally done in app-space, on the edges, and not as part of the network layer—then you open up the possibility of offline-capable, collaborative apps that require zero coordination between nodes. A node with changes only has to deliver their content to interested servers and peers, not engage in lengthy conversations about who has the definitive version, whether somebody has to revert, etc. You could build a Google Docs clone that synced entirely over Dropbox! And in any case, the "merge" part would still be up to the app. The data structures will always be able to merge, sure, but the app could still throw up a dialog box on wildly divergent changes saying, "Hey, some crazy stuff happened here—want to look it over and commit manually?" (Where "commit" means generating new changes to overwrite any undesired changes, since it's not possible to literally undo.) You could argue that we've simply implemented ad-hoc coordination protocols in the app layer at that point, but IMO, that's exactly where they belong in cases where there's no authoritative store for your data. (Which is really the case with mobile, offline-first development.)

xtagon 8y ago

Hey I just wanted to say thanks for this article. I'm interested in CRDTs but the papers are a little over my head, so it's nice to be able to step through your examples in detail.

archagon 8y ago
Glad you found it useful!

lewisjoe 8y ago

> IMHO, though, it’s a bit too “academic” and clever for any sort of general purpose use, though it may well be ideally suited for its stated purpose Exactly my thoughts. Looks like all the improvements in the OT/CRDT academics - is only useful to make plain string editors (like code editors and plain text editors). I maybe wrong or in a completely different page even. I'd like to see these improved algorithms applied to full featured rich text editors, with styles, tables, TOC sections, etc. They have a completely different set of challenges and I'd like to see how these improvements cater to those. For example the non-code editors like Google Docs & Zoho Writer still use a decade old OT algorithms and seem to do just fine. Not a skepticist here. Just curious how CRDT and the latest collaboration techniques will improve making rich text editors (I'm in the business of making one)

dunham 8y ago
Apple’s Notes.app uses CvRDTs (I know this from figuring out the data format). For attributed text, they’re using something homegrown that they’re calling “topotext”. It’s somewhat similar to RGA/Causal tree, but they’re maintaining a digraph (unnecessarily?) and I suspect the conflict resolution isn’t quite right (doesn’t seem to do newest first). But for the sake of discussion, it’s a list of characters with lamport timestamps and a tombstone flag. On top of this each character has a separate lamport time stamp for the attributes. This appears to act as a LWW register, per character. (So a conflicting attribute mutation would pick one users state and an insert conflicting with a embolding a range would not pick up the bold, but close enough?) (On disk, runs of increasing clock are stored as one node, with a length, and the resulting text and attribute runs are stored separately from the CRDT data.) A table is treated as an attachment in the main text (attributes on a placeholder character point to it). It is also encoded as a CRDT. (They compose CRDTs for maps, registers, etc here.) It is modeled as an ordered set of row ids, an ordered set of column ids, and a map of column id -> row id -> topotext. This is needed to preserve the semantics of adding/removing/ordering columns and rows in the face of conflicts. Drawings are also stored as a CRDT. (Sorry if this is terse or confusing, I’m typing on mobile.)
- archagon 8y ago

jxub 8y ago

Another explanation on CRDTs with a broader scope, can be found here: https://github.com/ljwagerfield/crdt https://github.com/ljwagerfield/crdt. There's also this conference talk by Arnout Engelen: https://www.youtube.com/watch?v=9xFfOhasiOE https://www.youtube.com/watch?v=9xFfOhasiOE