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!
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 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
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
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
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 ), …]
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 ), …]
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 ), …] [] ⊠ []
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
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
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
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
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
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+
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 , 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
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
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
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
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
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
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
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
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
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 ]
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
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
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!
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 —
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
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
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
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
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
• Introduces causal+ consistency causal snapshot isolation, mergeable transactions • Clients can execute completely offline and synchronize later • Rich Java API with many included CRDTs
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
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
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)
seancribbs
lycorptech_jp
.jpg){kind=avatar}
oshanqq
loglass2019
.png){kind=icon}
pharma_x_tech
kniino
minorun365
z63d
rvirus0817
wisemuji
qt_luigi
syoshie
ysknsid25
shlominoach
akosma
lynnandtonic
tammyeverts
csswizardry
speakerdeck
morganepeng
jmmastey
aleyda
kevinliebholz
keavy
dougneiner
![[ A:2, B:1, C:2 ] V E R S I](https://files.speakerdeck.com/presentations/cd7c277e22214534aa8937e40655fcae/slide_28.jpg){kind=link}
![[ a : 3 , b : 2 ] D](https://files.speakerdeck.com/presentations/cd7c277e22214534aa8937e40655fcae/slide_69.jpg){kind=link}
