Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

CRDT Basics

The whole lesson is free and interactive. Read it here, or press Start lab to run it for real in a live lab, with no account needed.

Container lab10 min read6 commands

Edit on the train, sync at home

You change a shared note on your phone on a train with no signal. At home, somebody changed the same note on a laptop. When the phone connects, both changes should survive. Apps that work offline first and sync later are called local-first, and the data types that make the merge safe are called CRDTs.

By the end of this lesson

Note

I can explain how two replicas that changed the same data offline end up agreeing.

Key words

  • Replica: one copy of the data, on one device.
  • Sync: sending changes between replicas.
  • Merge: combining two replicas into one state.
  • CRDT: a data type whose merge always gives the same answer, in any order.
  • Concurrent: two changes made without either knowing about the other.
  • Tombstone: a marker that says something was deleted.

Starter: what you already know

Note

Answer in your head. 1. You save a file on two computers. Which copy is right? 2. Is 3 + 5 the same as 5 + 3? 3. What is the largest of 4, 9 and 2? Answers: it depends on what changed in each; yes, order does not matter; 9. The last two ideas are what a CRDT merge is built on.

Before you start

Note

Press Start the lab on the bar at the top of this lesson and wait until it says it is running. There is one container, jupyter, and the terminal reaches its Python with docker exec jupyter, which runs one command inside it. The JupyterLab link opens its web page, port 8888. Each Run button below types its command into your lab's terminal, one after another in the same session. To watch them, or to type your own, press Open terminal on the bar.

A naive sync loses an edit

The phone changed the title at 10:05. The laptop changed the body at 10:07. The naive sync keeps the whole note saved last, so the phone's title edit is lost: it prints True. Merging field by field keeps both: the title "Trip to York" and the body "Pack bags, book hotel".

Command
docker exec jupyter python3 steps/lostedit.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

A counter that merges safely

Three replicas count page views offline: 3, 5 and 2. A G-Counter keeps one number per replica and merges by taking the larger of each. After syncing in different orders, every replica sees 10, and merging the same state twice more still gives 10. A plain number that adds each report counts a repeated message twice and reaches 19.

Command
docker exec jupyter python3 steps/gcounter.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

In a shared list, a concurrent add wins

Ana and Ben share a shopping list with milk and eggs. Offline, Ana removes milk while Ben adds milk again. After the sync both lists say eggs and milk. The set, an OR-set, gives every add a tag, and a remove only deletes the tags it has seen. Ben's new tag was never seen by Ana, so milk stays.

Command
docker exec jupyter python3 steps/orset.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Check

Tip

Why does merging a G-Counter twice not count anything twice? Answer: the merge takes the larger of two numbers for each replica, and the larger of 5 and 5 is still 5.

Two edits to one line of text

Both replicas start with "Hello". Offline, Ana adds " world" at the end, and Ben adds "Oh, " at the start and deletes the H. After the sync both read "Oh, ello world". Each character has an id and remembers which character it was typed after, so an insert means the same on every replica. The deleted H stays as one tombstone.

Command
docker exec jupyter python3 steps/text.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Vector clocks tell what happened before

Each replica counts its own changes in a vector clock. Replica a writes, and b writes without hearing from a: the two clocks are concurrent. Then b hears a and writes again, so a is now before b. A clock compared with itself is equal.

Command
docker exec jupyter python3 steps/clocks.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Three replicas, many edits, one answer

A phone, a laptop and a tablet each make 30 random changes to a shared list and a counter while offline. Then they sync with each other in a random order. All three end with the same five items and the same count, 28.

Command
docker exec jupyter python3 steps/offline.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

A common mistake

Warning

Many people think the newest change should always win. A clock on a phone can be wrong, and "newest" throws away the other edit. A CRDT keeps both changes when it can, and it only picks one by a rule that every replica applies the same way.

The same work in a notebook

Open JupyterLab from the bar and double-click start.ipynb. It merges two counters, two shopping lists and two copies of a line of text. Click a cell and press Shift and Enter to run it. The last cell is where your own question goes, and crdt.py is short enough to read in full.

Exit check

Tip

Answer without looking back. 1. What did the naive sync lose? 2. How does a G-Counter merge? 3. In an OR-set, what happens to an add the remover never saw? 4. What does concurrent mean for two vector clocks? Answers: the phone's title edit; it takes the larger number for each replica; it survives; neither change knew about the other.

For teachers

Tip

This lesson is a small example of a lesson worked in a lab: the steps and the Run buttons are the lesson, and the lab is each student's own copy. The lab is one service, JupyterLab with CRDTs written in the Python standard library, and nothing here marks itself: the student hands in a notebook of their own, downloaded from JupyterLab, and a sentence on what it showed. Key learning points: 1. A naive last-writer-wins sync loses edits. 2. A CRDT merge gives the same answer in any order and when repeated. 3. Vector clocks tell before from concurrent. Common mistake: thinking the newest change should always win. No real CRDT library runs in the lab: Automerge and Yjs are explained in the undergraduate module. Equipment: the lab and a browser. Tip: have two students edit one paper note, then merge the two copies aloud. Copy it into your own module and change it, or build one from scratch with the Lab menu in the lesson builder.

About this lab and its source: CRDT lab: local-first sync with counters, sets, vector clocks and text in Python

Teaching a class? Set these lessons for your students with marking and a lab for every student.