One computer isn't enough

Let's build a database together. You don't need to know anything about distributed systems for this. We'll just keep running into walls, and every wall has a name that sounds scarier than it is.

Wall one: your memory

I read you a phone number and ask you to remember it. Easy.

I read you ten. Still fine.

I read you a thousand and you stop me, because obviously you're going to write them down. So you grab a notebook.

That's a database. Something remembers things for you. And the reason you reached for the notebook is the reason databases exist: your head is fast but small, and it forgets everything the moment you fall asleep. Paper is slower, holds far more, and is still there tomorrow. Memory and disk, same trade.

My first version of BeeDB was the "head" part only: a hashmap with a socket in front of it. set, get, delete. A perfectly good database until you turn it off.

Wall two: one notebook, one hand

Now the numbers keep coming. Thousands an hour.

Two things break, and it's worth being precise about which.

The notebook fills up. That's capacity, RAM runs out, disks run out.

And your hand can only write so fast. That's throughput, and it doesn't care how big your notebook is. Even with infinite paper, one person writing is one person writing.

I met the second one at work before I ever met it in BeeDB. I had a job processing a big pile of data, and the machine ran out of memory and died. The fix was to stop doing everything at once: I split the work by date range, so each piece handled its own slice and knew nothing about the others. Later the same job was too slow, so I ran those pieces on different machines.

That's the whole idea. One box has a limit, so cut the work up.

And notice how easy that was. Nobody had to find anything. Each piece had its dates, did its work, wrote its output, and if it died we just ran it again.

Data is not so polite.

Wall three: now you have to find things

Say we've split the keys: A to M in your notebook, N to Z in your friend's. Someone asks for the value of zebra. Who has it?

Somebody has to know. So now the system keeps a map of who owns what, and that map won't sit still, because you add notebooks when you grow and lose them when a friend moves away.

Everyone solves this differently. In Scylla, every node knows the whole map, so you can ask any node and it forwards you. Its client driver keeps the map too, so usually it goes straight to the right node. BeeDB does the simplest version: a gateway sits in front and routes for you.

But whichever way you go, everyone has to agree on that map. If you and your friend disagree about who owns zebra, you'll write it in one notebook and read it from the other, and spend an evening wondering where your data went.

So some systems gossip the map around. Others keep it in ZooKeeper or etcd, which, if you look at what those things are, means they solved the problem by putting a small agreement system next to the big storage system. Agreement keeps showing up. Hold that thought.

Wall four: your friend spills chai on the notebook

Five notebooks, one is ruined, and a fifth of everything you know is gone. Not slow. Gone.

The fix is old and obvious: don't keep one copy. Write every number in a few notebooks instead of one, usually three. Lose one, the others still have it. That's replication, and the number of copies is the replication factor.

Which fixes the thing that scared you, and hands you a new thing to be scared of.

Wall five: the copies stop agreeing

Copies drift apart. One friend was out when a number came in. Another wrote it down wrong. And of course the notebook that was most up to date is the one that just got ruined.

Worse: if anyone can accept a write, two people can write the same key at the same time in two places. Now there are two values for one key, and someone has to pick.

The common answer is: whoever wrote last wins, by timestamp. Scylla does this.

I didn't want to build on it, for two reasons.

Clocks lie. Two machines don't agree on what time it is, so "later" by the clock isn't necessarily later in reality, and the newer write can lose. You also lose the thread of what caused what, if my write happened because of yours, no timestamp remembers that.

And even with perfect clocks, last-write-wins throws away data on purpose. Two writes land at the same moment, one silently vanishes, and the person who sent it was told it worked.

The other way: put one notebook in charge

Stop comparing. Pick one node as the leader. Every write goes through it. It decides the order, writes it down, and everyone else copies that order exactly.

Nothing to reconcile afterwards, because there was never a second version of events. The order of writes comes from the leader's log, not from comparing wall clocks. Raft still uses timers, to notice a leader that has gone quiet, but no timestamp ever decides which write came first.

You give up "anyone can take a write". You get "there is exactly one story about what happened". For a database where STORED has to mean stored, I'll take that trade every time.

And then, of course, the question that ruins your evening:

Who gets to be the leader? And what happens when they die?

If two nodes both think they're the leader, we're back to two versions of the truth, except now we've built a whole system that assumes there's only one. If nobody is the leader, nothing gets written at all. And here's the part that makes this genuinely hard: no machine can tell a crashed leader apart from a leader it just can't reach right now. From the outside, both look like silence.

Getting a handful of machines to agree on one leader and one order of writes, while some of them are dead or unreachable, is the consensus problem. Raft is one solution, and it's the one I built into BeeDB, mostly by getting it wrong repeatedly.

That's the next post.