Intro

This is the second installment in a series of blog posts - accompanied by planned screencasts - that introduces a proof-of-concept solution for sharing data across multiple devices, in a surprisingly tiny amount of code.

GitHub: https://github.com/indolamine/lizt

CRDTs

According to authority at crdt.tech, A Conflict-free Replicated Data Type (CRDT) is a data structure that simplifies distributed data storage systems and multi-user applications.

For our practical purposes, using converge, CRDT is a piece of Clojure data that is atom-like, in the sense that it can be swap!-ed reset! and deref-ed and even watched via the standard add-watch.

What makes it magical is that as the value changes, the datastructure’s underlying implementation makes sure that “history” is also kept.

CRDTs are built from the ground up under the assumptions that

• multiple actors will have their own copies of some revision of the data
• these actors will independently make changes to it
• there will come a time when these independent branches “meet again” and the changes done by the different actors will need to be consolidated
• this consolidation process should not rely on any kind of central authority, all actors should be able to do it themselves, with the exact same results when consolidating the change sets
• the consolidation process is convergent and eventually consistent - practically meaning that if two actors have seen the same change sets, independent from the order, the channel, possible duplications, and both run the data consolidation process in the pre-defined way, they will end up having the same end state of the data (and the history). Plus, if the whole distributed system is not in “motion” (nobody has changes that were not propagated in some way to all other actors), the system is consistent - everybody’s “truth” is exactly the same as everybody else’s.

That’s it in a nutshell. So, what then, in terms of implementation and usage?

When working with CRDTs, you’ll be dealing with structured, even “transaction-like” updates to your data, so that the recording of changes is possible. Plus, you’ll see “timestamps” or “clock states” that assist all actors in figuring out an exact ordering of changes that happened. And of course you’ll have some kind of record of the changes themselves, “timestamped”.

Let’s spend a minute on the timestamp wording. It’s actually not a timestamp in a traditional sense. For getting control of a distributed system, where stuff is happening concurrently, and both the communication channels and “system clock” settings are unreliable, you’ll have to live with a method of ordering happenings in an arbitrary way. It doesn’t need to represent the actual “order” of things that happened in a “wall clock” sense (which is by the way pretty volatile since Einstein), but it needs to provide a way where absolutely exact ordering is possible. Most CRDTs use something called a Lamport timestamp or a vector clock for this purpose. This idea itself has quite some literature which I won’t go into here; what matters from our perspective is that there is something that we’ll refer to as “clock” or “timestamp” which looks nothing like your standard timestamp, but assists us in making order in the chaos of this distributed data system.

For the sake of easy implementation we’ll actually rely on a central point of authority for our sync process (the “backend”) but this is not in any way a must. As stated before, actors can do data consolidation independently from each other and from the communication channel(s) used. It’s just easy in a PoC for everyone to talk to some well-known central actor, whose only special quality is that it is well-know by every actor. Nothing else. The whole sync process could be implemented in a peer-to-peer fashion without any central actor quite easily.

Our process then of consolidating data across actors will look something like the following:

• actors branch out from some common root data
• all actors will get this common root from the “backend”
• actors make changes and regularly check-in with the server, saying “this is the time as I know it being now” (a “clock” value), and “here’s what happened on my side” (a change set / diff, starting at the “time” of the last rendezvous)
• as a response to this check-in, the server will respond in kind, sending “this is the latest timestamp I’ve seen so far”, and “here are the changes that you haven’t seen yet, according to your own admission of your clock value”
• both sides to the data consolidation, at which point at least the “backend” and this one actor have their states consolidated

On to code

Let’s play around with this, in a single REPL (a JVM one for now).

;; require the api for data management
(require '[converge.api :as c])
;; => nil

;; create and initialize the root data
(def cref-origin (c/ref {:name "Foo" :items [0 1]}))
;; => #'session-1/cref-origin

;; let's grab the current value, as if from an atom
@cref-origin
;; => {:name "Foo", :items [0 1]}

;; let's create a copy of this, similar to what another actor will do to initialize
(def cref-branched (c/ref-from-ops (c/ref-log cref-origin)))
;; => #'session-1/cref-branched

;; verify that the branch has the same data
@cref-origin
;; => {:name "Foo", :items [0 1]}

;; AND now, let's diverge

;;We'll change the name in origin
(swap! cref-origin assoc :name "Bar")
;; => {:name "Bar", :items [0 1]}

;;We'll add a new item on the branched
(swap! cref-branched update :items conj 2)
;; => {:name "Foo", :items [0 1 2]}

;;now, we have two independetly changed crdt instances, let's merge them
;;this is a side-effecting call that will mutate cref-origin
(c/merge! cref-origin cref-branched)
;; => #converge.opset.ref.OpsetConvergentRef[{:status :ready, :val {:name "Bar", :items [0 1 2]}} 0x665831cf]

@cref-origin
;; => {:name "Bar", :items [0 1 2]}

;;yay, so our origin now has both changes - let's do the same with our branched
@cref-branched
;; => {:name "Foo", :items [0 1 2]}

(c/merge! cref-branched cref-origin)
;; => #converge.opset.ref.OpsetConvergentRef[{:status :ready, :val {:name "Bar", :items [0 1 2]}} 0x7da5f7e9]

@cref-branched
;; => {:name "Bar", :items [0 1 2]}

;; so, our first attempt in consolidation succeded, both actor hava both changes applied

The above is a nice demonstration of the foundations, but bear in mind, that we have the luxury of being in the same process; which makes it easy to just collide the two diverged pieces of data with each other fully. In a networked scenario it would mean sending a huge amount of data back-and-forth. We can do better.

;; create and initialize the root data, plus initialize a branch
(def cref-backend (c/ref {:name "Foo" :items [0 1]}))
(def cref-client (c/ref-from-ops (c/ref-log cref-backend)))

;; let's save the clock state that the client has seen upon initialization
(def client-seen-clock (c/clock cref-client))

;;We'll do the changes
(swap! cref-backend assoc :name "Bar")
(swap! cref-client update :items conj 2)

;;... and for the consolidation, we'll use "patches"

(def client-originated-patch (c/patch-from-clock cref-client client-seen-clock))

;; client shows this patch to origin and origin merges it
(c/merge! cref-backend client-originated-patch)

;;origin now has both changes, creates a patch for the client to use
(def backend-originated-patch (c/patch-from-clock cref-backend client-seen-clock))

;;sends this path to client, who receives it and merges
(c/merge! cref-client backend-originated-patch)

;;... and there we go, both sides have all changes and the same state

(= @cref-backend @cref-client)
;; => true

And there you have it, that’s all there to it to do a sync loop between two actors. Note that the process is pretty symmetrical, there is nothing special about “origin”. The loop can be repeated anytime… if there are no changes, the patch will just be empty in one or both directions.

What’s left to do really, is to pull up a client-server infrastructure, implement some backend endpoints and a client to “pull apart” what we did here in a single REPL. For this, we’ll turn to Pedestal, cljs-ajax, Transit and Reagent, but that’s a story for another day.

Cover photo

Photo by Zach Reiner on Unsplash