Building Better Teams

Articles and Posts

Blog

 

Editing Shared Resources: Conflict-free Replicated Data Types (“CRDTs”)

A relatively new concept offers both the rules for a data structure and the algorithm that promises to let you constantly edit data without using of locks or being afraid of conflicts. Somewhat similar to the previous article’s “diff and merge” strategy, except this is based on generic rules for types instead of business-case-specific rules.

But what rules do we need to reach this kind of system? There’s a few important design choices that will give us the properties we want.

First of all, we need to decide how we will handle a data change. There’s generally two methods for this:

  1. Send a set of instructions to change a value. For example “Increment by 1.“ If your CRDT does this, it is operation based.

  2. Send a specific value and use that one. For example, “Set to 2.“ If your CRDT does this, it is state based.

There are pros and cons for each of these, but for the sake of simplicity we will focus on Operation based CRDTs which I personally find easier to reason about and work with, but I suspect many others may find the opposite to be true.

Imagine a cluster of workers that increment one value, “counter” by 1 each time. We will use the redis INCR command which doesn’t require fetching the value with GET first.

There’s no conflicts! And no locks! This only appears to work for this simple example due to some basic reasons:

  1. There’s no special instructions for how to add the numbers. If redis had 5, it wouldn’t matter if it was 5+1, or 1+5. You just add them. This is known as “commutativity”.

  2. 1+5 (or 5+1) will always be 6. There’s no side-effects to the logic here, and no external data called upon to find out the datetime or some random numbers. This part is entirely deterministic and idempotent ()

  3. It didn’t matter what order the +1s came in, the answer would always end up the same.
    For example, if the INCR commands came in any order, it doesn’t matter if it was computed as 1+5+2+1, or 1+2+1+5, because both end up equaling 8. The result is the same. This is known as associativity.

  4. We’re only pushing INCR commands to a counter. If we used SET commands and overrode a value, we would lose this known “one directional order” of moving forward, because SET would change the concept from a set of operational based changes into a state based system. As a thought experiment imagine that redis was really slow and processed 1 command per second. The command buffer would look like an array of [+1, +1, +1, +1, +1]. This order only grows, we can’t remove commands that will get processed. If we wanted to decrement the value we would push a “DECR 1“ command. The main idea here is that commands are ordered and only grow in one direction (longer). While it is true that redis will read from the buffer and remove items, that is an optimization on Redis’s part, it could just as easily store this list in memory to keep values consistent, and compute the sum of values whenever needed.

When an individual worker runs there’s no locks and no conflicts. Values might be able to branch off into different solutions (for example, worker 1 and 2 could end up in a state where values in memory are different), but the design means that values will always be resolvable towards one final state. We’re just adding +1+1+1 many times, and because of how basic arithmetic works it will always be able to resolve this conflict.

Okay, okay. I know, this is just a simple counter. This isn’t helping you with that complex 50MB session object in your legacy system’s session storage. However CRDTs show us that these concepts can expand well beyond these simple cases. There are even libraries that can find solutions to “merge conflicts” in complex JSON objects, the kind you needed a lock for previously.

The secret is in those rules from earlier. If we find an operation based way to keep order and join values in a commutative, associative, and idempotent way: we get the same benefits as the simple counter we looked at before.

One last important note, CRDTs do not need a central repository like redis. I used this as a way to slowly introduce the concept while still using concepts well understood by web developers. In reality, CRDTs can communicate with any number of workers directly or indirectly with any number of storage systems. It can be freed from the “single source of truth” concept whenever you wish.

Lucky for us there already “discovered” CRDT algorithms that offer many different structures already. We won’t look at the implementations but here’s a few to get you started:

  • Grow-Only-Counter (“G-Counter”). This is almost exactly the example we walked through (but again, without needing one central redis server)

  • Positive-Negative-Counter. This design composes two G-Counters, using one for counting positive increments and the other for counting negative increments.

  • Grow-Only-Set. Think of this as an “append-only” array with arbitrary element values.

  • Two-Phase-Set. Combines two Grow-Only-Sets, where one stores new values and a second stores (what is referred to as) “tombstones” which keeps a list of which items should be considered “removed”. Imagine creating a basic “Todo List App” by using a list of growing values and a list of removed values.

  • Sequence CRDTs. This is a family of CRDT that permits much deeper complexity. Commonly, new Sequence CRDTs will be showcased by a collaborative real-time editor experience, the kind where many document editors send updates to the document.
    Most of us have probably seen collaborative editors already (like google docs), but this CRDT would permit an experience where there is no central server and both document editors are light-days apart from each-other (meaning updates from your peers are already many-days-old by the time you receive them). Also it permits a limitless number of editors who might not be able to communicate with each-other directly.

    • Replicated Growable Array. Creates a tree of changes where changes are added to the tree in specific ways. A proper explanation requires its own article, but if you only want a mental-model you can think of it as keeping track of changes by using a tree, which can then be “flattened” into something like a string of text (for wordprossing).

    • There are alternatives like logoot, CRATE, each seeking to improve a different part of the concept.

There are, however, some downsides! Obviously if we have no lock, processes do not need to wait to acquire a lock, and values can drift apart. Perhaps there are specific business-cases that are really hard (but not impossible) to map into CRDTs like doing e-commerce where you need to confirm the price, quantity, stock, and payment. However, I would argue that many concepts easily can fit into CRDTs, for example, in earlier articles we discussed “Flash Notification Messages” which force GET requests to use locks: easily solved with a Two-Phase-Set, and can be optimised further to not fill up memory by adding tags to joined values (similar to how git will merge commits).

Additionally, this field is still growing. New algorithms are constantly being worked on. Some “awkward” editing experiences haven’t been solved yet, and there is ongoing (but very successful) work with optimization for memory size and performance.

We’re not only lucky that people have thought about how to create different CRDTs, but actually a lot of these are implemented and used quite often. Here’s two popular and mature libraries:

There are also really exciting projects built on-top of CRDTs which can help you see what is really possible with this:

Lastly, if you wish to learn more, here are some great resources that helped me when I was learning this concept.

Brian Grahamediting-shared-resources-8