RyanRiddle.github.io/how-to-write-a-database.html at master · RyanRiddle/RyanRiddle.github.io · GitHub

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>How to Write a Database - Part 1</title>
<!-- 2018-02-07 Wed 21:54 -->
<meta  http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta  name="generator" content="Org-mode" />
<meta  name="author" content="Ryan Riddle" />
<style type="text/css">
 <!--/*--><![CDATA[/*><!--*/
  .title  { text-align: center; }
  .todo   { font-family: monospace; color: red; }
  .done   { color: green; }
  .tag    { background-color: #eee; font-family: monospace;
            padding: 2px; font-size: 80%; font-weight: normal; }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .right  { margin-left: auto; margin-right: 0px;  text-align: right; }
  .left   { margin-left: 0px;  margin-right: auto; text-align: left; }
  .center { margin-left: auto; margin-right: auto; text-align: center; }
  .underline { text-decoration: underline; }
  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  p.verse { margin-left: 3%; }
  pre {
    border: 1px solid #ccc;
    box-shadow: 3px 3px 3px #eee;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: visible;
    padding-top: 1.2em;
  }
  pre.src:before {
    display: none;
    position: absolute;
    background-color: white;
    top: -10px;
    right: 10px;
    padding: 3px;
    border: 1px solid black;
  }
  pre.src:hover:before { display: inline;}
  pre.src-sh:before    { content: 'sh'; }
  pre.src-bash:before  { content: 'sh'; }
  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  pre.src-R:before     { content: 'R'; }
  pre.src-perl:before  { content: 'Perl'; }
  pre.src-java:before  { content: 'Java'; }
  pre.src-sql:before   { content: 'SQL'; }

  table { border-collapse:collapse; }
  caption.t-above { caption-side: top; }
  caption.t-bottom { caption-side: bottom; }
  td, th { vertical-align:top;  }
  th.right  { text-align: center;  }
  th.left   { text-align: center;   }
  th.center { text-align: center; }
  td.right  { text-align: right;  }
  td.left   { text-align: left;   }
  td.center { text-align: center; }
  dt { font-weight: bold; }
  .footpara:nth-child(2) { display: inline; }
  .footpara { display: block; }
  .footdef  { margin-bottom: 1em; }
  .figure { padding: 1em; }
  .figure p { text-align: center; }
  .inlinetask {
    padding: 10px;
    border: 2px solid gray;
    margin: 10px;
    background: #ffffcc;
  }
  #org-div-home-and-up
   { text-align: right; font-size: 70%; white-space: nowrap; }
  textarea { overflow-x: auto; }
  .linenr { font-size: smaller }
  .code-highlighted { background-color: #ffff00; }
  .org-info-js_info-navigation { border-style: none; }
  #org-info-js_console-label
    { font-size: 10px; font-weight: bold; white-space: nowrap; }
  .org-info-js_search-highlight
    { background-color: #ffff00; color: #000000; font-weight: bold; }
  /*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart  The following is the entire license notice for the
JavaScript code in this tag.

Copyright (C) 2012-2013 Free Software Foundation, Inc.

The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version.  The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU GPL for more details.

As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.


@licend  The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">How to Write a Database - Part 1</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#sec-1">Introduction</a></li>
<li><a href="#sec-2">Definitions</a>
<ul>
<li><a href="#sec-2-1">Database</a></li>
<li><a href="#sec-2-2">Document Oriented</a></li>
<li><a href="#sec-2-3">Transaction</a></li>
<li><a href="#sec-2-4">ACID</a>
<ul>
<li><a href="#sec-2-4-1">Atomic</a></li>
<li><a href="#sec-2-4-2">Consistent</a></li>
<li><a href="#sec-2-4-3">Isolated</a></li>
<li><a href="#sec-2-4-4">Durable</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#sec-3">Conclusion</a></li>
</ul>
</div>
</div>

<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1">Introduction</h2>
<div class="outline-text-2" id="text-1">
<p>
In this series of blog posts we are going to write a database.  Specifically, we are going
to write a document-oriented database with ACID transactions.  Let's define those words.
</p>
</div>
</div>

<div id="outline-container-sec-2" class="outline-2">
<h2 id="sec-2">Definitions</h2>
<div class="outline-text-2" id="text-2">
</div><div id="outline-container-sec-2-1" class="outline-3">
<h3 id="sec-2-1">Database</h3>
<div class="outline-text-3" id="text-2-1">
<p>
When I write "database", I mean "database management system".  People use database
management systems to store, retrieve, update, and delete data.  In particular
people expect databases to&#x2026;
</p>

<ul class="org-ul">
<li>Store lots of data.
</li>
<li>Provide a query language for searching the data.
</li>
<li>Quickly return results.
</li>
<li>Remember the data. Even if the system crashes.
</li>
</ul>
</div>
</div>

<div id="outline-container-sec-2-2" class="outline-3">
<h3 id="sec-2-2">Document Oriented</h3>
<div class="outline-text-3" id="text-2-2">
<p>
Document-oriented databases store data as documents.  A document is a group of
key-value pairs.  Documents are similar to objects in JavaScript, hashes in Ruby, and
dicts in Python.  Each of these data structures is a group of key-value pairs.
You can lookup any value in the data structure by its key.
</p>

<p>
Related documents are stored together in a "collection".
</p>
</div>
</div>

<div id="outline-container-sec-2-3" class="outline-3">
<h3 id="sec-2-3">Transaction</h3>
<div class="outline-text-3" id="text-2-3">
<p>
A transaction is a set of work performed on the database. A set of work can include
a combination of reads, writes, updates, and deletes.
</p>
</div>
</div>

<div id="outline-container-sec-2-4" class="outline-3">
<h3 id="sec-2-4">ACID</h3>
<div class="outline-text-3" id="text-2-4">
<p>
ACID is an acronym where each letter stands for a certain property of a transaction.
</p>
<dl class="org-dl">
<dt> A </dt><dd>Atomic
</dd>
<dt> C </dt><dd>Consistent
</dd>
<dt> I </dt><dd>Isolated
</dd>
<dt> D </dt><dd>Durable
</dd>
</dl>
</div>

<div id="outline-container-sec-2-4-1" class="outline-4">
<h4 id="sec-2-4-1">Atomic</h4>
<div class="outline-text-4" id="text-2-4-1">
<p>
A transaction is atomic if it is treated as an inseparable unit.  Let's say we have
a transaction that inserts a document and then inserts another.  Suppose the computer
crashes while the transaction is running.  If the transaction is atomic, the database
will be in one of two states when we turn the computer on.  Either neither document
will have been inserted.  Or both documents will have been inserted.
</p>

<p>
Without atomicity it is possible that one document will be inserted but not the other.
</p>
</div>
</div>

<div id="outline-container-sec-2-4-2" class="outline-4">
<h4 id="sec-2-4-2">Consistent</h4>
<div class="outline-text-4" id="text-2-4-2">
<p>
If you start with a database in a valid state, apply a transaction, and the database
is still valid, that transaction is called consistent.  For this series we will say
a transaction is consistent if it does not leave any malformed documents.  As far
as I can tell consistency is more important in relational databases where you have
things like constraints.
</p>
</div>
</div>

<div id="outline-container-sec-2-4-3" class="outline-4">
<h4 id="sec-2-4-3">Isolated</h4>
<div class="outline-text-4" id="text-2-4-3">
<p>
A transaction is isolated if it does not interfere with other transactions.  Let's
say we have two transactions.  One transaction is going to read every document from
the database and the other is going to delete every document from the database.
If we run the transactions at the same time, the first transaction should read every
document despite the other transaction deleting the documents simultaneously.
</p>
</div>
</div>

<div id="outline-container-sec-2-4-4" class="outline-4">
<h4 id="sec-2-4-4">Durable</h4>
<div class="outline-text-4" id="text-2-4-4">
<p>
A transaction is durable if its affects are permanent once it has been committed.
Any changes made by a committed, durable transaction are still there if we restart
the database or if the database crashes.
</p>
</div>
</div>
</div>
</div>

<div id="outline-container-sec-3" class="outline-2">
<h2 id="sec-3">Conclusion</h2>
<div class="outline-text-2" id="text-3">
<p>
That's <i>what</i> a document-oriented database with ACID transactions is.  The rest of
the series will focus on <i>how</i> to build one.
</p>


<div class="rc-scout"></div>

<script async defer src="https://www.recurse-scout.com/loader.js?t=ab605878735c514b7bf09e2b9fa66cf9"></script>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">Author: Ryan Riddle</p>
<p class="date">Created: 2018-02-07 Wed 21:54</p>
<p class="creator"><a href="http://www.gnu.org/software/emacs/">Emacs</a> 24.5.1 (<a href="http://orgmode.org">Org</a> mode 8.2.10)</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>