The story I have in my head for CRDTs is basically all math and theory. I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world. Do they interact with disk storage? Are there dedicated DB solutions that don't ruin their mathematical guarantees?
https://www.antidotedb.eu is an example of a CRDT database that very much hits disk and preserves the mathematical guarantees. It's based on transactional causal+ consistency, which is formally proven to be the strongest consistency mode for an AP database. Other great examples are https://automerge.org and https://www.macrometa.com
(Disclaimer: building a database system on top of Antidote at https://vaxine.io).
You can move CRDT data over whatever data layer you have on hand, and insert them into whatever data stores you want. Care for the special semantics of CRDT are only needed when merging CRDTs, storage and transportation is like any other encoded format, like moving a JPEG encoded image over HTTP, or storing a JPEG as a byte stream in a database. Neither the HTTP client or the database need to know how to turn the JPEG bytes into screen pixels.
Here’s a possible design for a CRDT editor system:
Browser client composes a CRDT locally in-memory, and saves the CRDT data into IndexedDB periodically as a Blob of bytes.
When the client is online, it periodically performs a sync with the server using HTTP, with this protocol:
1. HTTP GET /doc/:id/stateVector - returns the latest state vector on the central server. A little analogous for checking the refs of a git remote.
2. HTTP POST /doc/:id/push - send the difference between the state vector returned from (1) and the client’s local state to the server. This is kinda like `git push`.
3. The server responds to (2) with the missing state on the client. It can compute this from the data the client sent.
Inside the server, writes are handled like this:
1. Start a RW transaction on a Postgres row containing the CRDT data.
2. Read the data from the DB and merge it with the incoming data in the client post.
3. Compute the update delta for the client
4. Write the merged data back into the DB
5. Commit.
6. Respond with the delta computed in (3).
This scheme is not optimally efficient, but shows that you can put together a CRDT system with a normal database and a bit of HTTP.
Yep. I've done something very similar on top of Diamond Types for a little personal wiki. This page[1] is synced between all users who have the page open. Its a remarkably small piece of code, outside of the CRDT library itself (which is in rust via wasm). The way it works is:
- On page load, the server sends the whole CRDT document to the browser, and the server streams changes from that point onwards.
- When a change happens in the browser, it makes that change locally then and sends anything the server doesn't know about upstream.
- Whenever the server finds out about a new change, it re-broadcasts that change to any subscribed browser streams.
I'm using the braid HTTP protocol for changes - but we could easily switch to a SSE or websocket solution. It doesn't really matter.
At the moment I'm just using flat files for storage, but there's nothing stopping you using a database instead, except that its a bit awkward to use efficient CRDT packing techniques in a database.
> I'd love a quick perspective on how CRDTs integrate into real app infrastructure in the real world.
There just aren't a lot of good integrations with databases yet. There's nothing technical stopping that from happening - but I don't think we even know CRDTs could be fast enough to be practically useful until last year. So its going to take a few years before this stuff bleeds into databases.
A list CRDT like diamond types or Automerge is just a set of changes. Changes are like git commits - they have an ID, parents, and details of the change. Its like if you wanted to store a git commit per edit / per keystroke a user makes. The algorithms / mathematical guarantees don't care how you store and send that data set.
Aside from some clever algorithms, an (operation based) CRDT is essentially an append-only set of operations, that needs to be replicated between peers. There's nothing magic about them, and any infrastructure which can do that can support CRDTs.
So you could just store each change as an entry in a database table - and actually, that'd work fine in practice[1]. The problem is that you'd end up using up a lot of space for a document, because there are so many changes. Type a 10 page paper? That'll be 260k database entries! There are plenty of tricks to storing this information compactly. Simple RLE encoding decreases size by an order of magnitude. (Thanks to Martin Kleppmann for this work). But lots of compact binary representation tricks don't play that nice with modern databases. And you don't want to have to load & re-save the data each time you change something.
One long term answer would be to bake CRDT compaction techniques into databases themselves, but obviously this will be idiosyncratic. And there's lots of shorter term solutions, like using multiple tables + run-length encoding values. But I think the CRDT libraries themselves (Yjs, Automerge, Diamond Types, etc) need to mature some more. I don't see much point hacking up postgres when the set of fields & semantics are still (somewhat) in flux. (Well, yjs might be more ready for this work - but its probably still a good idea to wait until yjs's rust port (yrs) is done).
[1] It'd work fine the way my own CRDT (diamond types) is designed, since DT just needs to store the "origin positions" of each change. In Yjs and Automerge, changes store references to the ID of the item to the immediate left. In order to generate those changes, both automerge and yjs need to look up those persistent IDs - which in practice means they need to load the document state into memory first.
...but it's important to note that CRDTs as used by Redis (and as defined by, for example, https://arxiv.org/pdf/1806.10254.pdf) really just means that you've defined a way to consistently resolve conflicts - it doesn't necessarily mean the all-singing-all-dancing collaborative text editing that a lot of people seem to be assuming. For example, as defined in the paper above, simple "last write wins" is a CRDT.
Well, I should rephrase: I didn't know CRDTs could be fast enough to be practical. At least in the context of collaborative text editing. I've been in the field I was arguing against using CRDTs for over a decade.
I ran a bunch of optimization experiments 18 months ago[1] and realised I was wrong. I demonstrated (at least to my own satisfaction) that all the problems that CRDTs had (memory usage, disk usage, CPU usage) seemed to be finally solvable. Last year I put out a blog post[2] talking about how to get insane performance. Both of these posts were discussed in detail here on HN.
One result of this is that automerge (an excellent CRDT) has started optimizing for performance. I hear their performance on this benchmark has improved from 5 minutes to ~2 seconds. Yjs can do the same thing in 1 second. Diamond types (my own CRDT) is now about 6 times faster than it was when I wrote that post last year. I can run the same benchmark in ~10ms (0.01 second). Memory usage has dropped from automerge's 880mb, to 2mb in diamond types. And I think we can get it much lower. Disk size for the same data set has dropped from 4mb of JSON down to 100kb while still storing the full edit history. (And this is for a 100kb document!)
There's a lot of tricks involved, and plenty more in the tank. But in short, modern list / string CRDTs are now close to the speed of their equivalent native data structures. With a text CRDT in rust, more CPU gets wasted in wasm overhead than is spent maintaining the CRDT itself.
Thats not something we knew was even possible a year or two ago. So, thats whats changed.
We have a log processing system that performs entity resolution and merging of data. It does this without synchronization, out of order, in parallel.
What that means is we may get N records referring to the same 1 entity. We incrementally build that entity as records come in. Regardless of the ordering of the updates, we always end up with the same information in that entity.
In our case this is for security analytics. This lets us process data from arbitrary sources, with arbitrary ingest cadences, and build a single graph of entities and relationships. Every property has a merge strategy.
The exception to this is that we also have immutable properties. These are contract based - we store the first write and assume that the value will never change, and it's up to the client to only mark immutable data as immutable when that is correct.
