Following one write through BeeDB

Three posts of theory is enough. Let's follow one real write, like a parcel, and see everyone who handles it.

You telnet into BeeDB and type:

set x 0 0 1
y

A moment later: STORED. Here's everything that happened in between.

Somebody has to pick up the bytes

BeeDB doesn't hand every connection its own thread to sit and block on. There's one loop watching all the sockets, and it wakes up whenever any of them has something.

The annoying truth about TCP is that it doesn't deliver commands, it delivers bytes. Your set x 0 0 1\r\ny\r\n might arrive whole, or in three pieces, or glued to the front of whatever you type next.

So every connection gets its own little buffer. Bytes pile up in it, and nothing is parsed until a complete command is in there: the first line, and then exactly as many bytes of value as that line promised. Send something enormous and the buffer grows once; send something bigger still and the connection gets SERVER_ERROR object too large for cache and gets dropped. Once you've read half a command off a stream, you can't tell where the next one begins, so there's nothing to do but hang up.

One more rule, which took me a while to learn the hard way: only one command per connection is in flight at a time. Memcached clients match replies to requests by order, there's no id to match on. Hand two commands to a thread pool and their replies can come back swapped, and the client will happily believe the answer to your get was the answer to your set. So the next command waits in the buffer until this reply has gone out.

Handing it to Raft

The parsed command goes to propose().

First question: am I the leader? If not, you get SERVER_ERROR Not Leader: node2, or SERVER_ERROR Election in progress if nobody is in charge this second.

Look at what that message doesn't have in it: an address. node2 is useless to a telnet session. That's one of the reasons BeeDB has a gateway sitting in front of the cluster, the gateway knows which node id lives where, so it can quietly retry against the real leader. The raw protocol just tells you the truth and stops.

If I am the leader, three things happen together, under one lock:

1. The entry takes the next index in the log.
2. It goes into the in-memory log.
3. A future goes into a map under that index, that's the thing your connection is waiting on.

Then the entry is handed to the write-ahead log, and we wait for the disk.

Why memory first, then disk?

It looks backwards. Surely you write to disk, then to memory?

The reason is that the replicator threads are watching that in-memory log. Putting the entry there first means they can start sending it to the followers while my own fsync is still in flight. Do it the other way and every write waits about five milliseconds on a disk before it even starts talking to anybody.

It isn't free. If the WAL write fails, there's now an entry in memory that isn't on disk, and it has to come back out. That rollback has bitten me badly enough to deserve its own post. These days, a failed WAL write stops the node instead: if I can't write to disk, I'd rather be dead than lying.

Out to the followers

Every follower gets its own lightweight thread whose entire job is keeping that one follower up to date.

Usually a follower is one entry behind, and it gets the new entry. Sometimes it's been away and is far behind, so it gets up to 50 entries at a time, because dumping ten thousand entries into one message helps nobody. And if it's been away so long that the entries it needs have already been compacted off the end of the log, it gets a snapshot instead.

Every reply tells the leader how far that follower has got. Every reply also gets checked for a term number bigger than mine, which, as we saw last post, means I'm not the leader any more and should stop behaving like one.

Once a majority of nodes have it on disk, including me, the entry is committed. (That "including me" is quietly the most interesting part of this whole system, and it's a post of its own.)

And back again

A separate thread applies committed entries to the cache, in order. It's the only thread allowed to touch the cache, so there's never an argument about what happened first, the log settled that already.

After applying entry N, it looks up the future parked under index N and completes it. Your connection wakes up, and STORED gets written back to your socket.

So by the time those six characters reach you, the entry is on at least two machines' disks and applied to the cache. Two, specifically, because of what each node does before it speaks: a follower waits for its own WAL write to complete before it acknowledges anything, and the leader refuses to commit past its own fsync point. A majority of acknowledgements is therefore a majority of completed fsyncs, not a majority of network replies.

That is the promise, and it has a boundary worth naming. An fsync returning is the last thing an application controls; whether the bytes are truly on the platter after that depends on the filesystem and on a drive that doesn't lie about its own cache. And my own tests prove the logical half of this, not the power-loss half. The post on writing to disk says exactly where that line falls.

When it doesn't go like that

Your client waits five seconds. No answer by then and you get SERVER_ERROR timeout.

Here's the uncomfortable bit: that entry might still be in the log, and it might commit a second later. A timeout means "I don't know", not "it didn't happen".

So if you retry, the write might apply twice. For set that's harmless, you overwrite with the same value. For append it isn't, retry once and your value has the suffix twice, and nothing in the system can tell that this was one intent arriving twice. My entries do carry a request id, but it's generated on the server, so a retry looks like brand new work. Proper deduplication needs the id to come from the client, and the server to remember what it already did for that client. Worth being clear that consensus does not give you this for free: deduplication has to be built into the replicated state machine itself, as client sessions. I haven't built that yet.

What I did do is smaller and honest: the gateway only exposes the commands that are safe to retry. append, prepend, add and replace exist in the server, and the HTTP API doesn't offer them. That's a decision, not an oversight.

Next: what happens when I kill the leader in the middle of all this.