Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Load Balancing and Partitioning: Two Hops of Hashing

Overview

Every request in a distributed system performs two placements before any business logic runs: it must find a server (load balancing — which healthy instance of a service should execute this?) and a data owner (partitioning — which node’s shard holds the row, the cache slot, or the log partition this request touches?). The two problems look like different chapters of different books — one lives in networking gear, the other in database internals — but they are the same mathematical object applied at two scales: a function from a request key to a slot in a changing pool, with a policy for what happens when the pool changes. The connections between them are where production systems actually succeed or fail: a request routed to a perfect server that does not own the data costs an extra network hop; a request routed to the data owner that is unhealthy costs an error; and a topology change that moves both the servers and the partitions at once is the rebalancing storm that takes down clusters during exactly the traffic events that prompted the scaling.

This page maps the full pipeline — L4/L7 balancing, session affinity, consistent hashing and its variants, range versus hash partitioning, service discovery, and health checks — treating each joint as a design decision with its own failure propagation. The unifying question is the senior-level one: who knows what, when, and how stale can their knowledge be? A load balancer with a stale health view sends traffic to corpses; a client with a stale partition map sends requests to nodes that no longer own the key and pays a redirect; a scheduler unaware of data locality defeats the entire purpose of partitioning. Every mechanism in this page is an answer to one of those staleness problems.

The Subsystems, Independently

L4/L7 load balancing and session affinity (see ../../networks/load-balancing/l4-vs-l7.md and ../../networks/load-balancing/algorithms.md). An L4 balancer routes on connection 4-tuples — fast, kernel/DPDK-implementable, blind to content (see ../../networks/advanced/l4-load-balancing-internals.md); an L7 balancer reads HTTP and can route by path, header, or cookie, terminate TLS, and retry intelligently. Selection policies range from round-robin and weighted variants to least-connections (join-shortest-queue, which adapts to request cost variance — the queueing-theory argument of ./scheduling-queueing.md). Session affinity pins a client to one backend (source-IP hash at L4, affinity cookie at L7) so server-local state survives across requests — a purely stateful workaround that trades balance for locality. Health checks close the loop: active probes or passive failure tracking eject dead backends, and the balancer is only ever as good as the freshness of that view.

Consistent hashing and its variants (see ../../distributed/partitioning/consistent-hashing.md). Naive hash(key) mod N moves almost every key when N changes — useless for dynamic pools. Consistent hashing maps keys and nodes onto a ring, each key owned by the next node clockwise, so adding a node moves only ~K/N keys; virtual nodes spread each physical node’s presence around the ring to smooth the load distribution; rendezvous hashing (../../distributed/advanced/rendezvous-hashing.md) computes, per key, the node maximizing hash(key, node) — no ring to maintain, perfect balance, O(nodes) per lookup — and jump hashing trades flexibility (slots must be numbered contiguously; no weights) for O(1) computation. L4 balancers adopt the same trick without state: Maglev-style lookup tables give connection affinity across balancer replicas, which is why “consistent hashing” appears in network gear as well as in storage clusters.

Data partitioning and discovery. Partitioning splits the dataset: range partitioning keeps ordered keys together (efficient range scans, vulnerable to hot ranges and skew — see ../../distributed/partitioning/range.md); hash partitioning spreads load uniformly (no range scans, no locality for ordered access). Placement of partitions onto nodes is itself a second application of consistent hashing in Dynamo-lineage systems. Service discovery (../../distributed/microservices/discovery.md) is the membership substrate both layers consume: who is alive, what addresses, which partitions are theirs — published via a registry (etcd/ZooKeeper/Consul), gossip, or control planes, always with a propagation delay that defines how stale any router’s view can be.

The Shared Principle

Both layers are “route a key to a slot in a changing pool,” and every design in both layers is a point on one tradeoff: spread (balance) versus locality (affinity) versus stability (movement on membership change). Round-robin maximizes spread at zero locality; sticky sessions maximize locality and create skew; naive mod-N hashing is stable under nothing; consistent hashing buys stability (only K/N keys move) at the cost of vnodes for spread. The same slider appears twice — for requests at the balancer and for data at the partitioner — and the two instances couple: affinity that ignores partition placement sends requests to servers far from their data; partition-aware routing that ignores server health sends requests to owners that are dead. The senior insight: the two placements should share information (data-local routing, cache-affinity scheduling), and the shared substrate is the membership view, whose staleness bounds both layers’ correctness.

A second shared idea: hashing layers compose multiplicatively in their failure modes. Two independent consistent-hash rings — one for servers, one for data — each move K/N of their domain on a membership change; a scaling event that touches both doubles the churn, and if the two rings are keyed on related keys (session key and user ID, say), movement can cascade: the session moves servers, invalidating server-local caches, while the data moves owners, invalidating the data’s local cache — a cache-coherence event manufactured by a scaling decision (see ./cache-coherence-consistency.md).

Where the Coupling HOLDS and BREAKS

JointCoupling that HOLDSWhere it BREAKS
Balancer ↔ health checksEjected backends stop receiving traffic within one check intervalFlapping (checks pass/fail near threshold) churns connections and evicts warm caches; passive detection sees only sampled failures — the first victim of each dead backend pays the cost
Affinity ↔ scalingSticky routing preserves per-server caches and long-lived stateAdding a server rebalances nothing automatically: with L4 hash affinity, ~all connections remap; with cookies, old servers keep unequal share; scale-out never reduces load on existing sticky sessions
Server placement ↔ data placementData-local routing (routed proxies, co-located compute) removes the cross-rack hopThe two rings drift independently: after a data rebalance, “local” servers stop being local until maps refresh — stale maps cost one extra hop (read) or a redirect (write)
Partitioner ↔ skewHash partitioning spreads uniform keys evenlyHash partitioning cannot fix hot keys: one celebrity user lands on one owner and no amount of resharding splits it — that is a key-design or caching problem (see ../../distributed/advanced/hot-keys-and-sharded-counters.md)
Discovery ↔ both layersOne membership view feeds balancers, clients, and partition mastersPropagation delay is the error term: views disagree during convergence, so the balancer, the client, and the data owner each hold a different “now” — the window in which requests are misrouted

Failure Propagation: Rebalancing Storms and Hot Partitions

The rebalancing storm. A cluster at capacity adds nodes; the partition layer must copy ~K/N of the data to each newcomer while the traffic layer redirects keys. Three load increases land simultaneously: the copy traffic itself (moving 1% of a 100 TB store is 1 TB of network and disk I/O), cache cold-start on every node that received keys (its hit ratio drops from warm to zero for the moved fraction), and read-repair/anti-entropy churn validating the moved ranges. If the cluster was adding nodes because it was saturated, the rebalancing consumes the exact headroom the expansion was meant to create — clusters die during their own resharding. Mitigations are all rate-limiting moves: throttle copy bandwidth, shift keys in small batches (vnodes make batches natural), schedule against traffic troughs, and decouple “ring updated” from “data moved” (proxy the moved keys until the copy lands). The Kafka consumer-group case (../../distributed/messaging-internals/kafka-consumer-rebalancing.md) is the same storm in miniature: membership changes stop-the-world while partitions reassign, so cooperative/incremental rebalancing exists precisely to shrink the blast radius.

Hot partitions versus hot servers. A hot server (oversubscribed instance) is a load-balancing problem — shed, rebalance, or least-connections it away. A hot partition (one key with 30% of traffic) is not: every request for it lands on one owner no matter how many servers you add, and a naive balancer that hashes on user ID will concentrate that user on one backend too. The fixes live at different layers — split the key’s storage (sharded counters), cache the value closer to callers, or duplicate the hot partition — and the diagnosis is the interview skill: “adding servers made it worse” is the signature of a data-side skew handled with a traffic-side tool. Health-check flap adds the third propagation pattern: an unstable backend that flaps ejects and rejoins repeatedly, and each rejoin re-enters rotation with cold caches, so the balancer’s attempt at self-healing manufactures cache misses and latency spikes downstream (see ./tcp-distributed-failure.md for the failure-detector tuning that governs flap).

A Concrete Worked Example

Two rings, one scaling event, with numbers. A service has 40 stateless servers behind an L7 balancer using consistent hashing on session ID, and a 40-node data tier holding 80 TB hash-partitioned with 256 vnodes per node. Black-Friday prep adds 5 servers and 5 data nodes. Server ring: ~5/45 ≈ 11% of sessions remap to new (cache-cold) servers. Data ring: ~11% of keys move — ~8.8 TB copied; at 2 GB/s sustained copy throughput that is ~73 minutes of background traffic, plus read-repair. If the two rings are keyed on the same user ID, the moved population overlaps: those users hit cold server caches and cold data caches simultaneously — their p99 doubles for the migration window. Sequencing the moves (servers first, then data in 5% batches with copy throttled to 500 MB/s and proxied reads during transit) keeps the worst-case overlap to ~2% of sessions and caps the added load at a level the pre-scaling cluster can absorb — the arithmetic turns “rebalancing is risky” into a schedule with a measured ceiling.

Affinity arithmetic. Sticky sessions on 40 servers with one failed: its sessions redistribute on reconnect, but the surviving 39 keep their warm share — total cache hit ratio dips by ~1/40. Contrast cookie-less L4 IP-hash: the failed server’s entire client population remaps by hash shift, and if all clients sit behind large CGNATs, the source-IP hash concentrates whole offices onto single backends — affinity mechanisms have their own skew models, and choosing one is choosing which skew you can tolerate.

When This Connection Is Useful

  • Problem-solving heuristics. For any “requests land on the wrong node” or “one node is melting” ticket, first classify: traffic-side skew (hot requests — balance, shed, or cache at the balancer) or data-side skew (hot key — split, duplicate, or cache at the partitioner); then check the membership view’s staleness at every hop (balancer health, client map, owner map). The two-hop model makes the diagnosis a table lookup instead of folklore.
  • Interview answers. “Design a URL shortener / chat system / rate limiter” all resolve to the same skeleton: pick the request-key hash and affinity policy at the front, the data-key partitioning at the back, and argue the coupling — where the two keys differ, what moves on scale-out, and how discovery keeps both views fresh. Candidates who treat load balancing and sharding as independent bullets miss the question interviewers are actually asking.
  • Engineering decisions. Prefer rendezvous or vnode-rich consistent hashing for pools that change; keep hash(key) mod N only for frozen pools; make the balancer partition-aware (or route through a proxy that is) when locality is worth a hop; rate-limit and batch all rebalancing; gate health-check ejection on consecutive-failure counts plus a cool-down to stop flap; and never scale the server ring and the data ring in the same window without a measured copy budget — see ../../dbms/advanced/database-sharding.md for the storage-side playbook and ../why-not-handbook/replication-modes.md for what the owner can promise once the request arrives.

Interview Questions

  1. A request must find both a server and a data owner. Enumerate the staleness sources at each hop (balancer health view, client partition map, owner map) and give the failure signature of each being stale.
  2. Why does naive mod N hashing break scale-out, what invariant does consistent hashing restore, and what do virtual nodes and rendezvous hashing each add? Which would you choose for a 1,000-node pool with frequent membership churn, and why?
  3. Adding five nodes to a saturated cluster makes latency worse for an hour. Give the three concurrent load increases of a rebalancing storm and the rate-limiting levers that cap each.
  4. One user generates 30% of traffic. Explain why neither the load balancer nor resharding alone can fix the resulting hot partition, and design a two-layer mitigation.
  5. Compare session affinity (sticky cookies) with stateless request hashing at L4: what does each preserve, what does each skew, and what happens to each when a backend fails?

Key Takeaways

  • Every request performs two placements — server (balancing) and data owner (partitioning) — and both are “route a key to a slot in a changing pool”: one slider (spread vs locality vs stability) applied twice.
  • Consistent hashing’s invariant is bounded movement (~K/N keys per membership change); vnodes buy spread, rendezvous buys simplicity and perfect balance, jump hash buys O(1) — choose by churn rate and weight needs.
  • The two hashing layers couple: shared membership views, shared keys, and simultaneous scaling multiply churn; rebalancing storms are copy traffic + cache cold-start + repair landing on a cluster that scaled because it was already saturated.
  • Hot servers are a balancing problem; hot partitions are a data-design problem — misdiagnosing one for the other (adding servers to fix a hot key) makes it worse.
  • Health checks and discovery define the freshness of both layers; flap manufactures its own cache misses, and every router’s staleness window is the system’s real error term.

Cross-References