ЗАМЕР

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

Скрипт

47 строк

"""
Тот же пул, но балансировщики читают ОБЩИЙ снимок состояния, который
обновляется раз в `refresh` единиц времени (так работают решения, где
метрики бэкендов собираются и раздаются с задержкой).
"""
import heapq, random, statistics

def simulate(algo, n=16, k_lb=16, n_req=300_000, rho=0.80, seed=1,
             refresh=0.5, warmup=20_000):
    rng = random.Random(seed)
    lam = n * rho
    free_at = [0.0] * n; truth = [0] * n
    snapshot = [0] * n; next_refresh = 0.0
    done = []; rr = 0; t = 0.0; lat = []
    for i in range(n_req):
        t += rng.expovariate(lam)
        while done and done[0][0] <= t:
            _, s = heapq.heappop(done); truth[s] -= 1
        if t >= next_refresh:
            snapshot = truth[:]                    # снимок устаревает до следующего
            next_refresh = t + refresh
        v = snapshot
        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; rr = (rr + 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
        heapq.heappush(done, (finish, s))
        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("Общий снимок состояния, обновляемый раз в `refresh`")
print(f"{'refresh':>9} {'алгоритм':>12} {'p50':>7} {'p95':>8} {'p99':>8}")
for refresh in (0.0, 0.1, 0.5, 2.0):
    for a in ("random", "round-robin", "least-conn", "p2c"):
        rs = [simulate(a, refresh=refresh, seed=s) for s in range(5)]
        m = [statistics.mean(x[j] for x in rs) for j in range(3)]
        print(f"{refresh:>9} {a:>12} {m[0]:7.2f} {m[1]:8.2f} {m[2]:8.2f}")