Conflict Resolution in Eventual Consistency
Conflict resolution in eventual
consistency
COS 418:
Distributed Systems
Lecture 9
Michael Freedman
[
S
e
l
e
c
t
e
d
c
o
n
t
e
n
t
a
d
a
p
t
e
d
f
r
o
m
M
.
S
h
a
p
i
r
o
a
n
d
I
.
S
t
o
i
c
a
]
•
E
v
e
n
t
u
a
l
c
o
n
s
i
s
t
e
n
c
y
:
I
f
n
o
n
e
w
u
p
d
a
t
e
s
t
o
t
h
e
o
b
j
e
c
t
,
e
v
e
n
t
u
a
l
l
y
a
l
l
a
c
c
e
s
s
e
s
w
i
l
l
r
e
t
u
r
n
t
h
e
l
a
s
t
u
p
d
a
t
e
d
v
a
l
u
e
•
Common: git, iPhone sync, Dropbox, Amazon Dynamo
•
Why do people like eventual consistency?
–
Fast read/write of local copy of data
–
Disconnected operation
2
E
v
e
n
t
u
a
l
c
o
n
s
i
s
t
e
n
c
y
•
Encountered in many different settings:
–
Peer-to-peer (Bayou)
–
Multi-master clusters (Dynamo)
•
Potential solutions
–
“Last writer wins”
•
Thomas Write Rule for DBs with timestamp-based
concurrency control: Ignore outdated writes
–
Application-specific merge/update: Bayou, Dynamo
3
C
o
n
c
u
r
r
e
n
t
w
r
i
t
e
s
c
a
n
c
o
n
f
l
i
c
t
T
o
w
a
r
d
s
g
e
n
e
r
a
l
i
t
y
?
4
•
Consider banking (double-entry bookkeeping):
–
Initial: Alice = $50, Bob = $20
–
Alice pays Bob $10
•
Option 1: set Alice to $40, set Bob to $30
•
Option 2: decrement Alice -$10, incremental Bob +$10
–
#2 better, but can’t always ensure Alice >= $0
•
Works because common mathematical ops are
–
Commutative: A
◎
B == B
◎
A
–
Invertible:
A
◎
A
-1
== 1
5
G
e
n
e
r
a
l
a
p
p
r
o
a
c
h
:
E
n
c
o
d
e
o
p
s
a
s
i
n
c
r
e
m
e
n
t
a
l
u
p
d
a
t
e
6
C
o
n
s
i
d
e
r
s
h
a
r
e
d
w
o
r
d
p
r
o
c
e
s
s
i
n
g
•
How do I insert a new word?
–
Send entire doc to server?
Not efficient
–
Send update operation!
7
C
o
n
s
i
d
e
r
s
h
a
r
e
d
w
o
r
d
p
r
o
c
e
s
s
i
n
g
•
How do I insert a new word?
–
Send entire doc to server?
Not efficient
–
Send update operation!
insert (string, position) = insert(“1500s”, 166)
–
Warning: Insert (rather than replace) shifted position of all following text
8
O
p
e
r
a
t
i
o
n
s
m
u
s
t
b
e
c
o
m
m
u
t
a
t
i
v
e
$
4
0
$
3
0
$
4
5
W
i
t
h
d
r
a
w
$
1
0
D
e
p
o
s
i
t
$
1
5
9
O
p
e
r
a
t
i
o
n
s
m
u
s
t
b
e
c
o
m
m
u
t
a
t
i
v
e
$
4
0
$
3
0
$
4
5
W
i
t
h
d
r
a
w
$
1
0
D
e
p
o
s
i
t
$
1
5
D
e
p
o
s
i
t
$
1
5
W
i
t
h
d
r
a
w
$
1
0
$
5
5
A
B
D
I
n
s
e
r
t
(
“
1
5
0
0
s
”
,
1
6
6
)
D
e
l
e
t
e
(
1
,
0
)
D
e
l
e
t
e
(
1
,
0
)
[
d
e
l
e
t
e
1
c
h
a
r
a
s
p
o
s
0
]
C
I
n
s
e
r
t
(
“
1
5
0
0
s
”
,
1
6
6
)
P
R
O
B
L
E
M
!
10
10
O
p
e
r
a
t
i
o
n
s
m
u
s
t
b
e
c
o
m
m
u
t
a
t
i
v
e
$
4
0
$
3
0
$
4
5
W
i
t
h
d
r
a
w
$
1
0
D
e
p
o
s
i
t
$
1
5
D
e
p
o
s
i
t
$
1
5
W
i
t
h
d
r
a
w
$
1
0
$
5
5
A
B
D
I
n
s
e
r
t
(
“
1
5
0
0
s
”
,
1
6
6
)
D
e
l
e
t
e
(
1
,
0
)
D
e
l
e
t
e
(
1
,
0
)
[
d
e
l
e
t
e
1
c
h
a
r
a
s
p
o
s
0
]
C
I
n
s
e
r
t
(
“
1
5
0
0
s
”
,
1
6
5
)
11
11
O
p
e
r
a
t
i
o
n
s
m
u
s
t
b
e
c
o
m
m
u
t
a
t
i
v
e
$
4
0
$
3
0
$
4
5
W
i
t
h
d
r
a
w
$
1
0
D
e
p
o
s
i
t
$
1
5
D
e
p
o
s
i
t
$
1
5
W
i
t
h
d
r
a
w
$
1
0
$
5
5
A
B
D
I
n
s
e
r
t
(
“
1
5
0
0
s
”
,
1
6
6
)
D
e
l
e
t
e
(
1
,
0
)
C
E
F
G
H
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
Pioneered in GROVE (GRoup Outline Viewing Edit)
C. Ellis and S. Gibbs, 1989
12
12
Now found in Apache Wave & Google Docs
•
State of system is
S,
ops
a
and
b
performed by concurrently on state
S
•
Different servers can apply concurrent ops in different sequential order
–
Server 1:
•
Receives
a
, applies
a
to state
S
:
S
◎
a
•
Receives b (which is dependent on
S,
not
S
◎
a
)
•
Transforms b across all ops applied since S (namely a):
b
’ = OT(
b
, { a
})
•
Applies b’ to state:
S
◎
a
◎
b’
–
Server 2
•
Receives b, applies b to state:
S
◎
b
•
Receives
a,
performs transformation
a
’ = OT(
a
, { b
}),
•
Applies
a’
to state:
S
◎
b
◎
a’
•
Servers 1 and 2 have identical final states:
S
◎
a
◎
b’ == S
◎
b
◎
a’
13
13
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
(
O
T
)
14
14
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
(
O
T
)
(
U
s
e
d
i
n
G
o
o
g
l
e
D
o
c
s
,
E
t
h
e
r
P
a
d
,
e
t
c
.
)
A
l
i
c
e
B
o
b
O
p
s
:
S
t
a
t
e
:
A
B
C
D
E
A
B
C
D
E
O
p
s
:
S
t
a
t
e
:
15
15
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
(
O
T
)
(
U
s
e
d
i
n
G
o
o
g
l
e
D
o
c
s
,
E
t
h
e
r
P
a
d
,
e
t
c
.
)
A
l
i
c
e
B
o
b
d
e
l
4
d
e
l
2
O
p
s
:
S
t
a
t
e
:
O
p
s
:
S
t
a
t
e
:
A
C
D
E
A
B
C
E
d
e
l
4
d
e
l
2
16
16
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
(
O
T
)
(
U
s
e
d
i
n
G
o
o
g
l
e
D
o
c
s
,
E
t
h
e
r
P
a
d
,
e
t
c
.
)
A
l
i
c
e
B
o
b
d
e
l
4
d
e
l
2
O
p
s
:
S
t
a
t
e
:
d
e
l
2
d
e
l
4
d
e
l
2
O
p
s
:
S
t
a
t
e
:
A
C
E
A
C
D
17
17
O
p
e
r
a
t
i
o
n
a
l
T
r
a
n
s
f
o
r
m
a
t
i
o
n
(
O
T
)
(
U
s
e
d
i
n
G
o
o
g
l
e
D
o
c
s
,
E
t
h
e
r
P
a
d
,
e
t
c
.
)
A
l
i
c
e
B
o
b
d
e
l
4
d
e
l
2
O
p
s
:
S
t
a
t
e
:
d
e
l
2
d
e
l
4
d
e
l
2
d
e
l
4
d
e
l
2
d
e
l
3
O
p
s
:
S
t
a
t
e
:
A
C
E
A
C
E
M
o
r
e
r
i
g
o
r
o
u
s
a
p
p
r
o
a
c
h
:
C
o
n
f
l
i
c
t
-
f
r
e
e
r
e
p
l
i
c
a
t
e
d
d
a
t
a
t
y
p
e
Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski
2011
18
18
D
e
f
i
n
i
t
i
o
n
o
f
E
C
v
s
S
t
r
o
n
g
E
C
•
E
v
e
n
t
u
a
l
d
e
l
i
v
e
r
y
:
A
n
u
p
d
a
t
e
d
e
l
i
v
e
r
e
d
a
t
s
o
m
e
c
o
r
r
e
c
t
r
e
p
l
i
c
a
i
s
e
v
e
n
t
u
a
l
l
y
d
e
l
i
v
e
r
e
d
t
o
a
l
l
c
o
r
r
e
c
t
r
e
p
l
i
c
a
s
•
T
e
r
m
i
n
a
t
i
o
n
:
A
l
l
m
e
t
h
o
d
e
x
e
c
u
t
i
o
n
s
t
e
r
m
i
n
a
t
e
•
C
o
n
v
e
r
g
e
n
c
e
:
C
o
r
r
e
c
t
r
e
p
l
i
c
a
s
t
h
a
t
h
a
v
e
d
e
l
i
v
e
r
e
d
t
h
e
s
a
m
e
u
p
d
a
t
e
s
e
v
e
n
t
u
a
l
l
y
r
e
a
c
h
e
q
u
i
v
a
l
e
n
t
s
t
a
t
e
•
Doesn’t preclude roll backs and reconciling
•
S
t
r
o
n
g
C
o
n
v
e
r
g
e
n
c
e
:
C
o
r
r
e
c
t
r
e
p
l
i
c
a
s
t
h
a
t
h
a
v
e
d
e
l
i
v
e
r
e
d
t
h
e
s
a
m
e
u
p
d
a
t
e
s
h
a
v
e
e
q
u
i
v
a
l
e
n
t
s
t
a
t
e
19
19
S
t
a
t
e
-
b
a
s
e
d
a
p
p
r
o
a
c
h
20
20
payload set
initial
state
query
update
merge
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
21
21
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
22
22
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
23
23
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
24
24
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
25
25
S
t
a
t
e
-
b
a
s
e
d
r
e
p
l
i
c
a
t
i
o
n
•
Desired property:
•
After receiving all updates (irrespective of order),
each replica will have same state
26
26
E
x
a
m
p
l
e
:
U
n
i
o
n
S
e
t
•
u: add new element to local replica
•
q: return entire set
•
merge: union between remote set and local replica
{5
}
{5
}
{5
}
{5
}
{5
}
{5
}
E
x
a
m
p
l
e
•
Partial order ⊆ on sets
•
⊔ : U (set union)
•
Then, we have:
–
commutative: A U B = B U A
–
idempotent: A U A = A
–
associative: (A U B) U C = A U (B U C)
E
x
a
m
p
l
e
•
Partial order ≤ on set of integers
•
⊔ : max( )
•
Then, we have:
–
commutative: max(x, y) = max(y, x)
–
idempotent: max(x, x) = x
–
associative: max(max(x, y), z) = max(x, max(y, z))
E
x
a
m
p
l
e
:
G
r
o
w
-
O
n
l
y
C
o
u
n
t
e
r
E
x
a
m
p
l
e
:
P
o
s
i
t
i
v
e
-
N
e
g
a
t
i
v
e
C
o
u
n
t
e
r
S
e
m
i
-
l
a
t
t
i
c
e
•
Partial order ≤ set S with a least upper bound (LUB),
denoted ⊔
–
m = x ⊔ y is a LUB of { x, y } under ≤ iff∀ m′, x ≤ m′ ∧ y ≤ m′
⇒ x ≤ m ∧ y ≤ m ∧ m ≤ m′
•
It follows that ⊔ is:
–
commutative: x ⊔ y = y ⊔ x
–
idempotent: x ⊔ x = x
–
associative: ( x ⊔ y) ⊔ z = x ⊔ ( y ⊔ z)
M
o
n
o
t
o
n
i
c
S
e
m
i
-
l
a
t
t
i
c
e
O
b
j
e
c
t
•
A state-based object with partial order ≤ and the
following properties, is a
monotonic semi-lattice
:
1.
Set S of values forms a semi-lattice ordered by ≤
2.
Merging state s with remote state s′ computes the
LUB of the two states, i.e., s • m (s′ ) = s ⊔ s′
3.
State is monotonically non-decreasing across
updates, i.e., s ≤ s • u
C
o
n
v
e
r
g
e
n
t
R
e
p
l
i
c
a
t
e
d
D
a
t
a
T
y
p
e
(
C
v
R
D
T
)
•
Theorem: Assuming eventual delivery and
termination, any state-based object that satisfies
the monotonic semi-lattice property is SEC
•
Why?
–
Don’t care about order:
•
Merge is both commutative and associative
–
Don’t care about delivering more than once
•
Merge is idempotent
•
Update-based CRDTs:
–
Sends update operations, not state like CvRDT
•
Operations are commutative, but not idempotent
–
System must ensure all ops are delivered to other
replicas, without duplication, but in any order
–
Often used in more complex settings for
concurrent editing
35
35
C
o
m
m
u
t
a
t
i
v
e
R
e
p
l
i
c
a
t
e
d
D
a
t
a
T
y
p
e
(
C
m
R
D
T
)
I
n
d
u
s
t
r
y
U
s
e
o
f
C
R
D
T
s
:
D
a
t
a
b
a
s
e
s
:
R
e
d
i
s
,
R
i
a
k
,
F
a
c
e
b
o
o
k
A
p
o
l
l
o
O
t
h
e
r
:
L
e
a
g
u
e
o
f
L
e
g
e
n
d
s
C
h
a
t
Soundcloud user stream
TomTom device sync
36
36
N
e
w
M
o
d
u
l
e
o
n
M
o
n
d
a
y
:
R
e
p
l
i
c
a
t
e
d
S
t
a
t
e
M
a
c
h
i
n
e
s
37
37
Eventual consistency allows for all accesses to eventually return the last updated value, even if there are concurrent writes that can conflict. Various solutions like "Last writer wins" and application-specific merge/update methods are explored to manage conflicts in distributed systems. The general approach involves encoding operations as incremental updates, akin to double-entry bookkeeping in banking. Considerations for shared word processing operations in a distributed environment are also highlighted.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Conflict resolution in eventual consistency COS 418: Distributed Systems Lecture 9 Michael Freedman [Selected content adapted from M. Shapiro and I. Stoica]
Eventual consistency Eventual consistency: If no new updates to the object, eventually all accesses will return the last updated value Common: git, iPhone sync, Dropbox, Amazon Dynamo Why do people like eventual consistency? Fast read/write of local copy of data Disconnected operation 2
Concurrent writes can conflict Encountered in many different settings: Peer-to-peer (Bayou) Multi-master clusters (Dynamo) Potential solutions Last writer wins Thomas Write Rule for DBs with timestamp-based concurrency control: Ignore outdated writes Application-specific merge/update: Bayou, Dynamo 3
General approach: Encode ops as incremental update Consider banking (double-entry bookkeeping): Initial: Alice = $50, Bob = $20 Alice pays Bob $10 Option 1: set Alice to $40, set Bob to $30 Option 2: decrement Alice -$10, incremental Bob +$10 #2 better, but can t always ensure Alice >= $0 Works because common mathematical ops are Commutative: A B == B A Invertible: A A-1 == 1 5
Consider shared word processing How do I insert a new word? Send entire doc to server? Not efficient Send update operation! 6
Consider shared word processing How do I insert a new word? Send entire doc to server? Not efficient Send update operation! insert (string, position) = insert( 1500s , 166) Warning: Insert (rather than replace) shifted position of all following text 7
Operations must be commutative $40 A Withdraw $10 Deposit $15 Insert Delete (1, 0) ( 1500s , 166) $30 $55 B C Deposit $15 Withdraw $10 Delete (1, 0) $45 D [ delete 1 char as pos 0 ] 8
Operations must be commutative $40 A Withdraw $10 Deposit $15 Insert Delete (1, 0) ( 1500s , 166) $30 $55 B C Deposit $15 Withdraw $10 Delete (1, 0) Insert ( 1500s , 166) $45 D [ delete 1 char as pos 0 ] PROBLEM! 9
Operations must be commutative $40 A Withdraw $10 Deposit $15 Insert Delete (1, 0) ( 1500s , 166) $30 $55 B C Deposit $15 Withdraw $10 Delete (1, 0) Insert ( 1500s , 165) $45 D [ delete 1 char as pos 0 ] 10
Operations must be commutative $40 A Withdraw $10 Deposit $15 Insert Delete (1, 0) ( 1500s , 166) $30 $55 B C Deposit $15 Withdraw $10 $45 E D F G H 11
Operational Transformation Pioneered in GROVE (GRoup Outline Viewing Edit) C. Ellis and S. Gibbs, 1989 Now found in Apache Wave & Google Docs 12
Operational Transformation (OT) State of system is S, ops a and b performed by concurrently on state S Different servers can apply concurrent ops in different sequential order Server 1: Receives a, applies a to state S: S a Receives b (which is dependent on S, not S a ) Transforms b across all ops applied since S (namely a): b = OT( b, { a }) Applies b to state: S a b Server 2 Receives b, applies b to state: S b Receives a, performs transformation a = OT( a, { b }), Applies a to state: S b a Servers 1 and 2 have identical final states: S a b == S b a 13
Operational Transformation (OT) (Used in Google Docs, EtherPad, etc.) Server Alice Bob ABCDE ABCDE State: State: ins ABC ins DE ins ABC ins DE Ops: Ops: 14
Operational Transformation (OT) (Used in Google Docs, EtherPad, etc.) Server del 2 del 4 Alice Bob ACDE ABCE State: State: ins ABC ins DE ins ABC ins DE Ops: Ops: del 2 del 4 15
Operational Transformation (OT) (Used in Google Docs, EtherPad, etc.) Server Alice Bob ACD ACE State: State: ins ABC ins DE ins ABC ins DE Ops: Ops: del 2 del 4 del 4 del 2 del 2 16
Operational Transformation (OT) (Used in Google Docs, EtherPad, etc.) Server Alice Bob ACE ACE State: State: ins ABC ins DE ins ABC ins DE Ops: Ops: del 2 del 4 del 4 del 3 del 2 del 2 T T del 4 del 2 17
More rigorous approach: Conflict-free replicated data type Marc Shapiro, Nuno Pregui a, Carlos Baquero, Marek Zawirski 2011 18
Definition of EC vs Strong EC Eventual delivery: An update delivered at some correct replica is eventually delivered to all correct replicas Termination: All method executions terminate Convergence: Correct replicas that have delivered the same updates eventually reach equivalent state Doesn t preclude roll backs and reconciling Strong Convergence: Correct replicas that have delivered the same updates have equivalent state 19
State-based approach An object is a tuple (?,?0,?,?,?) payload set merge initial state update query Local queries, local updates Send full state: on receive, merge Update is said delivered at some replica when it is included in its casual history Causal History: ? = ?1, ,?? where ci goes through a sequence of states: ?? 0, ,?? ? 20
State-based replication Local at source ?1.u(a), ?2.u(b), Precondition, compute Causal History: ?= ?? ? 1 on query: ?? Update local payload ?= ?? ? 1 {?? ?? } on update: ?? 21
State-based replication Local at source ?1.u(a), ?2.u(b), Precondition, compute Causal History: ?= ?? ? 1 on query: ?? Update local payload ?= ?? ? 1 {?? ?? } on update: ?? 22
State-based replication Local at source ?1.u(a), ?2.u(b), Precondition, compute Causal History: ?= ?? ? 1 on query: ?? Update local payload ?= ?? ? 1 {?? ?? } on update: ?? Convergence ?= ?? ? 1 ?? ? on merge: ?? Episodically: send ?? payload On delivery: merge payloads 23
State-based replication Local at source ?1.u(a), ?2.u(b), Precondition, compute Causal History: ?= ?? ? 1 on query: ?? Update local payload ?= ?? ? 1 {?? ?? } on update: ?? Convergence ?= ?? ? 1 ?? ? on merge: ?? Episodically: send ?? payload On delivery: merge payloads 24
State-based replication Local at source ?1.u(a), ?2.u(b), Precondition, compute Causal History: ?= ?? ? 1 on query: ?? Update local payload ?= ?? ? 1 {?? ?? } on update: ?? Convergence ?= ?? ? 1 ?? ? on merge: ?? Episodically: send ?? payload On delivery: merge payloads 25
State-based replication Desired property: After receiving all updates (irrespective of order), each replica will have same state 26
Example: Union Set u: add new element to local replica q: return entire set merge: union between remote set and local replica {5} {5} U {3} = {3, 5} {3, 5} U {5, 7} = {3, 5, 7} {5} {5} {5} U {3, 5} = {3, 5} {5} {3, 5} U {5, 7} = {3, 5, 7} {5} {5} {5} U {7} = {5, 7} {5, 7} U {3, 5} = {3, 5, 7}
Example Partial order on sets : U (set union) Then, we have: commutative: A U B = B U A idempotent: A U A = A associative: (A U B) U C = A U (B U C)
Example Partial order on set of integers : max( ) Then, we have: commutative: max(x, y) = max(y, x) idempotent: max(x, x) = x associative: max(max(x, y), z) = max(x, max(y, z))
Semi-lattice Partial order set S with a least upper bound (LUB), denoted m = x y is a LUB of { x, y } under iff m , x m y m x m y m m m It follows that is: commutative: x y = y x idempotent: x x = x associative: ( x y) z = x ( y z)
Monotonic Semi-lattice Object A state-based object with partial order and the following properties, is a monotonic semi-lattice: 1. Set S of values forms a semi-lattice ordered by 2. Merging state s with remote state s computes the LUB of the two states, i.e., s m (s ) = s s 3. State is monotonically non-decreasing across updates, i.e., s s u
Convergent Replicated Data Type (CvRDT) Theorem: Assuming eventual delivery and termination, any state-based object that satisfies the monotonic semi-lattice property is SEC Why? Don t care about order: Merge is both commutative and associative Don t care about delivering more than once Merge is idempotent
Commutative Replicated Data Type (CmRDT) Update-based CRDTs: Sends update operations, not state like CvRDT Operations are commutative, but not idempotent System must ensure all ops are delivered to other replicas, without duplication, but in any order Often used in more complex settings for concurrent editing 35
Industry Use of CRDTs: Databases: Redis, Riak, Facebook Apollo League of Legends Chat Soundcloud user stream TomTom device sync Other: 36
New Module on Monday: Replicated State Machines 37
