From these comnents it seems that OT requires a central server while CRDT can have a far more flexible topology. Is this true? And don’t we have robust implementations of CRDT for simple trees?
Why CRDT didn't work out as well for collaborative editing xi-editor
61–70 of 86 posts
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#62From these comnents it seems that OT requires a central server while CRDT can have a far more flexible topology. Is this true? And don’t we have robust implementations of CRDT for simple trees?
No, OT can handle decentralization without issues. It’s just usually far more desirable to centralize it.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#63Earlier quoted context omitted.
I think the assertion is that the edits are not distributed. Instead, an intent to edit is sent to a central server which forces them to be serialized or rejects them. It is not merging distributed edits. I'm not sure if this is a) the assertion or b) correct/relevant.
This is incorrect. Edits are made locally and sent to the server. The server merges the edit with any edits it received in the meantime from other clients. So the server serializes the rebased edits.
I'm not sure this is disagreeing with me. If a single central server/service is serializing and rebasing the edits, that is what I took the assertion to be.
Decentralized world be the clients communicating their edits to each other.
It can be confusing, as github is a centralized service for git, a decentralized protocol. So, much of the terminologies get blurred.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#64Earlier quoted context omitted.
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…
Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed…
> Instead of batch compiling artifacts to disk like its 1970 [...]
I am delighted to see people discussing this. Batch orientation made sense in a very resource-constrained era. But at this point we have more RAM and CPU than we know what to do with. It seems so obvious to me that the correct solution is to prioritize developer experience and keep everything hot.
My single biggest barrier to developing faster is the latency between making a change and seeing what that does to the test results. I would like that to be well under a second. Given the cost of programmer time, I could happily throw money at RAM and CPU. But standard, batch-oriented tools won't take advantage of it 99% of the time.
I think there's a revolution in developer experience out there, and I really want to see it happen.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#65> Indeed, the literature of CRDT does specify a mathematically correct answer. But this does not always line up with what humans would find the most faithful rendering of intent. This is a very salient point that anyone thinking of using CRDTs to "solve" synchronization in an user-facing application needs to take into consideration. Yes, CRDTs will guarantee that clients converge to an identical, mathematically "cons…
This really is the most important thing to get from all of this. In an editor the users can see any bad outcomes and correct them. In, say, a database system, bad outcomes can be much more problematic.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#66At 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…
Mosh has this idea that you can keep typing and sending asynchronously even though you need the ACKs to find out what really happened, then when you get them you just redraw accordingly. Humans won't type too fast for too long, so eventually there will be time to catch up and let the user see what actually happened. The key is to distinguish client-side speculative outcomes from actual outcomes. Imagine that the text you're typing is made reverse-video, or a different color (subject to color blindness constraints) to indicate speculative (as-yet-unacknowledged) text.
That is, I think humans can be part of the async system and understand that what they're typing isn't committed yet.
Sometimes when I type I don't even look at the screen or the keyboard for a bit -- entire sentences even. Less so with code, naturally. When I do this I do have to eventually look at what I actually entered, because I might not have noticed some typo, say. I just did that for this entire paragraph. I want to believe that I'd handle speculation in the UI just fine.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#67I 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…
> So is the gist of it that OT relies on central servers and they all use OT rather than CRDT?
You are right. I'd take shot at blowing out the why part. Practically, real-time collaboration apps can be categorized into two:
#1 The document editors, which stores information on the cloud. I'll refer these as document editors henceforth.
#2 The ones that doesn't need a thick server, except for broadcasting edits. Like plain text editors and code editors. I'll refer these as code editors for simplicity sake.
Both have a slightly different set of problems.
Document editors, usually have a slightly richer document representation schema (since most of them are rich text documents anyway). But they have the luxury of a central server. A central server means, now they have the power for good versioning, rollbacks to a consistent state, picking winners and ensuring ordering of edits when syncing large edits.
Code editors, although their doc representation is usually arrays of characters (it could be strings, ropes, or whatever but essentially just a set of characters), these don't have the luxury of a central server that could decide a winner when concurrent edits take place. This means the clients have to be very intelligent and converge to the same representation no matter how out-of-order the edits arrive.
Now coming back to the two algorithms camps - OT & CRDT:
The general outlook is that, OT - while being simple, they have this classic TP2 problem that would make it harder to arrive at a consistent state eventually - without a help from a central server. The alternative is to have a complicated system, almost as complicated as CRDTs. (More about this can be read through the Internet. If anybody's interested I'll post links to stuff I've read through)
CRDT - CRDT have (or maybe had?) a strong reputation of being efficient at arriving at a consistent state with out of order edits. They can do it, because basically no characters in a CRDT document is deleted anyway (they are just marked deleted and are termed tombstones). So no information loss, which means a clever algorithm can write a function to easily arrive at a consistent state at each site. This means, a central server is now only optional.
If I didn't lose you until now, you'd have intuitively guessed why document editors, tended to always pick OT and code editors prefer CRDT over OT.
This is complete oversimplifications and certainly there's a ton of things I left out for simplicity sake.
Source: I'm in the business of building a powerful Google Docs alternative, a word processor that runs on the browser: https://writer.zoho.com (Zoho Writer)
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#68I 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...
Stern Brocot is a better way to do fractional indexing (pathological cases are not aligned with common uses cases like putting something to the front).
https://en.m.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree?wp...
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#69Earlier quoted context omitted.
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…
Oh wow, cool! I made a simple proof-of-concept realtime PEG parser a couple years ago, which ingests text OT/CRDT operations ("insert at position X", etc) and invalidates & recalculates the compiler output by invalidating all overlapping ranges and recalculating from the root. My implementation is way slower than I expected it to be - though I'm sure you could use a lot of tricks from well optimized parsers to speed…
But, this is a hard thing to do, the compiler code will have to be organized in a different way, probably the language should be designed specifically towards this end. And the compiler code will be more brittle for sure and will probably be slower for batch compiles.
Most languages do already support ok-fine grained recompiles (at the module level) and it's just many linkers that are slow (I keep hearing from people that this need not be). And actually some of them already do something that is called "incremental linking".
Even C compilers regularly compile 100K+ LOC/second, so I think there's not much to be gained here. Yes, complicated C++ can be slow to compile. Maybe we shouldn't write compliated C++ code to begin with? In the end, batch compile performance also matters.
Re: Why CRDT didn't work out as well for collaborative editing xi-editor
#70I 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…
Very interesting and informative. But I suppose what the user really wants is the next step: not just incremental parsing, but also incremental compilation (or at least the error-checking part of the compilation process).