Whew, after almost a year I'm back with the sequel to my initial blogpost on building BeckDB, my custom key-value database modeled on the Bitcask storage engine.
I've always been enthused about distributed systems, and the turning point for me was reading the Raft paper. The design decisions documented in that paper opened me up to how correctness works at scale and knowing when to trade off certain factors. This evidently led me to build a distributed version of BeckDB, a replicated database that leverages Raft for consensus and gRPC for client communication.
In subsequent sections, I'll be covering the architectural design, tradeoffs, and findings during the development phase.
Replication At Scale
Consistency and Availability: if you've ever come across the CAP theorem you'd often see write-ups on trading off one for the other in a distributed system. A related model, PACELC, extends that conversation by emphasizing that even when no partition exists, latency can still be traded for consistency since nodes must coordinate before acknowledging writes.
I've been keen on making BeckDB fault tolerant in the sense that if it's run in cluster mode, data loss won't be tolerated at all, even if that costs us some availability.
Whenever a write is made to the leader of the cluster, it attempts to reach a quorum before acknowledging it as successful to the client. Now with this model, we ensure that committed writes are eventually replicated to all healthy nodes in the cluster.
Tunable consistency is one thing I found exciting along the line, considering that some systems may not compromise anything for strong consistency, hence all queries will have to go to the leader. BeckDB doesn't force that on every read though: ordinary reads get served by any node round-robin for speed, and only the ones that actually need freshness get routed to the leader. The tradeoff here is that follower reads may briefly lag behind the latest committed write, making them potentially stale. Clients that require freshness can opt into leader-routed reads instead.
Writes and strong reads go straight to the leader; ordinary reads round-robin across followers for lower latency, trading off some freshness.
Thin Servers, Thick Clients
My whole idea of a replicated BeckDB was to keep the setup dead simple with no reliance on external services. The decision was on whether to introduce a loadbalancer that keeps the cluster state and intelligently proxy reads amongst followers based on specified configuration, or leave clients to target specific followers they want to access data from. The former introduces an additional infrastructure dependency being a Single Point of Failure, while the latter meant clients having to store configuration and focus on routing themselves.
My gRPC lessons on client-side load balancing suddenly dawned on me and I got to realize that we could strike a balance between these two decisions while keeping every detail abstracted from the client, which meant no additional service and no manual client routing configuration.
gRPC client-side load balancing aims to shift all load balancing responsibilities to clients while keeping the servers dumb. This works on two concepts: Resolvers and Pickers. As their name suggests, the initial client setup passes addresses of all servers in the cluster to the Resolver for further namespace resolution, while building a persistent connection to each server known as a 'SubConnection'. The Picker, on the other hand, decides which server to proxy each specific request to, based on the load balancing strategy already in place. Writes are sent to the leader by default while Reads are distributed across followers in a round-robin manner. For cases where strong consistency is desired, Reads get proxied to the leader.
Cluster Changes: Leader Election
"Everything that can go wrong will go wrong at the worst possible moment". This expanded version of Murphy's Law is applicable to distributed setups like BeckDB where node failures are inevitable. Luckily our Raft setup ensures that when a leader goes down, the cluster can recover by electing a new leader once a quorum agrees on a candidate.
Since our load balancing is offloaded to gRPC, the resolver still needs a way of staying current with the cluster. I have it polling on a short interval, and if the node it's currently connected to becomes unreachable, it falls back and tries every other known address in the cluster instead of just giving up.
Now here's where things get funny. My tests surfaced a subtler issue: say the resolver is talking to the current leader, and that leader goes down. Whatever node picks up the conversation next can still respond, but if there's an election underway, that node genuinely doesn't know who the new leader is yet, not because the connection is broken, but because the cluster itself hasn't decided. Pushing that half-formed picture down to the picker, a full server list with no leader marked, would have been worse than doing nothing. So instead the resolver just holds onto the last known-good state and waits, updating only once a server actually reports back with a leader in place.
The learnings from this project have been great so far, considering how related some concepts here are to the system design pieces I used to practice.
The Raft paper and gRPC's blog on client-side load balancing will be a great place to start off in case you're much interested in this project. For the full implementation, check out the source on GitHub, and the design document walks through the design decisions and components in more detail.