Why CRDT didn't work out as well for collaborative editing xi-editor

#1

Post by UkiahSmith » Sat, May 11, 2019, 4:19 PM UTC

Why CRDT didn't work out as well for collaborative editing xi-editor
github.com

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#2

Post by hansjorg » Sat, May 11, 2019, 4:42 PM UTC

I'm assuming CRDT refers to conflict free replicated data type: https://en.m.wikipedia.org/wiki/Conflict-free_replicated_dat...

OT, operational transformation: https://en.m.wikipedia.org/wiki/Operational_transformation

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#3

Post by chubot » Sat, May 11, 2019, 5:15 PM UTC

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like:

- Etherpad

- Google docs

- Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html)

- repl.it https://repl.it/site/blog/multi

- figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than text editing)

So is the gist of it that OT relies on central servers and they all use OT rather than CRDT? That was not entirely clear to me.

Looking at the xi analysis, it sounds like "IME" is specific to a desktop application using X (?), so it doesn't apply to any of this web software.

The rest of them seem like they do apply?

Is the problem that you have to pay a "CRDT tax" for every piece of state in the application? I thought the same was true of OT. Don't you have to express every piece of state within those constraints too?

repl.it doesn't seem to have a problem with syntax highlighting or brace matching (try it, it's pretty slick). So is it just that they paid that tax with a lot of code or is there something else fundamentally different about xi vs. repl.it ? Or maybe xi is going for a lot lower latency than web-based editors?

recent thread about OT vs. CRDT that might be interesting: https://news.ycombinator.com/item?id=18191867

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#4

Post by spooneybarger » Sat, May 11, 2019, 5:22 PM UTC

hansjorg wrote: post #2

I'm assuming CRDT refers to conflict free replicated data type: https://en.m.wikipedia.org/wiki/Conflict-free_replicated_dat... OT, operational transformation: https://en.m.wikipedia.org/wiki/Operational_transformation

That's a correct assumption.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#5

Post by macintux » Sat, May 11, 2019, 5:26 PM UTC

chubot wrote: post #3

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like: - Etherpad - Google docs - Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html ) - repl.it https://repl.it/site/blog/multi - figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than…

Another OT/CRDT thread from just a few days ago: https://news.ycombinator.com/item?id=19845776

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#6

Post by jahewson » Sat, May 11, 2019, 5:35 PM UTC

chubot wrote: post #3

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like: - Etherpad - Google docs - Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html ) - repl.it https://repl.it/site/blog/multi - figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than…

OT doesn’t have to depend on central servers, but it is much simpler and less resource-intensive to do it that way. This is what Etherpad, Google Wave and Google Docs do.

As you say, both OT and CRDT come with a “tax” in that you must structure your application’ edits in a way that they can interpret. However, this is easier with OT for the text editing case, as OT uses position based addressing, whereas CRDT is identifier based (I’m assuming this is where the canonical IME issue mentioned comes from - somebody please correct me if I’m wrong).

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#7

Post by tomsmeding » Sat, May 11, 2019, 5:39 PM UTC

Relevant discussion from a couple of days ago: https://news.ycombinator.com/item?id=19845776

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#8

Post by zamalek » Sat, May 11, 2019, 5:41 PM UTC

chubot wrote: post #3

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like: - Etherpad - Google docs - Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html ) - repl.it https://repl.it/site/blog/multi - figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than…

I'm pretty certain that these are OT: Etherpad, Docs, Wave. I've done quite a bit of investigation into these too and I'm convinced that OT is the mathematically inferior, but practically superior model (it is far easier to reason about, which is important because not everyone on your team might read compsci books).

You can abstract OT/CRDT behind a step-locked view model, which should be fine for in-process. IME can be solved in this view model, too, by halting updates to the CRDT/OT between IME entries.

The problem is that, with xi, this would necessitate implementing that view model in each front-end, so there's certainly the "CRDT tax" there. xi is a bit of an oddball.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#9

Post by raphlinus » Sat, May 11, 2019, 5:58 PM UTC

chubot wrote: post #3

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like: - Etherpad - Google docs - Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html ) - repl.it https://repl.it/site/blog/multi - figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than…

Just to answer the IME question, it refers to "Input Method Editor" and is an important problem to solve for all platforms, desktop, mobile, and Web. The API's for IME are often crufty and it's easy to get edge cases wrong. These days, lots of people care because emoji, but formerly it was something that English language speakers tended to ignore.

Re: Why CRDT didn't work out as well for collaborative editing xi-editor

#10

Post by antoncohen » Sat, May 11, 2019, 6:00 PM UTC

chubot wrote: post #3

I don't have much experience in this area, but I'd be interested in an overview of how different pieces of sofware handle the concurrent / multiplayer editing problem, like: - Etherpad - Google docs - Apache / Google Wave (open sourced: http://incubator.apache.org/projects/wave.html ) - repl.it https://repl.it/site/blog/multi - figma https://www.figma.com/blog/multiplayer-editing-in-figma/ (image editing rather than…

Figma has a blog post about it, they use Fractional Indexing.

https://www.figma.com/blog/realtime-editing-of-ordered-seque...