Load Balancing from Round Robin to Consistent Hashing

A load balancer answers a deceptively small question: which eligible endpoint should receive this request? The answer affects latency, cache locality, capacity, failure isolation, and deployment safety. A poor choice can overload one instance while aggregate fleet utilization looks comfortable. A sophisticated choice can also be worse than round robin when its inputs are stale or its affinity key is skewed.

Load balancing is therefore a request-placement problem, not merely a way to spread connection counts. The useful design process separates three concerns: discover the eligible endpoint set, choose a placement policy using information available at that layer, and feed outcomes back without creating unstable oscillation. This article concentrates on that middle concern and its immediate health signals. It does not trace packets through hosts or explain network-stack internals.

The central thesis is that no algorithm balances an abstract quantity called load. Each balances a proxy such as requests, active work, measured latency, or hash-space ownership. Choose the proxy that follows the workload’s actual cost, then test it under skew, churn, slow endpoints, and partial failure.

Define the Placement Objective #

Assume a balancer has an eligible set $E$ and receives request $r$. A placement function chooses one endpoint:

state may be empty, as in simple random choice; local, as in active-request counters; or derived from the request, as in hashing a tenant ID. Correctness starts by defining what eligible means. Discovery and health checking should remove endpoints that cannot accept new work, while draining endpoints may finish existing work. The placement algorithm should not reinvent membership through unrelated heuristics.

Then define the objective. Common goals include equal request counts, equal concurrent cost, low tail latency, zone affinity, stable key ownership, bounded failover movement, and proportional use of heterogeneous capacity. These goals conflict. Stable affinity deliberately sends the same key back to the same endpoint even when another endpoint is momentarily less busy. Least-load placement sacrifices locality to react to current work.

A request count is a useful cost proxy only when requests are similar. If one endpoint receives ten image transformations while another receives ten cache hits, equal counts are not balanced compute. Active requests improve the estimate when duration varies, but a long-held streaming request may consume little CPU. Queue depth, CPU, or latency can add evidence, yet every remote metric is delayed and may trigger herd behavior.

Write the placement contract in domain terms. For example: “Keep requests for one document on the same cache shard while membership is stable; when one of 20 equal shards is added, move only a small fraction of documents; never place on an unready shard.” That contract points toward consistent hashing. A stateless JSON API with uniform requests and no local cache may need nothing beyond randomized round robin and health-aware weights.

Understand L4 and L7 Information Boundaries #

Layer 4 and layer 7 balancing describe what information is available when placement occurs, not which algorithm must be used.

An L4 balancer places transport connections using addresses, ports, protocol, and connection-level observations. It can be efficient and protocol-agnostic. All requests multiplexed over one long-lived connection generally follow that connection’s placement unless another mechanism operates behind it. Connection count may therefore diverge from request load: one connection can be idle while another carries many concurrent operations.

An L7 balancer understands an application protocol such as HTTP. It can select by host, path, header, method, authenticated tenant, or request class, and it can observe response codes and request latency. That enables routing image uploads separately from lightweight reads or hashing by a stable customer ID. It also requires protocol parsing or termination, compatible handling of upgrades and streaming, and careful treatment of sensitive metadata.

Neither layer guarantees fairness. L4 connection hashing can work well when clients open many similarly active connections, and poorly when a few proxies concentrate traffic. L7 round robin can still overload an endpoint if requests have unequal costs. Choose the layer needed to observe a meaningful placement unit, then choose an algorithm.

Layering balancers also composes policies. A regional L4 service may choose a zone-level proxy, which applies L7 routing to application instances. Each hop needs a distinct objective. Repeating affinity at both layers with unrelated keys can concentrate traffic unexpectedly, while retries at several layers can multiply attempts.

Start With Simple Stateless Choices #

Round robin cycles through the eligible list. With stable membership and similar independent requests, it gives each endpoint nearly equal counts over time. It is deterministic and easy to inspect. The list order and counter must update safely when membership changes; otherwise removed endpoints or repeated resets can bias selection.

Weighted round robin allocates more turns to endpoints with greater declared capacity. If endpoint A has weight 2 and B has weight 1, A receives roughly two placements for every one to B over a sufficiently large window. Static weights work for known hardware differences. Dynamic weights based on noisy utilization can oscillate unless smoothed and rate-limited.

Random choice selects uniformly from eligible endpoints. Its short-window counts vary, but concentration becomes predictable at scale, and independent balancers need no shared counter. Randomization avoids synchronization where many balancers all begin round robin at index zero and send their first request to the same instance.

These policies ignore current work. They still perform surprisingly well because they do not depend on delayed feedback. They are often the right baseline. Their main failure is workload variance: an endpoint that happens to receive several expensive requests remains eligible for more.

Weighted policies also require normalization during partial health. If a weight-8 endpoint disappears from a fleet with two weight-1 endpoints, the survivors receive far more traffic. Health-aware placement prevents sending to the failed endpoint but cannot manufacture missing capacity. Admission control, queue limits, or load shedding must handle the overload explicitly.

Use deterministic tests for list mutation, weight ratios over complete cycles, empty sets, and draining endpoints. For randomized selection, test distribution with broad statistical bounds and fixed seeds; do not demand an exact sequence from a supposedly random policy.

React to Work With Least Load and Two Choices #

Least connections or least active requests chooses the endpoint with the smallest local in-flight count. It reacts to variable duration: slow work remains counted, so new work tends to go elsewhere. Normalize by capacity when endpoints differ:

This estimate is strongest when the balancer itself owns the connections or requests and can update counters synchronously. A distributed fleet of balancers sees only its own assignments unless endpoints publish global state. Summing remote reports introduces delay, and choosing the globally smallest reported value can make every balancer stampede toward the same apparently idle endpoint.

Latency-aware policies face a similar trap. An exponentially weighted moving average can smooth observations, but low traffic means little evidence, and an endpoint that receives no requests cannot demonstrate recovery. Exploration traffic and a minimum sample policy prevent permanent exclusion. Separate application failures from client errors: a fast 400 should not make an endpoint look preferable to a slower successful response.

The power of two choices offers a robust compromise: sample two eligible endpoints uniformly and select the one with fewer active requests or lower normalized score. It avoids scanning the whole fleet, reduces dependence on exact global rankings, and sharply lowers the chance of placing on a busy endpoint compared with one random choice. Each balancer can use local active counts, accepting that its view is partial.

Queue length is tempting but semantically tricky. One endpoint may report work before admitting it while another reports only executing work. Metrics must have identical definitions and timestamps. CPU can lag bursty demand and may reflect unrelated tasks. A useful policy often combines a stable candidate sample with one immediate local signal rather than optimizing a large formula of stale metrics.

Slow start limits the weight of a newly ready or recovered endpoint and increases it gradually. Without it, least-load policies see a zero counter and direct a burst to a cold process. The ramp should be based on admitted work and readiness evidence, not wall-clock optimism alone.

Use Hashing When Locality Is the Requirement #

Hash-based placement maps a stable request key to an endpoint. A simple modulo scheme computes hash(key) mod N. It creates excellent affinity while $N$ is constant, but changing $N$ remaps most keys because nearly every remainder changes. That can empty caches or move state during precisely the period when the fleet is already changing.

Consistent hashing places both keys and endpoint tokens in a circular hash space. A key belongs to the first endpoint token encountered clockwise. Adding an endpoint moves only the keys in its newly claimed interval; removing one transfers its interval to the next owner. With ideal distribution and equal capacities, adding one endpoint to $N$ moves on the order of $1/(N+1)$ of keys rather than nearly all of them.

One physical endpoint receives many virtual nodes spread around the ring. Virtual nodes reduce variance and let a larger endpoint own more tokens. Too few tokens create uneven ranges; too many increase ring metadata and update cost. Token placement should be deterministic from endpoint identity and weight so independent balancers build the same ring.

Rendezvous hashing is a useful alternative. For each key, compute a score with every eligible endpoint and choose the highest. It has minimal movement and simple weighted variants without a ring, though evaluating every endpoint can be expensive for very large sets. Candidate hierarchies or precomputed structures can reduce that cost.

Hashing balances key space, not traffic. If one tenant produces 30 percent of requests, perfect token distribution still sends that hot key to one owner. Salting or splitting the key spreads load but weakens affinity and may require merging results. Replicating each key to several ranked owners allows a secondary choice, provided consistency and cache semantics tolerate it.

Choose a key that is stable, available before placement, safe to expose at that layer, and aligned with the locality target. Source address is often unstable behind proxies and can aggregate many users. A session cookie may create affinity but complicate expiration and failover. A tenant ID can isolate caches while making a large tenant hot. Hashing is justified only when the locality benefit exceeds those constraints.

Work a Stateful Rendering Example #

Suppose a document-rendering service has 12 workers. Each worker keeps parsed templates and customer fonts in a bounded local cache. Rendering cost varies: cached small documents finish quickly, while cold complex documents use more CPU. Requests for the same tenant benefit from affinity, but no worker owns authoritative state.

Pure round robin spreads request counts but destroys tenant cache locality. Least-active placement reacts to expensive documents but also sends a tenant across many caches. Modulo hashing by tenantId preserves locality until autoscaling changes worker count, at which point most tenants move and the fleet experiences a cold-cache wave.

A practical policy uses weighted rendezvous hashing to rank workers for each tenant, then compares the first two healthy candidates by normalized active render cost. The primary candidate preserves affinity in normal conditions. The secondary candidate provides an escape when the primary is draining or above a hard queue threshold. Workers report a coarse capacity weight based on their configured CPU class, not rapidly changing CPU samples.

Consider tenant T-91. Its ranking is [worker-7, worker-2, worker-11, ...]. Normally requests go to worker 7. When worker 7 begins draining, new requests go to worker 2 while existing renders finish. If worker 7 later returns as a new process incarnation, slow start caps its effective weight and cache warmup happens gradually.

Now tenant T-giant sends a sustained disproportionate workload. Hashing cannot solve that hotspot. The service detects per-tenant queue age above its admission threshold and splits this tenant into four explicit placement buckets using (tenantId, documentId mod 4). The exception is configuration with an expiry and an observable reason, not an automatic change to every tenant. Cache duplication increases, but the high-volume tenant gains parallel capacity.

The policy has clear tradeoffs. Ranking plus active-cost comparison is more complex than round robin. Local counters differ among balancers, failover cools caches, and explicit splitting needs lifecycle management. It earns that complexity only because the measured workload has both strong locality value and variable render cost.

Control Health, Churn, Retries, and Hotspots #

Placement must consume health state without amplifying it. Remove an endpoint from new selection after the health policy declares it ineligible, but let graceful draining preserve existing work. Ejecting an endpoint on one failed request is usually too aggressive; classify outcomes and require bounded evidence. Conversely, waiting for a central health update may be too slow after repeated connection failures, so a balancer can apply a short local ejection while preserving the authoritative membership record.

Membership churn perturbs every stateful algorithm. Ring updates move keys; round-robin counters reset; least-load state disappears with the endpoint. Debounce noisy membership transitions, identify process incarnations, and apply snapshots atomically. Never mix half of an old ring with half of a new one.

Retries are new placement decisions unless affinity or idempotency requires otherwise. Retrying the same failed endpoint is pointless for an endpoint-specific fault; retrying elsewhere can duplicate side effects if the first attempt actually succeeded. Bound attempts at one layer, preserve the request’s overall deadline, and use idempotency where effects matter. A retry storm can overload healthy endpoints after one member fails.

Hotspots appear at several levels: a hot key under hashing, a heavy request class under round robin, a zone with concentrated clients, or one endpoint receiving synchronized choices from many balancers. Mitigations differ: split keys, route by request class, reserve capacity by zone, randomize candidates, or shed work. Aggregate utilization does not reveal these patterns, so measure per-endpoint load and distribution skew.

Failover capacity must be planned. If a fleet of $N$ equal endpoints runs at utilization $u$, losing one raises idealized survivor utilization to approximately

The equation ignores queueing and unequal workloads, but it shows why balancing cannot rescue a fleet already too close to saturation. Multiple correlated losses are worse. Placement distributes available capacity; it does not replace headroom.

Verify Placement With Models and Operations #

Test algorithms first as pure functions over deterministic endpoint sets. Assert no ineligible endpoint is selected, weights converge to intended proportions, membership snapshots replace atomically, hash rankings are stable for the same input, and add/remove operations move only expected keys. Include empty and singleton sets, duplicate endpoint IDs, extreme weights, and hash collisions.

Then simulate workload rather than only keys. Generate cheap and expensive requests, long-lived connections, skewed tenants, changing membership, delayed load reports, and endpoint slowdowns. Record request-count variance, active-cost variance, queue age, p95 and p99 latency, cache hit rate, key movement, retries, and rejected work. Label all generated distributions as synthetic; their purpose is comparing mechanisms, not claiming production performance.

Fault tests should drain an endpoint, kill it without notice, make it slow rather than unavailable, partition one balancer from membership updates, and restore a cold instance. Verify slow start, local ejection expiry, retry bounds, and convergence to the current endpoint set. For hashing, compare the fraction of keys moved with the expected membership change and test a deliberately hot key.

Production telemetry should identify the chosen endpoint, policy version, membership revision, candidate count, selection reason, retry attempt, and coarse affinity key class without logging sensitive raw keys. Monitor per-endpoint request rate, active work, queue age, latency, error classification, ejection state, weight, and cache hit rate. Fleet-level histograms of assignment share expose imbalance that averages conceal.

Roll out a new policy in shadow mode by computing its choice without sending the request there. Compare predicted distribution and key movement, then canary a small traffic slice. Preserve a fast rollback to the previous policy and avoid changing health thresholds, retry policy, and placement algorithm in the same experiment.

The final decision can stay simple. Use round robin or random choice when work is uniform and locality has little value. Add weights for known capacity differences. Use least-active or two-choice selection when duration varies and a trustworthy immediate signal exists. Use consistent or rendezvous hashing when stable key locality is an explicit requirement, then design separately for hot keys and membership churn.

Good load balancing is not the most adaptive formula. It is a placement policy whose inputs are timely enough, whose objective matches request cost, and whose failures remain observable and bounded. Start with the simplest policy that satisfies the workload contract, and make every added signal prove that it improves decisions under the conditions where the fleet actually struggles.