Offline eventually consistent synchronization using CRDTS
Tags: webdev, go, programming, algorithms
Published: 2023-12-10 03:02:01


The 2023 way is to lock your data in a walled garden, keeping it safe and secure in someone else's computer (a server). You put trust in the service and hope for the best.  Hope for no  leaks, hacks, security breaches or rogue employees. When the service ends hopefully there are backups available and a way to extract your own data. This pattern is one most of you are familiar with. It's the way web 2.0 works, and by 2023 it's old hat!

Today; we talk about a niche suite of algorithms that enables a better way, Conflict Free Replicated Data Types (CRDTs) enable an eventual data sync data between peers. This can be, servers/browsers/phones or anything in between. It's a cool alternative to locking data behind a server, and it makes some hard features easy

- Users always having a copy of their own data
- Easy support for offline mode
- Simplified architecture

The local-first software movement aims to put that control back in users' hands. Groups like Ink & Switch Research have been doing some fascinating work in this space. Their insights into eventually consistent, yet resilient systems inspired me to embark on my own learning journey with CRDTs.

In this series, I plan to document my progress building a small prototype application using conflict-free replicated data types. CRDTs provide a neat way to replicate application state across devices without worrying about sync conflicts. The goal is to see these patterns in action by implementing database synchronization between server, desktop, mobile, and browser-based peers of the app.

## What are CRDTs?

![](/public/CRDT-merge.png)

So what exactly are conflict-free replicated data types? They are specially designed data structures that allow for eventual consistency of application state. What I mean by eventual consistency is that nodes can update their local copy of state independently and immediately then propagate changes to other nodes asynchronously, yet all nodes eventually converge to the same global state due to a mathematically-guaranteed merge procedure.

This magic lies in the CRDTs' commutative, associative, and idempotent merge function.

> Basically, no matter what order changes or updates arrive across nodes, applying them results in the same output state.

The most simple example of this is a Set. If multiple nodes perform an 'Add' operation, the same eventual state is reached. When you need to 'merge' state you simply do a 'Union' operation of each state and a final shared state is reached. The fantastic part is it doesn't matter what order of events happen on each of the peers, it can seamlesly be merged together at some point of time in the future. Pretty nifty! This is the key property that eliminates update conflicts even across disconnected and independent replicas.

By removing the need for coordinating events, you get this awesome property of local first editing. Immediate feedback can be given to the user, and whenever a sync is possible it can happen in the background

## The prototype

Theory is great, but how can we apply this in practice? Instead of starting from 0, and writing a CRDT, let's try and leverage an existing project to do the heavy lifting. My choice is [crSQLITE](https://github.com/vlcn-io/cr-sqlite), an extension for SQLite to support CRDT merging of databases. Under the hood, the extension creates tables to track changes and allow inserting into an event log for merging states of separated peers.

What's great about choosing SQLite as a platform, is it is a ubiquitous development environment. I can get this built for every platform, and all my favorite libraries are setup to work with SQL already.

Now, I wish I could share with you the skeleton of requirements for a big amazing project, but I'm just not quite there yet. Ideas I've been thinking about include:

- An extension to my markdown editor [markdown editor in tailwind react and wails](https://www.ersin.nz/articles/markdown-editor-with-wails-react-tailwind)
- Simple diagram tool
- Time tracker
- ????

No matter what, my goal with this is to test out this CRSqlite thing, and build something desktop based using wails, which can be run on my desktop, laptop(s), phone and anything with a web browser. So without further ado, I'm introducing the newfangled [cr-sqlite-go](https://github.com/ebuckley/cr-sqlite-go), a simple library that wraps the CRSQLite extension and provides a simple API for interacting with the database.

My vision is to eventually build an application that seamlessly synchronizes across peers, with offline support and including as many platforms as possible. Hopefully along the way we can learn some things about CRDT, and give my stack choice a good workout.