1 of 16

Composing and Decomposing Op-Based CRDTs with Semidirect Products

Matthew Weidner, Heather Miller, and Christopher Meiklejohn

Carnegie Mellon University

Pittsburgh, PA, USA

ICFP 2020

Virtual Jersey City, NJ, USA

8/24-26/2020

2 of 16

2

Composing and Decomposing Op-Based CRDTs with Semidirect Products

Say you're building a webapp that has some kind of stored state, which can be shared between different users. Basically any website nowadays. E.g. Slack, Facebook group, conference management. The way you'd typically architect this system is as follows. When a user wants to change or view part of the state, their client sends a request to a server, which does some application-specific logic before returning a result, which you display to the user. This server is probably actually a bunch of servers in the cloud working together as a large distributed system, through message passing. A lot of systems work has gone into making these sorts of systems more usable and efficient, but it's still complicated and easy to get wrong. It also requires specialized knowledge to write the server side.

3 of 16

An alternative: CRDTs (Conflict-free Replicated Data Types)

3

// Using Legion CRDT library

var legion = new Legion(...);

legion.joinGroup(...); // sets objectStore

var shopping = objectStore.getOrCreate(

"Shopping", legion.Set

);

shopping.add("milk");

Update local state immediately

Lazily broadcast the operation to other users/replicas

A “PL” way of solving a systems problem.

Composing and Decomposing Op-Based CRDTs with Semidirect Products

CRDTs provide an alternative way of managing shared data. Stands for CRDT. You write your client code as if it's a local single-user program, but replace ordinary data types with CRDTs. Changing the data updates it locally, and then the CRDT intelligently syncs with other replicas (users) in the background. Think like Dropbox but for data types instead of files---use data types locally as usual, but it also syncs them (and unlike Dropbox, get auto conflict resolution). CRDTs can be used to implement Google Docs-style collaboration (although Google Docs actually uses a different approach which still relies on a cloud server). Note this is a PL way of solving a systems problem; because the data types are designed in a principled and mathematical, it should be harder to make bugs than with raw message passing.

4 of 16

Pros

Cons

Data shared in small groups only (<100)
Conflict resolution alg makes specific choices, which may not be right for every app
Need to design conflict-resolution alg for each data type (difficult & ad-hoc)

⇒ Restricted to a few common data types with restricted interfaces

Simple client-side programming model
Generic server (broadcast messaging)
Minimal latency
Works offline
Supports end-to-end encrypted webapps

Data shared in small groups only (<100)
Conflict resolution alg makes specific choices, which may not be right for every app
Not for data that needs locking (e.g. money)

4

Composing and Decomposing Op-Based CRDTs with Semidirect Products

5 of 16

In this work

Composition

Decomposition

We present a compositional design technique for (op-based) CRDTs, the semidirect product.

Counter → add mult ops
List → add reverse op
Dictionary → add functional map ops

Set → two simpler (commutative) data types
Generic resettable CRDT → original CRDT + simple reset-only data type

5

(same state type)

(union of supported ops)

Composing and Decomposing Op-Based CRDTs with Semidirect Products

6 of 16

6

Reason about Causality

Alice: “add(‘milk’)”
Bob (later): “remove(‘milk’), but only after applying Alice’s op”
Result: no one has “milk”.

Make Ops Commute

+3, +5 instead of =3, =5
Clever sequence types

Update local state immediately

Broadcast the op to other users

Alice: value = 3

Bob: value = 5

Conflict resolution techniques

Composing and Decomposing Op-Based CRDTs with Semidirect Products

Before explaining our construction, I want to talk about designing CRDTs in general. Recall our system model: when a user changes their state, they apply the operation immediately locally, and they also broadcast the operation to the other replicas, who then apply it to their own states.

Of course, if two users make changes at the same time, we have to do some form of conflict resolution E.g. Alice sets to 3, Bob sets to 5. After they receive each others' messages, what to do?

One trick is to make operations commute. For example, say Alice and Bob are counting something, like the number of ad clicks: we want the total sum. (+3, +5 -> 8 for both.) You can be clever and make this work for a few other datatypes, e.g., sequences.

Another trick is to reason about *causality*. I'll go into more detail about this on the next slide, but for now, here's a simple example: Alice adds milk to a shared shopping list (represented as a set CRDT). Bob sees this and removes it, since he already bought milk. His CRDT then sends a message saying "remove milk, but only after applying Alice's add milk operation". That way if another user Charlie receives both messages, even if he gets them out of order, he'll apply the add then the remove. Hence he’ll end up with milk not in the set (same as Bob).

7 of 16

Causality in detail

The causal order on operations is a natural partial order < on operations:

CRDTs can query the causal order. Ex. Add-Wins Set CRDT: x is in the set if there is an add(x) operation that is not < any remove(x) operation.

So milk stays on the list.

7

add(‘milk’)

add(‘eggs’)

add(‘bread’)

add(‘milk’)

Alice

Bob

Charlie

remove(‘milk’)

<

concurrent

Composing and Decomposing Op-Based CRDTs with Semidirect Products

TODO: causal order slide. “Happened-before.” Usu. def, including concurrent. Explain sideways diagrams. Example of causally later messages with colors (color part causally after a given message)? Can use another message + color to illustrate concurrency. The causal order is the strictest order we can impose on message delivery without coordination (=latency). Enforce by attaching metadata about causally prior messages. CRDT (conflicts resolved) once concurrent ops commute (not all ops).

Using the causal order, you can design CRDTs like the add-wins set. Informally, the rule is "adds and removes as normal, except if add(a) concurrent to remove(a), leave a in the set". Formally, semantics defined by (usual). Note not immediately clear how to implement this without looking at the whole history each time.

8 of 16

8

Reason about Causality

E.g. for a set: specify “x is in the set if there is an add(x) operation that is not < any remove(x) operation.”

Make Ops Commute

+3, +5 instead of =3, =5
Clever sequence types

Conflict resolution techniques

Our semidirect product provides a uniform, reusable way of doing this, so you don’t have to.

New CRDT design workflow: Design commutative data types for simple subsets of operations → Glue together with semidirect products.

Our experience: works for most existing CRDT types, plus novel ones.

Composing and Decomposing Op-Based CRDTs with Semidirect Products

9 of 16

An example of our semidirect product

(int register w/ add ops) + (int register w/ mult ops) → int register with both

add operations alone are easy: they already commute.
Same for mult operations alone.
But they conflict with each other:

9

Dave

Mary

Composing and Decomposing Op-Based CRDTs with Semidirect Products

10 of 16

Observation: If we receive concurrent add and mult operations in the “wrong” order (mult before add), we get the right result if we act on the add with the mult.

Goal: Integer register CRDT supporting add and mult operations

Let us choose that in the face of concurrency, “adds go before mults”.

Works by distributive law:

10

Dave

Mary

Dave

Mary

Composing and Decomposing Op-Based CRDTs with Semidirect Products

11 of 16

Goal: Integer register CRDT supporting add and mult operations

When you receive an add operation, transform it by all concurrent mult operations you’ve already received.

So becomes , where are all of the operations you’ve previously received that are concurrent to .

Works more generally subject to algebraic constraints on the input CRDTs & action.

When you receive an add operation, transform it by all concurrent mult operations you’ve already received.

11

Dave

Mary

Composing and Decomposing Op-Based CRDTs with Semidirect Products

12 of 16

Recap

Thanks for watching :)

CRDTs are a nice “PL” way of building systems that act on shared state

Programmers just replace ordinary data types with CRDT versions
More info: https://crdt.tech/

Our semidirect product is a compositional design technique for CRDTs

Resolve conflicts between ops by reasoning about causality in a uniform, reusable way - so CRDT designers don’t have to
New CRDT design workflow: Design commutative data types for subsets of ops → Glue together with semidirect products

12

Questions?

Image credits: zombo.com, openclipart.org

Composing and Decomposing Op-Based CRDTs with Semidirect Products

13 of 16

13

Composing and Decomposing Op-Based CRDTs with Semidirect Products

14 of 16

Relation to Operational Transformation

Recall: OT is a competing approach to eventually consistent replicated data types. Instead of making concurrent operations commute, you define a transformation function tf_1: O x O -> O.

Received operations are transformed against previously-received concurrent operations using the (somewhat complicated) adOPTed algorithm (Ressel et al. ‘96).
Eventual consistency follows from 2 Transformation Properties, which are hard to verify (esp. TP2).

The semidirect product is the special case of OT when O = O_1 \sqcup O_2 and tf_1(p, q) = p except when p \in O_1, q \in O_2. (O_2 ops transform concurrent O_1 ops, but that’s it.)

With these restrictions, adOPTed becomes the simple algorithm described for the add/mult integer register, and TP2 is typically trivial to verify.

It is interesting that we get common CRDT semantics from this special case of OT.

14

Composing and Decomposing Op-Based CRDTs with Semidirect Products

15 of 16

Generality

Q: When can a CRDT be decomposed as a semidirect product of simpler CRDTs?

Let C be a CRDT in the POLog model of pure op-based CRDTs. I.e., C is defined by a function f mapping the partially ordered log of operations to a visible state.

Suppose the ops of C can be partitioned as O₁ U O₂ so that for any POLog L, f(L) = f(L’) whenever L = L’ except that we have added some edges o₁< o₂ with o₁ ∊ O₁, o₂ ∊ O₂. Then C is the semidirect product of a CRDT with only O₁ ops and a CRDT with only O₂ ops.

This expresses the rule that O₁ ops “go before” concurrent O₂ ops.

15

Composing and Decomposing Op-Based CRDTs with Semidirect Products

16 of 16

Name Origin: Semidirect Product of Groups

In abstract algebra, a group is a set G with a binary operation ∘ : G x G → G satisfying multiplication-like properties.

∘ is associative (g ∘ (h ∘ k) = (g ∘ h) ∘ k); ∃ 1 ∊ G s.t. g ∘ 1 = 1 ∘ g = g; ∀g ∊ G ∃ g^-1 ∊ G s.t. g ∘ g^-1 = 1.
I.e., a monoid with inverses.

The semidirect product combines two groups G, H into a group with set G x H. It contains copies of G and H which commute as

h ∘ g = (h ⊳ g) ∘ h

for a suitable action ⊳ of H on G.

The semidirect product of CRDTs uses an analogous rule to reorder concurrent ops from the components.

16

Composing and Decomposing Op-Based CRDTs with Semidirect Products