ЗАМЕР

bench/load-balancing/sim3.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

Скрипт

68 строк

import heapq, random, statistics
"""
Взвешенный round-robin и цена закреплённых сессий.

Модель та же, что в sim2.py: шестнадцать очередей FIFO, пуассоновский поток,
логнормальное время обработки. Файл самостоятельный — из sim2 ничего не
импортируется, чтобы его можно было запускать из любого каталога.
"""

def simulate2(algo, n=16, n_req=300_000, rho=0.80, seed=1, speed=None,
              weights=None, warmup=20_000, sessions=None):
    rng = random.Random(seed)
    speed = speed or [1.0] * n
    weights = weights or [1] * n
    lam = n * rho
    free_at = [0.0] * n; inflight = [0] * n
    done = []; t = 0.0; lat = []
    # развёрнутый список для взвешенного round-robin
    wheel = [k for k in range(n) for _ in range(weights[k])]
    wi = 0
    sticky = {}
    for i in range(n_req):
        t += rng.expovariate(lam)
        while done and done[0][0] <= t:
            _, s = heapq.heappop(done); inflight[s] -= 1
        if algo == "weighted-rr":
            s = wheel[wi % len(wheel)]; wi += 1
        elif algo == "sticky":
            # 5000 живых сессий, запрос принадлежит случайной; сессия закреплена
            sid = rng.randrange(sessions or 5000)
            if sid not in sticky:
                m = min(inflight)
                sticky[sid] = rng.choice([k for k in range(n) if inflight[k] == m])
            s = sticky[sid]
        elif algo == "least-conn":
            m = min(inflight)
            s = rng.choice([k for k in range(n) if inflight[k] == m])
        else:
            raise ValueError(algo)
        service = rng.lognormvariate(-0.36, 0.85) * speed[s]
        finish = max(t, free_at[s]) + service
        free_at[s] = finish; inflight[s] += 1
        heapq.heappush(done, (finish, s))
        if i >= warmup: lat.append(finish - t)
    lat.sort(); q = lambda p: lat[int(len(lat)*p)]
    return {"p50": q(.50), "p95": q(.95), "p99": q(.99)}

def avg(algo, **kw):
    rs = [simulate2(algo, seed=s, **kw) for s in range(5)]
    return {k: statistics.mean(r[k] for r in rs) for k in ("p50","p95","p99")}

slow = [4.0] + [1.0]*15
print("Один сервер вчетверо медленнее — что делает взвешенный round-robin")
for label, kw in [
    ("weighted-rr, вес угадан (1 против 4)", dict(algo="weighted-rr", speed=slow, weights=[1]+[4]*15)),
    ("weighted-rr, вес не менялся",          dict(algo="weighted-rr", speed=slow, weights=[1]*16)),
    ("weighted-rr, вес ошибочно занижен",    dict(algo="weighted-rr", speed=slow, weights=[1]+[2]*15)),
    ("least-conn (веса не нужны)",           dict(algo="least-conn", speed=slow)),
]:
    r = avg(**kw); print(f"  {label:38s} p50 {r['p50']:6.2f}  p95 {r['p95']:8.2f}  p99 {r['p99']:8.2f}")

print("\nЗакреплённые сессии на одинаковых серверах, загрузка 80%")
for ns in (5000, 500, 50):
    r = avg(algo="sticky", sessions=ns)
    print(f"  сессий {ns:>5}: p50 {r['p50']:6.2f}  p95 {r['p95']:7.2f}  p99 {r['p99']:7.2f}")
r = avg(algo="least-conn")
print(f"  без закрепления: p50 {r['p50']:6.2f}  p95 {r['p95']:7.2f}  p99 {r['p99']:7.2f}")