Upgrade to Pro — share decks privately, control downloads, hide ads and more …

The Final Causal Frontier

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
Tweet

More Decks by Sean Cribbs

Other Decks in Technology

Transcript

  1. 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
  2. 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
  3. 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
  4. C R D T S A R E A S

    O L U T I O N
  5. 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 :
  6. B O U N D E D J O I

    N S E M I - L AT T I C E S
  7. B O U N D E D J O I

    N S E M I - L AT T I C E S A ⊔ B ⊥
  8. 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
  9. 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
  10. 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 :
  11. 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
  12. V E R S I O N V E C

    T O R S A B C
  13. V E R S I O N V E C

    T O R S A B C
  14. 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
  15. 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 ]
  16. 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 ]
  17. 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 ]
  18. 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 ]
  19. 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 ]
  20. 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 ]
  21. 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
  22. 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
  23. 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
  24. 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 ]
  25. 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
  26. [ 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
  27. 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 :
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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
  48. O R - S E T G R O W

    S Q U I C K LY
  49. O R - S E T G R O W

    S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ]
  50. O R - S E T G R O W

    S Q U I C K LY [ (i, Ai , Ri ) , (j, Aj , Rj ), … ] []
  51. 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
  52. 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
  53. 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
  54. O P T I M I Z E D O

    R - S E T ( O R S W O T )
  55. 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 ), …]
  56. 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 ), …]
  57. 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 ), …]
  58. 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 ), …] [] ⊠ []
  59. 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
  60. 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
  61. 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
  62. 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
  63. 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
  64. 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+
  65. 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 ]
  66. 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
  67. [ 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
  68. 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
  69. 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
  70. 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
  71. 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
  72. 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
  73. 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
  74. 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
  75. 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 ]
  76. 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
  77. 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
  78. 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
  79. 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
  80. 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
  81. 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!
  82. 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 —
  83. 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
  84. 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
  85. 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
  86. 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
  87. 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
  88. 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
  89. 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
  90. 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
  91. 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
  92. 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
  93. 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
  94. 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
  95. 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)