►
From YouTube: "CRDTs Illustrated" by Arnout Engelen
Description
CRDTs (Conflict-Free Replicated Data Types) are a great way to implement applications that gracefully recover from partitions - such as clusters or (mobile) applications that can work offline.
This talk will:
Introduce the concept of CRDTs and their use cases
Describe the 2 main ways to implement a CRDT (convergent and commutative), with visual examples to illustrate their behavior
Show 2 examples of CRDTs used in practice (RIAK 2 Data Types (distributed storage) and swarm.js (offline-friendly web apps))
Arnout Engelen
XEBIA
@raboofje
With over a decade of experience in professional software development, Arnout is constantly on the lookout for tools to smoothen and simplify that process. He currently consults for Xebia, injecting the startup mentality into larger corporations in the Netherlands.
A
B
A
B
Goal
of
theologies
is
to
make
it
easier
to
write,
correct,
eventually,
consistent
systems,
so
to
achieve
consistency
in
distributed
systems
and
I'm
sure
you're
all
pretty
familiar
with
with
this
concept,
but
I'd
like
to
build
it
up
from
the
start,
real
quick.
So
the
really
simple
case
is
when
we
have
just
one
server.
There
were
a
couple
people
writing
to
that
server
and
a
couple
people
people
reading.
Oh,
that's
pretty
simple
right.
It's
pretty
clear
to
see
that
this
will
work,
so
the
problem
is
just
going
to
be
network
failures
and
all
kinds
of
failures.
B
So
this
means
if
the
server
is
in
Europe
and
your
users
are
in
America
and
connections
gone,
then
these
users
don't
have
any
can't
get
any
work
done.
So
that's
not
very
good,
so
the
obvious
solution
is
to
distribute
it.
So
you
distribute
the
information
of
multiple
servers.
People
write
to
the
servers
and
people
read
from
the
servers.
B
If
the
connection
between
two
of
those
servers
go
sound,
then
the
people
work
that
are
connected
to
that
can
which
one
of
them
can
still
get
work
done.
So
that
sounds
great
in
theory,
but
of
course,
in
practice
we
still
get
Network
failures
and
it's
not
obvious
how
to
deal
with
them.
So
you
want
it
to
look
like
they're
still
like
this
nice,
consistent,
sequential.
B
To
simulate
like
make
it
look
like
the
cluster
is
just
one
server,
it
would
need
strong
consistency,
and
this
is
basically
impossible
when
a
and
B
are
entirely
disconnected
at
some
time.
So
this
is
what
people
mean
when
they
say
you
can.
When
you,
when
there
are
petitions,
you
cannot
have
availability
and
consistency
at
the
same
time,
because
to
get
consistency,
you
would
have
to
have
some
kind
of
communication
between
the
different
servers
where
you
would
like
to
make
progress.
B
So
the
basic
thing
that
we've
done
is
we
introduced
eventual
consistency,
so
this
is
something
you
probably
all
very
familiar
with.
So
instead
of
saying,
okay,
we
want
to
make
it
look
like.
This
is
one
sequential
development
of
values,
it's
okay
to
be
eventually
consistent,
so
not
to
have
not
to
be
directly
in
the
same
state
but
after
the
partition
has
resolved.
B
Systems
that
have
very
nice
properties,
but
it's
also
complicated
and
serious.
These
are
one
way
to
think
about
algorithms,
that
are
achieving
eventual
consistency
and
the
first
thing
that
series
do
to
make
this
more
simple.
Is
we
actually
raise
the
bar
a
bit?
So
actually,
instead
of
just
saying
we
want
eventual
consistency,
so
after
the
network
petitioner
has
results,
you
want
to
be
consistent
again,
we
say
once
a
note
has
seen
the
same
events
that
note
has
to
be
in
once
two
notes
have
seen
the
same
events.
B
B
B
B
B
So
this
is
called
an
operation
based
counter
so
series
we've
got
two
kinds
of
sea
realities,
we've
got
the
operation
based
ones
and
the
state
based
ones,
and
they
can
express
the
same
algorithms,
but
they
look
different.
They
have
a
diary
different
rules
so
we'll
first
look
at
the
rules
for
the
operation
based
cheerleading
and.
B
So
this
leads
us
to
the
first
rule
of
operation
based
Co
duties,
the
operations
that
can
be
concurrent
so
that
can
happen
at
different
places
in
the
network
and
they'll
be
crossing
each
other.
They
have
to
commute
so
plus
or
minus
commute
in
the
sense
that
if
you
do
minus
4,
minus
3
or
you
do
minus
3,
minus
4,
you
get
the
same
result.
B
B
At
Bob,
and
then
this
is
delivered
again.
Oh
then
LS
will
see
five
and
Bob
will
see
them.
So
it's
obvious
to
see
that
this
is
not
allowed.
We
would
get
inconsistencies
if
we
would
allow
this-
and
this
is
basically
the
second
rule
for
operation
based
C
realities
in
an
operation
based
C
or
D.
You
have
to
be
able
to
assume
that
your
propagation
mechanism-
it
applies
to
the
update
exactly
once.
A
B
Reason
it's
impossible.
It's
actually
quite
easy
to
see
because
who
acknowledges
the
acknowledgement
when
you
want
to
deliver
a
message,
it's
exactly
once.
Well,
you
send
it
so
if
you're
not
waiting
for
acknowledgement,
then
you
never
know
if
it's
arrived
because
messages
can
drop.
So
if
you
so
say
you
wait
for
an
acknowledgement.
But
what,
if
you
don't
get
an
acknowledgement?
You
don't
know
if
the
message
got
last
of
the
already
acknowledgement
got
lost,
and
this
is
a
game
you
can
play
all
day.
You
will
never
win
right.
B
Can
have
at
most
once
delivery,
which
is
basically
send
the
message,
hope
it
gets
processed
or
you
can
have
at
least
once
delivery.
You
retry
until
you
see
the
acknowledgments
and
they
used
up
okay.
So
this
sounds
disappointing,
because
how
can
we
ever
get
will
work
done?
If
we
can't
get
exactly
what
slavery,
though
the
trick
is
really
simple,
you
can't
get
exactly
once
delivery,
but
you
can
get
exactly
once
delivery
semantics.
B
B
A
B
All
the
naive
approaches
lead
to
like
surprising
results,
because
if
we
say
if
we
just
are
to
the
set,
then
Alice
will
see
it,
but
then
Bob
sees
the
remove
and
they're
inconsistent.
So
what
do
we
do
and
the
tricky
thing
is
you
cannot
solve
this?
You
cannot
solve
this
in
a
way
that
this
is
like
ideal
set.
So
this
means
you
have
to
look
at
your
actual
problem
and
your
actual
problem
is
not
getting
a
set
synchronized.
B
Your
actual
problem
is
something
from
like
you
want
to
solve
some
real
problem
from
the
real
world
and
from
that
real
problem
in
the
real
world
you
can
derive,
which
semantics
are
actually
acceptable
to
you.
So
one
kind
of
set
in
see
realities
is
the
observe
to
remove
sets
and
what
we
do
in
the
absorption
move.
That
is
when
we
add
something
that
two
sets
before
we
really
audit
to
the
States.
We
are
the
marker,
a
unique
marker,
and
then
we
remove
an
element
from
the
set.
B
We
remove
all
the
values
that
match
that
remove
every
instance
of
the
value
that
we
also
send
over
the
marker.
So
basically,
this
is
a
set
where,
when
operations
are
when
an
out
and
remove
are
done
concurrently,
the
are
twins,
so,
whether
you
want
it
or
not,
that
depends
on
your
your
business
domain
or
whatever
you
want
to
call
it,
but
it's
one
way
to
resolve
the.
B
Yeah
to
be
conflict-free,
so
the
CNC-
this
is
usually
called
conflict-free,
and
that
doesn't
mean
that
no
strange
things
can
happen
at
your
sources.
I
mean
people
can
do
crazy
stuff,
but
you
have
to
build
into
your
datatype.
How
are
you
going
to
do
it
deal
with
it
and
this
data
type?
Well,
we
just
defined
that
are
twins
and
services,
don't
work.
B
A
then
we
move
to
X
a,
but
at
B
we
see
the
addition.
Before
we
see
the
removal,
then
we
still
get
an
inconsistent
and
in
case
of
state
by
a
sorry
in
case
of
operation
based
utility.
We
simply
say
the
rule
is
that
we
expect
your
network.
We
expect
your
propagation
algorithm
to
make
sure
updates
are
applied
in
order
and
within
order.
In
this
case
we
mean
the
order
there
they've
been
sent
by
the
source,
so
it's
like
when
a
and
B
send
at
the
same
time
or
a
sense
first
and
beasts.
B
B
Based
abilities
and
the
cool
thing
is
this:
is
all
you
need.
So
as
long
as
you
think
of
a
data
structure
that
follows
these
three
rules,
you
will
have
an
eventually
consistent
data
type.
It's
not
guaranteed
that
it's
going
to
do
what
you
would
want
it
to
do,
but
it's
guaranteed
that
it
all
the
replicas
are
going
to
be
in
the
same
state
that
yet
so
that's
a
really
nice
tool
to
fairly
simple
to
to
think
of
a
really
complicated
problem.
So
that's
nice.
B
It
would
be
nice
to
lift
some
of
those
assumptions
and
the
cool
thing
is
we
can
do
that
and
we
can
do
that
with
state-based
three
duties.
So
state-based
utilities
are
also
data
types
that
will
allow
you
to
design
eventually
consistent
systems,
but
they
work
differently.
So
the
operation
based
utilities-
remember
you
did
an
operation,
you
applied
it
to
your
local
state
and
you
also
sent
the
operation
to
the
other
nodes
in
the
network
with
straight
by
securities
you're
doing
something
different.
B
A
B
A
B
B
A
B
B
Function
function
has
to
be
independent
of
the
order
of
the
states
that
are
coming
in
so,
in
other
words,
the
merge
function
must
be
commutative
and
associative.
So
how
do
we
achieve
this
in
this
in
this
case?
But
we
achieve
this
in
this
case
by
having
our
murph
merge
function.
Take
the
maximum
contribution
from
all
the
contributions
in
the
state
we
cut
in
so
that
works.
But
that
means
this
is
an
increment
only
counter.
A
B
So
if
you
see
I
promised
you
that
you
can
do
the
same
with
state
cuties
than
what
you
can
do
with
operation
based
unities,
so
how
do
we
get
state
based
CDT
that
also
can
go
down
so
I
have
two
examples
for
you,
four
of
state
based
calendars
that
solve
that.
So
the
first
is.
We
can
actually
combine
to
see
oddities
to
get
a
new
CDT.
So
what
we
do
is
instead
of
keeping
track
of
the
contribution
by
a
to
the
results.
We
keep
track
of
two
contributions.
A
B
B
A
B
A
B
B
We've
seen
the
operation
based
charities,
which
are
also
called
commutative,
replicated
data
types
because
the
operations
are
sent
over
the
network
and
the
operations
must
be
cumulative
before
we
also
seen
the
state-based
here
disease.
Those
are
also
sometimes
called
the
convergent
replicated
data
types
because
the
states
are
sent
over
the
network
and
the
merge
function
makes
them
converge.
B
A
A
B
Example,
it's
fairly
transparent
to
use
a
user
that
this
is
gone
going
on
under
the
hood.
So
you
get
some
of
the
advantages,
because
if
there's
a
network
petition,
then
you
can
make
progress
in
both
petitions
of
the
network.
But
you
don't
really
have
to
think
about
it
too
much
as
a
consumer
of
the
API.
You
will
have
to
think
about
it.
For
example,
if
you
want
to
use
something
like
assets
because
they
react,
has
a
concept
of
assets
but,
as
we've
seen
like
the
ideal
set,
is
impossible
in
C
or
D
T's.
B
B
B
I
add
something
here:
it's
a
below,
so
these
are
two
clients
who
are
right
now
come
connected
to
one
server,
and
this
uses
C
realities
to
get
the
state
synchronous.
So
we
can
add
something
we
can
add
something
else.
So
what
would
happen
if
I
now
kill
the
server?
You
didn't
see
that
I
now
killed
the
server.
A
B
B
B
B
A
B
Cannot
no
model
every
data
type,
so,
for
example,
the
set
is
like
sort
of
inherently
impossible
to
model,
and
so
this
makes
it
worth
it
to
really
think
about
your
problem.
If
you
cannot
express
this
as
a
CDT,
then
maybe
you
have
some
opportunity
somewhere
to
make
an
assumption
and
to
have
all
the
nice
things.
Ttt
string
bring
you,
of
course.
In
some
cases
your
business
domain
really
requires
you
to
have
something
like
a
perfect
set.
Well
in
those
guys'
cases,
you
are
going
to
inherently
need,
for
example,
strong
consistency.
B
B
Given
you
a
really
gentle
introduction,
I
think
this
gives
you
a
good
grounding
to
read
further.
So
Mark
Shapiro
is
one
of
the
researches
that
has
done
a
lot
of
work
in
this
area
and
there's
a
couple
of
videos,
especially
one
that
he's
done
at
remarks
of
research,
is
from
in
Rio
himself
and
they're,
really
they're
really
good
watch
so.
B
Christopher
Michael
John
has
composed
a
reading
list
of
a
lot
of
background
material
about
sea
realities.
That's
really
interesting,
too,
and
he's
actually
giving
a
talk
after
lunch
in
the
theatre.
So
that's
warmly
recommended
it's
really
looking
forward
to
that
one.
So
that
concludes
the
talk
from
micro
state
perspective,
I'm
open
for
questions.
A
A
B
Sets
one
ad71
remove,
set,
that's
actually
a
common
implementation
and
the
remove
sets
are
often
called
tombstones.
So
that
way
you
can
remember
you
have
removed
that
element
and
I.
Think
if
you
do
something
smart
with
with
versions,
you
could
probably
find
safe
places
where
you
could
throw
away
tombstones,
but
I'm,
not
sure
of
if
any
search
algorithms
around
but
I
could
imagine
that
yeah.
A
A
B
Growing
the
state
could
be
like
manageable,
and
so,
if
you,
for
example,
have
a
situation
where
it's
common
for
there
to
be
Network
protections,
so,
for
example,
you
actually
expect
there
to
be
network
petitions
and
people
being
disconnected
for
a
while.
Then
it
could
actually
be
cheaper
to
have
a
state-based,
because
you
can
update
the
state
a
lot
of
times.
You
just
have
to
send
the
state
over
once.
B
If
it's
usually
connected,
then
it's
probably
true
that
the
operation
based
will
be
more
efficient
because
you
don't
have
to
communicate
whole
state
every
time,
but
it
really
depends
on
the
situation
in
general.
What
you
see
is
that
people
say
ok
state
based
it's
much
easier
to
think
about,
and
then,
if
you
have
something
that,
like
the
semantics
work
like
you
want
them
to,
then
you
can
try
to
convert
it
to
an
operation
based,
but
I
think
it
really
depends
on
your
situation.