What are CRDTs?

  • Basicly the technology thats required to really make collaborative offline-first apps a thing. If collaborative offline-first does not sound like a hard problem to you, I challenge you to try out implementing the simplest thing you can think of in a small app (e.g. a todo list)!
  • To give some hints: Syncinc.., State.., wait.. how do I merge data? Who wins the merges if both change the same file? What happens if both change the order of items? Do I just pick the latest merge and ruin the complete order for someone that adapted the order really carefully offline?...
  • I won't go into more details here. But CRDTs are a dream come true for solving these issues.

What is automerge

  • Automerge is a great library implementing CRDTs. It is also the library Martin Kleppmann brought into live. A really kind, and super smart dude (based on his work on CRDTs and what one could experience in the slack channel). The library can be found here.

Okay, lets continue with the good part, the learnings. I did implement the automerge library to solve the offline first and syncing problems for a shopping app I am creating using react-native.

1. Learning: An endless document history can cause big performance issues.

Problem: An endless history is... well, endless.

  • Being able to merge documents even if one user has not been online for months is a great feature. This would also be a quite complicated task (if we really want to merge instead of just overwrite it with the current state). It also means that we have to be careful with the amount of changes.. I slowly started to experience lag on my shopping list app and was really confused. I did not change anything... Why is it getting slower..? Why is this only happening with the shared list I have been using all the time, why not with a new one? I did add logging for the merging part (the moment when the local state and the remote state get combined into a correctly merged new state).Well, I quickly realized that if merging takes about 1.5 seconds, the ui is blocked for this whole time. This is a disaster. Testing it for the new lists, although having a similar amount of items, was done in some(40?) milliseconds.
  • Okay... lets see how big the history was.. After examining that, the history has been over > 1500 entires. Meaning 1500 times the state of the shopping list did change. This is not to much for a longer period of time, if we consider that every "done", "rename", "add", "delete", "drag and drop" etc is at least one change. But it was way to much to handle in the frontend. Also the history is of no real use for me, besides people that don't touch their phone for months, then do some stuff without internet connection, and then merge their changes correctly when they connect to the internet again. This rare case can just be dropped, if this means my app performance is not ruined.
  • Some basic tests showed this behavior: You can check out the doc on pastebin
result: 250ms for 58 changes.
result: 380ms for 128 changes.
result: 650ms for 228 changes.
result: 1s for 567 changes.
result: 3.1s for 1675 changes.

Yeah, waiting for 3 seconds whenever someone creates a new item in the shopping list, sounds good, no? :D

Solution: Create new documents

  • After digging throughly most of the github issues of automerge, I noticed this one: history compression. Where someone posted their solution for working with big documents (a lot of changes) is just to: - determine once the collaborative session is over - copy all data and create a new automerge document based on this.
  • What are the implications? - We will create a new document with history size of 1 and our merging problems are gone! ๐Ÿฅณ - We can't merge this document with anyone since they don't have the same root (this is the only hard requirement for merging two docs). ๐Ÿ˜Ÿ - BUT we can overwrite all the users documents with the new one (having same items, but no history) and then everything just works like before! ๐Ÿ˜ NOTE: This CAN cause ONE lost update, depending on your use case, this can be drastic. You will still need to sort this little bit out.

2. Switching work to the client can cause the UI/UX to feel terrible.

Problem: Merging blocks the UI in the client

  • Even with the optimization done in 1. we still are merging on the client which just takes time. It may not be much, but can be up to 300ms with my current approach for the devices I tested. At first I thought offloading to the client would be smart to save compute, but it turned out that I have to merge at the server anyway.

Solution: Don't merge on the client

  • Switching from merging the documents to just accepting the documents from the server as the "single source of truth" has been a great improvement in the UI/UX in the app. Now I get real time updates via websockets without the ui being blocked for a short amount of time (okay, the amount is just way shorter and does not get witnessed anymore :P). Since I had to merge on the server anyway, I am not even doing more compute on the server (what was what I did fear in the beginning).

3. CRDTs are awesome!

  • While having to adapt to certain constrains of the library, the result is still astonishing to me. Having something "git like" with automaticly merged conflicts just blows me away. Even if people are offline, and we are having multiple people doing different work.

And that's the end for now, I wish you a nice day!

Want to read more?
FP for the practical programmer. pt1 - The Either type
Hands on explanation of the concept behind Either and how you can implement and
Automerge Zustand React Native Drama
The tragedy of using react native async-storage with automerge and zustand
Built with ๐Ÿงก using RNW and Nextjs