If you were to build your own database today, not knowing that databases exist already, how would you do it? In this post, we'll explore how to build a key-value database from the ground up.

A key-value database works more or less like objects in JavaScript—you can store values using a key and retrieve them later using that same key:

$ db set 'hello' 'world'
$ db get 'hello'
world

Let's find out how they work!

Mutable Updates

This approach, simple as it is, doesn't actually work very well in practice. The problem lies with the way we're doing updates and deletes—they're wholly inefficient.

To a computer, our file looks something like this—nothing more than a long sequence of bytes:

When we go to update or delete a record, we're currently updating that record in-place, which means we potentially have to move all of the data that comes after that record:

Update

In this case, updating the record 005 to "adipiscing␣elit.␣vel␣mauris" means moving all of the records that come after it by 11 bytes (the length of the added string "␣vel␣mauris"). This can quickly get really costly, especially as our database grows in size!

Now this implementation isn't perfect; right now, there are two major issues:

1. The file can get very large. Since we're only appending to the file, the file will grow infinitely over time. Not good!

2. Searching is slow. To search for a specific key, we have to potentially iterate through all records in the database. For a database with millions of records, this can take a while!

How can we fix these problems?

Segments and Compaction

Here, we've set the maximum file size to seven records. Notice that the database is full—try clicking on "Add" to add a new record and notice what happens:

Add

Now, our database consists of two different files which we'll call segments. Each segment will usually become a lot smaller after compaction, which means we can merge them together as part of the compaction process.

With that, we've made a mechanism to stop our database from growing indefinitely!

Your First Index

Our next problem is on search performance:

What if we use objects? That's right, these little guys:

JavaScript objects, otherwise known as hash tables or dictionaries, are really efficient at storing and looking up key-value pairs:

const hashTable = {
  hello: "world",
  foo: "bar",
  baz: "qux",
};
const value = hashTable["hello"]; // "world"

It doesn't matter how many records there are—the time it takes to look up and retrieve a value in a hash table is more or less constant. The catch is they must live in memory.

let x = 1;
x = x + 1;
console.log(x); // 2
x = x + 1;
console.log(x); // 3

import fs from "fs";
let x = Number(fs.readFileSync("data.txt", "utf8")) || 1;
x = x + 1;
console.log(x);
x = x + 1;
console.log(x);
fs.writeFileSync("data.txt", x);

Here's how the index will work. For every record that we have in our database, we'll store that record's offset—the number of bytes from the beginning of the file to the start of the record—in the index:

Add record

The second record, 18: dolor sit, for example, has an offset of 15 because:

1. Each character is 1 byte large;

2. The first record is 13 characters long (1:Lorem ipsum);

3. The first record ends with a newline character, which is (at most) 2 bytes long;

This gives us an offset of 13 + 2 = 15.

One thing to note is that we need an index for each segment because the offset is relative to the start of the file—in other words, the start of each segment.

Searching With Indices

Using an index, our search algorithm can now run a lot more efficiently:

1. Starting at the most recent segment, look up the key in the index;

2. If the key is found, read the record at the offset;

3. If the key is not found, move on to the next segment;

4. Repeat (2) and (3) until the key is found or all segments have been searched.

Search

Updating Indices

An index is only useful if it's in sync with our data. Whenever we update, delete, or insert a record, we have to change the index accordingly:

Notice what this implies—writing to the database is slower with an index! This is one of the tradeoffs of using an index; we can search for data much faster at the cost of slower writes.

Tradeoffs

An index is great because it lets us query our database much faster, but there are some problems with our specific hash table implementation:

1. Keys have to fit in memory. Since we're using an in-memory hash table as our index, all of the keys in our database must fit in memory. This means there's a limit on the number of keys we can store!

2. Range queries are inefficient. Our index wouldn't help for search queries; if we wanted to find all the records between the keys 12 and 18, for example, we'd have to iterate through the entire database!

Sorted String Tables

Here's an idea: what if we ensure our database is always sorted by key? By sorting our data, we can immediately make range queries fast:

Sparse Indices

One benefit of sorting our data is that we no longer need to store the offset of every record in memory.

Take a look at this database with four records. Since there's no logical order to the records, there's no way to determine where a record is without storing its key or searching through the entire database.

Knowing that 10 has an offset of 50 doesn't help us find where 18 is.

Now if these records were sorted, we could determine the location of each record using any of the keys in the index, even if it's not the key we're looking for.

Let's say our database is sorted but we only had the offset for the key 10:

Let's say we want to find the key 18. We know that 18 is greater than 10, which means it must be after 10 in the database. In other words, we can start searching for 18 from 10's offset—36 in this case.

Search

While this is certainly slower than having the offset for 18 directly, it's still faster than looping through the database in its entirety.

The real unlock here lies in being able to control the trade-off between memory and performance: a denser index means faster lookups, but more memory usage.

Sorting in Practice

Ensuring our database is always sorted is much easier said than done; by definition, sorting data requires moving around records as new ones get added—something that cannot be done efficiently when we're storing data on-disk. This brings us to our problem:

The trick is to first sort the data in memory, and then write it to disk.

1. When we add a new record, add it to a sorted in-memory list;

2. When our in-memory list gets too large, we'll write it to disk;

3. When we want to read a record, we'll read the in-memory list first, and then the disk if necessary.

The data structure used to store the in-memory list is usually one optimized for sorted data like a balanced binary search tree or more commonly, a skip list.

Of course, the main downside of having some of your data in-memory is that it's not persistent—if the program crashes or the computer shuts down, all of the data in the in-memory list is lost.

The fix here is thankfully pretty straightforward—every time we add a record to the list, we also write it to an append-only file on disk. This way, we have a backup in case a crash does happen (which it most certainly will).

The append-only file doesn't need to be sorted nor does it need to have every record in the database; only the ones that are currently in memory.

LSM Trees

What we just built actually exists in the real world—it's called an LSM or Log-Structured Merge Tree.

An LSM tree works by combining an in-memory list (often called a memtable) with an on-disk file (typically called a sorted string table or SST) to create a really fast key-value database.

LSM trees are the underlying data structure used for large-scale key-value databases like Google's LevelDB and Amazon's DynamoDB, and they have proven to perform really well at scale—on Prime Day 2020, DynamoDB peaked at 80 million requests per second!

Now, LSM trees aren't perfect, and they're certainly not the only way to structure a database. In fact, relational databases like PostgreSQL or MySQL use a completely different structure called a B-Tree to store their data—but that's a deep dive for another post.

For now, thanks for reading!