ЗАМЕР

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

Скрипт

24 строк

"""Шары по корзинам: случайный выбор против выбора лучшей из двух."""
import random, statistics, math

def run(n, strategy, seed):
    rng = random.Random(seed)
    bins = [0] * n
    for _ in range(n):                      # n шаров в n корзин
        if strategy == "random":
            bins[rng.randrange(n)] += 1
        else:                               # power of two choices
            a, b = rng.randrange(n), rng.randrange(n)
            bins[a if bins[a] <= bins[b] else b] += 1
    return max(bins)

print(f"{'n':>8} {'random':>18} {'p2c':>18}   ln n/ln ln n    ln ln n/ln 2")
for n in (100, 1_000, 10_000, 100_000):
    r = [run(n, "random", s) for s in range(15)]
    p = [run(n, "p2c", s) for s in range(15)]
    pred_r = math.log(n) / math.log(math.log(n))
    pred_p = math.log(math.log(n)) / math.log(2)
    print(f"{n:>8} {statistics.mean(r):>8.2f} ±{statistics.stdev(r):<5.2f}"
          f" {statistics.mean(p):>8.2f} ±{statistics.stdev(p):<5.2f}"
          f"   {pred_r:>10.2f}   {pred_p:>10.2f}")