8 ms·

Using CRDTs for multiplayer text editing

204 points by henning 4y ago

rubatuga 4y ago
Yeah CRDTs are pretty annoying for collaborative text editing, even Google Docs doesn't use them. Some companies have switched from CRDTs back to traditional methods.
- nathansobo 4y ago
  We're quite happy with them. Why do you find them annoying?
  - tlb 4y ago
    One common failure mode is that two people start typing at the beginning of the same line, and rather than getting two lines, it alternates characters. At least, Etherpad did this.
    - maxbond 4y ago
      This is a common artifact of operational transforms I believe. Etherpad launched in 2008; CRDTs were proposed in 2011. AFAIK Etherpad used (uses?) OT. Open to correction though, it's been a while since I dug into the differences in these approaches & my memory is imperfect.
    - muxator 4y ago
      Etherpad used Operational Transform, not CRDTs. Source: I have been etherpad's maintainer for two years.
    - josephg 4y ago
      This is called the “interleaving problem”. It shows up with simple list algorithms like fractional indexing. All the main text editing CRDT algorithms around today solve this no problem. (Yjs, automerge, diamond types, etc).
      - nathansobo 4y ago
        We honestly don’t solve it yet, but haven’t found it that big of an issue in practice. Would be curious to see the best resource on it.
        josephg 4y ago
        I remember reading about it in one of Martin Kleppmann’s papers, though I can’t remember which one. It’s an ordering problem that comes from some of the simpler ordering algorithms. For Diamond types I’m using a variant of Yjs’s ordering. But even RGA doesn’t have this problem because each character’s insert location is specified by naming the character immediately to the left when that character was typed. This repository implements a few different list CRDTs using an insertion sort approach, where the algorithm scans for the appropriate location every time an insert happens. This is the scanning function for RGA (automerge’s algorithm): https://github.com/josephg/reference-crdts/blob/fed747255df9d457e11f36575de555b39f07e909/crdts.ts#L401-L459 https://github.com/josephg/reference-crdts/blob/fed747255df9... And this is an interactive visualisation of how diamond types works (which uses Yjs’s algorithm instead), complete with run-length encoding: https://home.seph.codes/public/diamond-vis/ https://home.seph.codes/public/diamond-vis/
        Horusiath 4y ago
        I've described this issue in my blog post together with CRDT variants that address and solve it: https://bartoszsypytkowski.com/operation-based-crdts-arrays-1/#interleaving https://bartoszsypytkowski.com/operation-based-crdts-arrays-... In practice, many CRDT libraries nowadays (eg. Yjs and Automerge) are using structures that don't come with interleaving issues.
      - sureglymop 4y ago
        Has anyone used Yjs in practice? I've tried recently but the docs seem terribly unfinished sadly. And their lacking examples of how to use it for another purpose (other than text editing).
        Horusiath 4y ago
  - maxbond 4y ago
    I'll offer up that I've had a hard time wrapping my mind around them and that in practice it seems like you need to implement a check pointing operation on top of them which is necessarily not conflict-free, or your replication log will expand without bound & eventually overwhelm your system. (Though perhaps not, depending on your problem domain. Not CRDTs but in this interview the engineers discuss a massive, high frequency replication log that they don't checkpoint, which they've been running at scale for years. Though you could also say they implicitly checkpoint every trading day, and they're working on implementing checkpointing. https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...) That being said I would use CRDTs for any greenfield collaboration project.
- paulgb 4y ago
  In addition to OP (nice work, Nathan!), one of the yjs authors has made a pretty in-depth argument that (modern) CRDTs are suitable for human-scale text editing. https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi...
  - nathansobo 4y ago
    Thanks very much!
- maxbond 4y ago
  The first version of Google Docs was written in 2006; CRDTs weren't proposed until 2011, and still seem to be maturing as a technology. So, I don't think this is a reflection on the merits of CRDTs versus operational transforms as much as it is a reflection on the ecosystem and the history of the codebase.
  - josephg 4y ago
    Yep. I’ve been working in the collaborative editing space for over a decade - with both OT algorithms and CRDT algorithms. The modern CRDTs I’ve been developing are significantly faster and smaller than any OT system I made 5+ years ago. Much more complex though. (~3k loc for a good, high performance text crdt merging algorithm, vs 300 loc for a good text OT algorithm.)
    - HWR_14 4y ago
      Sorry, I'm not sure I properly understood OT as an acronym. Did you mean "operational transformation"? Because I thought that OT was method of making operational based CRDTs[0]. But I'm probably wrong in at least one way! Hoping to learn. [0] https://link.springer.com/chapter/10.1007/978-3-662-43352-2_11 https://link.springer.com/chapter/10.1007/978-3-662-43352-2_...
      - throwawaymaths 4y ago
        Quick and dirty: OTs require a centralized controller and a (potentially complicated) merge strategy to shepherd conflicting changes. CRDTs on the other hand apply commutative operations so they don't need be centralized, though nodes that communicate infrequently might get very out of sync
      - josephg 4y ago
        Yes, OT = Operational Transform[1]. Usually the difference is that operational transform algorithms create an ordered global list of all the changes (typically on a centralized server). They flatten operations using a heuristic "transform" function. CRDTs don't reorder the changes, but guarantee that when all changes are merged (in any order) the final result would be the same. For example, MAX() is a complete CRDT merging function. But the distinction gets much more blurry at the edges. You can make OT algorithms which work without a central server, and CRDTs which use operation reordering to guarantee merge consistency. [1] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation
nmlt 4y ago
This webpage crashed my iPad 6 Gen Safari when repeatedly scrolling down without reading (iPadOS 16.1.1). It’s probably just too little memory, but still, isn’t this just a blog post?
- nathansobo 4y ago
  We embeded a lot of videos for animated diagrams. I think we need to disable autoplay, at least on mobile.
- iamnbutler 4y ago
  Apologies, looks like we underestimated how heavy the autoplaying diagrams would be. If you could try again in about 5 minutes and see if you still have the problem I'd appreciate it! Sorry for the hassle.
tym0 4y ago
Has Microsoft published anything about their pairing plug-in for VS Code?
sghosh2 4y ago
Very cool use case for CRDTs! I've seen a bunch of different use cases from other products like https://liveblocks.io/ https://liveblocks.io/ and https://electric-sql.com/ https://electric-sql.com/. It's interesting how CRDTs are now taking hold so much for all these collaborative syncing scenarios. Wonder what's driving the proliferation now given they've been around for awhile?
- nathansobo 4y ago
  I've been interested in them since the early days of Atom, but it's just taken a while for me to develop as an engineer and build a system around the theory that puts them to practical use.
eep_social 4y ago
This reminds me of Oracle’s SCN which blew my mind back in ~2009 when I moved up from mysql home gamer stuff to the corporate world. > Even long edit histories barely compare to the memory savings Zed obtains from not being built with Electron. I got a good chuckle out of this. Speaking of performance, I think it’s I nteresting that ms word and google docs are still using OT rather than CRDT. The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client. Anyone else interested in the background of OT vs CRDT might find this thread useful: https://news.ycombinator.com/item?id=18191867 https://news.ycombinator.com/item?id=18191867
- josephg 4y ago
  > The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client. Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse! Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop: 1. Generates some random changes on some fake "peers" 2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm 3. Assert that the state has converged between the peers I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this. When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word. As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b497e2df8ae4473d1e521d3c3bf2d2/test.ts#L262-L318 https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4... The code is so small it almost fits on my laptop screen.
  - auggierose 4y ago
AlabasterAxe 4y ago
As a Windows user, I'd be pretty concerned about the multiplatform story here. They say that this is MacOS only for now but they intend to eventually ship a Windows App, Linux App and web app. It just sounds like a recipe for a Sketch situation where it's really just a Mac app and web (and other platforms) is a second class citizen.
- nathansobo 4y ago
  We’ve gone to great lengths to abstract out the platform dependencies. Adding a platform right now doesn’t teach us enough for it to be worth it just yet, but we’re seriously planning for it.
- AlabasterAxe 4y ago
  Upon further reading, It sounds like this is being built stop cross-platform technologies (rust/webassembly) so it sounds like I spoke too soon!
jupiterelastica 4y ago
I wonder what happens when an edit can not be delivered to 1+ participant(s). Does an edit need aknowledgements from _all_ participants to be persisted? Is it just dropped?
- codetrotter 4y ago
  In Englebart's system you mean, or in Zed? The appeal of CRDTs is: > 1. The application can update any replica independently, concurrently and without coordinating with other replicas. Along with some other important points. See https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_... The featured article also talks about this in detail.
  - jupiterelastica 4y ago
    In Zed/CRDTs, these two seem synonymous to me since the OP's article is the first I read about CRDTs that I grasped, or so I thought ;) Doesn't the whole process assume that whenever any edit is done (insertion/deleteion/un-/redo) that the edit _eventually_ reaches all participants? So if a single edit is believed to be delivered to all, but actually never made it to a single participant, who resends it? And if it's not resent, then the participants state is inconsistent from now on, no? Edit:autocorrect
    - yazaddaruvala 4y ago
      Because it’s async first, the client can use both push or pull to receive the events. If you’ve used Git you’ve been using a CRDT (with manual pulls and manual merges). A better CRDT would do both automatically.
      - jupiterelastica 4y ago
        So, client that was "offline" can just ask a participant to get the edits from his own last one (aka pull), send out bis own offline edits (push) and resolve from there, I See. Actually, that cleared it up, thank you :)
celeritascelery 4y ago
Raph Levien posted a retrospective about using CRDT’s for collaborative editing in xi-editor here [1]. His conclusion is “I come to the conclusion that the CRDT is not pulling its (considerable) weight. When I think about a future evolution of xi-editor, I see a much brighter future with a simpler, largely synchronous model, that still of course has enough revision tracking to get good results with asynchronous peers like the language server.” [1]https://github.com/xi-editor/xi-editor/issues/1187#issuecomment-491473599 https://github.com/xi-editor/xi-editor/issues/1187#issuecomm...
- maxbrunsfeld 4y ago
  I think that the paragraph that you quoted was in reference to Xi's decision to use CRDTs (and asynchronous communication) for exchanging data between different plugins running in the same instance of Xi. It isn't a comment about the use of CRDTs for collaborative editing, as Zed does.
- infogulch 4y ago
  I noted the same a few months ago when Zed came up in a discussion about Atom, and Raph responded: https://news.ycombinator.com/item?id=31674931 https://news.ycombinator.com/item?id=31674931
throwaway14356 4y ago
if everyone is in the same area one could/should just pretend the client is a terminal(?) https://www.ookla.com/articles/gaming-cities-lowest-latency-2019 https://www.ookla.com/articles/gaming-cities-lowest-latency-... https://www.rtings.com/keyboard/tests/latency https://www.rtings.com/keyboard/tests/latency
infogulch 4y ago
How do the editor CRDTs integrate with source control?
lewisjoe 4y ago
To put it in a different perspective, plain text editing has well-solved CRDT patterns. But, semantic data-structures like rich-text or syntax trees is what's tricky and has unsolved challenges. Peritext[1] is the only one that came close to solving rich-text, but even that one left out important aspect of rich-text editing like handling list & table operations as "work to be done later". For people interested on why it's difficult to build CRDTs for richtext, here's a piece I wrote a year back: https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... Related HN discussion: https://news.ycombinator.com/item?id=29433896 https://news.ycombinator.com/item?id=29433896 [1] https://github.com/inkandswitch/peritext https://github.com/inkandswitch/peritext
- Horusiath 4y ago
  > semantic data-structures like rich-text or syntax trees is what's tricky and has unsolved challenges. Yrs developer here: - Yjs/Yrs have support for formatting attributes[1]. The matter if format attributes conflict resolution behaves as user desired is a subject to discussion (which is a common thing re. CRDTs and their trade offs), but its behaviour is consistent, convergent and algorithm itself works fast. This feature is in fact used in many rich text editors using Yjs bindings. - Embedding non-string elements in text is supported as well. - While syntax trees are not supported out of the box (AFAIK this CRDT is still being researched), Yjs also support XML nodes with attributes and nested children, which may be used for similar effects in some scenarios. [1] https://docs.yjs.dev/api/delta-format https://docs.yjs.dev/api/delta-format
zelphirkalt 4y ago
*Douglas Engelbart (The picture has the name wrong. Maybe intentionally, as some kind of typo which one wants to edit out, hinting at multiple people editing a document?)
- nathansobo 4y ago
  Hey, thanks for the heads up. I screwed it up once and duplicated it through everything. Going to fix it. He was too important to insult by misspelling his name.
nobu-mori 4y ago
I'm developing a new type (AFAIK) of database that makes many types of real-time multi-player use-cases really easy to implement. The original idea came from implementing something called "rollback netcode" in multi-player video games, but the technique works for all types of applications. Traditional databases (e.g. sql databases and key-value stores) treat the database as a blob of data. This makes multi-player updates very difficult, as reconciling differences in real-time is a hard problem, hence the invention of CRDTs. My new database, however, treats the data as a series of events. In the example of a text editor, the stream of events might be something like: User 1 connected, User 1 pressed key a, User 2 connected, User 2 pressed b, User 1 disconnected, etc. In addition to the stream of events, application developers also provide an "engine" that converts the stream of events into a blob of data. The engine runs locally on each connected client. When a client connects to the database, they fetch the engine from the database server. The client then receives the stream of events from the database server in real-time. When a client generates an event, it gets inserted into the local engine immediately and also gets broadcasted to the server. The server then broadcasts the event to other connected clients. The most important part that makes this work comes from a technique called rollback netcode. Events in the stream are ordered and undo-able. When a connected client generates an event, they insert it into their local engine immediately, but other clients are also generating events simultaneously. If all clients optimistically inserted events locally, the event order would differ across clients. To solve this, the engine automatically will undo events when new events come in from the server. The engine then applies the received event in its proper place and reapplies all the undone events on top. The result is that all users have a consistent view of the data. The logic of an engine looks something like this: 1) When User X connected, set X's cursor position to offset 0. 2) When User X types a letter, insert text at User X's cursor offset and increase User X's cursor offset by 1. Also increment the cursor offset of all other connected users if their cursor offset is > User X's. And that's it for a basic insert-only text editor. You can see that applying all the events in order yields the correct state. Adding a moveable cursor and the ability to remove text is also trivial. Basically just the opposite of 1 and 2 above. The whole engine can be implemented in like 100 lines of code and is very easy to reason about.
- paulgb 4y ago
  Our Aper (https://aper.dev https://aper.dev) implements a number of similar concepts (state machine replication with optimistic local transitions + rollback). I 100% agree that it’s an easier model to reason about. Your approach with cursors is clever, that part I haven’t seen elsewhere.

204 points by henning 4y ago

Yeah CRDTs are pretty annoying for collaborative text editing, even Google Docs doesn't use them. Some companies have switched from CRDTs back to traditional methods.

nathansobo 4y ago
We're quite happy with them. Why do you find them annoying?
- tlb 4y ago
  One common failure mode is that two people start typing at the beginning of the same line, and rather than getting two lines, it alternates characters. At least, Etherpad did this.
  - maxbond 4y ago
    This is a common artifact of operational transforms I believe. Etherpad launched in 2008; CRDTs were proposed in 2011. AFAIK Etherpad used (uses?) OT. Open to correction though, it's been a while since I dug into the differences in these approaches & my memory is imperfect.
  - muxator 4y ago
    Etherpad used Operational Transform, not CRDTs. Source: I have been etherpad's maintainer for two years.
  - josephg 4y ago
    This is called the “interleaving problem”. It shows up with simple list algorithms like fractional indexing. All the main text editing CRDT algorithms around today solve this no problem. (Yjs, automerge, diamond types, etc).
    - nathansobo 4y ago
      We honestly don’t solve it yet, but haven’t found it that big of an issue in practice. Would be curious to see the best resource on it.
      - josephg 4y ago
        I remember reading about it in one of Martin Kleppmann’s papers, though I can’t remember which one. It’s an ordering problem that comes from some of the simpler ordering algorithms. For Diamond types I’m using a variant of Yjs’s ordering. But even RGA doesn’t have this problem because each character’s insert location is specified by naming the character immediately to the left when that character was typed. This repository implements a few different list CRDTs using an insertion sort approach, where the algorithm scans for the appropriate location every time an insert happens. This is the scanning function for RGA (automerge’s algorithm): https://github.com/josephg/reference-crdts/blob/fed747255df9d457e11f36575de555b39f07e909/crdts.ts#L401-L459 https://github.com/josephg/reference-crdts/blob/fed747255df9... And this is an interactive visualisation of how diamond types works (which uses Yjs’s algorithm instead), complete with run-length encoding: https://home.seph.codes/public/diamond-vis/ https://home.seph.codes/public/diamond-vis/
      - Horusiath 4y ago
        I've described this issue in my blog post together with CRDT variants that address and solve it: https://bartoszsypytkowski.com/operation-based-crdts-arrays-1/#interleaving https://bartoszsypytkowski.com/operation-based-crdts-arrays-... In practice, many CRDT libraries nowadays (eg. Yjs and Automerge) are using structures that don't come with interleaving issues.
    - sureglymop 4y ago
      Has anyone used Yjs in practice? I've tried recently but the docs seem terribly unfinished sadly. And their lacking examples of how to use it for another purpose (other than text editing).
      - Horusiath 4y ago
- maxbond 4y ago
  I'll offer up that I've had a hard time wrapping my mind around them and that in practice it seems like you need to implement a check pointing operation on top of them which is necessarily not conflict-free, or your replication log will expand without bound & eventually overwhelm your system. (Though perhaps not, depending on your problem domain. Not CRDTs but in this interview the engineers discuss a massive, high frequency replication log that they don't checkpoint, which they've been running at scale for years. Though you could also say they implicitly checkpoint every trading day, and they're working on implementing checkpointing. https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...) That being said I would use CRDTs for any greenfield collaboration project.
paulgb 4y ago
In addition to OP (nice work, Nathan!), one of the yjs authors has made a pretty in-depth argument that (modern) CRDTs are suitable for human-scale text editing. https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi...
- nathansobo 4y ago
  Thanks very much!
maxbond 4y ago
The first version of Google Docs was written in 2006; CRDTs weren't proposed until 2011, and still seem to be maturing as a technology. So, I don't think this is a reflection on the merits of CRDTs versus operational transforms as much as it is a reflection on the ecosystem and the history of the codebase.
- josephg 4y ago
  Yep. I’ve been working in the collaborative editing space for over a decade - with both OT algorithms and CRDT algorithms. The modern CRDTs I’ve been developing are significantly faster and smaller than any OT system I made 5+ years ago. Much more complex though. (~3k loc for a good, high performance text crdt merging algorithm, vs 300 loc for a good text OT algorithm.)
  - HWR_14 4y ago
    Sorry, I'm not sure I properly understood OT as an acronym. Did you mean "operational transformation"? Because I thought that OT was method of making operational based CRDTs[0]. But I'm probably wrong in at least one way! Hoping to learn. [0] https://link.springer.com/chapter/10.1007/978-3-662-43352-2_11 https://link.springer.com/chapter/10.1007/978-3-662-43352-2_...
    - throwawaymaths 4y ago
      Quick and dirty: OTs require a centralized controller and a (potentially complicated) merge strategy to shepherd conflicting changes. CRDTs on the other hand apply commutative operations so they don't need be centralized, though nodes that communicate infrequently might get very out of sync
    - josephg 4y ago
      Yes, OT = Operational Transform[1]. Usually the difference is that operational transform algorithms create an ordered global list of all the changes (typically on a centralized server). They flatten operations using a heuristic "transform" function. CRDTs don't reorder the changes, but guarantee that when all changes are merged (in any order) the final result would be the same. For example, MAX() is a complete CRDT merging function. But the distinction gets much more blurry at the edges. You can make OT algorithms which work without a central server, and CRDTs which use operation reordering to guarantee merge consistency. [1] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation

nmlt 4y ago

This webpage crashed my iPad 6 Gen Safari when repeatedly scrolling down without reading (iPadOS 16.1.1). It’s probably just too little memory, but still, isn’t this just a blog post?

nathansobo 4y ago
We embeded a lot of videos for animated diagrams. I think we need to disable autoplay, at least on mobile.
iamnbutler 4y ago
Apologies, looks like we underestimated how heavy the autoplaying diagrams would be. If you could try again in about 5 minutes and see if you still have the problem I'd appreciate it! Sorry for the hassle.

tym0 4y ago

Has Microsoft published anything about their pairing plug-in for VS Code?

sghosh2 4y ago

Very cool use case for CRDTs! I've seen a bunch of different use cases from other products like https://liveblocks.io/ https://liveblocks.io/ and https://electric-sql.com/ https://electric-sql.com/. It's interesting how CRDTs are now taking hold so much for all these collaborative syncing scenarios. Wonder what's driving the proliferation now given they've been around for awhile?

nathansobo 4y ago
I've been interested in them since the early days of Atom, but it's just taken a while for me to develop as an engineer and build a system around the theory that puts them to practical use.

eep_social 4y ago

This reminds me of Oracle’s SCN which blew my mind back in ~2009 when I moved up from mysql home gamer stuff to the corporate world. > Even long edit histories barely compare to the memory savings Zed obtains from not being built with Electron. I got a good chuckle out of this. Speaking of performance, I think it’s I nteresting that ms word and google docs are still using OT rather than CRDT. The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client. Anyone else interested in the background of OT vs CRDT might find this thread useful: https://news.ycombinator.com/item?id=18191867 https://news.ycombinator.com/item?id=18191867

josephg 4y ago
> The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client. Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse! Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop: 1. Generates some random changes on some fake "peers" 2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm 3. Assert that the state has converged between the peers I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this. When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word. As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b497e2df8ae4473d1e521d3c3bf2d2/test.ts#L262-L318 https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4... The code is so small it almost fits on my laptop screen.
- auggierose 4y ago

AlabasterAxe 4y ago

As a Windows user, I'd be pretty concerned about the multiplatform story here. They say that this is MacOS only for now but they intend to eventually ship a Windows App, Linux App and web app. It just sounds like a recipe for a Sketch situation where it's really just a Mac app and web (and other platforms) is a second class citizen.

nathansobo 4y ago
We’ve gone to great lengths to abstract out the platform dependencies. Adding a platform right now doesn’t teach us enough for it to be worth it just yet, but we’re seriously planning for it.
AlabasterAxe 4y ago
Upon further reading, It sounds like this is being built stop cross-platform technologies (rust/webassembly) so it sounds like I spoke too soon!

jupiterelastica 4y ago

I wonder what happens when an edit can not be delivered to 1+ participant(s). Does an edit need aknowledgements from _all_ participants to be persisted? Is it just dropped?

codetrotter 4y ago
In Englebart's system you mean, or in Zed? The appeal of CRDTs is: > 1. The application can update any replica independently, concurrently and without coordinating with other replicas. Along with some other important points. See https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_... The featured article also talks about this in detail.
- jupiterelastica 4y ago
  In Zed/CRDTs, these two seem synonymous to me since the OP's article is the first I read about CRDTs that I grasped, or so I thought ;) Doesn't the whole process assume that whenever any edit is done (insertion/deleteion/un-/redo) that the edit _eventually_ reaches all participants? So if a single edit is believed to be delivered to all, but actually never made it to a single participant, who resends it? And if it's not resent, then the participants state is inconsistent from now on, no? Edit:autocorrect
  - yazaddaruvala 4y ago
    Because it’s async first, the client can use both push or pull to receive the events. If you’ve used Git you’ve been using a CRDT (with manual pulls and manual merges). A better CRDT would do both automatically.
    - jupiterelastica 4y ago
      So, client that was "offline" can just ask a participant to get the edits from his own last one (aka pull), send out bis own offline edits (push) and resolve from there, I See. Actually, that cleared it up, thank you :)

celeritascelery 4y ago

Raph Levien posted a retrospective about using CRDT’s for collaborative editing in xi-editor here [1]. His conclusion is “I come to the conclusion that the CRDT is not pulling its (considerable) weight. When I think about a future evolution of xi-editor, I see a much brighter future with a simpler, largely synchronous model, that still of course has enough revision tracking to get good results with asynchronous peers like the language server.” [1]https://github.com/xi-editor/xi-editor/issues/1187#issuecomment-491473599 https://github.com/xi-editor/xi-editor/issues/1187#issuecomm...

maxbrunsfeld 4y ago
I think that the paragraph that you quoted was in reference to Xi's decision to use CRDTs (and asynchronous communication) for exchanging data between different plugins running in the same instance of Xi. It isn't a comment about the use of CRDTs for collaborative editing, as Zed does.
infogulch 4y ago
I noted the same a few months ago when Zed came up in a discussion about Atom, and Raph responded: https://news.ycombinator.com/item?id=31674931 https://news.ycombinator.com/item?id=31674931

throwaway14356 4y ago

if everyone is in the same area one could/should just pretend the client is a terminal(?) https://www.ookla.com/articles/gaming-cities-lowest-latency-2019 https://www.ookla.com/articles/gaming-cities-lowest-latency-... https://www.rtings.com/keyboard/tests/latency https://www.rtings.com/keyboard/tests/latency

infogulch 4y ago

How do the editor CRDTs integrate with source control?

lewisjoe 4y ago

To put it in a different perspective, plain text editing has well-solved CRDT patterns. But, semantic data-structures like rich-text or syntax trees is what's tricky and has unsolved challenges. Peritext[1] is the only one that came close to solving rich-text, but even that one left out important aspect of rich-text editing like handling list & table operations as "work to be done later". For people interested on why it's difficult to build CRDTs for richtext, here's a piece I wrote a year back: https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... Related HN discussion: https://news.ycombinator.com/item?id=29433896 https://news.ycombinator.com/item?id=29433896 [1] https://github.com/inkandswitch/peritext https://github.com/inkandswitch/peritext

Horusiath 4y ago
> semantic data-structures like rich-text or syntax trees is what's tricky and has unsolved challenges. Yrs developer here: - Yjs/Yrs have support for formatting attributes[1]. The matter if format attributes conflict resolution behaves as user desired is a subject to discussion (which is a common thing re. CRDTs and their trade offs), but its behaviour is consistent, convergent and algorithm itself works fast. This feature is in fact used in many rich text editors using Yjs bindings. - Embedding non-string elements in text is supported as well. - While syntax trees are not supported out of the box (AFAIK this CRDT is still being researched), Yjs also support XML nodes with attributes and nested children, which may be used for similar effects in some scenarios. [1] https://docs.yjs.dev/api/delta-format https://docs.yjs.dev/api/delta-format

zelphirkalt 4y ago

*Douglas Engelbart (The picture has the name wrong. Maybe intentionally, as some kind of typo which one wants to edit out, hinting at multiple people editing a document?)

nathansobo 4y ago
Hey, thanks for the heads up. I screwed it up once and duplicated it through everything. Going to fix it. He was too important to insult by misspelling his name.

nobu-mori 4y ago

I'm developing a new type (AFAIK) of database that makes many types of real-time multi-player use-cases really easy to implement. The original idea came from implementing something called "rollback netcode" in multi-player video games, but the technique works for all types of applications. Traditional databases (e.g. sql databases and key-value stores) treat the database as a blob of data. This makes multi-player updates very difficult, as reconciling differences in real-time is a hard problem, hence the invention of CRDTs. My new database, however, treats the data as a series of events. In the example of a text editor, the stream of events might be something like: User 1 connected, User 1 pressed key a, User 2 connected, User 2 pressed b, User 1 disconnected, etc. In addition to the stream of events, application developers also provide an "engine" that converts the stream of events into a blob of data. The engine runs locally on each connected client. When a client connects to the database, they fetch the engine from the database server. The client then receives the stream of events from the database server in real-time. When a client generates an event, it gets inserted into the local engine immediately and also gets broadcasted to the server. The server then broadcasts the event to other connected clients. The most important part that makes this work comes from a technique called rollback netcode. Events in the stream are ordered and undo-able. When a connected client generates an event, they insert it into their local engine immediately, but other clients are also generating events simultaneously. If all clients optimistically inserted events locally, the event order would differ across clients. To solve this, the engine automatically will undo events when new events come in from the server. The engine then applies the received event in its proper place and reapplies all the undone events on top. The result is that all users have a consistent view of the data. The logic of an engine looks something like this: 1) When User X connected, set X's cursor position to offset 0. 2) When User X types a letter, insert text at User X's cursor offset and increase User X's cursor offset by 1. Also increment the cursor offset of all other connected users if their cursor offset is > User X's. And that's it for a basic insert-only text editor. You can see that applying all the events in order yields the correct state. Adding a moveable cursor and the ability to remove text is also trivial. Basically just the opposite of 1 and 2 above. The whole engine can be implemented in like 100 lines of code and is very easy to reason about.

paulgb 4y ago
Our Aper (https://aper.dev https://aper.dev) implements a number of similar concepts (state machine replication with optimistic local transitions + rollback). I 100% agree that it’s an easier model to reason about. Your approach with cursors is clever, that part I haven’t seen elsewhere.