stickybalancer 1.0.0

A minimalist load balancing library implementing Strict Po2C and the Sticky-Lazy protocol.

Sticky-Lazy Load Balancing

Quick Start

pip install stickybalancer

from stickybalancer import StickyLazyBalancer

servers = ["server-1", "server-2", "server-3", "server-4"]
lb = StickyLazyBalancer(servers, threshold=3)

# Route a request
target = lb.get_next()
print(f"Sending request to: {target}")

# After the request completes, release the server
lb.release(target)

Comparison table

A probe-efficient alternative to Power-of-Two-Choices (Po2C) that caches routing decisions to cut network overhead, while keeping the same logarithmic guarantee on worst-case queue depth.

Protocol	E[Probes / Request]	Asymptotic Max Queue Depth $M_N$
Pure Random	1	$\dfrac{\ln N}{\ln\ln N}$
Round Robin	0	Flat if tasks are i.i.d., unbounded variance if not
Strict Po2C	2	$\dfrac{\ln\ln N}{\ln 2} + O(1)$
Sticky-Lazy	$\geq \dfrac{1}{T}$	$\dfrac{\ln\ln N}{\ln 2} + T$

$N$ = number of servers, $T$ = sticky threshold (tunable), $M_N$ = max load over all bins after $N$ requests have landed (the standard "balls into bins" quantity).

---

1. The Problem

Po2C is the industry default for stateless load balancing: sample 2 servers, probe both, route to the lighter one. It guarantees max load $O(\ln\ln N)$ — exponentially better than random routing's $O(\ln N / \ln\ln N)$ — but it pays for this every single request, with 2 network round-trips just to decide where to send the 3rd.

At high QPS, the probe traffic itself becomes a meaningful fraction of your internal network load.

2. The Algorithm

get_next():
    if cached_server exists and blind_capacity > 0:
        blind_capacity -= 1                      # FREE — 0 probes
        return cached_server

    s1 = sample(servers)                          # 1 probe
    if load[s1] < T:
        cache(s1); blind_capacity = T - load[s1]
        return s1

    s2 = sample(servers)                          # 2nd probe (Po2C fallback)
    winner = argmin(load[s1], load[s2])
    if load[winner] < T:
        cache(winner); blind_capacity = T - load[winner]
    else:
        invalidate cache
    return winner

Three phases per cache cycle:

1. Sticky (caching): a probe finds a server under threshold $T$ → cache it, set a credit equal to its remaining headroom $(T - \text{load})$.
2. Lazy (blind): every subsequent request drains the credit with zero probe, until the credit hits 0.
3. Safety net: if a probe ever finds a server already at $\ge T$, the cache is invalidated and the request falls back to a strict Po2C double-probe, so the algorithm never blindly piles load onto a hot server.

3. Proofs

Po2C tail bound

Let $x_k$ = fraction of bins with load $\ge k$ after $N$ balls. A bin can only reach load $k$ if, at the moment it was chosen, both sampled bins already had load $\ge k-1$ (otherwise Po2C would have picked the lighter, sub-$(k-1)$ one). Treating choices as independent (folding any dependence into a constant $\lambda$):

$$x_k \le \lambda \cdot x_{k-1}^2, \qquad x_1 \le \lambda$$

Unrolling the recursion:

$$x_k \le \lambda^{1+2+4+\dots+2^{k-1}} = \lambda^{2^k - 1}$$

By a union bound over $N$ bins:

$$\mathbb{P}(M_N \ge k) \le N\cdot x_k \le N\cdot\lambda^{2^k-1}$$

Solving for the crossover point : We want the smallest $k$ where the RHS drops below 1. Set $N \lambda^{2^k-1}=1$:

$$2^k = 1 + \frac{\ln N}{\ln(1/\lambda)} \implies k = \log_2\left(1+\frac{\ln N}{\ln(1/\lambda)}\right) = \frac{\ln\ln N}{\ln 2} + O(1)$$

since the $1+$ and the $\ln(1/\lambda)$ constant only contribute an additive $O(1)$ term as $N\to\infty$. This recovers the classical $M_N = \dfrac{\ln\ln N}{\ln 2}+O(1)$ result (Azar–Broder–Karlin–Upfal, 1994).

$\mathbb{E}[P] = 2$ (for Po2C)

Each selection process of the server takes 2 random servers from the server list so we need 2 probes per call.

Sticky Lazy tail bound

Decompose any bin's load into two parts:

$$\text{load} = \underbrace{\text{load contributed by Po2C-style probe decisions}}{\text{bounded exactly as in Po2C}} + \underbrace{\text{load added blindly during one cache cycle}}{\le T-1 \text{ by construction}}$$

The first term is governed by the same recursion as plain Po2C.

The second term is the blind cap: by construction the cache never lets a server accept more than $T-1$ requests beyond the level it was caught at, because the credit is capped at $(T - \text{load})$ at cache time and load only increases monotonically during the blind run. So the blind phase adds at most $T$ to whatever the probed component would have been:

$$M_N \le \underbrace{\frac{\ln\ln N}{\ln 2}+O(1)}{\text{probed part }} + \underbrace{T}{\text{blind cap}}$$

$\mathbb{E}[P]$ (for Sticky-Lazy)

Two cases per probe. Let $t = \mathbb{P}(\text{probe lands on a server with load} < T)$ — the cache-hit case. The complementary case $(1-t)$ is the safety-net branch.

• Case 1 ($t$): $1$ probe; cycle serves $T-L$ requests for $L\in{0,\dots,T-1}$. Using the average-of-extremes estimate $L_{\text{avg}} = \frac{T-1}{2}$ (no assumption on which $L$ is likelier, because it will depend on many other factors like server processing speed, query size distribution for each request and others, but for calculation let the midpoint of the known range is the expected value): $$\text{cost}_1 = 1 \text{ probe}, \quad \text{served}_1 \approx T - \frac{T-1}{2} = \frac{T+1}{2}$$
• Case 2 ($1-t$): the first probe found $L\ge T$, so a second probe fires (Po2C fallback). Win or lose the cache, exactly $1$ request is served: $$\text{cost}_2 = 2 \text{ probes}, \quad \text{served}_2 = 1$$

Combine. Average probes and requests served per attempt, then take the ratio:

$$\mathbb{E}[P] \approx \frac{t\cdot 1 + (1-t)\cdot 2}{t\cdot\dfrac{T+1}{2} + (1-t)\cdot 1} = \frac{2-t}{1 + t\cdot\dfrac{T-1}{2}}$$

Comparison with Po2C. Po2C is the special case $t=0$ ($\mathbb{E}[P]=2$, always), Sticky-Lazy with any $t>0$ strictly reduces this, since raising $t$ shrinks the numerator and grows the denominator simultaneously. As $T\to\infty$ or $t\to 1$ (low contention, most probes land on safe servers), $\mathbb{E}[P] \to \frac{2}{T+1} \ll 2$. So Sticky-Lazy never does worse than Po2C, and the savings grow with both $T$ and the cache-hit rate $t$.

Round Robin's variance is unbounded under heterogeneous tasks

Round Robin assigns request $i$ to server $i \bmod N$, blind to load. If task durations $D_i$ heavy-tailed (e.g. $\text{Var}(D)=\infty$, as in many real workloads), a server can be unlucky enough to receive a run of long tasks purely by index coincidence, with no feedback mechanism to redirect future requests away from it. Formally, queue depth becomes a sum of i.i.d. heavy-tailed variables with no rebalancing term, so $\text{Var}(\text{queue depth}) \to \infty$ as task-duration variance grows. But in the case of Po2C and Sticky lazy protocol it actively avoids distribution of load over heavy loaded servers making the variance smaller.

---

4. Pros vs. Cons

✅ Pros

• Cuts probe traffic from a fixed 2 (Po2C) down to roughly $\frac{2}{T+1}$
• Same safety class as Po2C ($O(\ln\ln N)$), just shifted by a constant $T$.
• Self-healing: falls back to Po2C automatically the moment caching gets risky.
• One knob ($T$) to trade off bandwidth vs. balance, tuned per deployment.

❌ Cons

• Assumes uniform request cost , a string of expensive requests can overload a cached server before the credit runs out.
• Cache can go stale if load shifts from traffic outside the balancer's view.
• Slightly worse balance than Po2C within the threshold zone : a lighter server can sit idle while the sticky one keeps getting hit.
• Overhead is worst for small $N$, where the $+T$ term outweighs the tiny $\ln\ln N$ baseline.

Most of these are fixable — cost-weighted credits, a TTL on the cache, occasional re-probing, or just shrinking $T$ for small clusters etc.

5. Simulation Results

To validate the theory against something closer to production traffic, all four protocols were run through a discrete-event simulation: 50 servers, 30k requests, FCFS queues, diurnal traffic with burst windows, log-normal + Pareto-tailed request sizes, and heterogeneous server speeds — averaged over 5 seeded trials per workload (light, medium, heavy). Full simulation code →

Probes/Request	Peak Load

Wait Time	Response Time

Takeaways:

• Sticky-Lazy's probe rate stays well under Po2C's fixed 2 across all workloads — confirming the $\ge 1/T$ floor, with the safety net pushing it above the theoretical best case as expected.
• Peak load and latency for Sticky-Lazy track Po2C closely, both staying flat as Random/Round-Robin degrade sharply under heavier traffic — the predicted $+T$ gap is small and visible, not hidden.