Deep Engineering

ЗАМЕР

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

Скрипт

75 строк
"""
Модель балансировщика.

Каждый бэкенд — одна очередь FIFO с одним обслуживающим прибором: запросы
ждут своей очереди и обрабатываются по одному. Это классическая модель
G/G/1, а не придуманная формула: никаких коэффициентов «деградации от
нагрузки» здесь нет, замедление под нагрузкой возникает само, из ожидания
в очереди.

Поток заявок пуассоновский, время обработки логнормальное (тяжёлый хвост —
типичная форма для веб-запросов). Балансировщик видит только то, что видел
бы настоящий: число незавершённых запросов на бэкенде и скользящее среднее
времени ответа. Будущего он не знает.
"""
import heapq, random, statistics

def simulate(algo, n=16, n_req=300_000, rho=0.80, seed=1, speed=None, warmup=20_000):
    rng = random.Random(seed)
    speed = speed or [1.0] * n            # множитель времени обработки
    mean_service = 1.0
    lam = n * rho / mean_service          # интенсивность потока
    free_at = [0.0] * n                   # когда прибор освободится
    inflight = [0] * n                    # принято, но не завершено
    ewma = [mean_service] * n
    done = []                             # (время завершения, сервер) — куча
    rr, t = 0, 0.0
    lat = []

    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 == "random":
            s = rng.randrange(n)
        elif algo == "round-robin":
            s = rr; rr = (rr + 1) % n
        elif algo == "least-conn":
            m = min(inflight)
            s = rng.choice([k for k in range(n) if inflight[k] == m])
        elif algo == "least-time":
            s = min(range(n), key=lambda k: inflight[k] * ewma[k])
        elif algo == "p2c":
            a, b = rng.randrange(n), rng.randrange(n)
            s = a if inflight[a] <= inflight[b] else b
        else:
            raise ValueError(algo)

        service = rng.lognormvariate(-0.36, 0.85) * speed[s]
        start = max(t, free_at[s])        # ждём, пока прибор освободится
        finish = start + service
        free_at[s] = finish
        inflight[s] += 1
        heapq.heappush(done, (finish, s))
        ewma[s] = 0.97 * ewma[s] + 0.03 * (finish - t)
        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 table(title, **kw):
    print(f"\n{title}")
    print(f"{'алгоритм':>13} {'p50':>7} {'p95':>7} {'p99':>7}")
    for a in ["random", "round-robin", "least-conn", "least-time", "p2c"]:
        rs = [simulate(a, seed=s, **kw) for s in range(5)]
        m = {k: statistics.mean(r[k] for r in rs) for k in ("p50", "p95", "p99")}
        print(f"{a:>13} {m['p50']:7.2f} {m['p95']:7.2f} {m['p99']:7.2f}")

table("Одинаковые серверы, 16 штук, загрузка 80%")
table("Один сервер из шестнадцати вчетверо медленнее", speed=[4.0] + [1.0] * 15)
table("Одинаковые серверы, загрузка 95%", rho=0.95)