hard Request Routing & Partition Discovery

Partitioning splits the data; routing has to know where the pieces went

Once a dataset is split into partitions spread across N nodes, a request for key K is only correct if it reaches the one node (or replica set) that currently owns K’s partition — ask the wrong node and you get, at best, an extra hop, at worst a miss on data that is actually there. So partitioning is never complete on its own; it always ships with a second mechanism, request routing, whose only job is answering “who owns K right now?” and keeping that answer current as the cluster reshapes itself. Every partitioned system — Redis Cluster, Cassandra, Vitess/MySQL sharding, Kafka — picks one of exactly three places to put that answer.

Three places to put the key → node map

1. Routing tier (proxy). A dedicated, partition-aware layer sits in front of the cluster, holds the map, and forwards every request to the right node. The client just talks to the router as if it were the whole database and carries zero partitioning logic. Vitess’s VTGate and a Redis-fronting proxy (twemproxy, Envoy with a Redis filter) both work this way.
2. Node-forward (ask any node). Clients connect to any node in the cluster. If that node owns K it answers directly; if not, it redirects the client (or itself forwards internally). Redis Cluster’s MOVED/ASK replies and Cassandra’s any-node-can-coordinate model both work this way — every node holds the full map, so any entry point routes correctly, at the price of an extra hop on a miss.
3. Partition-aware (smart) client. The client itself holds the key → node map and connects straight to the owner — no intermediary, fewest possible hops. Cassandra’s token-aware drivers, Kafka producers (which cache the partition-leader map), and sharded-driver setups that skip a proxy layer all behave this way. The cost simply moves into the client: it must fetch the map and keep it from going stale.

The one problem all three share: the map changes

Wherever the map lives — router, every node, or every client — it is only a cached fact, and rebalancing invalidates it: a node joins, a node leaves, or a partition is split or moved, and the old answer for K becomes wrong. The routing tier concentrates that update problem in one process; node-forward and smart-client push the identical update out to N nodes or M clients, so *how the update propagates* matters as much as *what the map says*. Two mechanisms dominate in practice:

• Coordination service (ZooKeeper/etcd watch). The current map lives in a strongly-consistent store; every router/node/client sets a watch on the relevant path and gets pushed a notification the instant it changes. Kafka brokers and consumers watch partition-leader metadata this way (historically via ZooKeeper, now via the internal Raft-based controller); Kubernetes-style systems watch etcd the same way. You get a single source of truth and near-immediate propagation, but that store is now a dependency every router/node must reach.
• Gossip. Nodes exchange ring/membership state with a few random peers on a fixed interval; information reaches everyone in O(log N) rounds without any node being a single source of truth. Cassandra and Dynamo-style stores route this way: no external coordination service to run, but propagation is probabilistic and takes multiple rounds, so for a window after a change some nodes genuinely disagree about who owns K.

Traced: a client mid-flight during a rebalance

Key K=42 is owned by N2. An operator triggers a rebalance that moves its partition to N4. Two clients are in flight: one refreshes its map immediately, one is still holding the old answer.

step	event	map says	request lands on
1	lookup for K=42, before rebalance	N2	N2 — correct
2	rebalance starts: N2 ships the partition to N4	N2 (not yet updated)	N2 — still correct, data hasn’t moved yet
3	coordinator writes the new map; watches/gossip start propagating	fast watcher: N4 · slow watcher: N2	depends which watcher answered the client
4	stale client (map still says N2) sends the request	N2 (stale)	N2 replies MOVED → N4 — one wasted hop
5	client updates its map from the redirect, retries	N4	N4 — correct

Step 4 is the whole mechanism in miniature: a redirect isn’t a failure, it’s the system correcting a stale map on the fly — the true failure mode is a router/node that doesn’t redirect and silently serves the wrong answer (or errors) instead.

Pitfalls

• Caching the map forever. A Kafka client that never refreshes its partition-leader cache keeps sending produce requests to a broker that lost leadership, and only learns via a NOT_LEADER_FOR_PARTITION error — the client must treat that error as a trigger to refetch metadata, not just retry blindly.
• Redirect storms. If a hot key moves and every client discovers it via a live MOVED miss instead of a pushed update, the old owner is hit by a burst of doomed requests right as it’s trying to hand off — push-based invalidation (watches) avoids this; pure lazy-discovery does not.
• Gossip convergence window treated as instantaneous. During the rounds it takes gossip to reach every node, two nodes can legitimately disagree about who owns K — if both accept writes for it in that window, you get a real conflict to reconcile, not just a wasted hop.
• The routing tier as an unstated single point of failure. Moving routing logic out of every client into one proxy is only a win if that proxy is itself replicated and load-balanced — a single, unreplicated router turns a scaling helper into an outage waiting to happen.

Selection & trade-offs — how a senior engineer decides

Routing tier vs node-forward. Choose a routing tier when you want dumb, portable clients (any language, no driver logic) and can afford to run and scale one more tier — Vitess does this because MySQL clients speak the wire protocol unchanged. Choose node-forward when you’d rather not operate an extra service and can tolerate an occasional redirect hop — Redis Cluster picked this specifically to keep the deployment topology flat (just Redis nodes, no proxy fleet). You gain operational simplicity; you pay in worst-case latency on a miss and in every node needing the full map.

Node-forward vs smart client. A smart client gets the fewest hops of the three — it goes straight to the owner almost all the time — but it embeds partitioning logic in every client and every language binding, and it is the one place staleness is hardest to police, since you don’t control when a given client refreshes. Use it when clients are few, trusted, and share one well-maintained driver (Cassandra’s official drivers); avoid it when clients are many, thin, or third-party, where a routing tier or node-forward keeps the routing logic in one place you actually control.

ZooKeeper/etcd watch vs gossip for freshness. A coordination service gives near-immediate, strongly-consistent propagation at the cost of running (and depending on) a separate consensus system — worth it when misroutes must be rare and the cluster is small-to-medium (hundreds of nodes, Kafka-scale). Gossip needs no separate service and scales to very large, geographically spread clusters, but accepts an eventually-consistent view of the ring and a real convergence window — Dynamo-style stores choose this because they already accept eventual consistency elsewhere (see the Consistency Spectrum) and prioritize not having a single coordination dependency.

Takeaways

• Partitioning always ships with a second mechanism, request routing, whose job is answering “who owns K?” and keeping that answer current — via a routing tier, node-forward redirects, or a partition-aware client.
• All three store the same key → node fact in a different place (one router, every node, or every client) and break the same way: rebalancing invalidates the cached map until the update propagates.
• Freshness comes from a coordination service (ZooKeeper/etcd watch: fast, strongly consistent, adds a dependency) or gossip (no extra service, eventually consistent, has a real convergence window) — stale routing shows up as a redirect (cheap) or a silent misroute (a real bug) depending on whether the receiving node knows to say so.
• Fewest hops (smart client) trades against simplest clients (routing tier); node-forward sits in between. Pick based on how many client languages you support and whether you can operate an extra tier.

---

Re-authored for this guide; both diagrams hand-authored as SVG. Sources: Martin Kleppmann, Designing Data-Intensive Applications, ch. 6 (“Request Routing”); Redis Cluster Specification (MOVED/ASK); Vitess documentation (VTGate); Apache Cassandra documentation (token-aware drivers, gossip protocol); Apache Kafka documentation (partition leadership & metadata refresh). See also: Consistent Hashing, Online Resharding & Cross-Shard Operations, The Consistency Spectrum.

I just read a lesson on **Request Routing & Partition Discovery** (System Design) and want to truly understand it. Explain Request Routing & Partition Discovery from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Request Routing & Partition Discovery** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Request Routing & Partition Discovery** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Request Routing & Partition Discovery** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.