Elm-crdt: build collaborative local-first apps

[gampleman]

This week I’ve released elm-crdt, which is a library that allows you to use and compose different CRDT data structures. I’ll explain what those are and how they work in a minute, but first I’d like to give you an idea of what this enables:

• multiplayer collaboration: make your app behave like Google Docs, Figma, or Linear where you can collaborate with others in real time.
• offline capability: spotty wifi? Make changes while offline, then sync when you get reception.
• decentralized: build an app that distributes its data over a generic relay like Dropbox or Bluetooth, no server required.
• high performance: because you can merge with other edits seamlessly, having stale data is much less of a problem. Because of that, you can load and cache all the data a user might need and then simply render the data from memory instead of waiting for HTTP. Then just receive updates over Websocket and update the UI.

Now you might be wondering, how come so much functionality is enabled by just using a set of special data structures?

CRDT stands for Conflict free Replicated Data Types. The most important guarantee they give you is that the operations you can perform on these data types can be applied in any order while giving you the same result.

This is super important when you have multiple people working on a document at the same time - the key problem in that scenario is that we don’t want it to matter who’s network request was faster or so on.

Most webapps today solve this problem by having an authoritative server, and whose request arrives last “wins” and they overwrite everyone else’s data (often irretrievably so). Another somewhat common solution is locking - the first user who wishes to edit the document takes a lock on the resource with a certain timeout, and no one else is permitted to even start editing the resource. Neither is a great user experience - the first involves outright data loss, the second makes you wait in line to do your work.

CRDTs propose to solve this problem by intelligently merging the various edits users might do. But what does ‘intelligently merging’ actually entail? That’s why they are a family of datastructures, since what an intelligent merge means depends on the specific situation.

Perhaps the simplest practical CRDT is the Last Writer Wins register (LWW). It simply makes the resolved value equal to an arbitrary value that it decides was the last. You might be thinking - isn’t this the same as what you just criticized as being bad in normal web apps? You’re not wrong, but the LWW register has two tricks up its sleeve: it doesn’t loose any of the written values (they just aren’t visible), and it can do this without a central authority that decides who was actually last.

This kind of semantic is often useful anyway: for instance in a graphics program, if I move a certain rectangle 50 pixels to the x axis, and you move it 300 pixels on the x axis, it seems that either 50 or 300 pixels would be a reasonable value to end up with. 0, 175 or 350 would all be much worse options.

However, for integers specifically, we have also a different option: a PN-counter. The canonical example is counting likes (or votes). If I hit the like button, and you hit the like button, we want to end up with 2 likes, not 1 like. So a PN-counter adds up all the increment/decrement operations and comes up with a total.

It’s up to you as a developer when programming your application to think about how things will behave under concurrency. elm-crdt gives you the tools to do that.

We have CRDTs that merge text in very clever ways allowing multiple users to type into the same text field and end up in a reasonable place. We have ones for doing records, lists, re-orderable lists and even trees.

This all composes, so you can define merge semantics at every level of your document.

---

OK, so now we understand how getting rid of order dependence allows concurrent editing, but how do all the other features fall out of it?

Well multiplayer collaboration is otherwise fairly easy: just broadcast the changes each user is making along with “presence” information - who’s mouse cursor is where etc. (presence is BTW included in the library - it’s just a special CRDT that isn’t designed to be persistent) over some channel such as websocket. As long as you don’t have to worry about what happens when 2 people edit the same piece of information, the rest is fairly straightforward. (Don’t believe me? Check out our collaborative demo and it’s implementation.)

The main problem with offline work for web apps is that it effectively makes concurrency a way bigger problem. The last-writer wins semantic of your typical web app isn’t often a huge problem in practice, since for a lot of practical tasks (and many webapps are perhaps subconiously designed in a way to organize work into such tasks), the time between reading the current state and submitting an update is small enough that the likelihood of a concurrent edit is small enough, that the problem doesn’t occur often enough for anyone to get overly annoyed by this.

But if you go offline for a week, make a bunch of edits to a bunch of documents, then go back online, the probability that no one touched any of those documents becomes much lower.

So again, if you have intelligent merge semantics instead, this becomes a significantly mitigated problem. I think it’s fair to admit that I am using the word mitigated rather than _solved, because most CRDTs don’t have exhibit ideal behavior if the documents you are merging diverge to a drastic degree (they are guaranteed to “converge” - everyone will end up with the same document, but it’s not guaranteed to be the document any of the authors actually wanted to end up with).

So generally CRDTs work better with the kind of offline capability where you can take your work on a plane or train, or maybe to a cabin for the weekend, and less well for the six months on a desert island situation.

What about decentralization? I mentioned above that CRDTs have the property that they converge - everyone who merges in everyone else’s changes ends up with the same document - regardless of the order they merged in they’re changes. That means you don’t need a central server that reconciles what is the authoritative document. That means you can collaborate over any sort of network in a peer to peer sort of way. Of course you can still have a central server, it just means that you don’t need it to reconcile documents.

Right, so doesn’t all this clever machinery have a bunch of overhead? If so, why does it help with performance? In most web apps, the worst performance offender is the dreaded loading spinner. The reason you see it so often, is that the application needs to fetch data from the server, so it can make sure you see fresh data - because if the data you see is stale, you might overwrite newer data with older data. But if you can merge changes freely, than stale data becomes much less of a problem. For one, you can fetch fresh data in the background, and because it merges cleanly with the data the user is seeing/editing, it can be patched in place without much disruption. Furthermore, if the user makes a change based on stale data, it will merge cleanly with more fresh changes.

This allows you to store a copy of the users data in local storage and initiate the whole application without a single loading spinner. Then simply sync the data in the background - loading fresher copies and at the same time sending back the changes the user made.

Linear is a great example of this working.

---

Hopefully this gives you a flavour of what CRDTs can do for you and what functionality is enabled with them. There is a lot more depth to this topic (hey - there are even several conferences that focus on these topics) and I’m very pleased to offer my own implementation to the Elm community. Let me know if you build something cool with this!

[jri]

Congratulations! This is excellent work. I’ve browsed the elm-crdt API docs, tried the demo, and browsed the source code. Apparently elm-crdt is a complete, feature-rich, and flexible CRDT core, well engineered, and with informative docs. Very well done

Recently I’ve evaluated the major CRDTs from the JS world (Yjs, Atomerge, Loro), but really dreaded the boilerplate to couple these with Elm. For an Elm application it feels wrong to maintain a shadow model at JS side – and keep both in sync manually. So with elm-crdt we now have a solid CRDT foundation in the Elm world

I’m keen to utilize elm-crdt for my project ( dmx.berlin – DM6 Elm ). It will become a local-first application, supporting offline work and client sync via a sync server (using state vectors?). So it needs networking and storage (both, client side and server side), and I want transmit and store only deltas, not entire documents.

With Crdt.Doc.decodeInto and Crdt.Doc.encodeSince the basis for building all of this is provided by elm-crdt already, and the elm-crdt demo illustrates some of the networking part as well. Regarding the storage part possibly you can give some hints?

How would you store changes in IndexedDB, so that only deltas are written on each change? How would you do persistence at server side? Would a single text file be sufficient, and just appending? Or better some DB? Here i’m assuming elm-crdt runs at server side as well (via Node.js or elm-run).

[gampleman]

Here are some ideas, but of course other ways to do this are possible:

elm-crdt is an operational CRDT, so the thing you need to persist are the operations, and loading it back in is just replaying the operations.

So encodeSince gives you an object {"kind":"ops","ops":[…]}, where ops is a flat list of operations, each carrying its own id (counter + replicaId), its causal deps, and its action. Union of op sets is idempotent and order-independent,

So for IndexedDB you want two object stores, one where you store the ops keyed by their op id (which is just "<counter>@<replicaId>"). This is nice, because it’s indempotent, if you try to store an op you already have, than it will just work.

Then a meta table where you store your own replica ID and the current Version.

Then on every write you send out a port with:

persist doc model =
    ( { model | savedVersion = Doc.version doc }
    , saveOps (Doc.encodeSince model.savedVersion doc)  -- port
    )

which gives you just the ops since you last persisted. This is a nice delta write, the bytes you write will be proportional to the changes made.

Then when booting the application you just load all the ops and do:

Doc.decodeInto payload (Crdt.init myReplicaId schema)

and that should be it. You can then optimize it as necessary with snapshots etc.

Now for the server. You can start with a single append only log of ops:

ops(doc_id, replica, counter, seq INTEGER PRIMARY KEY AUTOINCREMENT, op_json)
UNIQUE(doc_id, replica, counter)

Than you can easily sync the ops with a lastSeq cursor. You don’t even need to run elm-crdt on the server to do that.

But if you do than you can also use some of the fancier features like compaction and causal versions, as well as potentially enforcing permissions etc.

I hope that helps.

[jri]

Thank you for very helpful response!