Merge-free synchronisation with mergeless

Synchronisation between a client and a server has been a problem that I have been brewing on in the back of my mind for a long time now. Today I am releasing a Haskell library that helps with exactly this problem.

Synchronising information between two parties is a non-trivial problem. Let us consider simple textual notes as an example.

If two parties can both create notes, then synchronisation involves sending over new notes, deleting notes that have been deleted remotely, etc. Most importantly, synchronisation also requires solving the problem of what should happen when two parties both modify a note. Now we must choose some strategy to merge the modifications to decide on which result to keep and synchronise. This is problem that requires careful nuanced consideration, as anyone who has used git will surely realise. However, when we make the assumption that modification does not occur, then the problem of merging modifications disappears.

In the case of notes, this could be a valid assumption depending on your application. A real world example of such a case is Intray. Intray items can be added and deleted, but never modified.

I wrote a little library that deals with merge-free synchronisation generically. The mergeless library is on hackage and on GitHub. The rest of this blogpost is about the API, the internal details are for another blogpost.

Tutorial

Let us consider an application as follows. A central server stores textual notes, and multiple clients can add or delete (but not modify) items and synchronise the items with the server.

+----------+              +--------+              +----------+
| Client 1 |  <-[Sync]->  | Server |  <-[Sync]->  | Client 2 |
+----------+              +--------+              +----------+

Specifically, we choose the items to be of type Text, and we need to choose how we will identify these items using a separate identifier. We can use UUID, Int, or anything that can be generated to be unique at the server-side. For this example, we will choose Int.

Server-side

On the server, we set up an endpoint that can respond to synchronisation requests. We will leave the specifics of the boundary up aside for now, and focus on the processing of the requests.

Using mergeless, a client will send a SyncRequest Int Text and it expects the server to respond with a SyncResponse Int Text. You can implement this processing manually, or you can use the processSync function provided by mergless.

processSync :: (Ord i, Ord a, MonadIO m) => m i -> CentralStore i a -> SyncRequest i a -> m (SyncResponse i a, CentralStore i a) 

The server will need to keep a CentralStore Int Text that contains the items. It also needs to be able to generate unique Int values. This is the m i argument to processSync. To generate unique Int values, the server should also keep the last Int that was generated, and increment that every time. The processSync function will use IO to figure out the time stamp for synchronisation, but you can also supply it manually with the processSyncWith function.

That is all for the server-side. Let us have a look at the client-side as well.

Client-side

On the client-side, we will keep a Store Int Text of the items. A client can get started with an emptyStore.

To perform a single synchronisation step, a client must first produce a SyncRequest Int Text using the makeSyncRequest function.

makeSyncRequest :: (Ord i, Ord a) => Store i a -> SyncRequest i a 

Note that nothing other than the store is necessary to make a synchronisation request.

When the server sends back its SyncResponse Int Text, the client only needs to update its local store using the mergeSyncResponse function.

mergeSyncResponse :: (Ord i, Ord a) => Store i a -> SyncResponse i a -> Store i a 

That is it! All the tricky parts are nicely encapsulated in the library so that you can focus on developing your application. To see mergeless in action, try out Intray and its command-line client. The client will automatically synchronise with your Intray so that you can use your Intray offline as well.

If you liked this blog post, please consider becoming a supporter:

Become A Supporter