►
Description
This presentation was recorded at GOTO Berlin 2016
http://gotober.com
Martin Kleppmann - Researcher at University of Cambridge
ABSTRACT
What do collaborative editors like Google Docs, the calendar app on your phone, and multi-datacenter database clusters have in common?
Answer: They all need to cope with network interruptions, and still work offline. They all allow state to be updated [...]
Download slides and read the full abstract here:
https://gotocon.com/berlin-2016/presentations/show_talk.jsp?oid=7910
RECOMMENDED BOOKS
Martin Kleppmann • Designing Data-Intensive Applications • https://amzn.to/3mk2Roj
https://twitter.com/gotober
https://www.facebook.com/GOTOConference
http://gotocon.com
A
Hello,
everybody.
Thank
you
very
much
for
coming
good
morning.
I
hope,
you're
doing
well,
I'd
like
to
talk
today
about
conflict
resolution
in
distributed
systems.
That
is,
if
several
people
change
some
data
at
the
same
time,
independently
of
each
other.
What
happens?
How
do
we
resolve
those
conflicts?
Okay,
my
background
is
I'm.
A
researcher
at
the
University
of
Cambridge
I
was
previously
in
industry
in
a
bunch
of
internet
startups,
so
I
worked
at
LinkedIn
for
a
couple
of
years.
A
So
in
the
case
of
get
you,
maybe
you'll
push
it
to
your
repository
on
github,
and
this
is
now
the
communication
mechanism
for
people
with
your
team.
So
if
there's
somebody
else
say
this
little
red
stick
figure.
Who
is
also
hacking
on
code,
then?
Well,
you
can
synchronize
up
through
the
central
repository.
This
is
all
very
familiar.
This
is
what
we
do
every
day
and
so
the
little
red
person
here
might
independent.
A
At
the
same
time
also
be
working
on
the
same
code
base
and
also
do
a
commit,
and
now
what
happens
if
this
person
now
fetches
from
github
well,
they'll
have
to
either
do
a
merge
or
rebase.
If
that's
how
your
workflow
goes
or
something
along
those
lines
zones
somehow
these
changes,
I
don't
have
to
be
combined
together
and,
as
you've
probably
experienced.
A
If
people
change
the
same
part
of
the
same
file,
then
you're
going
to
have
to
resolve
the
merge
conflict
yourself,
and
so
we
have
these
tools
for
doing
3-way
merges
for
copying
captures
from
one
side
to
another
and
figuring
out
what
the
result
should
be,
so
you've
probably
have
to
fight
with
things
like
this.
This
is
exactly
the
kind
of
problem
that
I'm
talking
about,
but
this
problem
happens
not
only
in
software
development.
It's
a
very
general
purpose
problem.
A
You've
got
the
email
as
the
communication
path
and
at
some
point
these
changes
are
going
to
have
to
be
merged
together
and
now
for
Microsoft
Word
I'm,
not
sure
there
is
even
this
kind
of
nice
user
interface
for
three-way
merges.
I
know
you
can
compare
two
documents
but
I
think
what
you,
what
people
then
end
up
doing
is
manually
copying
the
the
changes
from
one
version
of
the
document
to
another
and
so
performing
this
merge
really
manually.
So
that's
it
kind
of
this
aircraft
situation
here.
A
So
in
this
case
it's
kind
of
best
to
have
like
an
informal
lock
where
one
person
says
okay,
I'm
going
to
be
editing
the
document.
Now,
please
don't
change
it
for
the
next
day,
I'll
send
it
to
you
and
then
you
can
edit
it.
So
people
try
to
sequence
their
updates
like
this
through
manual
communication,
what
happens
in
another?
A
The
plants
I
just
remembered
so
adds
that
to
the
to-do
list
also,
does
this
post
to
the
server
comes
back,
ok,
and
so
in
this
case.
Actually
what
has
happened
is
if
this
central
server
stores
its
data
in
a
database
and
it
uses
something
like
transactions.
If
this
is
a
relational
database,
say
then
we
actually
have
serialization
going
on,
and
that
is
these
updates
are
actually
applied
in
a
sequential
order
in
a
serial
order.
A
So
in
this
case
you
don't
get
this
conflict
resolution
problem,
so
this
seems
nice,
but
on
the
other
hand
you
have
a
problem
which
is
well
what,
if
I
don't
have
signal
on
my
mobile
phone
right
now
or
if
the
network
is
interrupted
for
some
other
reason
or
I
can
press
the
button
to
save
and
I'll
just
get
a
spinning.
Spinning
wait
indicator
and
nothing
will
happen.
So
here
we
have
this.
It's
kind
of
obvious
this
problem.
If
you
don't
have
internet
connection,
then
you
can't
reach
the
central
server,
so
you
can't
store
any
data.
A
You
can't
edit
the
data
in
any
way,
so
it
doesn't
work
offline.
So
these
are
the
problems.
Yet
we
get
the
advantage
from
a
central
server
that
we
don't
have
to
worry
about
this
concurrency
and
these
these
different
edits
happening
at
the
same
time
and
having
to
merge
those
together,
but
at
the
cost
of
it
only
works
online.
So
we
now
require
constant
connectivity
to
the
server
which
is
not
so
great,
especially
if
you're
doing
things
on
mobile
devices.
A
Another
problem
is
that
these
requests
are
synchronous.
So
when
I
press
the
Save
button,
I
have
to
wait
until
I
get
the
okay
back
from
the
server
and
only
then
I
know
that
it
has
actually
been
saved
so
until
I
get
the
okay
back
I,
don't
know
whether
the
network
request
actually
made
it
through
or
not.
Maybe
if
the
network
is
unreliable,
so
that
also
can
be
a
timing
problem.
A
Let's
see
in
the
document
editing
case
so
say
in
the
case
of
Google
Docs,
you
know
you
can
press
one
letter
and
then
a
second
later
that
letter
will
appear
on
the
screen
of
another
person
who
is
editing
the
same
document.
So
there
the
edits
that
the
unit
of
editing
is
a
single
keystroke.
It's
not
even
like
a
commit
or
something
like
that.
A
It's
just
a
single
letter,
and
so
in
that
case,
if
you
wanted
to
send
up
through
a
central
server,
then
every
time
you
press
a
letter,
you'd
have
to
first
send
up
to
the
server
wait
for
it
to
be
saved.
There
wait
for
the
server
to
come
back
to
you,
say:
ok
and
then
you
could
display
the
letter
on
the
screen,
and
so
you
would
have
to
wait
for
that
network
round-trip
for
every
single
change
to
the
document,
which
is
particularly
what
happens
exactly
if
you're
editing
a
file
over
SSH.
A
So
if
you
logged
into
an
Linux
server
and
you're
using
vim
or
Emacs,
or
something
on
the
server-
and
you
type
a
letter,
then
that
editor
actually
lives
on
the
server.
So
you've
actually
got
that
synchronous
round-trip.
So
if
you've
got
a
slow
or
unreliable
Network
and
using
SSH
is
pretty
painful
as
you've
probably
experienced.
A
final
problem
with
putting
everything
on
a
central
server.
A
Is
that
now
there's
this
single
point
of
failure
and
people
make
fun
of
github,
for
example,
every
time
github
is
down
people
say:
oh
we've
got
this
nice
decentralized
version
control
system.
And
what
do
we
do
we
put
everything
back
in
a
centralized
service?
Isn't
that
great?
So
so
this
thing
can
be
disrupted.
A
If
you
worry
about
denial
of
service
attacks,
for
example,
or
if
you
worry
about
blocking,
maybe
in
some
countries
that
don't
have
such
free
internet
access,
if
you're
critical
of
the
local
regime
or
something
like
that,
then
actually,
this
kind
of
block
ability
is
quite
a
problem.
So
what
we'd
like
to
do
is
to
figure
out
how
to
not
have
these
problems
of
the
single
central
server
but
at
the
same
time
not
have
all
of
the
problems
of
having
to
do
the
merges
by
hand.
A
So
coming
back
to
the
to
do
list
example,
if
we
think
about
this
having
to
synchronously
communicate
with
our
server,
that's
okay!
If
the
servers
in
the
same
town,
but
if
the
servers
on
the
other
side
of
the
planet,
then
this
is
quite
slow
because
it's
simply
speed
of
light
takes
a
while
to
go
all
the
way
round
to
the
other
side
of
the
world
and
back
again.
So
what
if
we
just
put
data
centers
in
several
different
places.
A
So
let's
say
when
the
blue
person
adds
by
milk
to
the
to-do
lists
that
request
just
goes
to
the
blue
person's
local
data
center
call
it
data
center
one
and
get
saved
there,
and
when
the
red
person
adds
water
plants
to
de
to-do
list,
then
that
goes
to
the
local
data
center
too.
Those
are
two
different
local
data
centers.
A
If
the
people
are
in
different
locations-
and
so
now
that's
okay,
so
each
person
can
get
a
response
from
their
local
data
center
and
now
these
changes
will
be
propagated,
asynchronously
and
so
the
speed
of
lights
going
all
the
way
around
the
planet
is
still
as
slow
as
it
was
before.
So
it
could
happen
that
two
people
make
these
changes
without
knowing
about
each
other,
and
then
you
simply
don't
know
which
one
of
these
actually
came.
A
A
So
if
this
adding
an
item
to
dududu
to
the
to-do
list
means
just
appending
it
to
the
end
of
the
list,
then
which
order
should
these
items
appear
now
we
suddenly
have
to
worry
about
the
fact
that
the
data
center
one
might
have
buying
milk
first
and
watering
the
plant
second
and
the
other
data
center
might
have
them
flipped
in
the
other
order.
Oh
yeah.
A
Let's
think
this
further,
even
without
two
data
centers,
we
can
just
make
it
really
extreme
and
say:
ok,
we're
not
even
going
to
talk
to
a
data
center,
we're
just
going
to
talk
to
our
local
storage
on
the
device
and
I'm
going
to
treat
the
storage
on
my
mobile
phone
as
a
data
center
there.
It's
the
best
data
center
ever
because
I
can't
have
a
network
interruption
between
me
and
the
storage
on
my
phone.
A
That
has
to
happen
with
the
with
the
two
data
centers
exchanging
data
and
it's
exactly
the
same
synchronization
process
that
happened
with
the
git
commits
being
sent
by
github
or,
with
the
word
documents
being
sent
by
email.
It's
all
exactly
the
same,
which
is
you've,
got
some
changes
that
are
happening
concurrently
independently
from
each
other
and
those
changes
are
being
propagated.
Asynchronously
and
here,
of
course,
now
we're
back
to
this
problem
of
conflicts.
So
take
the
example
of
adding
two
items
to
do
to
the
to-do
list.
A
You
can
kind
of
imagine
that's
quite
easy
to
resolve.
You
just
make
sure
that
you
somehow
decide
on
a
consistent
order,
may
be
using
some
IDs
or
something
or
some
user
IDs
you
can
order
them
arbitrarily.
But
what?
If
one
item
is
one
where
one
change
is
deleted?
To-Do
item
and
the
other
actually
edits
that
same
to-do
item,
so
the
red
one
changes
buying
milk
to
buying
soy,
milk
and
the
blue.
One
just
deletes
the
buying
milk
item
and
these
two
changes
happen
without
knowing
about
each
other.
So
how
do
we
resolve
this
because?
A
Well,
if
you
say
that
the
deletion
wins
so
okay,
this
item
was
deleted.
The
to-do
list
item
was
deleted
so
that
edit
to
change
by
milk
device,
milk
is
just
gone
because
the
item
that
it
refers
to
is
no
longer
there,
but
that
means
that
we've
forgotten
about
the
fact
that
soy
milk
was
added
in
there,
and
so
maybe
that's
an
important
fact
that
we've
now
lost.
On
the
other
hand,
we
could
do
it
the
other
way
around.
A
We
could
say
that
despite
soy,
milk
wins,
but
then
the
deletion
has
been
lost,
and
so
maybe
the
deletion
is
meaningful.
So
how
do
we
resolve
this
kind
of
conflict?
In
general?
We
have
concurrent
operations
that
happen.
Concurrent
doesn't
mean
necessarily
at
the
same
moment
in
time.
It
just
means
they
happen
without
knowing
about
each
other
and
somehow
we
need
to
achieve
convergence
where
everybody
agrees
on
the
same
data
at
the
end,
and
so
people
talk
about
eventual
consistency
which
is
kind
of
the
database
term.
That's
often
used
for
describing
these
types
of
system.
A
Where
you
simply
you
can
allow
different
things
to
happen
concurrently
and
you
just
want
to
end
up
in
the
same
state.
At
the
end,
the
problem
with
the
term
eventual
consistency
is
that
it's
actually
very
vaguely
defined,
and
so
people
are
very
imprecise
when
talking
about
it
and
I'd
like
to
break
it
down
into
three
points.
Three
properties
that
a
bit
more
precise,
so
I'm,
going
to,
firstly,
assume
eventual
delivery,
and
that
is
we
send
messages
over
the
network
and
we're
going
to
assume
that
the
network
is
not
interrupted
forever.
A
So
we're
going
to
assume
that
after
some
finite
amount
of
time,
you
get
a
network
connection
again,
and
so,
if
you
keep
retrying,
then
you
can
get
the
message
through.
Eventually,
you
kind
of
have
to
make
this
assumption,
because
if
you
assume
that
a
device
can
be
offline
forever,
then
it
can
never
come
and
sync
with
the
other
devices
again
just
by
definition
of
on
off
line.
So
we're
just
going
to
assume
that
eventually
some
messages
go
through,
but
we're
not
going
to
make
any
assumptions
about
how
quick
that
is.
A
So
if
I
go
to
Iceland
and
there's
no
mobile
signal
and
I'm
hiking
somewhere
up
on
the
top
of
a
volcano
for
two
weeks,
then
I
won't
get
any
messages
for
two
weeks
and
when
I
get
back
to
Reykjavik,
then
I
will
get
some
messages
when
I
reach
an
internet
connection
again.
So
that
means
my
message.
Delay
is
two
weeks.
In
that
case,
that's
okay,
we're
just
going
to
assume
that's
all
right.
A
Secondly,
the
second
part
of
eventual
consistency
is
making
sure
that
everybody
ends
up
in
the
same
state.
That
is
if
we
assume
that
eventually,
everybody
gets
all
the
messages.
Then,
if
two
people
have
received
the
same
messages,
then
they
should
be
in
the
same
state.
So
that
means
that,
even
if
they
receive
the
messages
in
a
different
order,
they
should
still
end
up
in
the
same
state.
And
finally,
what
we
want
is
to
not
lose
data.
A
Now
this
it
seems
like
a
kind
of
slightly
really
ridiculous
point,
because
of
course
nobody
wants
to
lose
data,
but
it
is
actually
quite
important
to
make
this
explicit.
So
quite
a
few
database
users
do
use
this
mode
called
last.
Writer.
Wins
where
you
say
if
two
people
change
the
data
at
the
same
time,
we're
just
going
to
pick
one
of
them
arbitrarily,
based
on
the
timestamp
as
being
the
winner
and
the
other
ones
were
just
going
to
throw
away,
and
so
this
is
like
equivalent.
A
If
you
think
about
the
word
document
example
of
well,
you've
got
two
people
editing
the
word
document
and
one
person
emails
their
change
to
another
and
the
other
person
is
just
going
to
say.
Well.
I
made
changes
myself
as
well
and
I'm
going
to
declare
that
my
changes
are
newer
than
your
changes
and
so
I'm
just
going
to
ignore
your
changes.
Sorry-
and
so
this
is
not
very
friendly
to
people,
because
changes
get
lost.
So,
let's,
let's
require
not
losing
data
as
well.
A
That
is
you've,
got
a
list
of
to-do
items
and
they
have
to
appear
in
a
certain
order,
and
the
user
specifies
this
order
and
also
you
have
maps
so
you've
got.
Maybe
one
JSON
object
inside
another
JSON
object,
or
something
like
that
now,
once
we've
got
these
data
structures,
we
can
then
make
various
changes
to
them.
So,
as
the
users
interact
with
the
application,
they
will
make
changes.
For
example,
they
might
set
watering
plants
to
truth,
so
they
say
okay.
A
This
is
now
done,
I'm
going
to
check
the
box
on
my
phone
and
what
that
does
is
set
this
done
flag
from
forth.
So
the
operation
here,
the
change
operation,
the
edit
operation-
is
assigning
a
value
to
a
particular
field
in
this
JSON
document.
Another
thing
that
might
happen
is
somebody
might
edit
a
string
so
change
milk
change
by
milk
to
buy
soy
milk.
A
So
by
inserting
a
few
letters
into
that
string,
another
thing
that
might
people
might
do
is
insert
a
whole
new
list
item
of
phone
mum
between
buy
milk
and
before
ordering
watering
plants.
So
this
is
editing
the
ordered
list
objects
to
insert
a
new
item.
Another
thing
that
people
might
do
is
add
another
key
to
this
map
here
or
they
might
even
delete
an
entire
entry.
So
the
top-level
to-do
item
just
delete
the
entire
list.
Why
not?
Maybe
you
have
several
lists
or
something
like
that?
A
So
these
are
the
kinds
of
changes
that
people
can
make
to
these
documents
and
what
we
want
to
do
is
have
some
way
of
resolving
those
changes
so
that
even
if
people
make
these
changes
concurrently
to
each
other,
we
end
up
with
invention
consistency.
So
we
can
model
this
document
as
a
tree
and
we
can
have
some
data
type
annotations
on
it.
So
say
the
top-level
document
is
a
map
and
inside
it
we
have
a
list
under
the
key
to
do,
and
so
on
won't
go
into
too
much
detail.
A
So
this
is
actually
an
algorithm
that
I
developed
together
with
a
colleague,
and
we
wrote
this
paper
about
a
few
months
ago.
So,
if
you're
interested
in
that,
you
can
find
it
online,
it's
called
a
conflict
tree
replicated
Jason
data
type,
it
says:
is
anyone
here
heard
of
CRD
T's
before
ok,
a
few
people
cool?
So
this
is
an
example
of
a
CR
DT.
If
you
don't
know
what
a
CR
DT
is,
don't
worry.
Okay,
this
paper
is
very
theoretical.
A
A
It's
a
a
text
document
consists
of
the
file
name,
which
is
just
a
string,
consists
of
the
characters
of
the
body
of
the
actual
text.
So
each
individual
character
is
like
the
smallest
unit
you
can
edit
and
like
maybe
there
might
be
additional
stuff
for
formatting
setting,
fonts
and
so
on,
I'm
just
going
to
leave
all
of
that
out.
Another
thing,
that's
quite
useful,
is
cursor
positions
so
like
if
you
use
Google
Docs,
you
can
see
where,
in
the
document
and
other
users
editing
right
now,
that's
quite
handy
to
see.
A
Third,
that
you
don't
change
the
same
place
at
the
same
time
while
you're
online,
and
so
you
could
imagine
implementing
that
as
a
map
from
each
client
has
a
position.
A
position
is
like
a
location
in
the
document,
and
so
that
would
allow
you
to
keep
track
of
other
people's
cursors,
so
I'll
just
focus
on
the
body
characters
for
now.
So
the
ordered
list
of
characters
is
what
constitutes
the
content
of
the
document.
You
might
wonder
why
this
is
why
this
is
a
list
of
strings
and
not
a
list
of
characters
so
begin
footnote.
A
It's
a
list
of
strings
because
in
Unicode,
if
you
actually
represent
like
one
character,
one
or
the
smallest
editable
unit
of
a
document
is
not
necessarily
a
single
Unicode
code
point
because
you
have
things
like
combining
combining
marks.
I
think
they're
called
for
accents
and
diacritics
and
various
things
or
for
emoji
I
think
the
skin
color
annotation
is
combining
mark,
and
so
you
end
up
with
a
sequence
of
several
Unicode
code
points
that
constitutes
then
one
character
from
the
users
point
of
view.
A
If
you're
interested
in
this
look
at
the
Unicode
annex
number
29
anyway,
and
the
footnote,
this
is
completely
irrelevant.
I
just
wanted
to
mention
that
as
well.
I'll
give
a
little
demo
of
the
text
editor.
We
implemented,
because
it's
just
kind
of
fun
to
to
make
this
a
bit
more
interactive.
So
what
I
have
here
is
something
that
doesn't
work
hooray.
A
A
And
it
works,
so
you
can
see.
I
can
type
something
on
one
side
and
it
appears
on
the
other
side,
and
these
two
editors
are
actually
communicating
via
a
network
connection.
So
there
are
two
separate
processes
that
are
otherwise
don't
share
anything,
so
they
could
easily
be
on
two
separate
computers
on
other
sides
of
the
world.
No
problem
and
what
I
can
now
do
is
I
can
kill
the
server,
so
they
use
a
WebSocket
server
here
to
communicate
and
when
I
kill
the
server.
What
I'm
simulating
is
a
network
interaction
between
the
two.
A
So
we
have
these
two
now
and
so
I'm
going
to
restart
the
server
now
and
what
we
want
is
for
all
of
those
changes,
doopy
preserved
so
make
sure
look
at
that
everyone
at
is
still
there
and
hope.
You're
all
doing
well
is
still
there.
So
when
I
restart
the
server
the
editors
in
the
background,
keep
trying
to
reconnect
to
the
server
automatically
and
keep
retrying
in
the
background,
and
eventually
they
will
manage
to
connect
and
resynchronize.
A
A
Let's
have
a
look
at
how
this
algorithm
actually
works
because
that's
kind
of
interesting
this
is
basically
the
same
as
what
Google
Docs
does
right.
So
Google
Docs
is
a
bit
fussy
with
it
offline
support,
but
if
you
force
it
into
actually
doing
it,
it
essentially
does
the
same
kind
of
merge
and
I
can
run
through
a
better
of
how
the
algorithm
in
Google
Docs
works.
A
A
A
So
you
see
0
1,
2
3
4,
so
we
inserted
the
L,
so
the
oath
has
moved
from
position
3
to
position
4,
and
so
we
inserted
that
L
there,
and
on
this
side
we
have
the
inserting
exclamation
mark
at
position
4
and
so
that
describes
the
change
that
was
made
and
now
the
server's
forwards.
Those
changes
over
to
the
other
client
and
so
the
green
change,
inserting
the
L
gets
forwarded
by
the
server
over
here
insert
L
at
position.
3
position.
3
is
the
right
position
here.
A
So
you
end
up
with
hello
exclamation
mark,
which
is
what
we
wanted.
However,
if
you
think
about
what
happens
in
the
other
direction,
so
this
insert
exclamation
mark
at
position
4.
If
we
simply
send
that
through
unchanged,
what
we
will
get
is
hell
exclamation,
mark
OH,
because
over
here
we
inserted
the
letter
L
at
position
3,
so
the
O
moved
along
prong
3
to
4.
So
really
we
would
need
to
change
that
to
insert
exclamation
mark
at
position
5,
and
only
then
we
would
get
the
right
outcome
of
having
hello
exclamation
mark.
A
And
so
what
has
to
happen
here
is
that
this
position
for
needs
to
be
changed
to
position
five,
because
there
was
concurrently
an
insert
at
position
three.
So
the
server
has
to
keep
track
of
all
of
these
different
things
going
on
simultaneously
and
it
has
to
transform
the
messages
rewriting
this
three
to
four.
Some
of
the
transformation
happens
on
the
clients
as
well,
but
this
algorithm
does
actually
depend
on
the
server
to
do
some
work
as
well
and
that
works.
A
So
this
algorithm
is
called
operational
transformation
and
it's
been
around
for
quite
a
while,
so
it
was
first
discussed
in
the
academic
literature
back
in
the
1980s.
Although
the
first
paper
that
presented
this
algorithm
was
actually
incorrect
and
they
said
so
in
the
paper,
they
said
he
was
a
case
in
which
our
algorithm
fails
can
help.
Someone
help
us
fix
it.
A
They
all
use
this
Jupiter
design,
which
is
to
use
the
central
server
that
does
some
of
the
transformations
some
of
the
others
don't
use
the
central
server,
but
instead
keep
track
of
some
kind
of
multi-dimensional
hypercubes
of
all
of
the
edits
happening
simultaneously.
They
start
requiring
quite
a
lot
of
memory,
some
of
those
algorithms,
which
is
why
they're
not
used
as
often
in
practice,
and
so
this
kind
of
works
fine
for
Google's
purposes,
but
remember
what
we
wanted
is
to
be
able
to
work
with
end-to-end
encryption.
A
And
so
in
that
case
we
can't
have
a
server
transforming
our
messages,
because
the
server
would
then
have
to
see
the
content
of
the
messages
and
we
want
what
we
want
is
well.
We
want
to
avoid
one
central
server
because
that's
a
single
point
of
failure
and
we
want
to
avoid
the
server
seeing
the
content
of
our
messages.
So
we
want
to
be
able
to
just
forward
the
messages,
and
this
is
where
C
Rd
T's
come
in,
so
C
Rd
T
stands
for
commutative.
A
They've
got
merge,
functions
or
functions
which
allow
you
to
apply
operations
in
a
different
order
and
still
get
the
same
outcome
at
the
end,
and
if
we
want
to
model
something
like
a
text
document
like
what
I
have
in
our
editor
example.
In
that
case,
we
have
an
ordered
list
of
characters,
and
so
the
data
type
we
want
here
is
an
ordered
list
and
several
different
algorithms
were
have
been
proposed
to
that.
They
are
still
more
recent
only
about
in
the
last
10
years.
A
So
let
me
show
you
how
this
one
works
in
a
nutshell,
we
start
off
with
the
same
example
document,
which
is
a
chielo,
but
now,
instead
of
giving
each
letter
just
an
index,
0
1
2,
3
I'm,
going
to
give
it
a
unique
identifier.
Each
letter
has
a
unique
identifier
which
might
be
just
0
a
1,
a
2,
a
3
a,
and
we
now
have
the
same.
Edits
happens.
A
So
we
have
them,
they
have
to
be
globally
unique
and
they
also
have
to
have
a
certain
ordering
property
and
so
we're
going
to
construct
them
as
follows:
each
identifiers
a
number
and
a
letter
and
for
the
number
we
choose
one
greater
than
the
highest
number.
We
have
so
find
the
document,
and
so
the
document
server
file
contains
0
2
3
as
numbers.
So
the
next
number
we're
going
to
pick
is
4,
and
then
we
call
the
left-hand.
A
One
is
node,
a
the
right-hand
one
is
node
B,
and
so
that
will
be
the
letter
that
we
use
for
the
identifier.
And
so,
if
we
assume
that
the
names
of
the
nodes
are
unique,
so
there's
no
other
node
called
a
there's,
only
one
node
they
and
furthermore,
we
assume
that
these
numbers
are
generated
by
taking
one
plus
the
highest.
We
have
so
the
numbers
per
node
will
always
be
unique.
A
So
that
means
we
generate
for
a
on
the
left
hand
side
and
for
B
on
the
right
hand,
side
it's
the
same
for
because
they're,
both
in
the
same
starting
position,
but
they
have
two
different
node
IDs.
So
we
get
two
different
identifiers
and
so
that
works
and
now
we
can
send
these
things
by
our
server
or
it
doesn't
even
have
to
be
a
server.
A
A
Even
though
we
inserted
the
letter
L
before
it
hasn't
changed
the
fact
that
the
ID
of
the
letter
O
is
still
3a,
and
so
we
can
put
the
exclamation
mark
with
4b
after
the
letter
O
after
four
after
3a,
and
so
we
end
up
with
the
same
documents
in
both
places,
which
is
very
nice.
We
can
now
just
have
some
kind
of
network
between
these
two.
It
doesn't
have
to
transform
the
messages
in
any
way.
It
just
needs
to
make
sure
that
it
keeps
retrying
and
eventually
the
messages
get
through.
A
That's
all
we
need
here
we
can
encrypt
them,
and
it's
all
very
nice,
now
there's
still
a
problem
with
this
algorithm
which
I
wonder
if
anyone
can
spot.
Yes,
deletion
is
one
thing.
Yes,
I
deletion
is
actually
quite
easy,
so
what
we
do
for
deletion
is
just
to
set
a
flag
for
every
ID
and
say
that
if
it's
deleted,
then
the
ID
actually
remains
there
secretly
hidden,
but
we're
just
going
to
say.
Okay,
this
o
is
gone
now,
so
don't
show
it
in
the
user
interface.
A
A
So
let's
have
a
simpler
example:
document:
yeah
ABC
with
IDs
1,
a
2,
a
3,
a
and
now,
let's
say
x
and
y,
get
inserted
here
between
a
and
B.
So
the
left-hand
side
insert
X
and
y
gives
them
two
new
IDs,
according
to
the
rule
that
I
specified
earlier
so
4a
and
5a,
and
and
so
what
that
means
here
is
insert
X
after
a
1
a
insert
y.
A
And
now
we
need
to
make
sure
that
all
of
these
letters
end
up
in
some
kind
of
consistent
order
on
both
nodes
afterwards,
and
so
let's
take
those
operations
and
apply
them
to
the
other
side,
so
insert
P
with
the
new
ID
for
B
after
1
a
1
a
is
the
first
letter
a
so
we
insert
P
there
and
then
insert
Q
with
letter
with
with
ID
5
B
after
4
B
4
B.
What's
the
letter
Q,
which
we've
already
inserted,
so
we
can
put
the
key?
A
A
A
The
message
is
just
going
to
be
insert
X
with
ID
for
a
after
1
a,
but
if
we
put
it
straight
after
1a,
then
the
X
will
go
here
and
we
have
an
inconsistency
so
I'm
going
to
introduce
a
small
algorithm
which
uses
these
IDs
and
that
is
lookups.
The
ID
of
the
incoming
operation
yeah
when
you're
applying
an
operation
that
came
in
from
a
different
node
in
this
case.
That's
for
a
so
for
a
is
the
incoming
operation
and
we
first
find
the
position
after
which
we
want
to
insert
the
one
a
is
here.
A
So
we
start
here
after
the
a
and
we
look
at
the
next,
the
ID
of
the
next
element
in
that
list,
which
is
for
B,
and
if
that
ID
here
for
B
is
greater
than
the
incoming
element
ID
for
a
then
we're
going
to
skip
over
it
and
if
it's
greater,
the
next
one
is
greater
again
we'll
again
skip
over
that
and
we
keep
skipping
until
we
find
an
element
that
is
less
than
the
ID
of
the
incoming
operation.
So
2
a
is
less
than
4
a
so
in
this
ordering.
A
Here
we
look
at
first,
the
number,
then
the
latter
so
here
for
B,
is
greater
than
for
a
because
B
is
greater
than
a
5.
B
is
definitely
greater
than
for
a
because
5
is
greater
than
4,
but
2
is
less
than
4.
So
we
know
now
we
have
to
insert
between
the
5
B
and
a
2
a
whoo
and
then
for
the
final
operation
is
actually
easy.
A
A
So
let's
say
our
document
is
hey
guys
and
we
decide
that
that
is
not
general
gender-neutral
enough.
So
one
person
is
going
to
change
it
to
hey
everyone
and
the
other
person
is
going
to
change
it
to
pay
folks.
And
what
does
our
editor
do
in
this
case
now
so
I
described
just
now
how
deletion
works
and
so
deletion
just
means
setting
a
flag
on
these.
So
if
two
people
can
currently
delete
the
same
letter,
they
both
delete
the
G
of
guys
well
that
deleting
at
once
is
the
same
as
deleting
it
twice.
A
It
doesn't
get
any
more
deleted
through
being
deleted
several
times,
so
those
letters
just
get
deleted
and
the
insertion
stayed
because
one
insertion
doesn't
replace
another
insertion
so
at
least
to
merge
what
you're
going
to
end
up
with
with
is
the
two
insertions
concatenated,
so
it'll
be
hey
everyone,
folks
or
maybe
it'll,
be
hey
folks,
everyone.
So
the
order
of
those
two
is
arbitrary.
That
just
depends
on
coincidence
of
how
the
networking
happens
to
work
out,
and
you
know
there's
no
order.
That
is
any
one
order,
isn't
any
better
than
the
other.
A
The
problem
is
just
that.
What
we
have
here,
every
one
folks
is
not
an
English
word
and
so
you've
kind
of
end
up
with
junk.
In
the
document,
though,
this
is
actually
what
Google
Docs
does
as
well.
So
at
this
point,
I'm
willing
to
just
say:
okay,
we'll
tell
the
users
that
look
here.
This
doesn't
pass
the
spell
checker
and
it's
maybe
we
can
pop
up
a
warning.
Saying:
hey
several
people
edited
the
document
in
the
same
place,
the
actual
Google
Docs
doesn't
even
do
this
warning.
A
It
just
leaves
humans
too,
spotted
by
themselves,
and
it
seems
to
work
in
practice.
So
I
think
at
this
point
we
just
say:
okay,
it's
good
enough.
We're
not
going
to
try
to
do
a
grammatical
analysis
of
the
sentences
and
do
the
merges
automatically
so
that
they
obey
English
grammar,
because
that's
just
not
going
to
work.
Actually
people
have
tried
that
and
it
simply
didn't
work.
So
we've
got
this
CR
DT.
A
This
data
structure
for
ordered
lists,
which
several
people
can
change
at
the
same
time
describes
deletion
and
how
that
works
are
still
a
lot
of
open
questions
there.
So
the
problem
with
deletion
here
is:
we
need
to
actually
remember
for
a
long
time
afterwards,
where
a
pacific
particular
ID
is
because
we
use
these
ids
as
a
position
in
the
list
like
an
address
like
a
pointer,
and
so
we
can't
just
delete
if
something
gets
deleted
from
the
document.
A
We
can't
then
just
remove
it
and
forget
about
it
entirely,
because
then
some
operation
would
come
in
and
insert
after
503
a
and
we
go
503
a
sorry
that
was
deleted,
I,
where
to
put
that
insertion,
so
we
have
to
keep
those
things
which
are
called
tombstones.
Also
haven't
talked
about
how
to
do
undo,
like
you
know,
control,
Zed
type
undo
or
how
to
reorder
the
elements
in
the
list,
that's
kind
of
interesting
or
how
to
make
all
of
these
IDs
efficient.
So
it
doesn't
take
too
much
storage.
A
So
still
a
lot
of
open
questions
there
I
think
the
basic
algorithm
is
kind
of
fine,
but
actually
putting
it
into
practice
is
still
going
to
need
a
bit
of
work,
but
I
want
to
talk
about
some
other
stuff
as
well.
Actually
so
we
were
talking
about
these
JSON
documents
earlier
and
so
interesting
things
happen
when
several
people
can
currently
change
JSON
documents
that
don't
happen
just
in
the
case
of
a
text
document.
So
let's
say:
we've
got
here.
A
It's
a
bit
of
a
contrived
example,
I'm
afraid
a
map
of
colors,
and
so
this
is
imagine
this
is
an
actual
structure.
So
it's
not
like
curly
brace
quotation
mark
c/o
et
cetera
as
a
text
document,
but
it's
actually
the
JSON
syntax
tree
this
right
here
and
so
one
person
inserts
a
new
color,
the
color
red
into
this
map,
and
so
you
then
end
up
with
a
map
containing
blue
and
red
and
another
person
concurrently
decides.
A
A
What's
the
outcome?
What
what
is
even
the
right
behavior
here?
What
what
do
we
expect?
So
we
can
think
about
it
systematically
and
say:
well:
okay,
blue!
Does
it
contain
blue?
Well,
blue
was
deleted
on
the
right
hand,
side
by
setting
the
whole
map
to
empty,
so
I
guess
blue
should
not
be
in
the
final
result
because
it
was
deleted
and
the
left
hand.
So
I
didn't
touch
it.
A
What
about
red
red
initially
didn't
exist,
but
it
was
inserted
on
the
right
on
the
left,
hand,
side
and
right
hand,
side,
I,
didn't
touch
red,
so
I
guess
we
need
red
to
be
in
the
final
result.
What
about
green
Green
was
inserted
on
the
right
hand,
side
and
it
was
not
touched
on
the
left
hand
side.
So,
yes,
we
want
green
to
be
in
the
final
result.
So
our
final
expected
outcome
is
that
it
should
contain
red
and
green,
but
not
blue.
A
Does
that
seem
my
guess
so
so
we
can
do
that
and
our
algorithm
does
this.
What
this
means
here
is
that
we
have
to
keep
track
of
what
this
setting
the
map
to
empty
means,
because
if
you
just
take
this
and
say
on
the
left
hand
client,
you
first
add
the
red
in
and
then
you
take
that
change
that
came
from
the
right
hand,
side
which
is
setting
the
map
to
empty,
and
if
you
just
apply
that
naively
and
say,
you've
got
an
operation
of
his
set
map
to
empty.
A
Well,
then
you're
going
to
wipe
out
the
red
because
the
red
was
added
concurrently,
so
we
have
to
somehow
remember
what
the
state
of
the
map
was
at
the
time
when
you
set
it
to
empty.
So
we
have
here.
The
thing
is:
is
known
as
a
causal
context
or
something
like
that
in
databases
like
react.
For
example,
has
anyone
used
react
that
they
have
this
datatypes
feature?
A
Okay,
it
works
very
similarly
to
this
that
you
have
this
little
extra
bit
of
information
that
you
pass
around
in
an
HTTP
header
and
that
the
purpose
of
that
is
to
keep
track
of
what
is
the
state?
What
was
the
state
of
the
document
at
the
time
when
you
saw
it
so
that
then
later
you
know
what
the
changes
need
to
apply
to.
A
So,
let's
look
at
a
different
example
here,
we've
got
again
and
our
to-do
list
example
and
we've
got
buying
milk
and
it
is
not
yet
done,
and
so
on
the
left-hand
side
and
edit
happens,
and
it
just
deletes
buying
milk
from
the
list,
because
maybe
it's
been
done
or
maybe
we
know
that
no
longer
need
milk
or
whatever
it's
just
removed
from
the
list.
On
the
right
hand,
side
somebody
sets
done
to
true
so
taps
the
button
who
said
buying
milk
done
to
true
what
happens.
A
If
we
try
to
merge
these
two
different
updates,
we
can
apply
the
same
logic
as
we
had
just
now
with
the
colors
with
the
nested
naps.
So
with
the
colors.
What
we
said
is
okay,
does
it
contain
each
of
the
different
things
depending
on
who
edited
what
okay,
so
the
title
of
buying
milk?
On
the
left
hand
side
that
was
deleted
because
we
deleted
the
entire
to-do
item,
so
I
guess
the
title
should
not
be
in
the
result.
On
the
right
hand,
side
we
didn't
touch
the
title,
so
that's
got
to
be
deleted.
A
What
about
done
false
well
done?
False
was
deleted
on
the
left
hand
and
over
written
on
the
right
hand,
side
with
done
true,
so
I
guess
done.
False
is
out
what
about
done.
True,
don't
true
did
not
appear
on
the
left
hand,
side
and
the
right
hand.
Side
done
true
was
added,
so
we
weren't
done
true
to
be
an
in
the
end
result.
So
if
we
apply
exactly
the
same
reasoning
logic,
what
we
end
up
with
is
a
to-do
item.
A
That
cane
contains
the
flag
done
true,
but
no
title,
and
this
is
kind
of
not
what
you
expect
because,
like
we've
applied
exactly
the
same
logic,
but
what
we've
ended
up
with
something
is
that
looks
weird,
and
it
looks
weird
because
we
kind
of
have
this
implicit
schema
here.
We
expected
to
do
item
to
always
have
a
title
and
the
done
field,
but
this
merge
here
has
essentially
tampered
with
our
schema.
So
what
do
we
do
here?
A
Maybe
we
need
a
schema
to
explicitly
say
exactly
what
fields
something
must
have,
but
in
that
case,
what
do
we
do?
So
if
somebody
changes,
if
one
person
changes
our
field
within
an
object
that
has
a
schema
and
another
person
deletes
that
entire
object?
Well,
do
we
say
the
deletion
wins,
so
in
that
case,
any
changes
to
stuff
within
the
deleted
item
are
just
going
to
be
lost,
but
we
said
earlier,
we
don't
want
to
lose
data.
A
So
how
do
we
resolve
this,
or
maybe
we
say
actually,
if
somebody
concurrently
changes
this
and
sets
done
to
true,
then
we're
actually
going
to
bring
the
title
back
as
well.
So,
even
though
the
title
was
actually
deleted
on
the
left-hand
side,
we
kind
of
resurrect
this
whole
deleted
item
and
say:
okay,
it's
going
to
back
at
both
the
title
and
done
true,
but
then
we've
forgot
about
the
fact
that
somebody
deleted
this
item.
So
it
seems
like
something
has
got
to
give
here
and
we
don't
really
know
what
it
is.
A
That's
I
think
there's
a
lot
of
value
in
having
these
kind
of
data
structures
that
you
can
just
merge
automatically
and
not
have
to
about
writing
manual
conflict
resolution
code,
but
the
same
time.
Concurrency
still
is
hard,
even
if
you
abstract
a
way
that
can
color
and
communication
and
everything
you've
still
got
the
problem
that
some,
how
long
you
can
sometimes
end
up
in
these
merged
situations,
where
there's
no
one
right
way
of
doing
it,
and
so,
if
any
of
you
have
ideas,
I'd
love
to
hear
done.
A
A
This
oh
crap
scenario
we're
just
going
to
let
users
resolve
all
of
the
edits
manually,
I,
don't
think
that's
really
friendly
to
users
and
so
I
think
that,
like
the
popularity
of
things
like
Google
Docs
and
indeed
like
meld
or
things
like
that
for
conflict
resolution,
it
shows
that
actually
people
do
need
a
bit
of
tooling
and
help
in
order
to
in
order
to
resolve
conflicts.
We
could
say:
okay,
we'll
just
put
everything
on
a
central
server
and
serialize
everything.
That's
an
option.
A
But
again
we've
got
this
problem
that
you
require
network
communication,
all
the
time
and
it's
stuff
doesn't
work
offline,
which
is
also
a
shame.
So
I
think
it
is
worth
working
on
this
problem,
but
it
is
an
open
problem.
If
you're
interested
in
more
details
on
this
I've
put
tweeted
the
slides
already
here,
so
you
can
find
it
there
and
there
are
links
to
all
of
the
papers.
Here's
the
second
page
and
here's
a
third
page
of
references,
so
our
paper
is
one
of
those
in
there.
A
There
are
also
several
others
about
different
CR
duties
and
different
operational
transformation
functions,
so
that
goes
into
vast
amounts
of
detail.
Here
is
a
book
that
I've
been
writing,
which
I
just
sent
off
to
the
publishers
just
two
days
ago,
so
you
can
get
an
early
release
of
this
online
already.
This
is
it's
not
specifically
about
merging
it's
very
broad
kind
of
introduction
to
the
architecture
of
databases,
and
what
do
databases
do
under
the
hood?
A
A
Do
you
have
a
minute
or
two
for
questions
I'm
a
bit
short
of
time?
We
do.
Okay.
Does
anyone
have
any
questions
or
comments
or
anything?
We
have
some
wonder
app,
that's
right.
So
the
question
is
a
putter.
Apart
from
the
operational
transformation
algorithm,
is
there
any
algorithm
which
uses
weighted
operators
to
decide
the
last
operation?
For
instance,
the
delete
operation
has
the
lowest
impact
for
that
losses.
A
There
is
that
it's
really
hard
I
think
to
communicate
that
to
developers
of
like
what
does
that
actually
mean?
If
you
don't
have
a
PhD
in
distributed
systems,
will
you
still
be
able
to
understand
what
this
flag
in
your
schema
actually
means,
so
I
think
just
making
stuff
comprehensible
in
a
way
that,
like
somebody,
you
can
just
go
and
build
an
app,
and
they
don't
have
to
know
about
all
of
the
internal
details
of
how
conflicts
have
resolved
internally.