Load Balancing and Traffic Management Questions

Direct answer

Draining safely with a mix of short HTTP and long-lived WebSocket connections means stopping admission of new work immediately (fail readiness, deregister), letting in-flight HTTP finish naturally since it is already short, and giving WebSocket connections an explicit grace period bounded by a measured drain timeout, after which any still-open connection is force-closed. The timeout itself should not be a guess: measure the real duration distribution of long-lived connections in staging, pick a percentile with a safety margin, and validate that choice by re-running the drain and checking how many connections it actually force-closes.

Structured elaboration

• Stop new traffic first. Flip readiness to failing (or deregister from the load balancer's target pool) before doing anything else, so no new HTTP request or WebSocket upgrade attempt lands on the draining instance. New upgrade attempts should get a fast rejection (503), not a connection that immediately gets drained.
• Let short HTTP finish on its own. In-flight HTTP requests are typically done within seconds; rely on the load balancer's own connection-draining or deregistration-delay setting to keep the instance reachable for just those existing connections, not new ones.
• Give WebSockets a bounded grace period. Send a close frame with a reason and, where the client supports it, a suggested reconnect delay. Track how many WebSocket connections remain open and how long the drain has been running; when the timeout is reached, force-close whatever is left rather than draining indefinitely.
• Measuring the timeout in staging. Generate a realistic connection-duration distribution under staged load (not just connection count, the actual spread of session lengths), trigger a controlled drain, record how long each connection was open, and compute a high percentile (for example p90 or p99) of that distribution as the timeout floor before adding a safety margin.

stateDiagram-v2
    [*] --> InRotation
    InRotation --> Draining: marked for removal, readiness fails
    Draining --> Draining: HTTP finishes naturally; WS gets close frame
    Draining --> SafeToTerminate: HTTP count = 0 and WS count = 0
    Draining --> ForceClose: drain timeout reached
    ForceClose --> SafeToTerminate
    SafeToTerminate --> [*]

Worked example

A staging drain test records 10 WebSocket session durations in seconds (fully specified for this example): 12, 15, 20, 22, 30, 35, 40, 55, 90, 240. Already sorted ascending, with $n = 10$.

Using the nearest-rank method, the 90th percentile index is:

The 9th value in the sorted list is 90 seconds, so $p_{90} = 90\text{ s}$.

Add a 20% safety margin and round to a configuration-friendly value:

Validate by re-running the same drain with the 110-second timeout: only the 240-second session exceeds it, so exactly 1 of 10 sessions would be force-closed, a $1/10 = 10\%$ forced-close rate in this sample. If the team's tolerance for forced WebSocket closures during a deploy is, say, under 5%, this result fails validation and the timeout needs to go higher, or the long tail needs a real fix (session handoff and client-side reconnect) instead of a longer wait.

Autoscaling context. The same drain path fires on scale-in, not just deploys. If sticky routing pins long-lived sessions to specific pods, a scale-in event has to drain those pinned sessions the same way, and frequent autoscaling churn means paying this drain cost far more often than a deploy cadence would; that is a real argument for moving session state out of the pod (a shared store) rather than tuning the drain timeout ever higher to compensate.

Trade-offs & pitfalls

• Too-short a timeout forces out legitimate long sessions and shows up as user-visible disconnects; too-long a timeout slows every deploy and scale-in and holds resources the orchestrator thinks it already reclaimed.
• A percentile chosen from a staging dataset is only as good as how representative that dataset's traffic mix and connection-duration shape are; validate against real production duration distributions periodically, not once at design time.
• Common wrong turn: reusing the same drain timeout for HTTP and WebSocket paths. HTTP's tail is usually seconds; WebSocket's tail can be minutes to hours, and forcing HTTP to wait for the WebSocket-sized timeout just slows every deploy for no benefit.
• Session handoff or reconnect logic on the client is what actually solves the extreme tail (a connection open far longer than any reasonable timeout); a timeout alone only bounds how long you wait before giving up on it.

Direct Answer

Consistent hashing (CH) places nodes and keys on a hash ring and routes each key to the next node clockwise; rendezvous hashing (also called highest-random-weight, HRW) scores every node for a given key with an independent hash and routes to the node with the highest score. Both move only a small, bounded fraction of keys when the node set changes, but they differ in what they need to operate: CH needs a maintained ring data structure (and virtual nodes to balance load), while HRW needs nothing shared at all, it recomputes from scratch on every lookup. That operational difference, not raw performance, usually decides which one you pick.

How Each Handles Node Changes

Consistent hashing. Nodes (or their virtual tokens) occupy positions on a ring. A key is owned by the first node clockwise of its hash position. Adding a node inserts a new position and reassigns only the keys that fall in the arc between the new node and its counterclockwise neighbor. Removing a node deletes its position, and in a plain single-token ring, every key that node owned is reassigned entirely to its clockwise successor. That successor absorbs the whole load, it is not spread across the rest of the cluster. This is why production consistent-hash rings almost always use virtual nodes: giving each physical node many tokens scattered around the ring means a removal's load lands on many different successors instead of one.

Rendezvous hashing. For a key, each node's score is an independent draw from a hash function, and the node with the maximum score wins. Adding a node adds one more independent score into the comparison; only keys where the new score happens to be the maximum move, and they move only to the new node. Removing a node drops one score out of the comparison; for every key that node used to win, the new winner is whichever of the remaining nodes had the second-highest score, which, because all scores are independently drawn from the same distribution, is uniformly distributed across the survivors. Rendezvous hashing gets even redistribution on removal for free, without virtual nodes.

Cost of Rebalancing

Worked Example

Take a cluster of $N = 10$ nodes holding keys uniformly on the ring, so each node owns an expected $\frac{1}{10}$ of the keyspace.

Join (both schemes). Adding one node makes it 1 of 11 exchangeable ring owners (CH) or 1 of 11 exchangeable score-holders (HRW). By symmetry, the new node's expected share is:

and every other node's share is unaffected in expectation, for both schemes.

Leave, plain single-token consistent hashing. The removed node held $\frac{1}{N} = \frac{1}{10} = 10\%$ of keys. All of it moves to one clockwise successor, whose share becomes:

That successor now carries double its prior load, a hotspot, while the other 8 surviving nodes are untouched.

Leave, rendezvous hashing (or CH with enough virtual nodes to approximate it). The removed node's $10\%$ share spreads uniformly across the 9 survivors. Each survivor's new share:

which is exactly the uniform $\frac{1}{N-1}$ share you would expect if the whole keyspace were freshly and evenly split across 9 nodes. This algebra generalizes: $\frac{1}{N} + \frac{1}{N(N-1)} = \frac{1}{N-1}$, confirming that rendezvous hashing (and a well-provisioned virtual-node ring) reach the ideal uniform post-removal distribution automatically, while a plain single-token ring does not.

Which to Use

For cache routing (many roughly similar-capacity nodes, request-level lookups, simplicity matters, weights may differ per node's memory size), rendezvous hashing is usually the simpler choice: no ring to maintain, exact per-node weighting by scaling scores, and even load redistribution on failure without tuning a virtual-node count. The O(N) lookup cost is rarely the bottleneck unless N reaches the high hundreds or thousands of cache nodes.

For partitioned storage with a large number of partitions (sharded databases, distributed key-value stores), consistent hashing with virtual nodes is usually preferred: ownership maps to contiguous ranges, which supports range scans and simple "move this token's range" rebalancing tooling, and lookup stays O(log T) even as the ring grows large. Heterogeneous weights are handled by giving higher-capacity nodes proportionally more virtual nodes, though that is a discrete approximation rather than an exact ratio.

Trade-offs and Pitfalls

• The single-token consistent-hashing hotspot on removal (shown above) is a frequent interview trap: candidates who describe CH without mentioning virtual nodes are implicitly describing a scheme with an uneven-failover problem.
• Rendezvous hashing's O(N) per-lookup cost is a real scaling limit for very large node counts; production systems mitigate it with a hierarchical or bounded-candidate variant rather than switching to CH purely for that reason.
• Weighting is exact and continuous with rendezvous hashing (scale each node's score by its weight) but only approximate with CH virtual nodes (weight is quantized by how many tokens you assign).
• Neither scheme is free of the "every key touches every node during full re-sharding" cost if you ever need to change the hash function itself (e.g., migrating hash algorithms); that requires a coordinated dual-write or shadow-ring migration regardless of which scheme you use.

Direct answer

Client-side load balancing puts backend selection logic in the calling process, using a locally cached view of the service registry; server-side balancing puts selection in a centralized proxy or LB that every client talks to. The core trade-off is where you pay the cost: client-side removes a network hop and lets each caller apply its own resilience policy, at the price of pushing service-discovery integration and consistent LB logic into every client; server-side centralizes control, observability, and policy enforcement, at the price of an extra hop and a fleet of LB infrastructure to run. If you implement client-side selection yourself, the hard part beyond basic routing is handling membership changes (scale-up, scale-down, deploys) without needlessly disrupting connections that didn't need to move.

Comparison

A sidecar/service-mesh pattern (e.g. a local proxy per instance) is the common middle ground: it gets client-side benefits (one hop after the sidecar, per-caller circuit breaking) while keeping policy and telemetry centrally managed, at the cost of running a sidecar per instance.

Building client-side selection yourself

Beyond basic round-robin over a discovered list, three things need explicit design:

• Dynamic discovery integration: decide push vs pull (long-poll/streaming updates vs periodic refresh), how staleness is bounded (max age before a cached endpoint list is considered untrustworthy), and what happens on registry unavailability (fail open with the last-known-good list, generally, rather than fail closed).
• Weighted/health-aware routing: incorporate backend health and load signals (not just "is it in the registry") so the client doesn't keep sending traffic to an instance that's registered but degraded; this usually means combining discovery with lightweight client-observed health (recent error rate, latency) rather than trusting the registry alone.
• Minimizing connection churn on rebalance: this is the part naive implementations get wrong. If the client picks a backend by hashing the request key modulo the current endpoint count, every membership change (an instance added or removed) reshuffles almost the entire mapping, forcing most existing connections to move even though only one instance actually changed.

Worked example

Compare naive modulo hashing to consistent hashing when the backend pool grows from 100 to 101 instances. With consistent hashing on a ring, only the requests that fall in the ring segment newly owned by the added instance need to move; since 101 nodes partition the ring into (in expectation) equal arcs, that segment is 1/101 of the total:

With naive modulo hashing, key mod 100 and key mod 101 agree for almost no keys, so essentially the entire mapping (about 99%) reshuffles for a single instance added to a 100-instance pool, meaning nearly every existing connection gets torn down and re-established even though only 1 backend changed. Consistent hashing bounds that churn to roughly 1%, which is the actual justification for using it in client-side selection, not just an abstract preference.

Trade-offs and pitfalls

• Client-side LB trades a network hop for distributed complexity: every client language/runtime needs the same discovery + selection + circuit-breaking logic kept in sync, which is why organizations that adopt it usually invest in a shared client library or move the logic into a sidecar instead of reimplementing it per service.
• A common pitfall in building this yourself is optimizing routing quality (best-of-N latency-aware selection, say) while ignoring rebalance churn; a routing policy that's marginally better under steady state but reshuffles most connections on every scale event can net out worse for tail latency during autoscaling events, which happen far more often than people plan for.
• Server-side LB is usually the safer default for heterogeneous or external clients (mobile, third-party) where you cannot control client behavior; client-side (or sidecar) LB earns its complexity budget mainly inside a trusted internal service mesh where the latency and infrastructure savings compound across many services.

Direct answer

Map both nodes (as multiple virtual replicas) and keys onto the same circular hash space, keep the virtual-node positions in a sorted array, and find a key's owner with binary search for the first position at or after the key's hash, wrapping to the start of the ring if the key hashes past the last node. Virtual nodes exist so that a single physical node isn't a single point on the ring, without them, adding or removing one node would create a wildly uneven split.

Approach

Three pieces: a stable hash function (any well-distributed hash works; SHA-256 truncated to an integer is simple and collision-safe enough for this purpose), a sorted list of ring positions for binary search, and a map from ring position back to node id. Each physical node is hashed multiple times (once per virtual replica index) so it occupies many scattered points on the ring rather than one; this is what smooths the distribution and is what limits key movement to roughly the fraction of the ring the added or removed node owned.

Code (Python)

import bisect
import hashlib


class ConsistentHash:
    def __init__(self, replicas=100):
        self.replicas = replicas
        self.ring = []            # sorted list of integer hash positions
        self.hash_to_node = {}    # position -> node_id

    def _hash(self, value: str) -> int:
        return int(hashlib.sha256(value.encode("utf-8")).hexdigest(), 16)

    def add_node(self, node_id: str):
        for i in range(self.replicas):
            h = self._hash(f"{node_id}#{i}")
            if h in self.hash_to_node:
                continue
            bisect.insort(self.ring, h)
            self.hash_to_node[h] = node_id

    def remove_node(self, node_id: str):
        for i in range(self.replicas):
            h = self._hash(f"{node_id}#{i}")
            idx = bisect.bisect_left(self.ring, h)
            if idx < len(self.ring) and self.ring[idx] == h:
                self.ring.pop(idx)
                self.hash_to_node.pop(h, None)

    def get_node_for_key(self, key: str):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.hash_to_node[self.ring[idx]]

Key points

• Data structures: a sorted Python list (ring) used with bisect for binary search, plus a dict (hash_to_node) for the O(1) reverse lookup from a ring position to its owning node.
• Virtual nodes are what make consistent hashing actually consistent-ish in practice: with only one point per physical node, adding a node could take an arbitrarily large or small share of the ring depending on hash luck; with many replicas per node, each node's total share converges toward its fair proportion.
• Wraparound: bisect_right finds the first position strictly greater than the key's hash; if that search runs off the end of the list, the key belongs to the first node on the ring (index 0), since the ring is circular.

Complexity

• add_node/remove_node: O(replicas * n), not O(replicas * log n). Each of the replicas calls does an O(log n) binary search (the search phase of bisect.insort/bisect_left) to find the insertion or removal point, but the actual insertion or removal on a plain Python list then requires shifting every element after that point by one slot, which is O(n) and dominates the O(log n) search. So each replica costs O(log n) to locate plus O(n) to shift, giving O(replicas * n) total per add_node/remove_node call, consistent with the list-shift cost called out below in Trade-offs and pitfalls.
• get_node_for_key: O(log n) for the binary search, O(1) for the dict lookup.
• Space: O(n) for the ring and the reverse map, where n = number of nodes times replicas.

Edge cases

• Empty ring: get_node_for_key returns None rather than raising.
• Hash collisions between two different virtual-node keys: skipped defensively (if h in self.hash_to_node: continue), though with SHA-256 this is not a practical concern at any realistic node count.
• Removing a node that was never added: no-op, since none of its hashed replica positions exist in the ring.
• Wraparound key (hash greater than every ring position): correctly routed to the first node on the ring.

Running this with 3 nodes (A, B, C) and 100 replicas each, then adding a 4th node and removing one, against 10000 fixed keys (key-0 through key-9999):

distribution across A/B/C (10000 keys): {'A': 3257, 'B': 3536, 'C': 3207}
keys moved after adding D: 2380 / 10000 = 0.2380
expected fraction ~= 1/4 = 0.25
keys moved after removing B: 2677 / 10000 = 0.2677
keys still mapped to B after removal (should be 0): 0

With 4 equal-weight nodes, adding a node should move roughly 1 in 4 keys (the new node's fair share); the measured 23.80% is close to the 25% expectation, with the gap explained by finite-sample variance at 100 replicas per node (more replicas would tighten this further, at the cost of a bigger ring). After removing B, 0 keys are still mapped to it, confirming the removal is complete.

Trade-offs and pitfalls

• Replica count is a distribution-smoothness versus memory/lookup-cost trade. More replicas per node means a more even split (lower variance) but a bigger ring array, so slower inserts and more memory; 100 to a few hundred replicas is a common practical range.
• A plain Python list with bisect.insort/.pop is O(n) per underlying array shift, not O(log n), for the insertion/removal itself, even though the search to find the position is O(log n). At very large node counts, a balanced tree or skip list would be needed to make mutation itself sub-linear; call this out explicitly if asked to scale this past a modest node count.
• This design assumes a single process owns the ring. In a distributed setting, every client needs the same ring (same node set, same replica count, same hash function) to agree on key ownership; a stale or divergent ring on one client silently routes some keys to the wrong node.

Direct answer

The fix has to work at both layers: the load balancer should bring a recovered instance back into rotation gradually (slow-start / weight ramp) rather than at full weight immediately, and clients should retry with jittered exponential backoff rather than reconnecting in lockstep the moment they see the instance healthy again. Neither alone is sufficient: LB-side ramping protects against a coordinated flood, but internal callers that bypass client backoff will still hit the instance hard once its weight is nonzero, so admission control (a hard per-instance connection/request cap) is the backstop that holds regardless of what clients do.

Load balancer mitigations

• Slow-start / weighted ramp-up: on transition to healthy, start the instance's LB weight near zero and increase it on a schedule (linear or exponential) instead of jumping to full share immediately.
• Health-check hysteresis: require several consecutive successful probes, not one, before even starting the ramp, so a flapping instance doesn't repeatedly trigger fresh thundering-herd events.
• Hard admission caps: independent of weight, enforce a per-instance connection/request ceiling at the LB so the ramp schedule isn't the only thing standing between the instance and overload.
• Sticky-routing caution: if session affinity is in use, avoid re-establishing it fully during ramp-up, since affinity can concentrate a disproportionate share of long-lived clients onto a still-warming instance.

Application-level mitigations

• Jittered exponential backoff on clients: spread reconnect attempts in time instead of retrying immediately or on a fixed interval that resynchronizes across clients.
• Admission queueing with a bound: the instance itself accepts up to a limit and returns 429/503 with Retry-After beyond that, rather than accepting everything and falling over.
• Circuit breakers upstream of the instance: if error/latency crosses a threshold during ramp-up, upstream callers back off automatically instead of continuing to hammer it.

Worked example

Suppose the recovered instance's established safe steady-state capacity is $C = 5{,}000$ RPS, and the pent-up demand specifically targeting it (clients that were failing over away from it and are now retrying) is $D = 50{,}000$ RPS, 10x its safe capacity. The LB ramps its weight starting at $w_0 = 1\%$, doubling every 10 seconds:

By t=40s the instance is already running at its full safe capacity even though the LB weight is still far below 100%; from that point on, the hard admission cap (not the weight ramp) is what's actually protecting it, and the ramp continuing upward just determines when the instance starts absorbing a "fair" share once the herd's backlog (D) has drained through the rest of the pool. This is the concrete reason both mechanisms are needed: the ramp controls the early window when D is far above C, and the hard cap controls everything after, once weight alone would otherwise overshoot.

Trade-offs and pitfalls

• Slow-start delays how quickly the pool's overall capacity recovers, which matters if the rest of the pool is itself under strain; the ramp duration is a real trade-off between protecting the recovering instance and relieving the rest of the fleet faster.
• Implementing only client-side backoff misses internal service-to-service callers that don't go through the same retry library; implementing only LB-side ramping misses the fact that a fixed weight schedule can still be overwhelmed if pent-up demand is large enough relative to the ramp rate, which is exactly why the hard admission cap has to exist independent of the ramp.
• A common failure in postmortems is tuning the ramp curve without ever computing whether the ramp rate can plausibly outrun realistic pent-up demand (as in the worked example above); a ramp that's too slow relative to D just delays the herd, and one that's too fast relative to C doesn't protect the instance at all.