Why CRDT didn't work out as well for collaborative editing xi-editor • Hacker News Board

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

#31

Post by lucb1e » Sat, May 11, 2019, 9:27 PM UTC

laughinghan wrote: post #30

lucb1e wrote: 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 se…

> it needs to result in a consistent state in both people's editors

Ah, that makes sense :). Stupid question indeed.

I figured the server is just the authority and whatever order it arrives there is the truth. But we only send deltas (we must, because how else will the client still know where to put the cursor after applying a new version) and so we can't use that. Makes sense.

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

#32

Post by braythwayt » Sat, May 11, 2019, 9:30 PM UTC

lucb1e wrote: 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…

Well (strokes grey beard), before we talk about offline support, we should consider that there are two kinds of "online editing."

The first kind of "online editing" is where you make a request to a server, and nothing happens until the server acknowledges it and sends you an approval. That's synchronous.

The second type of "online editing" is where you have an independent process in your browser or client, and it communicates asynchronously with a server, while simultaneously allowing you to edit a local model of the data.

In the first case, we really need an editor to send every keypress to the server and wait for a response.

In the second case, we really are talking about the browser or local app or whatever being offline, it just synchronizes very frequently with the server.

I think that the moment you want to support typing faster than the round trip to the server, you are already talking about offline editing.

And in most cases, yes you do want to support typing faster than teh round trip to the server, because what works in an urban area with high-speed internet becomes comically unusable in low-bandwidth and low-latency environments.

---

So... I suggest that we almost always want to design for "offline editing," it's just that we don't always imagine someone writing an essay on a weekend camping trip, then synchronizing when they get back to the office on Monday.

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

#33

Post by lucb1e » Sat, May 11, 2019, 9:31 PM UTC

k__ wrote: post #24

lucb1e wrote: 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…

In our company, we work with a small team on each pentest, and we do have concurrent edits in the same file quite regularly. One example is going through the network scan results at the beginning of a test: one person works from the top, the other from the bottom, and frequently, we will be editing the file at the same time because we are just getting an overview of the infrastructure and picking interesting targets. Locking the whole file would actually be cumbersome for us.

But I agree that locking sounds like a fairly low-tech solution to reliably solve the issue, though I would do it on row level (or perhaps the current row plus one above and below). The way I see this work is that your client will automatically fetch a lock on the row where your cursor is placed, and you can type at will. If you are inactive, your client could automatically release the lock. Most of the time you're not working on the exact same line as someone else anyway (two persons one sentence, feels a little like trying to type with two persons on one keyboard).

Edit: In a sibling thread, u/espadrine raised a good point:

> what if concurrently someone inserts Enter on line 3? Executing "line 9 […] insert " must not be done on line 9.

I guess my idea of line locking may not work after all. Or at least, we would have to change "line number" to some identifier that can not be modified by an edit.

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

#34

Post by marknadal » Sat, May 11, 2019, 9:40 PM UTC

raphlinus wrote: post #25

marknadal wrote: post #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…

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.

That is what I thought, though when I read your sections titled "Actual collaborative editing is a lot harder" and "CRDT is a tradeoff" it seemed to suggest otherwise particularly with this comment:

"The flip side of the tradeoff is that you have to express your application logic in CRDT-compatible form"

Previously I assumed this was speaking of xi, but it sounds like this was meant generically (not specific to xi)?

I am curious now, it seems like the decision isn't a matter of CRDTs not working out (technically), and more a matter of the amount of effort not being worth it compared to other more synchronous approaches?

Absolutely the right call to make. Though, the last thing we want is people giving up on CRDT research which is how the hackernews title reads "CRDTs not working". So I was just trying to clarify things for future audience.

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

#35

Post by espadrine » Sat, May 11, 2019, 9:50 PM UTC

OJFord wrote: post #27

lucb1e wrote: 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!

To make it more obvious: what if concurrently someone inserts Enter on line 3? Executing "line 9 […] insert " must not be done on line 9.

Worse, divergence is often invisible! Proof of convergence is hard!

More generally, the problem of client-side sync is a hard one, whatever the product: the client has a partial view of the data, and its UI must not show contradictory information. You want your online video game to extrapolate positions to avoid lag. You want your bank account page to have the balance match that after the list of transactions listed below. As we move away from webpage-based navigation (aka "reload everything on every operation") to PWAs, authors get more complex requirements.

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

#36

Post by kahnjw » Sat, May 11, 2019, 9:58 PM UTC

coldtea wrote: post #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).

Collaborative editing is very difficult to implement in a pre-existing codebase. Decisions made during the initial design will be prohibitive to just bolting on collaborative editing in the future.

To me, xi seems like an aspirational project, so this seems like the perfect place to take some time and design for these features up front.

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

#37

Post by lucb1e » Sat, May 11, 2019, 9:59 PM UTC

braythwayt wrote: post #32

lucb1e wrote: 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…

Well (strokes grey beard), before we talk about offline support, we should consider that there are two kinds of "online editing." The first kind of "online editing" is where you make a request to a server, and nothing happens until the server acknowledges it and sends you an approval. That's synchronous. The second type of "online editing" is where you have an independent process in your browser or client, and it com…

> we almost always want to design for "offline editing,"

Fair enough, a one-size-fits-all solution is ideal. Offline support would be great, especially when traveling in a country like Germany. But I would already be happy if we had a good collaborative editor without offline support before we have a good collaborative editor and offline support. Right now, all the options I know of are all either web-based and licensed (Confluence/CKEditor5), just web based and really basic (etherpad), really basic and occasionally unstable (gobby+infininote), or some tech demo alpha version.

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

#38

Post by munificent » Sat, May 11, 2019, 10:04 PM UTC

DannyBee wrote: post #13

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…

TL;DR CRDT is completely irrelevant to any of the highlighting/etc stuff Most highlighters are lexers. Advanced highlighters/folders are parsers. The lexing/parsing that is required for highlighting is easy to make incremental for all sane programming languages. for LL(star) grammars, adding incrementality is completely trivial (i sent patches to ANTLR4 to do this) for LR(k) grammars, it's more annoying but possible…

This is a great comment!

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

#39

Post by munificent » Sat, May 11, 2019, 10:05 PM UTC

lucb1e wrote: post #31

laughinghan wrote: post #30

Earlier quoted context omitted.

> 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 se…

> it needs to result in a consistent state in both people's editors Ah, that makes sense :). Stupid question indeed. I figured the server is just the authority and whatever order it arrives there is the truth. But we only send deltas (we must, because how else will the client still know where to put the cursor after applying a new version) and so we can't use that. Makes sense.

It's not a stupid question if you learned something from it.

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

#40

Post by espadrine » Sat, May 11, 2019, 10:11 PM UTC

coldtea wrote: post #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).

I think (from reading the documentation) an implicit aim of Fuchsia is to treat a device no longer as a holder of documents (a storage medium for photos / messages / candy crush scores) but as a view into a universal storage space.

https://webcache.googleusercontent.com/search?q=cache:S9poew...