-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcodebeam_sto.html
244 lines (199 loc) · 10.6 KB
/
codebeam_sto.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Tictac Trees - Code BEAM Stockholm</title>
<meta name="description" content="A walk-through of how The Big NHS Computer was replaced">
<meta name="author" content="Martin Sumner">
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/black.css" id="theme">
<!-- Code syntax highlighting -->
<link rel="stylesheet" href="lib/css/zenburn.css">
<!-- Printing and PDF exports -->
<script>
var link = document.createElement( 'link' );
link.rel = 'stylesheet';
link.type = 'text/css';
link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
document.getElementsByTagName( 'head' )[0].appendChild( link );
</script>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section data-background="#934b29">
<h2>Anti-Entropy</h2>
<img width="900" height="550" data-src="images/mhen97_hi.jpg" alt="Entropy"/>
</section>
<section data-background="#934b29">
<h3 align="left">National Health Service - England</h3>
<p align="left"> - Why do we need Riak?</p>
<p align="left"> - Why do we need anti-entropy in Riak?</p>
<p align="left"> - Why do we need better anti-entropy in Riak?</p>
<h3 align="left">Riak</h3>
<p align="left"> - Developed by Basho</p>
<p align="left"> - Bought to open source by Bet365</p>
<p align="left"> - Run by community (part funded by NHS)</p>
</section>
<section data-background="#934b29">
<h2>Spine Core</h2>
<p align="left">Backend to many applications:</p>
<p align="left"> - 2bn records/documents (10KB - 1MB)</p>
<p align="left"> - 300 different transactional messages supported</p>
<p align="left"> - 40M requests per day</p>
<p align="left">We care about</p>
<p align="left"> - Availability, Durability, and Reduced Variation</p>
</section>
<section data-background="#934b29">
<h2>2003 - First Answer</h2>
<img width="900" height="500" data-src="images/2003_SpineDB.png" alt="2003 Trucopy"/>
</section>
<section data-background="#934b29">
<h2>2008 - Thousands of Years of Effort to get ...</h2>
<img width="900" height="500" data-src="images/2008_SpineDB.png" alt="2008 Dataguard"/>
</section>
<section data-background="#934b29">
<h2>Evolution or Revolution?</h2>
<img width="500" height="500" data-src="images/database_cio.jpg" alt="Oracle - been there">
</section>
<section data-background="#E6E68A">
<h2>2014 - Riak KV</h2>
<img width="900" height="500" data-src="images/2014_SpineDB.png" alt="2008 Dataguard"/>
</section>
<section data-background="#E6E68A">
<h2>Riak KV - Benefits</h2>
<p align="left">98% reduction in hardware annuity charges</p>
<p align="left">Operational cost and fear of failover transformed</p>
<p align="left">Outcome - 99.999%, 24/7, one engineer on-call</p>
</section>
<section data-background="#E6E68A">
<h2>Riak KV - Distribution of Data</h2>
<p align="left">Dotted Version Vectors</p>
<p align="left">Hinted Handoff</p>
<p align="left">Read Repair</p>
<p align="left">Real-time replication push</p>
<p align="left">Per-vnode key-listing full-sync</p>
</section>
<section data-background="#E6E68A">
<h2>Active Anti Entropy</h2>
<img width="500" height="550" data-src="images/AAE_WebShot.png" alt="Hashtree"/>
</section>
<section data-background="#E6E68A">
<h2>Merkle Trees</h2>
<img width="900" height="500" data-src="images/hashtree.png" alt="Hashtree"/>
</section>
<section data-background="#E6E68A">
<h2>Dirty or Mismatched Segments - Need a segment-ordered store</h2>
<p align="left">vnode -> index_hashtree -> hashtree {preflist, n_val)}</p>
<p align="left">Keys hash to segments, keys & clocks to segment values</p>
<p align="left">Need to know keys/hashes by segement</p>
<p align="left"> - updates to trees are deferred (dirty segments)</p>
<p align="left"> - mismatched segments need to be converted back</p>
</section>
<section data-background="#E6E68A">
<h2>AAE Issues</h2>
<p align="left">Keystore has a memory cost</p>
<p align="left">Rebuilds have unpredictable impact</p>
<p align="left">Hashes don't support smart decisions</p>
<p align="left">Inter-cluster synchronisation requires alignment</p>
<p align="left">Inter-cluster synchronisation works only sometimes</p>
<p align="left">No flexibility - e.g. per bucket</p>
</section>
<section data-background="#A3C2FF">
<h2>Calculating a Hash Securely</h2>
<p align="left">H([{K0, DVV0}, {K1, DVV1} .... {Kn, DVVn}])</p>
<p align="left">H({K0, DVV0}) XOR H({K1, DVV1}) XOR .... H({Kn, DVVn})</p>
<img width="600" height="400" data-src="images/StackExchangeQ.png" alt="Do not xor"/>
</section>
<section data-background="#A3C2FF">
<h2>XOR benefits</h2>
<p align="left">Read before write - can make a delta change</p>
<p align="left">Can fold across a stores incrementing a tree</p>
<p align="left">Can merge trees across stores</p>
</section>
<section data-background="#A3C2FF">
<h2>LSM trees need a hash of the key already</h2>
<img width="300" height="300" data-src="images/LSM_Pic1.png" alt="LSM Bloom"/>
<img width="300" height="300" data-src="images/LSM_Pic2.png" alt="LSM Bloom"/>
</section>
<section data-background="#A3C2FF">
<h2>Segment Hash Benefits</h2>
<p align="left">Can use an ordered store - Native</p>
<p align="left">Can use ordering to make Parallel stores multi-purpose</p>
</section>
<section data-background="#A3C2FF">
<h2>KV Index Tictac Tree</h2>
<img width="900" height="500" data-src="images/2018_kv_index_tictactree.png" alt="Tictac Tree"/>
</section>
<section data-background="#A3C2FF">
<h2>New AAE Features - Riak</h2>
<p align="left">More frequent checking - and double-checking</p>
<p align="left">Validate not rebuild</p>
<p align="left">Low cost full-sync - without rebuild pause</p>
<p align="left">Intelligent repair</p>
<p align="left">Ring resizing</p>
<p align="left">Backups - e.g. compare n=3 with n=1</p>
<p align="left">Compare with other databases</p>
</section>
<section data-background="#A3C2FF">
<h2>Results</h2>
<img width="900" height="500" data-src="images/ThroughputcompareAAE.png" alt="AAE Test"/>
</section>
<section data-background="#A3C2FF">
<h2>Results</h2>
<p align="left">< 0.1% delta compares to no AAE</p>
<p align="left">> 4% improvement compared to legacy AAE</p>
<p align="left">92.5% root_compare, 7.5% root_confirm</p>
</section>
<section data-background="#A3C2FF">
<h2>Better Idea?</h2>
<img width="500" height="500" data-src="images/DottedDB.png" alt="Dotted DB"/>
</section>
<section data-background="#A3C2FF">
<h2>Related Work</h2>
<p align="left">Leveled</p>
<p align="left">Core node worker pool</p>
<p align="left">Coverage fold</p>
<p align="left">Rabl</p>
</section>
<section data-background="#A3C2FF">
<h2>Thank-You</h2>
<p>http://martinsumner.github.io/presentations/codebeam_sto#/</p>
<p>https://github.com/martinsumner/kv_index_tictactree</p>
<p>https://github.com/martinsumner/leveled</p>
<p>https://github.com/basho/riak</p>
<p>@masleeds</p>
</section>
</div>
</div>
<script src="lib/js/head.min.js"></script>
<script src="js/reveal.js"></script>
<script>
// Full list of configuration options available at:
// https://github.com/hakimel/reveal.js#configuration
Reveal.initialize({
controls: true,
progress: true,
history: true,
center: true,
transition: 'slide', // none/fade/slide/convex/concave/zoom
// Optional reveal.js plugins
dependencies: [
{ src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
{ src: 'plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/highlight/highlight.js', async: true, condition: function() { return !!document.querySelector( 'pre code' ); }, callback: function() { hljs.initHighlightingOnLoad(); } },
{ src: 'plugin/zoom-js/zoom.js', async: true },
{ src: 'plugin/notes/notes.js', async: true }
]
});
</script>
</body>
</html>