Day 18: Build a Request Router to Direct Traffic to the Correct Partition Owner — and Avoid Cross-Node Hops

In our previous step, we successfully partitioned our storage engine into multiple independent data directories (shards) on different ports. However, our client was left with a problem: it had no idea which node owned which key.

Today, we are going to solve the "Coordinator Tax"—the massive latency and throughput penalty that occurs when a database node has to act as a middleman, proxying requests to its peers because a client sent a key to the wrong machine. We will build a smart, high-performance Gateway Request Router that inspects incoming keys, determines their exact partition owner using deterministic hashing, and forwards them with zero unnecessary hops.

In the next lesson, we will make this partition map dynamic, introducing a consensus-backed control plane to handle node additions and partition migrations without downtime.

The Production Stakes: The Coordinator Tax

When you design a distributed database, you have to decide who routes the queries. There are two primary patterns:

1. Coordinator-Proxy Routing: The client can hit any node in the cluster. If that node does not own the key, it acts as a coordinator, proxying the request to the correct node over the internal network, receiving the response, and sending it back to the client.

2. Gateway/Client-Side Routing: The client or an edge proxy knows the partition map. It sends the request directly to the node that owns the key.

Many engineers default to Coordinator-Proxy Routing because it makes the client code simple. But in production, this pattern is a leading cause of tail-latency spikes and cascading failures.

Consider Cassandra or Elasticsearch. When a coordinator node receives a request for a key it does not own, it must:

1. Parse and deserialize the incoming request.

2. Look up the key in its partition routing table.

3. Serialize the request again.

4. Send it over the internal network to the owner node.

5. Wait for the owner node to read from disk and serialize the response.

6. Deserialize the response from the owner node.

7. Serialize it one final time to send back to the client.

This process is called double serialization. Under heavy load, this double serialization consumes massive amounts of CPU and generates significant Garbage Collection (GC) pressure.

In a documented post-mortem, Discord migrated away from Cassandra for their message store because coordinator nodes spent more time proxying requests and handling GC pauses than actually executing disk I/O. The internal network amplification factor was 2x, and a single slow node could drag down the performance of the entire cluster by stalling coordinator threads.

By introducing a dedicated, stateless Request Router (or a smart client), we reduce the internal network hop count from $2$ to $1$, eliminate double serialization, and protect our storage nodes from coordinator overhead.

The Architecture: Deterministic Gateway Routing

Our system consists of three storage nodes (Node 0, Node 1, Node 2) and a single Gateway Router.

The Gateway Router uses a deterministic partitioning algorithm. When a request arrives, the router:

1. Extracts the key from the request query parameters.

2. Hashes the key using the FNV-1a non-cryptographic hash function (highly efficient for short strings).

3. Computes the partition index: partition = hash(key) % total_partitions.

4. Maps the partition to the owning storage node.

5. Proxies the request directly to that node using an optimized HTTP reverse proxy.

If a client bypasses the router and sends a request directly to a storage node that does not own the key, the storage node will still process it by proxying it internally to the correct owner—but it will append an X-Internal-Hop: true header to the response and artificially simulate internal network latency so we can observe the performance penalty.