3 ms·

In general, I've read that OT tends to be very complicated to get right, which is why only a few libraries implement it. If you can use what's called a CRDT, yo

In general, I've read that OT tends to be very complicated to get right, which is why only a few libraries implement it. If you can use what's called a CRDT, your life will be easier, but there are fewer data structures that are supported. Aral Balkan gave a talk on OT vs a CRDT called WOOT for text editing[1] that I found really helpful. If you want more of the nitty-gritty on some of the different types of CRDT, there's fairly readable paper on the topic[2]. [1] https://www.youtube.com/watch?v=NSTZ4mIv_wk https://www.youtube.com/watch?v=NSTZ4mIv_wk [2] http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf

aidos 12y ago
That's great information, thank you. The paper looks really interesting - going to take a little while to get through, might start with the video :) I'd also read that it's hard to get right (I think that was in a comment on HN by one of the people who worked on wave/sharejs). In my case I've limited myself to two different flavours of small object with a limited set of fields (instead of a totally generalised system). Most of the algorithms I've seen focus on the text element of the syncing but I'm much more interested in the object / list / field part for my use case. Sharejs actually have a generic system of handling the OT on arbitrary json structures, but I'm not sure how well it works.
- dahjelle 12y ago
  I've not tried it, but you might also be interested in an approach called differential synchronization[1]. Basically, it's just a specific way of passing diffs around to guarantee convergence, though (as far as I can tell) it doesn't guarantee much else (as in do you lose data if a patch can't be applied?). The really nice bits, though, are that it is a simple algorithm and that it can be applied to anything that you have diff/patch algorithms for. [1] https://www.youtube.com/watch?v=S2Hp_1jqpY8 https://www.youtube.com/watch?v=S2Hp_1jqpY8
  - aidos 12y ago
    I already watched that video the other day! Didn't quite get to the end of it but I thought the general idea was interesting. My use case is a little different, and one that OT seems to suit. I have multiple users working on the same documents but they don't want/need to see each other's changes straight away. They perform a number of operations and then eventually save. When they save I'd like to propagate that that history to the other user(s) that haven't saved yet. It feels like OT works there - you have two threads of history and you need to rebase the uncommitted one on top of committed one. Maybe I'm coming at the problem wrong, but it feels like something that could work quite well as a pattern in general.
pjc50 12y ago
I'm looking at trying to build something using CRDT; I've had my eye on the field for a while and it seems like by far the best solution. Yes, you give up generality. But in exchange you get a more natural system with fewer strange edge cases that has good performance and won't lose data under pressure.
- josephg 12y ago
  OT also won't lose data under pressure. The biggest downsides of CRDTs are that your data ends up much bigger (although usually by a constant multiple), and nobody has figured out how to edit JSON documents using CRDTs yet. Its not all that surprising that CRDTs will be larger - imagine a stream of operations happening to a document (think about them like tiny git commits, if that helps). You can end up with a lot of changes for a small document (tens of thousands of changes for a single page of text isn't unheard of). CRDTs in effect embed the history of operations into the document, while OT stores them separately. As such, with OT you can eventually migrate the operation log to secondary storage (or throw it away). You can never really do that with CRDTs. The JSON problem is harder, and obviously very important for realtime web apps that do more than text editing. Decent CRDTs will be trivial to add to ShareJS when they're ready.

aidos 12y ago

That's great information, thank you. The paper looks really interesting - going to take a little while to get through, might start with the video :) I'd also read that it's hard to get right (I think that was in a comment on HN by one of the people who worked on wave/sharejs). In my case I've limited myself to two different flavours of small object with a limited set of fields (instead of a totally generalised system). Most of the algorithms I've seen focus on the text element of the syncing but I'm much more interested in the object / list / field part for my use case. Sharejs actually have a generic system of handling the OT on arbitrary json structures, but I'm not sure how well it works.

dahjelle 12y ago
I've not tried it, but you might also be interested in an approach called differential synchronization[1]. Basically, it's just a specific way of passing diffs around to guarantee convergence, though (as far as I can tell) it doesn't guarantee much else (as in do you lose data if a patch can't be applied?). The really nice bits, though, are that it is a simple algorithm and that it can be applied to anything that you have diff/patch algorithms for. [1] https://www.youtube.com/watch?v=S2Hp_1jqpY8 https://www.youtube.com/watch?v=S2Hp_1jqpY8
- aidos 12y ago
  I already watched that video the other day! Didn't quite get to the end of it but I thought the general idea was interesting. My use case is a little different, and one that OT seems to suit. I have multiple users working on the same documents but they don't want/need to see each other's changes straight away. They perform a number of operations and then eventually save. When they save I'd like to propagate that that history to the other user(s) that haven't saved yet. It feels like OT works there - you have two threads of history and you need to rebase the uncommitted one on top of committed one. Maybe I'm coming at the problem wrong, but it feels like something that could work quite well as a pattern in general.

pjc50 12y ago

I'm looking at trying to build something using CRDT; I've had my eye on the field for a while and it seems like by far the best solution. Yes, you give up generality. But in exchange you get a more natural system with fewer strange edge cases that has good performance and won't lose data under pressure.

josephg 12y ago
OT also won't lose data under pressure. The biggest downsides of CRDTs are that your data ends up much bigger (although usually by a constant multiple), and nobody has figured out how to edit JSON documents using CRDTs yet. Its not all that surprising that CRDTs will be larger - imagine a stream of operations happening to a document (think about them like tiny git commits, if that helps). You can end up with a lot of changes for a small document (tens of thousands of changes for a single page of text isn't unheard of). CRDTs in effect embed the history of operations into the document, while OT stores them separately. As such, with OT you can eventually migrate the operation log to secondary storage (or throw it away). You can never really do that with CRDTs. The JSON problem is harder, and obviously very important for realtime web apps that do more than text editing. Decent CRDTs will be trivial to add to ShareJS when they're ready.