An introduction to Conflict-Free Replicated Data Types

Part 1: Preliminaries

Next part

This is a series about Conflict-Free Replicated Data Types, or CRDTs for short. Their purpose is to allow seamless replication of data on different nodes in a distributed system. Merging is by construction always possible, without any conflicts. This series assumes no knowledge about CRDTs, but be prepared to learn a thing or two about algebras. All code samples on this page are interactive and executed in your browser. Understanding the code is necessary for understanding the concepts, so you should be familiar with JavaScript. If you notice any bugs on this page, please let me know!


Dear reader! If you’re reading this, that’s most likely because you’ve pointed your browser to my website and/or followed a link to this page. Maybe you’re even reading this from a mobile device!1 Perfect conditions for motivating what all this is about.

Contents

  1. Preliminaries (this page)
  2. Algebras & contracts
  3. Lattices
  4. Combinators
  5. Tombstones
  6. Time
  7. Registers and Deletion
  8. Outlook

The web is a truly distributed application platform

A network of nodes

That’s right. When you’re building a web application, you absolutely, positively have to care about the distributed aspect of the web. (Unless your application is stateless, like my website.)

What does this mean? You may have a bunch of users. These users may be manipulating their data from a variety of devices. Some devices may have a slow Internet connection. Devices may go offline at any point in time.

Sometimes, application developers punt on this issue: the mobile app displays “You’re offline” and won’t let you see your data (best case), or silently discard information (worst case).

One particular piece in the puzzle of building distributed applications is to figure out the storage. Ideally, this storage should be resilient towards users that may become unavailable, concurrent edits, and so on.

Enter Conflict-free Replicated Data Types. A glorious example of Computer Science naming that actually Makes Sense™, they attempt to provide a flexible solution to the storage problem. The fundamental idea is this: You have data. This data is stored on multiple replicas. CRDTs describe how to coordinate these replicas to always arrive at a consistent state.

Note that there are two different categories of CRDTs: state-based and op-based. Both serve the same purpose, but work in different ways and come with their own design trade-offs. In this series, I’m mostly going to focus on state-based CRDTs.

About CRDTs

Abed Nadir thinks CRDTs are cool

That’s it! You now understand the idea behind CRDTs.

Of course, that’s only half the story. There are at least two sides to understanding CRDTs deeply.

  1. Knowing all the varieties (counters, maps, sets, …) and how they can be embedded in application software.
  2. Diving into the mathematical background (lattices! partial orderings! wooooooo) powering their implementations.

In this series, I want to focus on the second aspect and explain everything that’s needed in a bottom-up fashion using interactive notebooks, diagrams and code notation that’s familiar with a large amount of programmers: JavaScript. I’ll be employing a few libraries for testing code and visualizing data, but otherwise, there are no further dependencies. The research papers that describe them often assume a great deal of background knowledge in abstract algebra. I’ll try to introduce just the necessary knowledge gently.

If however, you want to learn more about their use, this series is not for you. But fear not: there are tons of resources to check out, e.g. crdt.tech. There’s no tracking on this page so I won’t even notice if you’re gone 🤷

Still here? Cool. Cool, cool, cool.

But before we can strap in and talk about CRDTs, we first need to get some paperwork out of the way.

How to work with this document

All code snippets here are live: this page functions similarly to Jupyter Notebook. The main difference is that all code is executed in your browser; there’s no roundtrip to a backend service. Snippets are evaluated when a page is loaded and can be re-evaluated by clicking the Run button. Feel free to change any snippet to your liking, but note that subsequent snippets are not automatically re-run. If you want to reset the session, e.g. because you deleted some code, just reload the page. Your code is not saved between reloads!

Tests

This page has a built-in test runner. It takes named properties that should be checked. The term property is overloaded in programming, so let me be clear: I’m not talking about properties in an object; instead I’m talking about functions that may take arguments and return a truth value. In other words, a property is a predicate that should be evaluated on ideally all inputs to see if it always holds.

In the following example, we have two properties, one is valid, the other one isn’t. They are defined using the fast-check library, which is available under the fc object.

checkAll({
  "succeed": fc.property(fc.string(), x => x == x),
  "fail": fc.property(fc.string(), x => x != x)
});

Under the hood, fast-check automatically generates 100 different inputs. Granted, 100 different inputs is not exactly all inputs, but since there are infinitely many strings, we can’t exactly do that, can we? fast-check will call the function (e.g. x => x == x) with the inputs as specified (fc.string() generates ASCII strings with only printable characters). If the function ever returns false or throws an exception, the property is marked as failed. Otherwise, it’s marked as successful.

Fortunately, we can also use Chai assertions inside our properties to get rich error messages:

checkAll({
  "succeed": fc.property(fc.string(), x => assert.equal(x, x)),
  "fail": fc.property(fc.string(), x => assert.notEqual(x, x))
});

The great thing about fast-check is that it will automatically show you the smallest (and hopefully simplest) input it could find where the property failed. This is called the counterexample. There could be many counterexamples, but here, we only show one.

checkAll({
  "strlen": fc.property(fc.string(), x => assert.isAtMost(x.trim().length, 5))
});

You’ll see in the results a failure where the counterexample has length 6 and does not just consist of spaces.

Note that a property could be invalid and we’d still not notice it because fast-check didn’t generate that input for us. That’s a risk we have to live with.

Playground

Intrigued? Why not play around with the test runner a little. Of course, you could modify the code boxes above, but maybe you were afraid to. So, I prepared a special playground just for you. Go wild!

checkAll({
  "be-creative": null
});

Feel free to consult the fast-check documentation about which data generators there are.

Printing

The runner can also print different kinds of outputs, e.g. arrays. Note that only the last expression in a snippet is printed.

1 + 1;

[
  "this",
  "is",
  "an",
  "array"
]

If you define variables without var (or const or let), they can be accessed in subsequent snippets. I will use that throughout the series.

We can define different printing for a particular object using the interactiveRender symbol. It can be declared as a method and will be invoked by the runner automatically:

class Test {
  constructor(value) {
    this.value = value;
  }

  [interactiveRender]() {
    return `Hi ${this.value}!`;
  }
}

new Test("reader")

Onwards

You are now ready to proceed with the actual introduction. Go here to learn all about contracts.

Testimonials

People on The Internet™ seem to enjoy these posts:

References

  1. This page is developed on a desktop browser. I’ve tried my best to make it accessible on mobile browsers too, but I’m not so experienced, so any bug reports are appreciated! 


Thanks to the people who've read drafts of this series and provided valuable feedback: Andrea, Clement Delafargue, Heiko Seeberger, Hillel Wayne, Johannes Link, Matthew Weidner, Princess.