Live data from Hacker News

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

github.com

21–30 of 86 posts

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

#21
TLDR;

CRDTs cannot be "bolted ontop".

----

I really don't like this answer, but it is sadly true - even as an expert in the space (my database https://github.com/amark/gun is one of the few CRDT-based systems out there). And there is a simple reason for this:

Distributed systems are composable, they can be used to build higher-level strongly consistent systems on top. (Note: Sacrificing AP along the way, but then you can have a "tunable" system where each record you save you decide what consistency requirement you need, fast or slow.)

However centralized systems are not composable, you can't go "down" the latter of abstraction by adding more stuff.

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

#22
At the risk of asking a stupid question: is there a reason other than offline support why we bother with conflict resolution algorithms?

Every time concurrent editors come up, one of the main points of discussion is the pros and cons of different possible conflict resolution algorithms. People seem to be spending a lot of time on debating and implementing that. The way I see it, whichever packet reaches the server first gets applied first. Send something like "line 9 column 19: insert ", and when another client whose cursor is on line 15 receives that, it moves the cursor down to line 16 and scrolls the view down one line. Because you can see each other's cursors and selections, it shouldn't be hard to avoid typing in the same place. Unless you have round trip times of multiple seconds (satellite uplinks maybe?), and unless you edit continuously with more than, say, one people per ten sentences, you should hardly ever need it, and if it happens, the person editing will notice within two seconds and just wait a second for the other to finish. It's not as if you can reliably apply edits anyway: as the article already describes, changing a line from ABC to EFG concurrently with someone modifying B to D, does not really have a good outcome. In a more realistic example, it would be changing "its" to "it's" concurrently with changing the word to "that". There is no good solution (the server wouldn't know which person to ignore: the apostrophe inserter or the replacer), so someone will have to resolve it manually anyway, so why bother with complex resolution algorithms? Heck, I'd be fine if my editor would do exclusive locks for the line I'm on before I can start typing.

For slow things like the customer report, internal documents, code, etc., I use something like git. Collaborative editing is (to me) for realtime things like jotting down notes about what I'm working on and looking at what others are working on right now, where even a proper revision control system is too cumbersome (git pull, vim notes.txt, small edit, :wq, git commit, git push, repeat) because someone might be working on the same thing. In such a case, where I need to work together on a file in real time, I'm not working offline, so this conflict resolution is by definition unnecessary. Is that different from the majority of people that use collaborative editing?

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

#23
@dang, can we edit the title? It's inaccurate. This post is about how the CRDT didn't work for asynchronous editing by automated tools like syntax highlighting, automatic bracket balancing, etc. The post explicitly contrasts those use cases with collaborative editing as a use case that the author didn't implement, but where they think "the CRDT is not unreasonable".

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

#24
post #22

At the risk of asking a stupid question: is there a reason other than offline support why we bother with conflict resolution algorithms? Every time concurrent editors come up, one of the main points of discussion is the pros and cons of different possible conflict resolution algorithms. People seem to be spending a lot of time on debating and implementing that. The way I see it, whichever packet reaches the server fi…

I never understood this either.

Why not simply lock the file automatically when someone types and unlock it after a few seconds pause.

What do I get from parallel edits? When I finish my stuff and my collaborator isn't finished, we will end up with broken code until they have finished editing.

Sure it is nice to be able to write comments at some place while someone else edits code at another place, but then row-based locking would do the trick too.

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

#25

TLDR; CRDTs cannot be "bolted ontop". ---- I really don't like this answer, but it is sadly true - even as an expert in the space (my database https://github.com/amark/gun is one of the few CRDT-based systems out there). And there is a simple reason for this: Distributed systems are composable, they can be used to build higher-level strongly consistent systems on top. (Note: Sacrificing AP along the way, but then you…

What you say is certainly true, but also not a fair characterization of what I wrote; we deliberately designed xi-editor from the early days to be consistent with the CRDT model (see the "rope science" series for thinking from the very early days).

But yes, if you have an existing editor or application and you try to just add CRDT, there are a lot of things that can go wrong.

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

#26
post #6
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 iden…

xi-editor pioneers a hybrid where "identifiers" are actually the tuple of revision and position. The motivation is to buy back some of the performance edge that OT has because of its use of position. I think if you are going to do CRDT it's pretty compelling, but that's also somewhat orthogonal to the complexity concerns raised in my original post.

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

#27
post #22

At the risk of asking a stupid question: is there a reason other than offline support why we bother with conflict resolution algorithms? Every time concurrent editors come up, one of the main points of discussion is the pros and cons of different possible conflict resolution algorithms. People seem to be spending a lot of time on debating and implementing that. The way I see it, whichever packet reaches the server fi…

> why we bother with conflict resolution algorithms? […] The way I see it, […] Send something like "line 9 column 19: insert ", and when another client whose cursor is on line 15 receives that, it moves the cursor down to line 16 and scrolls the view down one line.

What you describe is (an aspect of) the algorithm you want to do away with!

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

#28
Having a bit of difficulty following this, so I'll break down my understanding of CRDTs and see if someone can help me out.

A CRDT can be thought of as an algebraic structure, consisting of data type D, and a join function. So for all a, b, c in D, it's:

Associative:

  join(a, join(b, c)) == join(join(a, b), c)
Commutative:

  join(a, b) == join(b, a)
Idempotent:

  join(a, a) == a
Partially ordered:

  if join(a, b) == b then a  a) then a == b
  if (a 
So given all of that, I am not sure why the example in the article holds. I assume it's a consequence of the partial ordering, but I don't know what the partial ordering is. What's the join operation and what's the data type?

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

#29
Maybe first build a capable editor, with plugins, etc (xi-editor is not that yet) and worry about "collaborative editing" later?

And even for that, I think simply "taking turns" (where users share an editor session, can chat with each other, and can switch on sequentially who gets to actively edit) is enough for 99% of cases, and is not more difficult than mere single-person editing (since there are no conflicts).

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

#30
post #22

At the risk of asking a stupid question: is there a reason other than offline support why we bother with conflict resolution algorithms? Every time concurrent editors come up, one of the main points of discussion is the pros and cons of different possible conflict resolution algorithms. People seem to be spending a lot of time on debating and implementing that. The way I see it, whichever packet reaches the server fi…

> it shouldn't be hard to avoid typing in the same place [...] if it happens, the person editing will notice within two seconds and just wait a second for the other to finish

But if it does happen, it needs to result in a consistent state in both people's editors, right?

> In a more realistic example, it would be changing "its" to "it's" concurrently with changing the word to "that". There is no good solution (the server wouldn't know which person to ignore: the apostrophe inserter or the replacer)

Discarding the apostrophe seems like a good solution to me, what's wrong with it?

As long as, if the replacer hits Undo, "it's" is what is restored. (Not sure if any existing algorithms do so, but I believe it's possible and am intending for the collaborative editor I'm designing to do so. Haven't implemented it yet though, so who knows.)

Post reply on HN