ЗАМЕР

bench/load-balancing/herd.py

Скрипт, которым получены числа в статье, и запись прогона. Файл читается на сборке из репозитория — это тот самый код, который запускали, а не его копия.

Цитируется в статье

/ru/system-design/traffic/load-balancing

Как запустить

python3 bins.py
python3 sim2.py
python3 sim3.py
python3 herd.py
python3 herd2.py
pip install dnspython && python3 dns2.py && python3 ecs.py

Запись прогона

Замеры для статьи «Балансировка нагрузки»

Два разных вида доказательств, и путать их нельзя.

Живые замеры DNS

dns2.py — ротация ответов: двадцать запросов подряд к трём доменам, печатает число адресов в ответе, диапазон TTL и распределение того, какой адрес оказался первым.

ecs.py — geoDNS через EDNS Client Subnet (RFC 7871): один и тот же вопрос задаётся с подстановкой четырёх клиентских подсетей, печатает адреса и SCOPE PREFIX-LENGTH из ответа.

Требует dnspython и сетевого доступа. Адреса у вас будут другие — они зависят от того, откуда вы спрашиваете и через какой резолвер. Воспроизводится не адрес, а scope: ноль означает «ответ годится всем», ненулевой — «ответ зависит от подсети». Именно на этом различии построен раздел про geoDNS.

Модель очередей

bins.py — чистая задача о шарах и корзинах: n шаров в n корзин, случайный выбор против выбора менее полной из двух. Пятнадцать прогонов на каждое n, рядом печатаются асимптотические оценки ln n / ln ln n и ln ln n / ln 2.

sim2.py — основная модель: шестнадцать бэкендов, каждый — одна очередь FIFO с одним обслуживающим прибором (G/G/1). Пуассоновский поток, логнормальное время обработки. Сравниваются random, round-robin, least-conn, least-time, p2c на одинаковых серверах, на кластере с медленным сервером и при загрузке 95%.

sim3.py — взвешенный round-robin с угаданным, отсутствующим и заниженным весом, и отдельно цена закреплённых сессий при 5000, 500 и 50 живых сессиях.

herd.py — несколько независимых балансировщиков, у каждого свои счётчики.

herd2.py — те же балансировщики, но с общим снимком состояния, устаревающим на refresh. Эти два скрипта дают главный результат статьи и отвечают на разные вопросы: первый показывает, что неполнота данных не ломает least connections, второй — что общая устаревшая ошибка ломает.

Модель отвечает на один вопрос — как распределение запросов влияет на ожидание в очередях. В ней нет сети и её задержек, разрывов соединений, проверок живости, кеша на бэкенде и ограничений по памяти. Числа воспроизводятся точно: зёрна фиксированы, первые 20 000 запросов из 300 000 отбрасываются, результат усредняется по пяти прогонам.

python3 bins.py
python3 sim2.py
python3 sim3.py
python3 herd.py
python3 herd2.py
pip install dnspython && python3 dns2.py && python3 ecs.py

Скрипт

49 строк

"""
Несколько независимых балансировщиков перед одним пулом бэкендов.

Каждый балансировщик видит ТОЛЬКО свои собственные запросы: он не знает,
что отправили соседи. Именно так устроены sidecar-прокси и несколько
ingress-контроллеров. Бэкенды по-прежнему одна очередь FIFO каждый.
"""
import heapq, random, statistics

def simulate(algo, n=16, k_lb=1, n_req=300_000, rho=0.80, seed=1, warmup=20_000):
    rng = random.Random(seed)
    lam = n * rho
    free_at = [0.0] * n
    truth = [0] * n                       # реальное число незавершённых
    view = [[0] * n for _ in range(k_lb)] # что видит каждый балансировщик
    done = []; rr = [0] * k_lb; t = 0.0; lat = []

    for i in range(n_req):
        t += rng.expovariate(lam)
        while done and done[0][0] <= t:
            _, s, lb = heapq.heappop(done)
            truth[s] -= 1; view[lb][s] -= 1
        lb = rng.randrange(k_lb)
        v = view[lb]
        if algo == "least-conn":
            m = min(v); s = rng.choice([x for x in range(n) if v[x] == m])
        elif algo == "p2c":
            a, b = rng.randrange(n), rng.randrange(n)
            s = a if v[a] <= v[b] else b
        elif algo == "round-robin":
            s = rr[lb]; rr[lb] = (rr[lb] + 1) % n
        else:
            s = rng.randrange(n)
        service = rng.lognormvariate(-0.36, 0.85)
        finish = max(t, free_at[s]) + service
        free_at[s] = finish
        truth[s] += 1; v[s] += 1
        heapq.heappush(done, (finish, s, lb))
        if i >= warmup: lat.append(finish - t)
    lat.sort(); q = lambda p: lat[int(len(lat)*p)]
    return q(.50), q(.95), q(.99)

print(f"{'балансировщиков':>16} {'алгоритм':>12} {'p50':>7} {'p95':>7} {'p99':>7}")
for k in (1, 4, 16, 64):
    for a in ("round-robin", "least-conn", "p2c"):
        rs = [simulate(a, k_lb=k, seed=s) for s in range(5)]
        m = [statistics.mean(x[j] for x in rs) for j in range(3)]
        print(f"{k:>16} {a:>12} {m[0]:7.2f} {m[1]:7.2f} {m[2]:7.2f}")