The Single-Writer Principle in CRDT Composition - Bitly

The Single-Writer Principle in CRDT Composition

Vitor Enes

Paulo S´ergio Almeida

Tuesday 20th June, 2017 MSc Student at University of Minho PMLDC ’17, Barcelona

Carlos Baquero

Outline

• Building CRDTs • building blocks / composition techniques • examples of CRDTs

1

Outline

• Building CRDTs • building blocks / composition techniques • examples of CRDTs

• The Single-Writer Principle (and yet another Building Block) • what it is • how it can be exploited for another building block

1

Building CRDTs

Building Blocks • primitive lattices (Boolean, Naturals)

2

Building Blocks • primitive lattices (Boolean, Naturals) • set-based (Set, Sinked)

2

Building Blocks • primitive lattices (Boolean, Naturals) • set-based (Set, Sinked) • lattice-based (Map, Pair, LexPair)

2

Building Blocks • primitive lattices (Boolean, Naturals) • set-based (Set, Sinked) • lattice-based (Map, Pair, LexPair) • dot stores (DotSet, DotFun, DotMap)

2

State-based CRDT?!? What’s that? • Partially ordered set S with p.o. v • Least Upper Bound (LUB) for every two elements

3

State-based CRDT?!? What’s that? • Partially ordered set S with p.o. v • Least Upper Bound (LUB) for every two elements • LUB given by t s.t. ∀x, y , z ∈ S:

idempotent commutative associative

x tx =x x ty =y tx x t (y t z) = (x t y ) t z

3

Primitive Lattices Boolean • B = {False, True}

False v True x ty =x ∨y

4



True False

4



Naturals • N = {0, 1, 2, . . . }

x vy ≡x ≤y x t y = max(x, y )

True False

4



Naturals • N = {0, 1, 2, . . . }

x vy ≡x ≤y x t y = max(x, y )

True

.. .

False

2 1 0 4

Set • SethE i = P(E )

x vy ≡x ⊆y x ty =x ∪y

5



E = {a, b}, SethE i = {{}, {a}, {b}, {a, b}}

5



E = {a, b}, SethE i = {{}, {a}, {b}, {a, b}}

{a, b} {a}

{b} {}

5



E = {a, b}, SethE i = {{}, {a}, {b}, {a, b}}

{a, b} {a}

{b} {}

• This data type is know as grow-only set: GSethE i • It only allows additions to the set (why?) 5

Sinked E = {0, 1, 2, 3, 4} > 0

1

2

3

4

6

Sinked

0

E = {0, 1, 2, 3, 4}

E = {,, ♪, F}

>

>

1

2

3

4

,

♪

F

6

Sinked

0

E = {0, 1, 2, 3, 4}

E = {,, ♪, F}

>

>

1

2

3

4

,

♪

F

• SinkedhE i = E > = E ∪ {>}, s.t. > 6∈ E

6

Sinked E = {0, 1, 2, 3, 4}

E = {,, ♪, F}

>

>

0

1

2

3

4

,

♪

F

• SinkedhE i = E > = E ∪ {>}, s.t. > 6∈ E

x vy ≡x =y ∨y =>

6

Sinked E = {0, 1, 2, 3, 4}

E = {,, ♪, F}

>

>

0

1

2

3

4

,

♪

F

• SinkedhE i = E > = E ∪ {>}, s.t. > 6∈ E

x v y ≡ x =y ∨y => x if x = y x ty = > otherwise

6

Sinked E = {0, 1, 2, 3, 4}

E = {,, ♪, F}

>

>

0

1

2

3

4

,

♪

F

• SinkedhE i = E > = E ∪ {>}, s.t. > 6∈ E

x v y ≡ x =y ∨y => x if x = y x ty = > otherwise

(that doesn’t look very useful . . . )

6

Map • MaphK , V : Latticei = K ,→ V

7


x t y = {k 7→ v | k ∈ dom(x) ∪ dom(y )}

7


x t y = {k 7→ v | k ∈ dom(x) ∪ dom(y )} where v = x(k) t y (k)

7


x t y = {k 7→ v | k ∈ dom(x) ∪ dom(y )} where v = x(k) t y (k)

• grow-only counter : GCounter = I ,→ N - keys: set of replica identifiers (I) - values: Naturals primitive lattice (N)

7

Map • GCounter = I ,→ N I = {A, B}

{}

8


{A 7→ 1} {}

8


{A 7→ 1}

{B 7→ 1} {}

8


{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 1} {}

8


{A 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{}

8


{A 7→ 2, B 7→ 1} {A 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{}

8


{A 7→ 2, B 7→ 1} {A 7→ 2}

{A 7→ 1, B 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{}

8

Map • GCounter = I ,→ N I = {A, B} {A 7→ 2, B 7→ 2} {A 7→ 2, B 7→ 1} {A 7→ 2}

{A 7→ 1, B 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{}

8


{A 7→ 1, B 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{} • It only allows increments (why?) 8


{A 7→ 1, B 7→ 2}

{A 7→ 1, B 7→ 1} {A 7→ 1}

{B 7→ 2} {B 7→ 1}

{} • It only allows increments (why?) • Why did I stop talking about v ? 8

Pair • PairhX : Lattice, Y : Latticei = X × Y

9


(x1 , y1 ) t (x2 , y2 ) = (x1 t x2 , y1 t y2 )

9


(x1 , y1 ) t (x2 , y2 ) = (x1 t x2 , y1 t y2 )

• positive-negative counter : PNCounter = GCounter × GCounter = (I ,→ N) × (I ,→ N)

9


(x1 , y1 ) t (x2 , y2 ) = (x1 t x2 , y1 t y2 )

• positive-negative counter : PNCounter = GCounter × GCounter = (I ,→ N) × (I ,→ N) • or PNCounter = I ,→ (N × N)

9

Pair • PNCounter = I ,→ (N × N) I = {A}

{}

10


{A 7→ (0, 1)} {}

10


{A 7→ (1, 1)} {A 7→ (0, 1)} {}

10


{A 7→ (1, 1)} {A 7→ (0, 1)} {}

(tell me more about counters . . . )

10

LexPair • LexPairhX : Lattice, Y : Latticei = X Y

11


(x1 , y1 ) t (x2 , y2 ) =

   

if x1 = x2

  

if x1 = x2

if x1 < x2

(this definition assumes X is a total order)

11


(x1 , y1 ) t (x2 , y2 ) =

   (x1 , y1 )

if x1 = x2

  

if x1 = x2

if x1 < x2


11


   (x1 , y1 ) (x1 , y1 ) t (x2 , y2 ) = (x2 , y2 )   

if x1 = x2 if x1 < x2 if x1 = x2


11


   (x1 , y1 ) (x1 , y1 ) t (x2 , y2 ) = (x2 , y2 )    (x1 , y1 t y2 )

if x1 = x2 if x1 < x2 if x1 = x2


11


   (x1 , y1 ) (x1 , y1 ) t (x2 , y2 ) = (x2 , y2 )    (x1 , y1 t y2 )

if x1 = x2 if x1 < x2 if x1 = x2

(this definition assumes X is a total order) • cassandra-like counter : LexCounter = I ,→ (N Z)

11

Pair • LexCounter = I ,→ (N Z) • first component works as version number I = {A}

{}

12


{A 7→ (1, 1)} {}

12


{A 7→ (2, 0)} {A 7→ (1, 1)} {}

12


{A 7→ (3, −12)} {A 7→ (2, 0)} {A 7→ (1, 1)} {}

12

Causal CRDTs: Dot Stores and Causal Context • examples of Causal CRDTs:

enable-wins flag : EWFlag disable-wins flag : DWFlag multi-value register : MVRegister

13

Causal CRDTs: Dot Stores and Causal Context • examples of Causal CRDTs:

enable-wins flag : EWFlag disable-wins flag : DWFlag multi-value register : MVRegister add-wins set: AWSet remove-wins set: RWSet ...

• generalize previous techniques • avoid unbounded growth of metadata state (more on this soon)

13

Causal CRDTs: Dot Stores and Causal Context • CausalhT : DotStorei = T × CausalContext

14

Causal CRDTs: Dot Stores and Causal Context • CausalhT : DotStorei = T × CausalContext • CausalContext = P(Dot) is a set of dots

14

Causal CRDTs: Dot Stores and Causal Context • CausalhT : DotStorei = T × CausalContext • CausalContext = P(Dot) is a set of dots • Dot = {l, s, n}

unique event identifiers (in practice they are not geometric figures)

14



• there are three dot stores:

DotSet = P(Dot), a set of dots

14




DotSet = P(Dot), a set of dots DotFunhV : Latticei = Dot ,→ V , mapping dots to some lattice V

14




DotSet = P(Dot), a set of dots DotFunhV : Latticei = Dot ,→ V , mapping dots to some lattice V DotMaphK , V : DotStorei = K ,→ V , mapping keys in K to another dot store V

14




• e.g.

DotSet = P(Dot), a set of dots DotFunhV : Latticei = Dot ,→ V , mapping dots to some lattice V DotMaphK , V : DotStorei = K ,→ V , mapping keys in K to another dot store V

AWSethE i = CausalhDotMaphE , DotSetii = (E ,→ P(Dot)) × P(Dot) 14

AWSet (without conflicts) • AWSethE i = (E ,→ P(Dot)) × P(Dot)

{}

15


({x 7→ {l}}, {l}) {}

15


({x 7→ {l}}, {l})

({y 7→ {s}}, {s}) {}

15


({x → 7 {l}, y→ 7 {s}}, {l, s}) ({x 7→ {l}}, {l})

({y 7→ {s}}, {s}) {}

15

AWSet (with conflicts) • AWSethE i = (E ,→ P(Dot)) × P(Dot)

{}

16


({x 7→ {l}}, {l}) {}

16


({}, {l}) ({x 7→ {l}}, {l}) {}

16


({}, {l})

({x 7→ {s}}, {s})

({x 7→ {l}}, {l}) {}

16

AWSet (with conflicts) • AWSethE i = (E ,→ P(Dot)) × P(Dot) ({x 7→ {s}}, {l, s}) ({}, {l})

({x 7→ {s}}, {s})

({x 7→ {l}}, {l}) {}

16

The Single-Writer Principle (and yet another Building Block)

The Single-Writer Principle • in shared memory, race conditions can be avoided by, e.g., enforcing mutual exclusion

17

The Single-Writer Principle • in shared memory, race conditions can be avoided by, e.g., enforcing mutual exclusion • design simplifications can be achieved by only allowing each object to be written by a single process: The Single-Writer Principle

17

The Single-Writer Principle • in shared memory, race conditions can be avoided by, e.g., enforcing mutual exclusion • design simplifications can be achieved by only allowing each object to be written by a single process: The Single-Writer Principle • in a distributed setting, CRDTs allow concurrent writes without coordination

and if a conflict occurs, it is resolved in a meaningful way (add-wins, remove-wins, . . . )

17



• deciding which conflict-resolution strategy to use is application-specific, but . . .

17



• deciding which conflict-resolution strategy to use is application-specific, but . . .

Do conflicting operations occur in all applications? 17

Doodle • could be modeled as a Map: - keys: participants - values: AWSet

18

Doodle • could be modeled as a Map: - keys: participants - values: AWSet

• but conflicts never occur since every participant writes in its own set of dates - metadata required for conflict-resolution and causality tracking (l, s, . . . ) is unnecessary

18

Single-Writer Versioned Object

Given a set of possible values S, a single-writer versioned object can be defined as: LexPairhN, SinkedhSii = N S >

19


Given a set of possible values S, a single-writer versioned object can be defined as: LexPairhN, SinkedhSii = N S > • the first component stores the current version of the object while • the second component stores its value

19


Given a set of possible values S, a single-writer versioned object can be defined as: LexPairhN, SinkedhSii = N S > • the first component stores the current version of the object while • the second component stores its value • to change the value of the object: - increment the version - set the new value

19

Single-Writer Versioned Set S = P({“monday”, “tuesday”, “wednesday”})

20


20


(0, {})

20


(1, {“monday”, “tuesday”}) (0, {})

20


.. . (2, {“tuesday”}) (1, {“monday”, “tuesday”}) (0, {})

20

Collection of Single-Writer Versioned Objects • we can now define a collection of single-writer versioned objects as a Map from participant to versioned object

21

Collection of Single-Writer Versioned Objects • we can now define a collection of single-writer versioned objects as a Map from participant to versioned object • note: we are not limited on the values stored per participant: - a versioned object can store values from any sequential data type (due to Sinked building block)

21

Collection of Single-Writer Versioned Objects • we can now define a collection of single-writer versioned objects as a Map from participant to versioned object • note: we are not limited on the values stored per participant: - a versioned object can store values from any sequential data type (due to Sinked building block)

{A 7→ (2, {“tuesday”}), B 7→ (7, {“tuesday”, “wednesday”})}

• how to find the dates where all participants are available to meet?

21

Before we go

• generic collection of single-writer versioned objects (collection of versioned set as example) • construction hidden in specific implementations (LexCounter) • by making it explicit, we aim to provide a new tool for safe construction of complex CRDT compositions

22

Questions? bit.ly/single-writer-pmldc

22