Handmade databases: An exploration

A few years ago I stumbled over Handmade Hero, a YouTube series about how to build a game engine from scratch. A few things stuck with me: 1) if you understand what’s going on under the hood, you can choose what to build yourself and what you should reuse, 2) solving concrete actual problems is easier than solving hypothetical future problems, or problems that other people might have if they reuse your code, and 3) what’s going on under the hood might not be as scary as we’re made to believe.

One thing we often reuse are database engines, and with good reason: they solve hard problems with high stakes. You don’t need me to picture what happens if you press that update button and your service goes down, or worse, you lose user data. But what exactly are those hard problems? What actual problems do we need to solve for our specific use case? And what assumptions lie behind those hard problems?

This is a personal learning journey. I’ve mostly done web development my entire career living at the higher levels of abstraction. I know almost nothing yet about the theory behind database technology and have done very little low-level programming. So, this journey might very well lead to a dead end or wrong conclusions, but I’m here to learn, have fun and maybe meet some interesting people along the way by writing this stuff. I may end up producing something, or just leaving some thoughts around the internet.

Why databases engines are hard

Let’s start with the requirements. When I write something, it should be safe in a whole range of scenarios from program crashes to reboots, hardware failures and network problems. Also, it should be available when I need to read or write something giving me the correct result and should do that in an acceptable amount of time depending on the use case.

There’s at least two things making these requirements harder to achieve. First, a typical database engine contains a whole host of features that might be useful in a whole range of use cases, but yours actually only needs a subset of those. Second, typically a scalable database is a distributed system, which introduces really, really hard problems.

What if we could just ignore those problems? At the simplest level, your application has specific read and write patterns on a specific data model. What if we implement those specific routines directly in the database engine as a simple program that takes requests and manipulates data?

And the distributed nature of databases usually is because data sets are too large for a single machine and for failsafe reasons. What if we only focus on failsafe reasons? Memory and disks are getting faster, larger and are changing their nature: disks are nearing memory speeds and new types of memory offer persistence. Could we come up with different ways of scaling and dealing with failures?

But… why?

These are already solved problems, right? There’s already a range of ready-to-use database systems out there for a whole wide range of use. Well, first and foremost, it never hurts to have idea of what’s inside the black box you’re using at the core of your entire business. But what I’m curious about is how hard it actually is to write a custom engine that can grow with you at least until you get to unreasonable scales where everything changes (Facebook, Linkedin, etc.)

Most applications data is actually not too big, especially in the first few years. So if we’re taking a simpler approach, could it be useful to have control over how exactly the data is stored? And can we come up with different approaches to handle those pesky schema migrations? Also, if we need some feature like live updates, or atomic counters in a specific places, it might just be simple to implement it yourself.

So, how?

Instead of making a distributed, disk-based system, we’ll try to get the maximum out of a single machine with a leader-follower (a.k.a. master-slave) system. We’ll keep all data in memory, but create an append-only log that will get written to disk and replicated to followers. In case the leader goes down, a follower should be elected as the leader. Only in case something catastrophic happens, we’ll restore from the append-only log written to durable storage.

This way, we solve a bunch of traditional database problems. We don’t have to coordinate writes across multiple servers, becuase there’s only one server doing the writes (like we’re used to from MySQL, etc.) We also don’t use the disk for anything other than backup, so there’s no question of what’s ‘committed’ and what is not. First we write to disk, then we do the operation in memory and we always order the operations in a consistent way.

If we want to scale up, we create a new, bigger follower, make that the leader and deactivate the old leader. Same if we want to upgrade the database schema: we create a new version of the application, make it a follower, replicate all data to it, maybe verify the data is intact and make it the new leader.

We still need to make sure the append-only log doesn’t get corrupted. And there’s probably a whole host of failure cases I’m not aware of. Also, this whole experiment relies on the assumption that a single, well-written program can process a huge number of requests. And, how difficult will it be to correctly fail over, or code out these schema migrations?

Next steps

That’s the basic idea. To keep this fun for myself, I’d like to implement little experiments one by one and write about them. I’m only comfortable in C(++) for now as a low-level language, so I’ll be using this to learn a little bit of Rust, so I at least get some experience under my belt there.

That said, these are the steps I have in mind, observing performance at every step:

Your turn

What do you think? Are you curious about what happens at a lower level? Or do you have experience building databases? I want to hear from you and nerd out together! Either talk to me at hello@youapt.eu or connect with me on Twitter / LinkedIn.