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

RICON West 2012: Bringing Consistency to Riak (...

Sponsored · SiteGround - Reliable hosting with speed, security, and support you can count on. →
Avatar for Joseph Blomstedt Joseph Blomstedt
October 30, 2013
Programming
790
3

RICON West 2012: Bringing Consistency to Riak (Part 2)

Avatar for Joseph Blomstedt

Joseph Blomstedt

October 30, 2013

More Decks by Joseph Blomstedt

See All by Joseph Blomstedt
Data Structure Adventures for Fun, Profit, and Performance
Avatar for Joseph Blomstedt jtuple
2
370
Riak -- Seattle Scalability
Avatar for Joseph Blomstedt jtuple
2
480
Hansei: Property-based Development of Concurrent Systems
Avatar for Joseph Blomstedt jtuple
3
2.2k
Riak 1.2 Webinar Preview
Avatar for Joseph Blomstedt jtuple
1
290
Test First Construction of Distributed Systems
Avatar for Joseph Blomstedt jtuple
3
1.1k

Other Decks in Programming

See All in Programming
レガシーPHP転生 〜父がドメインエキスパートだったのでDDD+Claude Codeでチート開発します〜
Avatar for panda_program panda_program
0
270
AIと共にエンジニアとPMの “二刀流”を実現する
Avatar for Naruo Yoshiki naruogram
0
130
存在論的プログラミング： 時間と存在を記述する
Avatar for Akihito Koriyama koriym
5
770
PHPで TLSのプロトコルを実装してみるをもう一度しゃべりたい
Avatar for higaki higaki_program
0
170
Feature Toggle は捨てやすく使おう
Avatar for gennei gennei
0
420
Go_College_最終発表資料__外部公開用_.pdf
Avatar for xe-pc23 xe_pc23
0
120
AI時代のシステム設計：ドメインモデルで変更しやすさを守る設計戦略
Avatar for 増田 亨 masuda220
PRO
7
1.2k
Kubernetesでセルフホストが簡単なNewSQLを求めて / Seeking a NewSQL Database That's Simple to Self-Host on Kubernetes
Avatar for nnaka2992 nnaka2992
0
200
Symfony + NelmioApiDocBundle を使った スキーマ駆動開発 / Schema Driven Development with NelmioApiDocBundle
Avatar for Shohei Okada okashoi
0
260
我々はなぜ「層」を分けるのか〜「関心の分離」と「抽象化」で手に入れる変更に強いシンプルな設計〜 #phperkaigi / PHPerKaigi 2026
Avatar for shogogg shogogg
2
800
Linux Kernelの1文字のミスで 権限昇格ができた話
Avatar for rona rqda
0
2.3k
Codex CLIのSubagentsによる並列API実装 / Parallel API Implementation with Codex CLI Subagents
Avatar for 冨澤宝斗 takatty
2
840

Featured

See All Featured
JavaScript: Past, Present, and Future - NDC Porto 2020
Avatar for David Neal reverentgeek
52
5.9k
Unlocking the hidden potential of vector embeddings in international SEO
Avatar for Frank van Dijk frankvandijk
0
750
How to Build an AI Search Optimization Roadmap - Criteria and Steps to Take #SEOIRL
Avatar for Aleyda Solis aleyda
1
2k
Keith and Marios Guide to Fast Websites
Avatar for Keith Pitt keithpitt
413
23k
技術選定の審美眼（2025年版） / Understanding the Spiral of Technologies 2025 edition
Avatar for Takuto Wada twada
PRO
118
110k
Done Done
Avatar for chrislema chrislema
186
16k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
Avatar for Eileen M. Uchitelle eileencodes
27
3.4k
Heart Work Chapter 1 - Part 1
Avatar for Lake Fama lfama
PRO
5
35k
How STYLIGHT went responsive
Avatar for nonsquared nonsquared
100
6k
Building an army of robots
Avatar for Kyle Neath kneath
306
46k
Bootstrapping a Software Product
Avatar for Garrett Dimon garrettdimon
PRO
307
120k
Java REST API Framework Comparison - PWX 2021
Avatar for Matt Raible mraible
34
9.2k

Transcript

  1. Joseph Blomstedt (@jtuple) Basho Technologies Bringing Consistency To Riak (Part

    2) Tuesday, October 29, 13

  2. CAP Theorem 2 Tuesday, October 29, 13

  3. 3 Partition-tolerance Consistency Availability Tuesday, October 29, 13

  4. 4 Partition-tolerance Consistency Availability Tuesday, October 29, 13

  5. 5 Partition-tolerance Consistency Availability CP AP Tuesday, October 29, 13

  6. 6 Partition-tolerance Consistency Availability CP AP Tuesday, October 29, 13

  7. 7 Partition-tolerance Consistency Availability CP AP Tuesday, October 29, 13

  8. 8 C/P Strict Quorum A/P Sloppy Quorum A/P Tuesday, October

    29, 13

  9. 9 C/P Strict Quorum A/P Sloppy Quorum A/P Tuesday, October

    29, 13

  10. 10 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  11. 11 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  12. 12 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  13. 13 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  14. 14 C/P Strict Quorum A/P Sloppy Quorum A/P Tuesday, October

    29, 13

  15. 15 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  16. 16 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  17. 17 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  18. 18 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  19. 19 C/P Strict Quorum A/P Sloppy Quorum A/P Tuesday, October

    29, 13

  20. 20 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  21. 21 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  22. 22 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  23. 23 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client Tuesday, October 29, 13

  24. 24 Node 1 Node 2 Node 3 Node 4 Node

    5 client client client client client Tuesday, October 29, 13

  25. Eventual Consistency 25 Tuesday, October 29, 13

  26. 26 A A A Tuesday, October 29, 13

  27. 27 A A A Tuesday, October 29, 13

  28. 28 A A A B Tuesday, October 29, 13

  29. 29 A A A B Tuesday, October 29, 13

  30. 30 A A A B B B B Tuesday, October

    29, 13

  31. 31 A A A Tuesday, October 29, 13

  32. 32 A A A B C Tuesday, October 29, 13

  33. 33 A A A B C Tuesday, October 29, 13

  34. 34 A A A B {B,C} {B,C} {B,C} C Tuesday,

    October 29, 13

  35. 35 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  36. 36 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  37. 37 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  38. 38 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  39. 39 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  40. 40 Write Once Immutable Last Write Wins Business Rules CRDTs/Monotonicity

    Tuesday, October 29, 13

  41. Strong Consistency 41 Tuesday, October 29, 13

  42. Strong Consistency 42 Why? Tuesday, October 29, 13

  43. Strong Consistency 43 Recency Tuesday, October 29, 13

  44. Strong Consistency 44 Recency Partial Writes Tuesday, October 29, 13

  45. Strong Consistency 45 Recency Partial Writes Atomicity Tuesday, October 29,

    13

  46. 46 Recency Partial Writes Atomicity Tuesday, October 29, 13

  47. 47 Recency Partial Writes Atomicity Tuesday, October 29, 13

  48. 48 Eventual consistency is great Tuesday, October 29, 13

  49. 49 But, when is eventual? Tuesday, October 29, 13

  50. 50 Do I have the most recent value? Tuesday, October

    29, 13

  51. 51 CRDTs don’t help Tuesday, October 29, 13

  52. 52 (a,1) (a,1) (a,1) =1 Tuesday, October 29, 13

  53. 53 (a,1) (a,1) (a,1) Tuesday, October 29, 13

  54. 54 (a,1) +1 +3 (a,1) (a,1) (a,2) (a,1),(b,3) =2 =4

    Tuesday, October 29, 13

  55. 55 (a,1) +1 +3 (a,1) (a,1) (a,2) (a,1),(b,3) Tuesday, October

    29, 13

  56. 56 (a,1) +1 +3 (a,1) (a,1) (a,2) (a,1),(b,3) (a,2),(b,3) (a,2),(b,3)

    (a,2),(b,3) Tuesday, October 29, 13

  57. 57 (a,1) +1 +3 (a,1) (a,1) (a,2) (a,1),(b,3) (a,2),(b,3) (a,2),(b,3)

    (a,2),(b,3) =5 Tuesday, October 29, 13

  58. 58 (a,1) +1 +3 (a,1) (a,1) (a,2) (a,1),(b,3) =2 =4

    Tuesday, October 29, 13

  59. 59 Recency Partial Writes Atomicity Tuesday, October 29, 13

  60. 60 A write B (fail) A A B A A

    Tuesday, October 29, 13

  61. 61 B A A Tuesday, October 29, 13

  62. 62 B A A read A read A read A

    Tuesday, October 29, 13

  63. 63 B A A read A read A read A

    Tuesday, October 29, 13

  64. 64 B A A read A read A read A

    read B Tuesday, October 29, 13

  65. 65 Recency Partial Writes Atomicity Tuesday, October 29, 13

  66. Strong Consistency 66 Tuesday, October 29, 13

  67. Strong Consistency 67 What does mean for Riak 2.0? Tuesday,

    October 29, 13

  68. 68 Conditional single key atomic operations Tuesday, October 29, 13

  69. 69 No siblings Tuesday, October 29, 13

  70. 70 get sees most recent put Tuesday, October 29, 13

  71. 71 get/modify/put fails if object changed Tuesday, October 29, 13

  72. 72 get/modify/put fails if object changed (eg. concurrent put) Tuesday,

    October 29, 13

  73. 73 puts w/o vclock fails if object exists Tuesday, October

    29, 13

  74. 74 partial writes resolved on read Tuesday, October 29, 13

  75. 75 Consensus Tuesday, October 29, 13

  76. 76 Paxos Tuesday, October 29, 13

  77. 77   1RGH    1RGH  

     1RGH    1  SUHSDUH 1   SURPLVH 1 9 %  SURPLVH 1 9 &  9 1 I 9 $  9 %  9 &  FRPPLW 1 9 1    DFFHSW 1  Tuesday, October 29, 13

  78. 78 Rinse/repeat for each request Tuesday, October 29, 13

  79. 79 2 round trips/request Tuesday, October 29, 13

  80. 80 Multi-Paxos Tuesday, October 29, 13

  81. 81 First Request Tuesday, October 29, 13

  82. 82   1RGH    1RGH  

     1RGH    1 ,   SUHSDUH 1 ,   SURPLVH 1 , 9 %  SURPLVH 1 , 9 &  9 1 I 9 $  9 %  9 &  FRPPLW 1 , 9 1    DFFHSW 1 ,  Tuesday, October 29, 13

  83. 83 Each Additional Request Tuesday, October 29, 13

  84. 84   1RGH    1RGH  

     1RGH    ,  FRPPLW 1 , 9    DFFHSW 1 ,  Tuesday, October 29, 13

  85. 85 1 round trip/request (common case) Tuesday, October 29, 13

  86. 86 Problem Shipping entire state each request is expensive Tuesday,

    October 29, 13

  87. 87 Solution Paxos + Replicated Log Tuesday, October 29, 13

  88. 88 Problem Now I have N problems Tuesday, October 29,

    13

  89. 89 Log recovery Log trimming Rollup Snapshots Fault Recovery Tuesday,

    October 29, 13

  90. 90 Choose your own adventure... Tuesday, October 29, 13

  91. 91 Better Solution Build log replication into protocol Tuesday, October

    29, 13

  92. 92 Better Solution ZK Atomic Broadcast Raft Tuesday, October 29,

    13

  93. Zab 93 Tuesday, October 29, 13

  94. 94 Tuesday, October 29, 13

  95. 95 Tuesday, October 29, 13

  96. 96 Tuesday, October 29, 13

  97. 97 Tuesday, October 29, 13

  98. Raft 98 Tuesday, October 29, 13

  99. 99 Tuesday, October 29, 13

  100. 100 raftconsensus.github.io Tuesday, October 29, 13

  101. 101 Text Tuesday, October 29, 13

  102. Back to Riak 102 Tuesday, October 29, 13

  103. 103 Key/Value Keys are independent Active Anti-Entropy Tunable backends Tuesday,

    October 29, 13

  104. 104 Each key is independent state Tuesday, October 29, 13

  105. 105 Simple multi-paxos per key Tuesday, October 29, 13

  106. 106 1B keys = 1B consensus groups? Tuesday, October 29,

    13

  107. 107 No Tuesday, October 29, 13

  108. 108 Consensus group per preflist (replica set) Tuesday, October 29,

    13

  109. 109 Emulate paxos per key Tuesday, October 29, 13

  110. Node 0 Node 1 Node 2 Tuesday, October 29, 13

  111. 111 1 2 3 4 5 6 7 123 Tuesday,

    October 29, 13

  112. 112 1 2 3 4 5 6 7 123 234

    Tuesday, October 29, 13

  113. 113 1 2 3 4 5 6 7 123 234

    345 Tuesday, October 29, 13

  114. 114 1 2 3 4 5 6 7 123 234

    345 456 Tuesday, October 29, 13

  115. 115 1 2 3 4 5 6 7 123 234

    345 456 567 ... Tuesday, October 29, 13

  116. 116 1 2 3 4 5 6 7 123 234

    345 456 567 Ensembles ... Tuesday, October 29, 13

  117. 117 64 partition ring = 64 ensembles Tuesday, October 29,

    13

  118. 118 Each Ensemble Elects leader Establishes epoch Supports get/put ops

    Tuesday, October 29, 13

  119. 119 Establish a new epoch Tuesday, October 29, 13

  120. 120   1RGH    1RGH  

     1RGH    1 ,   SUHSDUH 1 ,   SURPLVH 1 , 9 %  SURPLVH 1 , 9 &  9 1 I 9 $  9 %  9 &  FRPPLW 1 , 9 1    DFFHSW 1 ,  Tuesday, October 29, 13

  121. 121 consensus state epoch sequence membership leader Tuesday, October 29,

    13

  122. 122 K/V objects epoch sequence key value Tuesday, October 29,

    13

  123. 123 GET leader reads local object if obj.epoch old: refresh

    reply w/ val Tuesday, October 29, 13

  124. 124   1RGH    1RGH  

     1RGH    REMHSRFK  HSRFK  JHW .H\   UHSO\ (SRFK %  6HT %  9DO %  UHSO\ (SRFK &  6HT &  9DO &  9DO ODWHVW 9DO $  9DO %  9DO & 9DOHSRFK HSRFK  ZULWH (SRFK 6HT 9DO    DFN (SRFK 6HT  Tuesday, October 29, 13

  125. 125   1RGH    1RGH  

     1RGH    REMHSRFK HSRFK  5HSO\ ORFDOBJHW .H\  Tuesday, October 29, 13

  126. 126 2 roundtrips/get (worst) 0 roundtrip/get (best) Tuesday, October 29,

    13

  127. 127 PUT leader reads local object if obj.epoch old: refresh

    if modify(obj) false: fail commit modified obj reply ok Tuesday, October 29, 13

  128. 128   1RGH    1RGH  

     1RGH    REMHSRFK  HSRFK  JHW .H\   UHSO\ (SRFK %  6HT %  9DO %  UHSO\ (SRFK &  6HT &  9DO &  /DWHVW ODWHVW 9DO $  9DO %  9DO & 9DO PRGLI\ /DWHVW  ZULWH (SRFK 6HT 9DO    DFN (SRFK 6HT  Tuesday, October 29, 13

  129. 129   1RGH    1RGH  

     1RGH    REMHSRFK HSRFK  /DWHVW ORFDOBJHW .H\ 9DO PRGLI\ /DWHVW  ZULWH (SRFK 6HT 9DO    DFN (SRFK 6HT  Tuesday, October 29, 13

  130. 130 2 roundtrips/put (worst) 1 roundtrip/put (best) Tuesday, October 29,

    13

  131. 131 Leader abandons leadership if any quorum operation ever fails

    Tuesday, October 29, 13

  132. 132 Which forces new epoch to be established Tuesday, October

    29, 13

  133. 133 Partial Writes Tuesday, October 29, 13

  134. failed partial write X (2) X (2) X (2) X

    (2) X (2) Y (2) epoch 2 epoch 3 Tuesday, October 29, 13

  135. read / rewrite / reply X X (2) X (2)

    Y (2) X (3) X (3) Y (2) epoch 3 epoch 3 Tuesday, October 29, 13

  136. X (3) X (3) Y (2) X (3) X (3)

    X (3) read / repair / reply X epoch 3 epoch 3 Tuesday, October 29, 13

  137. Usage 137 Tuesday, October 29, 13

  138. 138 AP or CP per bucket type Tuesday, October 29,

    13

  139. 139 consistent = true Tuesday, October 29, 13

  140. 140 $ riak-admin bucket-type create strong \ '{"props": {"consistent": true}}'

    strong created Tuesday, October 29, 13

  141. 141 $ riak-admin bucket-type activate strong strong has been activated

    Tuesday, October 29, 13

  142. 142 > riakc_pb_socket:get(Socket, {<<"strong">>, <<"bucket">>}, <<"key">>). {error,notfound} Tuesday, October 29,

    13

  143. 143 > Obj = riakc_obj:new({<<"strong">>, <<"bucket">>}, <<"key">>, <<"1">>)). > riakc_pb_socket:put(Socket,

    Obj). ok Tuesday, October 29, 13

  144. 144 > Obj2 = riakc_obj:new({<<"strong">>, <<"bucket">>}, <<"key">>, <<"2">>)). > riakc_pb_socket:put(Socket,

    Obj2). {error, failed} Tuesday, October 29, 13

  145. 145 {ok, Obj3} = riakc_pb_socket:get(Socket, {<<"strong">>, <<"bucket">>}, <<"key">>). Tuesday, October

    29, 13

  146. 146 Obj4 = riakc_obj:update_value(Obj3, <<"2">>). Tuesday, October 29, 13

  147. 147 Obj5 = riakc_obj:update_value(Obj3, <<"22">>). Tuesday, October 29, 13

  148. 148 > riakc_pb_socket:put(Socket, Obj4). ok Tuesday, October 29, 13

  149. 149 > riakc_pb_socket:put(Socket, Obj5). {error,<<"failed">>} Tuesday, October 29, 13

  150. 150 Your client may vary Tuesday, October 29, 13

  151. 151 Your client may vary We’re working on it Tuesday,

    October 29, 13

  152. Tech Preview 152 Tuesday, October 29, 13

  153. 153 No AAE syncing No 2i No stats Tuesday, October

    29, 13

  154. 154 Will be in 2.0 final Tuesday, October 29, 13

  155. Coming Soon 155 Tuesday, October 29, 13

  156. 156 Datatypes Multi-DC Lightweight Tx? Perf benchmarks Tuesday, October 29,

    13

  157. 157 Datatypes Multi-DC Lightweight Tx? Perf benchmarks Tuesday, October 29,

    13

  158. 158 Datatypes Multi-DC Lightweight Tx? Perf benchmarks Tuesday, October 29,

    13

  159. 159 Datatypes Multi-DC Lightweight Tx? Perf benchmarks Tuesday, October 29,

    13

  160. 160 Datatypes Multi-DC Lightweight Tx? Perf benchmarks Tuesday, October 29,

    13

  161. Questions? 161 Tuesday, October 29, 13