Share
Embed
The Final Causal Frontier
Cyberspace… the final causal frontier. These are the voyages of the software enterprise. Its continuing mission: to explore strange new datacenters…to seek out new sites and new applications…to boldly code where no coder has gone before!
Sean Cribbs
April 23, 2015
Transcript
102 slides
-
T H E F I N A L C A
U S A L F R O N T I E R S E A N C R I B B S C R A F T C O N F E R E N C E , 2 3 A P R I L 2 0 1 5 -
M O B I L E O F F L
I N E W E B G L O B A L P O P S I N T E R N E T O F T H I N G S -
M O B I L E O F F L
I N E W E B G L O B A L P O P S I N T E R N E T O F T H I N G S C L I E N T S E R V E R -
C R D T S A R E A S
O L U T I O N -
M O N O T O N I C I
T Y A N D L AT T I C E S C O R E C O N C E P T S : -
B O U N D E D J O I
N S E M I - L AT T I C E S -
B O U N D E D J O I
N S E M I - L AT T I C E S A ⊔ B ⊥ -
B O U N D E D J O I
N S E M I - L AT T I C E S A ⊔ B ⊥ mappend mempty -
B O U N D E D J O I
N S E M I - L AT T I C E S A ⊔ B ⊥ A ⊔ B = C 㱺 A⊑C and B⊑C mappend mempty -
V E R S I O N V E C
T O R S A N D D O T S C O R E C O N C E P T S : -
D E T E C T I O N O
F M U T U A L I N C O N S I S T E N C Y I N D I S T R I B U T E D S Y S T E M S D . S T O T T PA R K E R J R , E T A L , 1 9 8 3 -
V E R S I O N V E C
T O R S A B C -
V E R S I O N V E C
T O R S A B C -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] A B C B : 1 C : 1 [ A:0, B:1, C:1 ] -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] A B C B : 1 C : 1 [ A:0, B:1, C:1 ] Dominates -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] B A C A : 1 B : 1 C : 1 C : 2 [ A:1, B:1, C:2 ] Dominates -
V E R S I O N V E C
T O R S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] B A C A : 1 B : 1 C : 1 C : 2 [ A:1, B:1, C:2 ] Dominates Concurrent -
V E R S I O N V E C
T O R S & D O T S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] -
V E R S I O N V E C
T O R S & D O T S A B C A : 1 A : 2 B : 1 C : 1 [ A:2, B:1, C:1 ] C : 2 DOT -
[ A:2, B:1, C:2 ] V E R S I
O N V E C T O R S & D O T S A B C C A : 1 A : 2 B : 1 C : 1 C : 2 DOT -
C O N F L I C T- F R
E E R E P L I C AT E D D ATAT Y P E S C O R E C O N C E P T S : -
C O N V E R G E N T
S TAT E / C O M M U TAT I V E O P E R AT I O N S -
S T R O N G E V E N
T U A L C O N S I S T E N C Y -
T H E S TAT E O F T H
E A R T C A T C H I N G U P W I T H -
L AY E R E D A R C H
I T E C T U R E D I A G R A M K E R N E L A P P L I C AT I O N S U S E R S PA C E -
L AY E R E D A R C H
I T E C T U R E D I A G R A M K E R N E L A P P L I C AT I O N S U S E R S PA C E M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S D Y N A M O -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S D Y N A M O M V / LW W -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S D Y N A M O M V / LW W A D H O C / A P P E N D O N LY -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T M A P -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T M A P S W I F T C L O U D -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T M A P S W I F T C L O U D Δ - C R D T S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T M A P S W I F T C L O U D Δ - C R D T S I N V C R D T S -
L AY E R E D A R C H
I T E C T U R E D I A G R A M M I D D L E WA R E A P P L I C AT I O N S D ATAT Y P E S T R C B D V V S E T S O R S W O T M A P S W I F T C L O U D L A S P Δ - C R D T S I N V C R D T S -
N E W D ATAT Y P E S S
E T S , R E G I S T E R S , M A P S , D E LTA S , I N VA R I A N T S -
O P T I M I Z E D O
R - S E T B I E N I U S A , E T A L . O B S E R V E D - R E M O V E S E T W I T H O U T T O M B S T O N E S -
O R - S E T G R O W
S Q U I C K LY -
O R - S E T G R O W
S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] -
O R - S E T G R O W
S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] [] -
O R - S E T G R O W
S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] [] [(1, {a}, {})] A D D 1 -
O R - S E T G R O W
S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] [] [(1, {a}, {})] A D D 1 [(1, {a}, {}), (2, {b}, {})] A D D 2 -
O R - S E T G R O W
S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] [] [(1, {a}, {})] A D D 1 [(1, {a}, {}), (2, {b}, {})] A D D 2 [(1, {a}, {a}), (2, {b}, {})] R E M O V E 1 -
O P T I M I Z E D O
R - S E T ( O R S W O T ) -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones VV ⊠ [ (i, Ai ), (j, Aj ), …] -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated VV ⊠ [ (i, Ai ), (j, Aj ), …] -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated • General technique! VV ⊠ [ (i, Ai ), (j, Aj ), …] -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated • General technique! VV ⊠ [ (i, Ai ), (j, Aj ), …] [] ⊠ [] -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated • General technique! VV ⊠ [ (i, Ai ), (j, Aj ), …] [] ⊠ [] [a:1] ⊠ [(1, {a:1})] A D D 1 -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated • General technique! VV ⊠ [ (i, Ai ), (j, Aj ), …] [] ⊠ [] [a:1] ⊠ [(1, {a:1})] A D D 1 [a:1,b:1] ⊠ [(1, {a:1}), (2, {b:1})] A D D 2 -
O P T I M I Z E D O
R - S E T ( O R S W O T ) • Version vector plus latest dot replaces unique ids and tombstones • Merge is more complicated • General technique! VV ⊠ [ (i, Ai ), (j, Aj ), …] [] ⊠ [] [a:1] ⊠ [(1, {a:1})] A D D 1 [a:1,b:1] ⊠ [(1, {a:1}), (2, {b:1})] A D D 2 [a:1,b:2] ⊠ [(2, {b:1})] R E M O V E 1 -
D O T T E D V E R S
I O N V E C T O R S E T S A L M E I D A , E T A L . S C A L A B L E A N D A C C U R A T E C A U S A L I T Y T R A C K I N G F O R E V E N T U A L LY C O N S I S T E N T S T O R E S -
P R O B L E M S W I
T H R E G I S T E R S • Last-Write-Wins : loses data • Causal history MV : write-identifier explosion • Client-identified MV : actor explosion • Server-identified MV : sibling explosion -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ -
a : 3 / C a r r i e
D O T T E D V E R S I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d a : 2 / B o b [ a : 4 , b : 5 ] -
a : 3 / C a r r i e
[ a : 3 , b : 2 ] D O T T E D V E R S I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d a : 2 / B o b [ a : 4 , b : 5 ] E u g e n e -
[ a : 3 , b : 2 ] D
O T T E D V E R S I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 4 , b : 5 ] E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 2 / B o b a : 3 / C a r r i e [ a : 4 , b : 1 ] b : 1 / A l i c e a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 2 / B o b a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 2 / B o b a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 2 / B o b a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 2 / B o b a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e -
D O T T E D V E R S
I O N V E C T O R S E T S • Version vector with dots on values • Writes remove “seen” dots • Similar optimization and merge to the ORSWOT • Default KV behavior in Riak 2.0+ a : 4 / D a v i d [ a : 5 , b : 5 ] [ a : 3 , b : 2 ] b : 2 / F re d a : 3 / C a r r i e [ a : 4 , b : 1 ] a : 3 / C a r r i e a : 4 / D a v i d a : 5 / E u g e n e [ a : 4 , b : 2 ] -
R I A K 2 . 0 M A P
B R O W N E T A L . R I A K D T M A P : A C O N V E R G E N T, C O M P O S A B L E R E P L I C A T E D D I C T I O N A RY -
R I A K ’ S M A P •
Recursive dictionary for other state-based CRDTs: counters, sets, registers, flags, maps • Reset-remove semantic on concurrent update/remove • Atomic batch updates to multiple contained types • Similar optimizations/merge to ORSWOT: top-level version vector, per-field dots -
D E LTA S TAT E - B A S
E D C R D T S A L M E I D A , S H O K E R , B A Q U E R O . E F F I C I E N T S TA T E - B A S E D C R D T S B Y D E C O M P O S I T I O N -
D E LTA S TAT E - B A S
E D C R D T S • Combines best of operation- and state-based CRDTS: Small payloads over unreliable channels • Delta-mutator produces minimal state representing change • Deltas can be collected into batches -
B O U N D E D C O U
N T E R S B A L E G A S , E T A L . E N F O R C I N G N U M E R I C I N VA R I A N T S O N E V E N T U A L C O N S I S T E N T C L O U D S T O R E S -
B O U N D E D C O U
N T E R S • “Comprehensive” mentions NN-counters may require coordination • Local decrements never exceed local increments • Rights can be transferred to peers (escrow) • Transfer can be coordinated lazily - it’s still a lattice! -
B O U N D E D C O U
N T E R S • “Comprehensive” mentions NN-counters may require coordination • Local decrements never exceed local increments • Rights can be transferred to peers (escrow) • Transfer can be coordinated lazily - it’s still a lattice! A B C {10,0} — 0 0 {5,4} 0 — 0 {30,10} 0 0 — -
B O U N D E D C O U
N T E R S • “Comprehensive” mentions NN-counters may require coordination • Local decrements never exceed local increments • Rights can be transferred to peers (escrow) • Transfer can be coordinated lazily - it’s still a lattice! A B C {10,0} — 0 0 {5,4} 0 — 0 {30,10} 0 0 — A B C {10,0} — 5 0 {5,8} 0 — 0 {30,10} 0 0 — B : D E C R E M E N T 4 -
M I D D L E WA R E P
U R E O P - B A S E D , TA G G E D R E L I A B L E C A U S A L B R O A D C A S T -
P U R E O P - B A S
E D C R D T S , TA G G E D R E L I A B L E C A U S A L B R O A D C A S T M A K I N G O P E R A T I O N - B A S E D C R D T S O P E R A T I O N - B A S E D . B A Q U E R O , A L M E I D A , S H O K E R -
P U R E O P - B A S
E D C R D T S • Current operation-based CRDTs conflate delivery concerns with type semantics • Focus on minimal pure state and direct operations e.g. integer counter with direct add/subtract • Op-log moved to middleware layer to ensure reliable delivery -
TA G G E D R E L I A
B L E C A U S A L B R O A D C A S T • Uses vector clock per message • Causal stability - all future messages will have dominant clocks • Partially-ordered log of unapplied operations • Semantic compaction of PO-log -
A P P L I C AT I O N
S S W I F T C L O U D , L A S P -
S W I F T C L O U D
Z A W I R S K I , E T A L . S W I F T C L O U D : FA U LT- T O L E R A N T G E O - R E P L I C A T I O N I N T E G R A T E D A L L T H E WA Y T O T H E C L I E N T M A C H I N E -
S W I F T C L O U D
• Introduces causal+ consistency causal snapshot isolation, mergeable transactions • Clients can execute completely offline and synchronize later • Rich Java API with many included CRDTs -
L A S P : L AT T I C
E P R O C E S S I N G M E I K L E J O H N & VA N R O Y. L A S P : A L A N G U A G E F O R D I S T R I B U T E D , C O O R D I N A T I O N - F R E E P R O G R A M M I N G -
L A S P : L AT T I C
E P R O C E S S I N G • Based on deterministic dataflow programming • Functional: map, filter, fold • Set: product, union, intersection • Safety: monotonic read -
T H E F I N A L C A
U S A L F R O N T I E R W H A T ’ S N E X T O N -
T H E F I N A L C A
U S A L F R O N T I E R • Applications at the edge • Increased robustness • Reduced metadata and communication • Larger applications -
A C K N O W L E D G
M E N T S • Basho: Russell Brown, Christopher Meiklejohn • SyncFree FP7: Marc Shapiro, Nuno Preguiça, Carlos Baquero, Annette Bieniusa, João Leitão, Peter Van Roy, Valter Balegas • NASA Astronomy Picture of the Day (APOD)