Load Balancing — L4 বনাম L7 আর অ্যালগরিদমের গণিত

"""lb_sim.py -- round-robin vs least-connections vs consistent-hashing,
under a heterogeneous workload and a backend-removal event.
Two independent measurements:
  (1) load-distribution fairness: round-robin vs least-connections when
      request processing times vary significantly.
  (2) remapping fraction on a backend-set change: naive modulo hashing
      vs consistent (ring) hashing.
Every number below is computed by actually running this script.
"""
import hashlib
import random
import statistics

random.seed(7)

# ---------------------------------------------------------------------
# Part 1: load-distribution fairness under heterogeneous request times
# ---------------------------------------------------------------------
BACKENDS = ["b1", "b2", "b3", "b4", "b5"]
N_REQUESTS = 4000

# 80% of requests are "light" (short processing time), 20% are "heavy"
# (much longer) -- this is what makes round-robin's blindness to load
# visible: it hands out requests strictly in turn, with zero regard for
# how long each backend's *current* work will take.
def draw_duration():
    if random.random() < 0.8:
        return random.uniform(1.0, 3.0)      # light request
    return random.uniform(30.0, 50.0)        # heavy request

arrivals = [i * 0.5 for i in range(N_REQUESTS)]
durations = [draw_duration() for _ in range(N_REQUESTS)]

# --- round robin: pick backend purely by request index, ignore load ---
rr_busy = {b: 0.0 for b in BACKENDS}
for i, dur in enumerate(durations):
    b = BACKENDS[i % len(BACKENDS)]
    rr_busy[b] += dur

# --- least connections: an event-driven simulation ------------------
# active[b] = end-times for requests currently "in flight" on backend b.
# At each arrival, count how many end-times are still in the future
# (= active connections right now) and pick the fewest; tie-break on
# cumulative busy-time so far.
active = {b: [] for b in BACKENDS}
lc_busy = {b: 0.0 for b in BACKENDS}
for t, dur in zip(arrivals, durations):
    for b in BACKENDS:
        active[b] = [e for e in active[b] if e > t]
    b = min(BACKENDS, key=lambda x: (len(active[x]), lc_busy[x]))
    active[b].append(t + dur)
    lc_busy[b] += dur

def fairness_report(name, busy):
    vals = list(busy.values())
    mean = statistics.mean(vals)
    spread = (max(vals) - min(vals)) / mean * 100
    stdev = statistics.pstdev(vals)
    print(f"{name}")
    for b in BACKENDS:
        print(f"  {b}: total busy time = {busy[b]:8.1f}  ({busy[b]/mean*100:6.1f}% of mean)")
    print(f"  mean={mean:.1f}  stdev={stdev:.1f}  max-min spread={spread:.1f}% of mean")
    print()

print("=== (1) load fairness: round-robin vs least-connections ===")
print(f"{N_REQUESTS} requests, 80% light (1-3 units), 20% heavy (30-50 units), {len(BACKENDS)} backends\n")
fairness_report("round-robin", rr_busy)
fairness_report("least-connections", lc_busy)

# ---------------------------------------------------------------------
# Part 2: remapping cost on backend removal -- naive modulo vs ring
# ---------------------------------------------------------------------
def h(s):
    return int(hashlib.md5(s.encode()).hexdigest(), 16)

N_KEYS = 20000
KEYS = [f"client-{i}" for i in range(N_KEYS)]

def modulo_map(backends, keys):
    n = len(backends)
    return {k: backends[h(k) % n] for k in keys}

VNODES = 100
def ring_map(backends, keys):
    ring = sorted((h(f"{b}#{v}"), b) for b in backends for v in range(VNODES))
    points = [p for p, _ in ring]
    import bisect
    out = {}
    for k in keys:
        i = bisect.bisect(points, h(k)) % len(ring)
        out[k] = ring[i][1]
    return out

BEFORE = ["b1", "b2", "b3", "b4", "b5"]
AFTER = ["b1", "b2", "b3", "b5"]   # b4 removed mid-simulation

mod_before = modulo_map(BEFORE, KEYS)
mod_after = modulo_map(AFTER, KEYS)
ring_before = ring_map(BEFORE, KEYS)
ring_after = ring_map(AFTER, KEYS)

mod_moved = sum(1 for k in KEYS if mod_before[k] != mod_after[k]) / N_KEYS * 100
ring_moved = sum(1 for k in KEYS if ring_before[k] != ring_after[k]) / N_KEYS * 100

print("=== (2) remapping cost when a backend is removed (5 -> 4 backends) ===")
print(f"{N_KEYS} keys, naive modulo hash(key) % N  vs  consistent-hash ring ({VNODES} vnodes/backend)\n")
print(f"naive modulo hashing : {mod_moved:5.1f}% of keys remapped to a different backend")
print(f"consistent hash ring : {ring_moved:5.1f}% of keys remapped to a different backend")
print(f"theory check          : ring remap should be close to 1/{len(BEFORE)} = {100/len(BEFORE):.1f}%")

প্রকৃত চালিয়ে পাওয়া output (deterministic — random.seed(7)-এর কারণে হুবহু এটাই আসবে):

=== (1) load fairness: round-robin vs least-connections ===
4000 requests, 80% light (1-3 units), 20% heavy (30-50 units), 5 backends

round-robin
  b1: total busy time =   7539.1  (  99.0% of mean)
  b2: total busy time =   7119.7  (  93.5% of mean)
  b3: total busy time =   8438.6  ( 110.8% of mean)
  b4: total busy time =   7978.0  ( 104.8% of mean)
  b5: total busy time =   6996.5  (  91.9% of mean)
  mean=7614.4  stdev=537.4  max-min spread=18.9% of mean

least-connections
  b1: total busy time =   7597.3  (  99.8% of mean)
  b2: total busy time =   7622.8  ( 100.1% of mean)
  b3: total busy time =   7601.6  (  99.8% of mean)
  b4: total busy time =   7625.9  ( 100.2% of mean)
  b5: total busy time =   7624.4  ( 100.1% of mean)
  mean=7614.4  stdev=12.3  max-min spread=0.4% of mean

=== (2) remapping cost when a backend is removed (5 -> 4 backends) ===
20000 keys, naive modulo hash(key) % N  vs  consistent-hash ring (100 vnodes/backend)

naive modulo hashing :  79.8% of keys remapped to a different backend
consistent hash ring :  21.0% of keys remapped to a different backend
theory check          : ring remap should be close to 1/5 = 20.0%

দুইটা ফলাফলই এই লেসনের কেন্দ্রীয় দাবি সংখ্যায় প্রমাণ করে। প্রথম অংশে: গড়-busy-time দুই অ্যালগরিদমেই সমান (৭৬১৪.৪, কারণ মোট কাজের পরিমাণ একই), কিন্তু spread-এ আকাশ-পাতাল ফারাক — round-robin-এ stdev ৫৩৭.৪ (max-min spread প্রায় ১৮.৯%), least-connections-এ stdev মাত্র ১২.৩ (spread ০.৪%, প্রায় নিখুঁত সমান)। round-robin ঠিক ততটাই request সংখ্যায় সমান ভাগ করেছে যতটা তার কথা — কিন্তু heavy/light request কোন backend-এ পড়বে সেটা নিছক পালার কপাল, তাই busy-time অসম। দ্বিতীয় অংশে: naive mod-hash ৭৯.৮% key সরিয়েছে একটা মাত্র backend সরানোয়, আর ring মাত্র ২১.০% সরিয়েছে — theory-র প্রত্যাশিত ১/৫ = ২০%-এর প্রায় হুবহু কাছাকাছি (vnode-placement-এর randomness-এর কারণে সামান্য ওঠানামা স্বাভাবিক)।