00. Introduction

0.1 Master fundamentals by building your own X

Three ideas of databases

Even complex systems such as a database are based on a small number of simple ideas. You can master them by coding a simplified toy DB.

The most important database ideas in this book are:

1. Durability (fsync). How not to lose or corrupt your data after a crash.
2. Data structures (B-tree or LSM-tree). For efficient queries and updates.
3. Storage engines. High-level features such as SQL built on top of a KV.

You can do it from the bottom up

Databases may seem like magic if all you know is writing SQL and using indexes. On the surface, SQL alone seems quite complicated. But they can be easily understood from the bottom up (the 3 ideas).

The project is broken down into small, incremental steps. We start with a B+tree, then a simple KV, and end with a mini relational DB with concurrent transactions.

Learning from principles, not jargon

Database writing is full of jargon that has no consistent meaning. Ideas are expressed in confusing, overloaded terms. It’s hard to understand databases just by reading about them.

On the other hand, Feymann once said, “what I can’t build, I don’t understand”, so can you build a database by reading about databases? This is a simple test of your understanding.

While databases are a broad and deep topic, not all knowledge is equally important, it takes only a few principles to build a DB, so anyone can do it, which is what this book is about.

0.2 Durability

Files are not enough

Durability is the #1 reason you need databases, not just files. Let’s say you open a file and write some data to it, then the power goes out, what’s the state after rebooting?

• Does the file just lose the last write?
• Or does it end up as a half-written file?
• Or does the file even exist?

Any outcome is possible. Simply using files only works in the best case, you need extra steps to make it work more often.

`fsync` makes data durable

One of these extra steps is the fsync syscall. Writing to a file is not a synchronous process; there are multiple levels of caching (OS page cache and on-device cache). An fsync syscall requests that all written data be flushed immediately and will block until it’s done.

A database will not respond to the client until the data has been fsync’ed; it’s a confirmation of durability you can rely on.

Atomicity and durability

Atomicity means that data is either updated or not, not in between. This is not a separate concern from durability. There is a way to achieve both with files:

1. Write the whole updated dataset to a new file.
2. Call fsync on the new file.
3. Overwrite the old file by renaming the new file to the old file, which is guaranteed by the file system to be atomic.

This is only acceptable for infrequent updates to tiny data, and it has other gotchas besides being inefficient. All the more reason to use databases.

0.3 Indexing data structures

Reduce latency and cost with indexes

Two distinct types of queries: analytical (OLAP) and transactional (OLTP).

• Analytical (OLAP) queries typically involve a large amount of data, with aggregation, grouping, or join operations. Indexing can be very limited or nonexistent.
• Transactional (OLTP) queries aim to touch small amounts of data using indexes. Low latency and low cost.

The word “transactional” has nothing to do with database transactions as you may know. This book focuses only on OLTP techniques.

Most user-facing software is expected to respond in a small amount of time using a small amount of resources (memory, IO). This falls into the OLTP category. How to find the data quickly, even if the dataset is large? That’s why we need indexing data structures.

In-memory data structures vs. on-disk data structures

Finding the data quickly is a data structure problem. But database indexes can be larger than memory, and persisting data structures to disk has additional challenges (See my book “Build Your Own Redis” for a much easier in-memory DB).

Updating a data structure in-place is problematic because you have to deal with corrupted states after a crash. You cannot just treat disk as slow memory.

Another thing to note is that random access is much slower, even with SSD, so data structures like binary trees are not viable.

There are a few requirements for our indexing data structure.

1. Disk-based.
2. Safe incremental update.
3. Minimize random access.

Common data structures for indexing include B-trees and LSM-trees. We will code a copy-on-write B+tree with easy concurrent transactions.

0.4 Relational DB on top of KV

Two levels of DB interfaces

For some people, SQL is a synonym for database. But SQL is just a user interface to databases, so it is not the most important idea. What’s important is what databases can do and how they do it.

Another much simpler interface is key-value (KV). You can get, set, and delete a single key, and most importantly, list a range of keys in sorted order.

KV is simpler than SQL because it’s one level lower. Relational DBs are built on top of KV-like interfaces called storage engines.

Query languages

The final challenge is to create a SQL-like query language for your own DB. To do this, we first need to parse the language into structures and map them to database operations. This is called a parser and an interpreter.

This challenge is the easiest because both the parser and the interpreter are coded with nothing but recursion. Once you’ve seen this, you can parse almost any computer language, or create your own programming language or DSL (See my book “From Source Code To Machine Code” if you want more challenges).

0.5 Book series

This is part of the “Build Your Own X” book series, where X includes Redis, web server and compiler. Read the web version on the website.

https://build-your-own.org

( Report an Error | Ask a Question) @ build-your-own.org