An interactive intro to CRDTs
jakelazaroff.com
jakelazaroff.com
Also, the fact that we always use text editing as the de-facto solution is so weird to me since that problem is both niche and extremely complex. IMO a better example would be something like "Can this person drink alcohol?". Age moves in one direction so it has a simple merge function:
def set_age(self, new_age: int):
self.age = max(self.age, new_age)
This means you can have distributed caches without invalidation logic. A pretty amazing property since cache invalidation is a hugely complex problem and has seriously negative performance/ storage implications.
It also means you can drop writes. If my system gets information that a person was 18, but that information is out of date, I can drop that write, and I can do so by examining the cache and viewing stale information, only checking the real value if the cache value is < 18.
This whole thing lets you push computation to the edge, drop expensive writes, ignore any cache invalidation logic, cache values forever, potentially answer queries from stale cache values, etc.
Anyway, kudos for the writeup. I skimmed the second half but the first half was great and the second half looked legit.
The reason we use that is because it is complex enough to show the problems that CRDTs solve. I would argue that this painting example is too simple. The core merge loop is:
if pixel.created_at < newPixel.created_at {
pixel = newPixel;
}
Simple text inserts with a simple "insert after" CRDTs is not much more complicated but involves things like generated unique IDs without communication and how to resolve conflicts with some sort of globally consistent ordering.
It's something to build up to maybe, not to start with.
Seriously, want to make some easy money? Build this.
It used to be between 21 in most of the US until the voting age was lowered to 18 in 1971. It was then either 18 or 19 in most states (generally the more liberal ones) until 1984 when the national minimum was passed. 19 really is sort of a sweet spot for socially liberal North America.
You have to be careful here.
My first foray into collaborative editing was for my text editor. Indeed, things get super linearly harder as you add basic functionality of editors such as deleting and replacing, especially when those space multiple lines.
Instead, I reached for Fraser’s differential syncing. https://neil.fraser.name/writing/sync/. There’s a lot of ambiguity and nuances in various versions of the prose and white paper that I could never really flesh out.
I think anyone attempting to relay a collaborative editing algorithm needs to do is start with the simplest scenarios: append only / monotonically increasing data.
Better to use date of birth as that doesn't change at all.
I initially thought more of the inner workings could be managed this way, but it seems better implemented as it is in the article.
That said, there are a lot of trade offs. Some things that are easy in a traditional server-client model become difficult in the local-first context that CRDTs provide. Role based authorization is hard, data model changes must be done additive (never mutative), and knowing what state a client is in when debugging is tough too, without a lot of “full-surveillance”-level tooling. Also with the automatic , bidirectional syncing a lot of CRDT architectures afford you, a bug in production that corrupts data can virally propagate and cause a huge headache.
Investor-funded services like Liveblocks are starting to pop up that promise to make this stuff easier, but as an indie I find them expensive; I’m sure they’re a great value for big corps or funded teams though. Rolling my own infrastructure for Yjs has been taxing, but I’ve learned a lot, and have been able to tailor it exactly to my needs.
My team has built an open-source debugger for Yjs that might interest you (docs: https://y-sweet.cloud/advanced/debugger)
You mention the investor-funded services that pop up to make this stuff easier -- our goal with Y-Sweet is to build the same type of DX you’d get from those services, but build it on a fully open-source (MIT) platform with Yjs at the core: https://github.com/drifting-in-space/y-sweet
1) Does the server keeps in memory the "active" documents? In other words, does the server need to open a document and keep it in RAM while clients are connected to it (I assume there's a websocket connection somewhere in the client that keeps it hot)? Or is the server stateless - just connects to the store when needed? I found the latter very hard to do.
2) Does the client persist entries using indexeddb? If yes, does opening many tabs cause redundant writes as they all sync with the server? If not, does the client need to fully re-sync with the server anytime it wakes up?
3) Is it possible to observe updates on the client as they come? One of the major use cases of CRDTs is to index data on the client - then you can have a dumb server that just syncs data between clients and a smart client that does search, graphs, visualizations etc. on the data it receives. To do that, the client needs to observe updates one by one and process them to create secondary indexes. Is it possible to do with y-sweet without forking its source code? I remember getting updates yn Y.js being quite inefficient as you need to replay them all or something similar, but that was a couple of years ago.
> 1
The server keeps the documents in memory when they are open, but it is horizontally scalable by hosting using CloudFlare Durable Objects. (We also plan to support Plane.dev but that's not built out yet).
> 2
The client is based on Yjs, so it's compatible with Yjs' y-indexeddb provider to store in IndexedDB. Tabs synchronize state between each other using a local broadcast channel. The client only synchronizes unsynced state with the server, so if one tab has already pushed the local offline edits to the server, the other tabs can discover that and avoid pushing them. That said, I'm not 100% sure if Yjs deals with the race condition where two tabs wake up at the same time so the server has not yet received offline edits from either, I'd have to check on that.
>3
Yes, Yjs types have an `observe` method that takes a callback, which receives an event with details of each edit. Here’s an example for observing events of a Y.Map: https://docs.yjs.dev/api/shared-types/y.map#observing-change...
Our tentative pricing is $25/month + $10/10k minutes of “open connection” time (per-document, not per-connection, so multiple users with the same doc open are not double-counted). Storage is free if you bring your own R2/S3 bucket, or a nominal fee if you use ours.
Unlike supabase we don’t do any of the relational stuff, but for Figma-like apps where a lot of documents are never touched, I think our hot/cold storage model can be significantly cheaper at scale than a hosted postgres database like supabase.
Sounds painful. It means your mutative data model changes, which exist, live somewhere else.
LegendKeeper looks really awesome btw, I might bring this up for my own campaign use. I've been thinking of using Yjs to build some character sheet builders myself which is why I'm asking.
As long as you have garbage collection turned on for your Ydocs, they stay pretty small, especially if you are avoiding using YMaps. (The strings that serve as YMap keys can't be GC'd, from what I understand. YMaps are great for bounded domain objects, but not so great for storing collections, dictionary-style. Y-KeyValue solves this problem.)
I eventually added a X MB document size limit on the backend, but only after doing a statistical analysis on existing documents. I found a size threshold that was a strong indicator of abnormal/buggy behavior, and set a limit under that. Without the limit, occasionally I had huge Ydocs, usually created by a bug or weird user behavior, clogging up database resources. Now I block those ydocs on the backend and send a messsage to the user with some mitigation/recovery tips. I plan to add automatic document repair, but just haven't gotten to it yet. As LK matures and I get better with Yjs, these bugs become much rarer.
In practice, most apps will only need Last-Writer-Wins registers and not the more complicated sequence CRDT's that you find in Y.js and Automerge.
We've built a auto-syncing database that uses CRDTs under the hood but never exposes them through the API. So if you want all of the benefits of CRDTs e.g. offline-first user experience, checkout our project, Triplit!
We also recently came up with a relational-style querying system without joins! https://twitter.com/triplit_dev/status/1707509447789043760
https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
For example, if I have a field which is "color" and one person writes red and the other writes blue, there is no way to automatically resolve that conflict when they both become reconnected. It's physically impossible since the intent cannot be established without the ability to read the minds of both participants. You can't just merge the letters into the word "reblued" nor can you allow one to completely overwrite the other while letting both participants believe that their change was settled when in fact, only one made it through. Often, it's desirable that both participants must be online and better to show one an error message if they're not so that they are not mislead into thinking that they're actually changing the system state when in fact their change hasn't been persisted.
I've worked on realtime systems which don't rely on CRDTs. This was a suitable approach in my case since accuracy of the data was paramount and each section of the data was well isolated from one another and offline editing was not required.
This, for me, is the crux of the issue that I can not understand - a general CRDT library simply cannot work, as the changes are in context of what is being edited.
IOW, I cannot think of a situation where conflicts can be resolved automatically. I think it might be best for the application (which does have context) to display the conflicted state (like the way git does), marking it as a conflict and requiring manual intervention to resolve.
In this example, perhaps the application can display the field? If the field is displayed as text, then display "Conflict: {[joe:~blue~][bob:~red~]}". If the field is being displayed as a colored element in an image, the conflict must be displayed with (for example) an overlay on the conflicted part as a red-outlined box, with the snippet of both changes to the image displayed on mouse-over, or on click (or similar).
It makes no sense, to me, to approach CRDTs as a general mechanism - it'll be a CRDT for text, a different mechanism for rasterised images, another one for vector graphics, another for video, for sound, etc.
Here is a good overview article, which has pointers to other articles: https://cacm.acm.org/magazines/2022/11/265835-research-for-p...
To me it seems that while state-based CRDTs are easy to understand, operation-based CRDTs are actually what is used in practice. Furthermore, it seems to me the difference between operation-based Automerge, and operational transform (OT) is actually not that big.
Seems like conditions may be right for a boom in the application of CRDTs.
We've found most multi-user apps running over websocket experience significant degradation in performance in the high teen and low twenties. Beyond that we were able to update nested CRDTs and all presence/user data in one connection with the backend.
TipTap has a great backend called HocusPocus with well documented API. Y-websocket backend is already quite good but the support for user tokens isn't there natively. We were actually able to be backend provider agnostic for well into the project. It's a fun ecosystem.
https://www.youtube.com/watch?v=Mr0a5KyD6BU | HN Submission: https://news.ycombinator.com/item?id=37770541
Those are really only issues with state-based CRDTs. The fundamental concepts behind operation-based CRDTs vs operational transforms vs bespoke hybrid approaches aren't really different. It's all about determining an unambiguous order, then getting everyone to update their state as if it had been applied in that order. Much less democratic but much more practical.
https://www.figma.com/blog/how-figmas-multiplayer-technology...
It’s a client-server architecture with a bit of CRDT inspired algorithm sprinkle on for offline mode. The name of the game remains consensus and CRDTs convoluted approach is there to server a niche in the spectrum of distributed consensus. It is slower, more complex, and less transparent. I wouldn’t really use it outside of long lived and erratic P2P nodes — CRDTs solve that problem and that is what they are really designed for: partition prone, long lived, distributed, peer to peer, collaborative global state changes.
I believe Figma, Notion, Google Docs, etc all use some form of OTs which aren't necessarily a perfect CRDT
https://github.com/actualbudget/actual
The original author has both written about and given presentations about CRDTs.
Also see: https://github.com/yjs/yjs
[1] https://digest.browsertech.com/archive/browsertech-digest-ho...
https://pijul.org/manual/theory.html?highlight=CRDT#conflict...
> When two different authors add lines at the same position in a file, and it is impossible to tell which comes first in the file.
> When one author adds a line in a block of text or code, while another author deletes that block.
I don't think this is true. Two different authors can modify the same line in different ways, which is a conflict that's different than either of these categories.
> It is important to note that conflicts in Pijul always happen between changes, for example we might say that “change A conflicts with change B”.
I also don't think this is true. Conflicts can occur in a history (lineage, sequence, etc.) of concurrent changes, which are different than the delta between any two independent changes.
- Edits can be made on any node at any time independently and without coordinating with other nodes.
- All nodes eventually converge to the same state.
CRDTs just provide a common interface for automatic synchronization of replicated data and uses metadata (timestamps etc.) to resolve conflicts in a best-effort manner. With CRDTs, you still have to accept that cases may occur where the conflict resolution does not reflect the intersubjective intention of all participating users.
Depending on the use case this may work well, e.g., in simultaneous collaborative editing where you can loose just some of you last keystrokes or mouse clicks but less in others like banking applications.
However, for building user-facing applications with CRDTs, their importance is unclear.
The question with CRDTs and local-first paradigms has always been the pressing need (or the lack thereof). The only one plausible 'need' that CRDTs serve is real-time collaboration and that too with a squinting eye.
Real-time collaboration support translates, in practice, to text-editing and picture-editing collaboration. Google docs and the ilk have solved that problem (using central solutions). A CRDT-inspired central-solution like Figma is inspiring, and maybe that's the only place CRDTs fit in their survival quest when combating against central-solutions.
The rest of the claimed advantages seem to not withstand the test of times. This articles talks about 7 features of CRDTs [1].
Fast: Things are already fast with central solutions.
Multi-device: There is multi-device support with almost all solutions (if you decouple the real-time collaboration aspect).
Offline: It's rare, at least in first world countries, to be in a need for offline access (except maybe in airplanes).
Longevity: As can be seen from another comment here, longevity is actually a problem with CRDTs because data model updates are not easy.
Privacy: With BYOK encryption pattern, privacy is not as much an issue.
User control: Even with CRDTs, user is not in control of their data - other peers can mess with your data.
It's not just this way for collaboration software. Servers make everything more brittle. A few years ago, I tried to restore every website I've ever made. Static files were easy, things that relied on old versions of server-side languages were harder and anything stored on a server or in a database was just gone. That sucks. I want us to be able to keep our memories forever, not lose them because we stopped paying a hosting bill.
Also, it is hard to buy the argument that docs based on Google Docs will live less longer than docs served by some CRDT-based collaborative application. It is easy to argue the opposite. My Google doc history shows docs I have even forgotten ever existed, and Google docs play nice with Microsoft Word - making it interoperable with the largest ecosystem around structured documents. Again, this is about product features and prioritization, not underlying building blocks.
CRDTs hold a very special place in my heart. But I also believe they don't offer a differentiated solution - on the user facing side.
Yes, if everything goes right, a centralized service will probably do a better job of keeping your files around than you will. But I have way more stories where something went wrong and I lost them.
[1] https://www.gabrielgambetta.com/client-side-prediction-serve...
Will look into it, thanks!
On a Last-Write-Wins CRDTs, can I just set my computer's time to like 100 years in the future, and thus make changes that can never be reverted by anyone?
Maybe one should take the larger of the server and client times?
My take years ago on a simple ERC-20 token (source) for a "SpaceX" (sic, should have been SpaceBit) token.
Pretty obvious name though.