automerge-rs

21 Jul 2020

TLDR; I’ve been working with a few other people to build a rust port of the Automerge CRDT. The core library is nearly done and I’m starting to think about what we can use it for.

Intro - the frustration of handling multiple devices in a p2p world

I have a little app on my phone that I use for tracking my workouts. I built it in about a day in Kotlin, it’s incredibly basic, but it does everything I need. I’ve been using it for a year and there’s only one feature I miss from other offerings: multi device synchronisation. I find this is true of a lot of simple software that I write for my own use, it’s very straightforward to write a little application or script, but as soon as you want to start accessing that data on multiple platforms or devices things become thorny.

The dominant architecture for handling this kind of problem at the moment is a server/client based one. Now, I’m a “full stack developer” in the sense that I write software which runs on both the client and server, (with a bias towards the server) so when I started wanting to access my workout data on my laptop my first instinct was to start writing a REST API for storing workout data. I decided not to go down that route this time though, because there are some problems with it that I’ve had enough of.

1. It’s intellectually very unsatisfying to have two applications, both running on devices on my local network, which have to send data over the public internet in order to communicate.
2. Unless you’re going to run one server per user it requires introducing the concept of a “user” to an application which has no need of it. I’m not planning on sharing my workout with anyone else.
3. Actually running a server, no matter how simple, is a technically difficult task. I like sharing stuff I make with other people but requiring a server to enable features means that none of my non technical friends or family will be able to use those features. I could run a server for them, but a) I don’t want to and b) that still limits the set of people who could use this software to people who know someone technical to run a server for them.
4. The technical work is incredibly boring. Defining validation and authentication/authorization logic, serialization/deserialization on both ends of the pipe, managing network requests and caching. All of this feels very repetitive, and incidental to the actual problem I’m interested in solving.

These problems have some implications. As a developer there’s a huge jump in complexity from a simple app or script to that same app or script on multiple devices. Furthermore, if you do make that jump, you now need someone to maintain some servers somewhere in order for the application to continue working, which means that person needs to be paid. Now you don’t have an app, you have a SaaS business. My hypothesis is that this double whammy is denying us the creative and productive potential of the powerful computing devices that increasingly surround us.

But what to do? Data has to get from one device to the other somehow. What I want is a way that I can write my application as if it’s just operating on local data, but transparently enable sharing that data with other devices without having to write more application code. How?

CRDTs in general, automerge in particular

The reason that this is a hard problem to solve is that data can conflict. Even if there was a magic networking layer that transported all our data from one replica to another without any application code we would still need to write code on each replica to merge the changes from the other replicas. You can get around this by using data structures which are easy to merge, a class of such data structures are CRDTs. There are plenty of excellent summaries of CRDTs elsewhere, the important point is that you can merge a CRDT from two replicas deterministically and automatically. The strategy seemed clear, express your application state as a CRDT and then just send your state directly to the other replicas, no need for a server!

Unfortunately, “express your application as a CRDT” is non-trivial. There are various surprising edge cases that need to be handled and - in my opinion more importantly - our tools and design patterns are generally designed around mutable state, rather than sequences of events, maybe that will change in the future, for now though, I started looking for a bridge. At some point I stumbled across automerge. Automerge is a CRDT for arbitrary JSON objects. This means that you can write the majority of your application as if you are just working with some kind of mutable state, and Automerge will take care of merging those changes with other peers. This feels like the bridge we need.

Automerge Rust

There was just one problem for me, the canonical automerge implementation is written in javascript. I want to write my applications in Rust, so I rolled up my sleaves and made a start on a Rust port of the javascript library. I got a basic proof of concept working and posted it in the automerge slack channel. It turns out that the folks at Ink And Switch who fund a lot of the work on Automerge, were already interested in building a Rust port, they jumped in as well - and kindly funded me working on the project for 6 weeks - and the result is automerge-rs. automerge-rs is a Rust implementation of an upcoming version of the automerge algorithm with a bunch of performance improvements and small API changes (outlined here). Right now the algorithm is fully implemented and you can see an example of using it in a GUI application here. Right now the API is extremely clunky and the internals are ugly, but it exists, which I count as a triumph.

One of the interesting approaches we took with this project was to compile it to WASM and inject it into the existing javascript implementation. This had two benefits; firstly it allowed us to use the existing test suite to check our implmentation was correct, and secondly it allows us to get performance benefits in environments where WASM can be executed. More generally, Rust’s FFI story is promising for building automerge implmentations in other languages which are backed by the rust implementation (for example, there is an in progress Swift implementation which is backed by the Rust library)

Conclusion

That’s all for now. Right now I’m working on cleaning up the internals of the library, then I want to write a more friendly API for Rust APIs.