/
leveled.html
200 lines (178 loc) · 8.21 KB
/
leveled.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
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Leveled</title>
<meta name="description" content="An overview of the Leveled Key/Value Store">
<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>
<img width="450" height="600" data-src="images/ascot6201.jpg" alt="Bookmaker"/>
</section>
<section>
<h2>Leveled - Why?</h2>
<p align="left">Seeking a challenge</p>
<p align="left">Didn't understand how LSM-Trees really worked ....</p>
<p align="right">.... so try implementing one in Erlang</p>
</section>
<section>
<h2>Leveled - The Hypothesis</h2>
<p align="left">The store only needs to support Riak ... </p>
<p align="right">.... and with objects of a non-trivial size</p>
<p align="left">Is it simpler to trade-off GET optimisation ....</p>
<p align="right">.... for reduced write amplification?</p>
<p align="left">What if the store natively supported a HEAD operation ....</p>
<p align="right">.... and GETs could be avoided?</p>
</section>
<section>
<img width="1000" height="650" data-src="images/leveldb_intro.png" alt="LevelDB Intro"/>
</section>
<section>
<h2>Leveled - The Key Changes</h2>
<p align="left">Make the nursery log a perpetual journal of changes</p>
<p align="left">Roll only the Keys and Metadata into the merge tree</p>
<p align="left">Use the Actor Model</p>
<p align="left">All data compressed in PageCache - assisted by fadvise</p>
<p align="left">Tolerate small delays - reduce variation</p>
</section>
<section>
<img width="1000" height="650" data-src="images/leveled_intro.png" alt="Leveled Intro"/>
</section>
<section>
<h2>Leveled - The Inker and the Journal</h2>
<p align="left">The journal is a series of (DJ Bernstein) CDB files</p>
<p align="left">The Inker has a manifest of PIDs -> FSMs -> Files</p>
<p align="left">The Inker has a Clerk to help with compaction ....</p>
<p align="right">.... Failure to compact does not block</p>
<p align="right">.... Compaction is a lazy/scheduled background task</p>
</section>
<section>
<img width="1000" height="650" data-src="images/inker.png" alt="Inker"/>
</section>
<section>
<h2>Leveled - The Penciller and the In-Memory Ledger</h2>
<p align="left">Skip Lists pushed from Bookie are then immutable</p>
<p align="left">Hash-based lookup so that not all SkipLists need be checked</p>
<p align="left">When count exceeds size of a sft file - persist to L0</p>
<p align="left">Any fresh pushes returned until L0 complete</p>
<p align="left">Once L0 complete and in the manifest, flush all _imm files</p>
</section>
<section>
<img width="1000" height="650" data-src="images/penciller.png" alt="Penciller"/>
</section>
<section>
<h2>Leveled - The Penciller and Compaction</h2>
<p align="left">The Penciller has a clerk for compaction</p>
<p align="left">The Clerk polls for work - a level with too many files</p>
<p align="left">Max Files = 8 ^ Level</p>
<p align="left">Choose a file, any file, at the highest overloaded level</p>
<p align="left">Merge whole file to new files at level below - update manifest</p>
<p align="left">Make replaced files delete_pending</p>
</section>
<section>
<h2>Leveled - The Penciller Files</h2>
<p align="left">Files are FSMs - like Journal</p>
<p align="left">Manifest maps levels/key-ranges to files</p>
<p align="left">Files are sst like</p>
<p align="left">Data is grouped in slots of 128 Keys</p>
<p align="left">Slots contain 4 blocks of 32 keys (t_to_b compressed)</p>
<p align="left">Bloom is single-hash gcs with in-built crc-style check</p>
<p align="left">Single hash of bloom is also segment ID</p>
</section>
<section>
<h2>Leveled - Clones</h2>
<p align="left">Penciller and Inker can be cloned</p>
<p align="left">Clone needs a copy of memory, and the manifest</p>
<p align="left">Clones are registered for files entering delete_pending</p>
<p align="left">All folds via snapshot clones</p>
</section>
<section data-background="#A3C2FF">
<h2>Leveled - Status</h2>
<p align="left">Functionally complete backend</p>
<p align="left">Initial integration testing into Riak (GET/PUT/2i/LIST)</p>
<p align="left">Close to 100% test coverage</p>
<p align="left">Still currently private</p>
</section>
<section data-background="#A3C2FF">
<h2>Leveled - Standalone Load Tests</h2>
<p align="left">Vanilla basho_bence for eleveldb</p>
<p align="left">Tested on a desktop, so reduced instances to 12</p>
<p align="left">Reduced value size to 8KB</p>
<p align="left">... Populate (all PUT)</p>
<p align="left">... Load (5 GET, 1 PUT)</p>
<p align="left">Sync writes enabled in both cases</p>
</section>
<section data-background="#A3C2FF">
<h3>Leveldb .... .... Leveled</h3>
<img width="400" height="600" data-src="images/leveldb_pop.png" alt="Populating LevelDB"/>
<img width="400" height="600" data-src="images/leveled_pop.png" alt="Populating Leveled"/>
</section>
<section data-background="#A3C2FF">
<h3>Leveldb .... .... Leveled</h3>
<img width="400" height="600" data-src="images/leveldb_load.png" alt="Loading LevelDB"/>
<img width="400" height="600" data-src="images/leveled_load.png" alt="Loading Leveled"/>
</section>
<section data-background="#A3C2FF">
<h2>Leveled - Next Steps</h2>
<p align="left">Comparison test with unmodified Riak</p>
<p align="left">Optimise GET & PUT FSM to use HEAD</p>
<p align="left">Comparison test with modified Riak</p>
<p align="left">Long-running tests</p>
<p align="left">Release Alpha</p>
</section>
<section data-background="#A3C2FF">
<h2>Leveled - TODO List</h2>
<p align="left">Supervision</p>
<p align="left">Property-Based Testing</p>
<p align="left">AAE as-is</p>
<p align="left">Investigate continuous AAE rebuild</p>
<p align="left">Fold HEADs</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>