I was wrong – CRDTs are the future (2020)(josephg.com)
josephg.com
I was wrong – CRDTs are the future (2020)
https://josephg.com/blog/crdts-are-the-future/
8 comments
As an aside, I was pretty excited about the concept of Wave. Sorry it didn't work out at Google. I still remember Lars doing an entertaining little dance onstage during an I/O demo that succumbed to network issues!
Thanks for saying so.
In many (most?) ways, I think Wave was ahead of its time. We were ahead of the curve on collaborative technology. Modern CRDTs would have made the federation protocol so much easier. And it was really difficult to build a web app like that at the time.
I think we're getting close to the point where we could re-make wave if we wanted, on top of modern CRDTs and using modern web development practices. I'm not sure if the world is ready, but technically? We could make software like wave scream.
In many (most?) ways, I think Wave was ahead of its time. We were ahead of the curve on collaborative technology. Modern CRDTs would have made the federation protocol so much easier. And it was really difficult to build a web app like that at the time.
I think we're getting close to the point where we could re-make wave if we wanted, on top of modern CRDTs and using modern web development practices. I'm not sure if the world is ready, but technically? We could make software like wave scream.
I don't really understand why every single article on CRDTs is about collaborative text editing. Is no one else bothering to build systems with CRDTs outside of this space?
Not to detract from the article, which I found interesting for a number of reasons - both in terms of the technology and future of that technology as well as the personal realization of "the thing I'm building won't be necessary one day".
Not to detract from the article, which I found interesting for a number of reasons - both in terms of the technology and future of that technology as well as the personal realization of "the thing I'm building won't be necessary one day".
Collaborative text editing is an easy-to-understand example of a Hard Problem that can't be solved with any simpler abstraction. You can try to throw an MVCC database at it, a BFT consensus algorithm at it, whatever, but without having those substrates implement a CRDT (or its cousin, Operational Transformations), you won't get the results you want.
More generally, CRDTs are useful when syncing any kind of change-events between peers (with no central ability to pre-linearize those events), where the ordering of change-events doesn't matter — i.e. where the operations described by the events are "commutative", such that you'll get the same results out if you apply events {1,2,3} or {3,2,1} or any other order. As long as all peers see all events, all peers arrive at the same eventually-consistent position in the "lattice" of possible states. In other words, CRDTs + gossip protocols = the ability for peers to just process events as they hear about them, without a worry about receiving events from peers "out of order"; rather than needing to wait around for a some elected peer to forcibly linearize the events (i.e. without the need to introduce a serial write bottleneck.)
A good example of the distributed-systems-backend kind of use of CRDTs, is in the Elixir web framework Phoenix, which does a sort of mesh delivery of web-socket messages between a cluster of backends. CRDTs are used to sync presence information (= which clients are connected to which backend) between the backends.
More generally, CRDTs are useful when syncing any kind of change-events between peers (with no central ability to pre-linearize those events), where the ordering of change-events doesn't matter — i.e. where the operations described by the events are "commutative", such that you'll get the same results out if you apply events {1,2,3} or {3,2,1} or any other order. As long as all peers see all events, all peers arrive at the same eventually-consistent position in the "lattice" of possible states. In other words, CRDTs + gossip protocols = the ability for peers to just process events as they hear about them, without a worry about receiving events from peers "out of order"; rather than needing to wait around for a some elected peer to forcibly linearize the events (i.e. without the need to introduce a serial write bottleneck.)
A good example of the distributed-systems-backend kind of use of CRDTs, is in the Elixir web framework Phoenix, which does a sort of mesh delivery of web-socket messages between a cluster of backends. CRDTs are used to sync presence information (= which clients are connected to which backend) between the backends.
It just seems like an extremely niche, difficult problem, whereas CRDTs are a very general tool.
edit: Oh you edited your post there's way more now, but I can't read it all now x_x but fwiw when I said "anyone else" I meant that I use crdts.
edit: Oh you edited your post there's way more now, but I can't read it all now x_x but fwiw when I said "anyone else" I meant that I use crdts.
On the other hand: A lot of practical applications are fine with last write
Isn’t ignoring the difficult edge cases of commutative operations what got darcs and theory of patches into problems?
I never used it (darcs) but got the impression that it was easy to get into merge cases that were very hard to resolve.
(To be clear: I am not /claiming/ the above, I am asking whether my recollection is correct)
I never used it (darcs) but got the impression that it was easy to get into merge cases that were very hard to resolve.
(To be clear: I am not /claiming/ the above, I am asking whether my recollection is correct)
I'm extremely excited about CRDT Matrix[0], especially in the context of decentralized chains[1]. I think if we combine this message stream concept, with the entirely separate concept of torrent databases[2], you get the ability to get fully decentralized, self-hosted, web applications - all with no concept of some crypto-token, as it's all incredibly efficient.
It's going to take some time for this to all come together, but it's exciting.
[0]: https://news.ycombinator.com/item?id=29978659
[1]: https://news.ycombinator.com/item?id=30560573
[2]: https://news.ycombinator.com/item?id=30605252
It's going to take some time for this to all come together, but it's exciting.
[0]: https://news.ycombinator.com/item?id=29978659
[1]: https://news.ycombinator.com/item?id=30560573
[2]: https://news.ycombinator.com/item?id=30605252
Author here. Its because I've been focussing on collaborative text editing first, and a fair few of the articles which pop up on HN were written by me.
There's more great CRDT writing which deserves some attention. For example, this series by Bartosz Sypytkowski is long but excellent:
https://bartoszsypytkowski.com/the-state-of-a-state-based-cr...
He talks about CRDTs from the ground up, from much more of a mathematical / FP point of view. I learned a lot reading this series!
Why have I been focussing on collaborative text editing? Because I think performance has been the #1 blocker stopping us from using CRDTs in most software. And text CRDTs are a canary in the coal mine for performance. Uh, thats a tortured metaphor. I mean, If we can make text CRDTs fast, we can make everything fast.
And JSON editing (what everyone actually wants) needs to embed text editing anyway. So we've sort of gotta do that first anyway.
Smart people have also been working on the JSON editing problem. I'm a big fan of Greg Little's Shelf algorithm[1] for last-writer-wins JSON editing (which is what people usually want). Shelf is simple enough you can implement it in less than 100 lines of code. But shelf doesn't support collaborative list or text editing (text is a list of characters). We need all of these pieces, then we need to mush them all together in a sensible way. And thats something Yjs and automerge both already do, and do quite well.
There's more great CRDT writing which deserves some attention. For example, this series by Bartosz Sypytkowski is long but excellent:
https://bartoszsypytkowski.com/the-state-of-a-state-based-cr...
He talks about CRDTs from the ground up, from much more of a mathematical / FP point of view. I learned a lot reading this series!
Why have I been focussing on collaborative text editing? Because I think performance has been the #1 blocker stopping us from using CRDTs in most software. And text CRDTs are a canary in the coal mine for performance. Uh, thats a tortured metaphor. I mean, If we can make text CRDTs fast, we can make everything fast.
And JSON editing (what everyone actually wants) needs to embed text editing anyway. So we've sort of gotta do that first anyway.
Smart people have also been working on the JSON editing problem. I'm a big fan of Greg Little's Shelf algorithm[1] for last-writer-wins JSON editing (which is what people usually want). Shelf is simple enough you can implement it in less than 100 lines of code. But shelf doesn't support collaborative list or text editing (text is a list of characters). We need all of these pieces, then we need to mush them all together in a sensible way. And thats something Yjs and automerge both already do, and do quite well.
There are people looking at how to use them outside of rich text editing, it’s just that the technology was developed/initially applied to text editing.
I’m more excited about the use of CRDTs outside of text editing, there are so many use cases. However there are still some problems to solve with the existing general purpose toolkits such as Yjs and Automerge. Both give you simple data structures and some more complex structures specifically for rich text. For a true conflict free system you need the CRDTs to match your data model exactly so you can never have a invalid state after a merge. This is almost never the case with existing toolkits.
Take Yjs and it’s ProseMirror bindings, Yjs can represent any internal state of a ProseMirror document and merge them. However it does not have an understanding of the specific ProseMirror schema being used, this could limit the valid states possible (a max length on a heading for example). When Yjs merges multiple edits you could end up with an invalid document for your schema, Yjs loads this into ProseMirror which then throws away the invalid data (with the heading example it just deletes the excess text, it may be better to dump it into the next line but should be configurable).
These sorts of problems are “ok” in a text editor but would be much harder to cope with in a database or a 3d cad tool.
Ultimately the general purpose CRDT toolkits need to have more internal types with a wider ability to capture intent. I also think they need to have the ability to understand the schema of the data structure they are tracking and how to handle more complex merges.
The alternative to doing that with a general purpose toolkit is to build your own CRDTs from scratch for your data model. I don’t think many people would go that route though.
Once those sorts of problems have been solved I think we will see their use explode into new areas.
It’s still early days with them but exciting time ahead.
I’m more excited about the use of CRDTs outside of text editing, there are so many use cases. However there are still some problems to solve with the existing general purpose toolkits such as Yjs and Automerge. Both give you simple data structures and some more complex structures specifically for rich text. For a true conflict free system you need the CRDTs to match your data model exactly so you can never have a invalid state after a merge. This is almost never the case with existing toolkits.
Take Yjs and it’s ProseMirror bindings, Yjs can represent any internal state of a ProseMirror document and merge them. However it does not have an understanding of the specific ProseMirror schema being used, this could limit the valid states possible (a max length on a heading for example). When Yjs merges multiple edits you could end up with an invalid document for your schema, Yjs loads this into ProseMirror which then throws away the invalid data (with the heading example it just deletes the excess text, it may be better to dump it into the next line but should be configurable).
These sorts of problems are “ok” in a text editor but would be much harder to cope with in a database or a 3d cad tool.
Ultimately the general purpose CRDT toolkits need to have more internal types with a wider ability to capture intent. I also think they need to have the ability to understand the schema of the data structure they are tracking and how to handle more complex merges.
The alternative to doing that with a general purpose toolkit is to build your own CRDTs from scratch for your data model. I don’t think many people would go that route though.
Once those sorts of problems have been solved I think we will see their use explode into new areas.
It’s still early days with them but exciting time ahead.
Figma uses them too.
https://www.figma.com/blog/how-figmas-multiplayer-technology...
https://www.figma.com/blog/how-figmas-multiplayer-technology...
CRDTs match multiplayer collaboration to edit a target free data structure, but they don't match multiplayer competition to put a database through a series of transaction states. Note the word "transaction" is almost the opposite of "conflict-free" in that the whole point of a transaction is to reject certain actions as resulting in an invalid state.
Most of the applications I worked on in the last decade (web saas crud stuff) are dominantly transactional with maybe a thin slice of collaborative functionality. I suppose the next decade could look different but I don't see why that would be the case.
Most of the applications I worked on in the last decade (web saas crud stuff) are dominantly transactional with maybe a thin slice of collaborative functionality. I suppose the next decade could look different but I don't see why that would be the case.
I am. But i know very little about CRDTs lol, so we'll see how that goes. I'm interested in converting some immutable, local-first data warehouse tooling i enjoy to a CRDT version. Prior it was more.. Git-like. Basically just Git with data structures inspired-massively from Noms[1].
The thing i've found most interesting is it appears[2] that CRDT backends need to expose CRDT flavored types to users. Which is to say how i'm writing this combines the notion of a type, say `[i32]` with how you want the merges to work. CRDT works great but based on my amateur-hour researching on the subject i don't feel you can write a single CRDT merge strategy for a single data type ala `[i32]` and have it be always correct. Applications need to indicate enough context on what makes sense for a given data type.
So yea, i agree with you. I'm interested in making a database-like thing, backed by CRDTs, but i also have seen very few general purpose implementations with CRDTs. It feels like i'm breaking "new ground", while having no idea what i'm doing and having no intention of being an actual researcher here. I'm just making apps i enjoy heh.
[1]: https://github.com/attic-labs/noms [2]: appears, because i could easily be wrong
The thing i've found most interesting is it appears[2] that CRDT backends need to expose CRDT flavored types to users. Which is to say how i'm writing this combines the notion of a type, say `[i32]` with how you want the merges to work. CRDT works great but based on my amateur-hour researching on the subject i don't feel you can write a single CRDT merge strategy for a single data type ala `[i32]` and have it be always correct. Applications need to indicate enough context on what makes sense for a given data type.
So yea, i agree with you. I'm interested in making a database-like thing, backed by CRDTs, but i also have seen very few general purpose implementations with CRDTs. It feels like i'm breaking "new ground", while having no idea what i'm doing and having no intention of being an actual researcher here. I'm just making apps i enjoy heh.
[1]: https://github.com/attic-labs/noms [2]: appears, because i could easily be wrong
I was recently working on implementing CRDTs for a company that did retail shelf edge printing (the sale tags and strips you see when you go the the grocery store). The idea was to build a PDF rendering engine in Rust that we would compile to WASM allowing the clients (stores) to render PDFs on the fly with their in-store devices and printers. One of the challenges was keeping tens or hundreds of thousands of product data (that could update hourly) in sync across thousands of stores.
Ideally when clients (corporate overlords) would send product data an event streaming broker (like Kafka) would log the product. One consumer would insert the product data into the SQL database (current implementation), one would generate CRDTs based on diffs from the current product model, and a chained consumer would broadcast the CRDTs to all connected clients.
The initial sync would be brutal so we'd still support server side queries and rendering but eventually the customers could generate the PDFs themselves regardless of if our server was busy (or offline which happened often).
It was a fun project and I helped lay a ton of the ground work but due to company politics and a generally toxic workplace I jumped ship. My new job would never need CRDTs so I'm now just sitting back and watching the space evolve.
Ideally when clients (corporate overlords) would send product data an event streaming broker (like Kafka) would log the product. One consumer would insert the product data into the SQL database (current implementation), one would generate CRDTs based on diffs from the current product model, and a chained consumer would broadcast the CRDTs to all connected clients.
The initial sync would be brutal so we'd still support server side queries and rendering but eventually the customers could generate the PDFs themselves regardless of if our server was busy (or offline which happened often).
It was a fun project and I helped lay a ton of the ground work but due to company politics and a generally toxic workplace I jumped ship. My new job would never need CRDTs so I'm now just sitting back and watching the space evolve.
Not all CRDT libraries focus on text editing. For example, I'm working on a Byzantine fault tolerant general-purpose data sync library loosely based on CRDTs: https://www.hyperhyperspace.org
I'm finding it painfully difficult but it is evolving steadily.
I'm finding it painfully difficult but it is evolving steadily.
"CRDTs" is a very general term that amounts to rather weak constraints on any notion of eventual consistency. So I suppose that CRDT-equivalent things pop up in many distributed settings, they just aren't necessarily thought of as such.
I have a distributed/multiplayer domino and a scrabble (tm) clone game in javascript/redis that I'll change to CRDT. At the end of the day, the concept of updating a board with some tiles lends itself pretty well for CRDTs imho.
What value do CRDTs add to a turn-based game?
Agreed. It doesn't help that the idea of concurrent editing of a single document is.... Not really that useful. Makes fun performances/demos. But that isn't really where the friction is in how folks collaborate.
Concurrent editing of documents is a $100B+ market
How is that true? I accept we don't have the tools so no one actually works this way, but if I am say pair programming we don't literally edit at the same time - it's a you go, I go, you go situation - and that's the same way to do it. Even collaborative white boarding is "handing over the pen" - because we are not trying to teach the whiteboard our ideas, we are trying to teach each other - and one of us needs to be listening ..
Amusingly, I just accepted the claim. This is largely the kind of thing that businesses pay for, so seems fairly easy for it to be inflated.
Example products in this space you may have heard of:
- Google Docs
- Microsoft Office 365
- Figma
- Quip
- Notion (my employer)
- Google Docs
- Microsoft Office 365
- Figma
- Quip
- Notion (my employer)
I think it is a stretch to claim all of those need concurrent editing. More, the best documents over seen in those have all largely been single threaded in editing.
They have had review features that are decent. But... Best feedback I get is still typically verbal or otherwise out of band.
They have had review features that are decent. But... Best feedback I get is still typically verbal or otherwise out of band.
Is Notion using CRDTs?
So is videoconferencing. And somehow, all offerings are some version of garbage. :(
Probably because outside collaborative text editing, it's called more generally, like CRQS or event sourcing
> bout collaborative text editing
In the beginning was the word.
A lot of things can be expressed using text.
In the beginning was the word.
A lot of things can be expressed using text.
Previous discussion: https://news.ycombinator.com/item?id=24617542
I've been delving into CRDTs lately, and one thing I've been wondering is if there's an implementation that is purely SQL-based. All operations and merges would happen through database queries. This may not be suitable for real-time use, but I've noticed that most CRDT implementations expect you to have the entire data structure in memory, forcing you to be clever with the way you model your data and save to disk.
We at www.ditto.live will likely get to a SQL like implementation with Delta state CRDTs this year.
Although I'm not super familiar with CRDTs, respect for being intellectually honest and humble. Its tough separating ego from our work, especially if we spend a lot of time and energy on it.
The three.js JavaScript library can load VRML files and render them using WebGL - demo here: https://threejs.org/examples/webgl_loader_vrml.html
This is a false dichotomy. OP can be wrong with their new prediction too.
> This is a false dichotomy. OP can be wrong with their new prediction too.
It's not "I was wrong, therefore CRDTs are the future" but "CRDTs are the future, therefore I was wrong." As you say, this new prediction, too, can be wrong, but I don't see where any sort of false dichotomy comes into it.
It's not "I was wrong, therefore CRDTs are the future" but "CRDTs are the future, therefore I was wrong." As you say, this new prediction, too, can be wrong, but I don't see where any sort of false dichotomy comes into it.
You're right that OP doesn't directly make that correlation, but I deduced it from his insistence on that one thing can either be "the future" or not. That kind of thinking usually stems from a dualistic perspective. I wanted to emphasize that. I find such extreme stances generally unhelpful and likely to turn out wrong again.
We really have three OK-ish options for rich collaboration:
* CRDT's
* OT
* Maybe differential synchronization
If a key OT partisan now backs CRDT, that's a significant development. It means CRDT's arguments have become compelling enough to convince people on the other side.
Now, maybe something new and wonderful will pop up and supplant all of the above...
* CRDT's
* OT
* Maybe differential synchronization
If a key OT partisan now backs CRDT, that's a significant development. It means CRDT's arguments have become compelling enough to convince people on the other side.
Now, maybe something new and wonderful will pop up and supplant all of the above...
In CoCalc, I use a fourth approach that I think isn’t in your list. https://blog.cocalc.com/2018/10/11/collaborative-editing.htm...
I don’t claim it is better than any other approach, except it is easy to understand. Also I’m not sure that it isn’t technically an extreme special case of OT.
> Also I’m not sure that it isn’t technically an extreme special case of OT.
It sure looks like the trivial case of OT to me.
It sure looks like the trivial case of OT to me.
> That kind of thinking usually stems from a dualistic perspective. I wanted to emphasize that. I find such extreme stances generally unhelpful and likely to turn out wrong again.
Author here. Bold stances make for better reading. Its fun to stake your reputation on a perspective you hold. Being bold and sometimes wrong is better on most metrics than never saying anything at all. The best way to optimize for "least likely to be wrong" is to never be noticed, or do anything notable. That sounds like a waste of a life to me.
I'm not optimizing for "least wrong". I'm optimizing for "most movement forward".
If I took your advice, perhaps I could have titled my article "CRDTs perform a bit better than I thought. I have a hypothesis that the choice-gradient should shift by a moderate amount toward CRDTs in situations where both OT and CRDTs would be appropriate." Yikes! I believe that if I said that, my article wouldn't have hit the front page at all. Let alone multiple times.
You may have preferred that article had you read it (though I roll to doubt even that). But I suspect you wouldn't have had that chance, because you would never have found it.
Of course reality is complicated. In this case, there is probably room for both OT and CRDT based systems. (Or even, CRDT based systems which provide an OT frontend). But making a new possibility for the future depends on a communicated vision. You can't communicate that vision if you bore everyone to death whenever you start talking.
Author here. Bold stances make for better reading. Its fun to stake your reputation on a perspective you hold. Being bold and sometimes wrong is better on most metrics than never saying anything at all. The best way to optimize for "least likely to be wrong" is to never be noticed, or do anything notable. That sounds like a waste of a life to me.
I'm not optimizing for "least wrong". I'm optimizing for "most movement forward".
If I took your advice, perhaps I could have titled my article "CRDTs perform a bit better than I thought. I have a hypothesis that the choice-gradient should shift by a moderate amount toward CRDTs in situations where both OT and CRDTs would be appropriate." Yikes! I believe that if I said that, my article wouldn't have hit the front page at all. Let alone multiple times.
You may have preferred that article had you read it (though I roll to doubt even that). But I suspect you wouldn't have had that chance, because you would never have found it.
Of course reality is complicated. In this case, there is probably room for both OT and CRDT based systems. (Or even, CRDT based systems which provide an OT frontend). But making a new possibility for the future depends on a communicated vision. You can't communicate that vision if you bore everyone to death whenever you start talking.
I wrote this a couple years ago. Since then I've been working on my own CRDT called Diamond Types[1], which uses a lot of these ideas to be bonkers fast. I've built several OT based collaborative editing systems, and diamond types is much faster than any of them - though rust and wasm might be the real MVPs here. I wrote a follow-up to this article last year when I got that working, talking about how some of the optimizations work. That article is here[2].
A fair bit has changed since I wrote that article. Yjs has started a rewrite in rust (called yrs[3]). And Automerge has apparently dramatically improved performance based on some of the ideas I talk about in this article. Oh, and diamond types has been rewritten from the ground up. Its now about 5x faster than it was last year, by completely changing the internal structure. But thats a story for another day.
Unfortunately I still only support collaborative text editing. Adding full JSON support comes soon, after I document some more of the tricks I'm doing. Its really fun work!
Why do I only support collaborative text editing? Because I care about performance, and text CRDT performance is hard because you have so many individual changes - generally one for each keystroke! Making text editing (and list CRDTs in general) fast opens up a lot of other design approaches for a general purpose CRDT. But we've still got to do the work itself. To make that happen, my plan is to add full JSON editing support to diamond types using shelf[4]. Shelf is a super simple CRDT which fits in 100 lines of javascript. The next piece of work is marrying them together.
[1] https://github.com/josephg/diamond-types/
[2] https://josephg.com/blog/crdts-go-brrr/
[3] https://github.com/y-crdt/y-crdt/tree/main/yrs
[4] https://github.com/dglittle/shelf