Shelf: easy way for recursive CRDT documents

In the past we already discussed how to build JSON-like Conflict-free Replicated Data Type. We used operation-based approach, with wide support for many operations and characteristics of a dynamically typed recursive documents. However with that power came complexity. Today we'll discuss much simpler approach, which some may find more appealing, even thou it comes with much more severe limitations.

We'll be discussing a Shelf CRDT, which original JavaScript version could be found on github. Here, we'll discuss a pros and cons of this approach and show an implementation in statically typed F# code.

We'll start from defining our value containers:

[<Struct>]
type Shelf<'t when 't : comparison> =
  { value: Node<'t>
    version: int }   // used for conflict resolution

and Node<'t when 't : comparison> =
  | Value of 't
  | Object of Map<string, Shelf<'t>>

Shelf recognizes only two kinds of values: objects representing multiple entries and scalars treated by the algorithm as an atomic pieces of data (replaced in their entirety during conflict resolution).

If you got some intuition about conflict-free algorithms (if not, I encourage you to start reading here) you know that in order to figure out how to resolve potential conflicts between multiple agents updating the same value concurrently, we need some metadata to keep around to even discover that concurrent updates have happened. Here, we use version field for this - it's just a single number incremented every time a corresponding entry gets updated:

module Shelf 

//NOTE: deeply nested shelf updates will increment version on all
// nodes on a path from the document root down to the leaf
let set v shelf = { value = v; version = shelf.version + 1 }

Ok, so now we have something to compare for concurrent updates. But how merging would work with it?

1. If we merge two Object nodes, we recursively merge their corresponding entries. Entry which didn't exist on merge side will just get added.
2. If we merge nodes of different types, we arbitrary allow for Objects to take precedence over Values.
3. If we merge two Values, we first compare their versions: greater version number wins. But what if versions were the same? You may have notices that our type Shelf<'t when 't : comparison> puts a comparison constraint over 't. That's right: since we don't use replica identifiers, we compare values themselves and pick the one that's logically "higher".

With these rules at hand, we can produce an extremely simple merge algorithm.

module Shelf

let rec merge a b =
  let cmp = a.version.CompareTo(b.version)
  if cmp > 0 then a
  elif cmp < 0 then b
  else
    match a.value, b.value with
    // objects takes precedence over scalar values
    | Object _, Value _ -> a
    | Value _, Object _ -> b
    // scalar values are compared against each other - greater one wins
    | Value ma, Value mb -> if mb > ma then b else a
    // recursively merge objects entries
    | Object ma, Object mb ->
      let result =
        mb
        |> Map.fold (fun acc kb vb ->
          match Map.tryFind kb ma with
          | Some va -> Map.add kb (merge va vb) acc
          | None -> Map.add kb vb acc
        ) ma
      { a with value = Object result }

That's basically all you need to work with this data type. But as you might have noticed, there are strings attached: this approach has multiple drawbacks and we're going to talk about them now.

Tradeoffs

Obvious observation is that our version used here is just a simple numeric value. What does it give?

Delta-based replication

Most (if not all) of the time we considered using vector clocks or at least pair (id, seqNr). Shelf doesn't recognize concept of unique replica identifiers, which on positive side makes things easier and reduces the metadata size to only 4-8 bytes per entry. On negative one it makes impossible to simply calculate deltas, therefore forcing full state replication even when only one entry has been changed. What can we do with it?

1. Limit the use case of this approach only to a small documents.
2. Fall back to change version type to make use of vector clocks and dots. This would allow to compute deltas (as we would know which entry has been lately changed by which replica) and introduce branch cutting for potentially faster conflict resolution in deeply nested documents. Of course this comes at the price of higher memory footprint and overall complexity.
3. If you'd consider a push-based replication approach, it would be possible to store delta aside of main Shelf structure. That delta gets reset to zero state every time it's being replicated and it's filled only with copies of entries which have been modified locally by current peer since last replication round. This way we only replicate change sets, but at the flip side we're now responsible for ensuring that these changes were received by remote peers (popular approach is to use push-based deltas for frequent and cheaper replication then from time to time send a full state to ensure that all changes have been synced).

Accuracy

Another problem we could talk about is the accuracy of conflict resolution algorithm. We simply use combination of version + native comparison of value type stored inside of the shelf to determine which of the conflicting entries to store and which to drop. This means that ie. person who makes two updates of the same entry in a row will always be prioritized over the one who did it once. It doesn't matter which update was the most recent, only which one is changed more often. In order to fight that we could use ie. hybrid logical clocks instead of sequence numbers.

The property above, combined with the fact that native type comparison is rarely a desired way to do a conflict resolution, may lead to a situations where conflict resolution produces an unexpected outcomes. In defence of this approach what we're prioritizing here is eventual consistency - having a good accuracy that correctly reflects users intentions requires specialized algorithms and data structures. Here however we value simplicity and low metadata footprint.

Missing operations

You can notice, that Shelf doesn't have a concept of lists. We could mock them by using Map<int, Shelf<'t>>, but this approach doesn't cover all use cases ie. we're still unable to differentiate between updating and inserting elements.

Another thing is element deletion, which is also absent. Again we could mock it by having a dedicated tombstone type among the variants of 't, but we would need to correctly interpret it during value reading.

I would advise against using Shelf as universal one-size-fits-all CRDT document implementation, as this will inevitably result in raising the complexity over time as more and more uses cases will have to be covered. Instead, let's think about scenarios where the inherent limitations of Shelf could be ignored or they are not much of an issue.

Use cases

Lack of deletion support works strongly against using Shelfs for general-purpose CRDT map implementation. However, if all you need is to apply CRDT merge semantics over existing instances of statically typed structures, it's no longer a problem (for statically typed systems objects don't have their fields spontaneously removed at runtime).

Notice that concept of tombstones is also absent here. Since Shelf is also state-based approach, we don't have operations that we need to store and send over. This means, that this structure is good fit for a frequent updates that could otherwise produce a ton of quickly-outdated data.

Lack of replica identifiers means, that we're not affected by spontaneous vector clock size explosion (it could happen ie. for long living documents, whenever a new user session creates a new replica ID).

Lack of native support for delta-state replication suggests using it for instances that are small in size or have all of their fields changed frequently.

With these properties in mind, let's theorize about potential practical applications for this data structure:

• When working on Yrs we figured out that this approach may be useful for keeping user metadata (cursor positions, name etc.). Since a user may be logged on multiple devices (each one would need its own replica ID), but usually uses only one at the time, inaccuracy of conflict resolution doesn't seem to be much of an issue. Our discussions there were also primary inspiration for this blog post.
• Another thing could be a fleet of vehicles, where we want to track their recent location.
• With potential overhead as low as 4-8 bytes per element, we could even create a collaborative bitmap canvas data type on top of Shelf merge algorithm! Imagine canvas which consists of pair: bitmap of RGBA pixels + bitmap of versions per each pixels. Each pixel change also increments a version of a corresponding pixel. This is also nicely aligned with usage of SIMD operations (including shaders!) for merging multiple entries (pixels) at once as well as potential of using well known compression algorithms to optimize replication payload. You can see proof of concept of this approach in this gist.