3 ms·

@raphlinus, fantastic work! I'd love to connect because I am also one of those people who has been working on CRDT/OT algorithms for a couple years now. I wound

@raphlinus, fantastic work! I'd love to connect because I am also one of those people who has been working on CRDT/OT algorithms for a couple years now. I wound up building a custom database because of it, haha. My approach (not finished) is to use linked lists and tombstones. I found index transformations to not be provably correct in an arbitrary P2P system because it always required a document root. Here is a (terrible terrible) demo of the linked list approach: https://www.youtube.com/watch?v=rci89p0o2wQ https://www.youtube.com/watch?v=rci89p0o2wQ . What are your thoughts on your approach handling rich text? (document nesting) Would love to chat more, mark [AT] gundb [DOT] io

raphlinus 10y ago
Yes, let's connect offline. I have thought some about rich text, but haven't implemented anything yet. My general thinking is that attribute spans lend themselves well to the OT model, but trees do not. The classic example is if you have three words, user A bolds the first two, and user B italicizes the last two. With spans, they just partially overlap, which is fine, but with trees you have an ambiguity. Representing certain kinds of document structure (like nested bullet lists) is not obvious with spans. I want to explore the combination of a marker representing "beginning of tree" and a span, and define transformations in and out of tree form that would be robust to concurrent edits. However, this is all just ideas at this point.
- sjansen 10y ago
  Since you've been deep diving into OT, you've probably already seen: http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation http://www.codecommit.com/blog/java/understanding-and-applyi... But just in case you haven't, it has a nice high level overview of how Google Wave implemented rich text on a tree using annotation boundaries.
- marknadal 10y ago
  Nice pun ;) . I couldn't find your email address, so you'll have to shoot me one. Several years ago I got rich text working just fine by using a deterministic HTML sanitizer/serializer - however, the hilarious thing was, the constant switch between hard space and soft space ruined it. So everything worked... except spaces, which wasn't going to fly. I think the graph approach you mention in the article will be the winner, though. Trees require too many transformations it doesn't seem efficient. :/
- amk_ 10y ago
  Have you looked at the Quill delta format? https://quilljs.com/guides/designing-the-delta-format/ https://quilljs.com/guides/designing-the-delta-format/
  - raphlinus 10y ago
    I've heard of Quill but hadn't seen that document. Looks like interesting reading, thanks!

raphlinus 10y ago

Yes, let's connect offline. I have thought some about rich text, but haven't implemented anything yet. My general thinking is that attribute spans lend themselves well to the OT model, but trees do not. The classic example is if you have three words, user A bolds the first two, and user B italicizes the last two. With spans, they just partially overlap, which is fine, but with trees you have an ambiguity. Representing certain kinds of document structure (like nested bullet lists) is not obvious with spans. I want to explore the combination of a marker representing "beginning of tree" and a span, and define transformations in and out of tree form that would be robust to concurrent edits. However, this is all just ideas at this point.

sjansen 10y ago
Since you've been deep diving into OT, you've probably already seen: http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation http://www.codecommit.com/blog/java/understanding-and-applyi... But just in case you haven't, it has a nice high level overview of how Google Wave implemented rich text on a tree using annotation boundaries.
marknadal 10y ago
Nice pun ;) . I couldn't find your email address, so you'll have to shoot me one. Several years ago I got rich text working just fine by using a deterministic HTML sanitizer/serializer - however, the hilarious thing was, the constant switch between hard space and soft space ruined it. So everything worked... except spaces, which wasn't going to fly. I think the graph approach you mention in the article will be the winner, though. Trees require too many transformations it doesn't seem efficient. :/
amk_ 10y ago
Have you looked at the Quill delta format? https://quilljs.com/guides/designing-the-delta-format/ https://quilljs.com/guides/designing-the-delta-format/
- raphlinus 10y ago
  I've heard of Quill but hadn't seen that document. Looks like interesting reading, thanks!