"""Балансировка: почему случайный выбор двух бьёт круговой перебор. Модель.

ЧТО ЭТО ЗА ФАЙЛ. Симуляция четырёх правил распределения запросов по серверам —
без сети, без серверов и без балансировщика. Выводы верны настолько, насколько
верны допущения (ADR-017), и допущения названы здесь.

ДОПУЩЕНИЯ:
  1. Серверов 16, каждый обрабатывает свою очередь строго по одному запросу за
     раз. Очередь без предела.
  2. Запросы приходят пуассоновским потоком со средним интервалом, дающим
     загрузку 0,85 от суммарной ёмкости.
  3. Время обслуживания неоднородно: 90 % запросов по 10 мс, 10 % по 100 мс.
     Среднее 19 мс. Именно неоднородность — предмет замера: при одинаковых
     запросах круговой перебор сравнивается с лучшим правилом, и разницы
     между ними не остаётся (блок 3).
  4. Балансировщик решает в момент прихода запроса и не переигрывает решение;
     сама балансировка бесплатна — ни времени на опрос, ни устаревания данных.
  5. Ни отказов, ни повторов; серверы одинаковы по мощности.
  6. Зерно случайных чисел фиксировано, поэтому прогон воспроизводим.

ПРАВИЛА. round-robin — по кругу; random — равновероятно; least-work — тому из
ВСЕХ, кто освободится раньше всех; two-choices — двум случайным, из них тому,
кто освободится раньше.

ПОЧЕМУ least-work, А НЕ least-connections. Правило в модели выбирает по
точному моменту освобождения, то есть по остатку работы вместе с длительностью
уже выполняющегося запроса. Настоящий least-connections считает соединения и
не отличает соединение с десятимиллисекундным запросом от соединения со
стомиллисекундным — то есть слеп ровно к тому разбросу, на котором всё здесь и
держится. Поэтому строка least-work — это потолок правила, которому известно
всё, а не результат least-connections; называть её его именем значило бы
приписать настоящему правилу чужое число.

ЗАПУСК: python3 bench/balancing/choices.py
Вывод: runs/choices.txt
"""

import os
import random
import statistics
import sys

SERVERS = 16
REQUESTS = 200_000
SEED = 20260905
# Отдельное зерно для решений: иначе выбор сервера сцеплен с потоком запросов,
# и абсолютный p99 у random двигается при смене одного зерна на другое.
DECISION_SEED = 20260906

# Неоднородное обслуживание: короткие запросы и редкие длинные.
SHORT_MS, SHORT_SHARE = 10.0, 0.90
LONG_MS = 100.0
MEAN_SERVICE_MS = SHORT_MS * SHORT_SHARE + LONG_MS * (1 - SHORT_SHARE)

TARGET_LOAD = 0.85
MEAN_GAP_MS = MEAN_SERVICE_MS / (SERVERS * TARGET_LOAD)


def show(title: str) -> None:
    print()
    print(title)
    print("-" * len(title))


def row(label: str, value: object) -> None:
    print(f"  {label:<44} {value}")


def workload(rng: random.Random) -> list[tuple[float, float]]:
    """Один и тот же поток запросов для всех правил: (приход, обслуживание)."""
    stream = []
    now = 0.0
    for _ in range(REQUESTS):
        now += rng.expovariate(1 / MEAN_GAP_MS)
        service = SHORT_MS if rng.random() < SHORT_SHARE else LONG_MS
        stream.append((now, service))
    return stream


def simulate(rule: str, stream: list[tuple[float, float]], rng: random.Random) -> dict:
    """Прогон одного правила на готовом потоке.

    `free[i]` — момент, когда сервер i освободится. Ожидание запроса — это
    разница между этим моментом и его приходом: сколько он простоит в очереди
    до начала обслуживания.
    """
    free = [0.0] * SERVERS
    waits = []
    next_rr = 0

    for arrived, service in stream:
        if rule == "round-robin":
            chosen = next_rr
            next_rr = (next_rr + 1) % SERVERS
        elif rule == "random":
            chosen = rng.randrange(SERVERS)
        elif rule == "least-work":
            chosen = min(range(SERVERS), key=lambda i: free[i])
        elif rule == "two-choices":
            a = rng.randrange(SERVERS)
            b = rng.randrange(SERVERS)
            chosen = a if free[a] <= free[b] else b
        else:
            raise ValueError(rule)

        start = max(arrived, free[chosen])
        waits.append(start - arrived)
        free[chosen] = start + service

    waits.sort()
    return {
        "mean": statistics.fmean(waits),
        "p50": waits[len(waits) // 2],
        "p99": waits[int(len(waits) * 0.99)],
        "max": waits[-1],
    }


RULES = ("round-robin", "random", "least-work", "two-choices")


def main() -> None:
    print(f"Python {sys.version.split()[0]} · Linux {os.uname().release}")
    print("model, not a measurement: assumptions are in the docstring")
    print(f"{SERVERS} servers, {REQUESTS} requests, load {TARGET_LOAD:.2f}")
    print(f"service time {SHORT_MS:.0f} ms for {SHORT_SHARE:.0%}, {LONG_MS:.0f} ms for the rest")

    results = {}
    for rule in RULES:
        stream = workload(random.Random(SEED))
        results[rule] = simulate(rule, stream, random.Random(DECISION_SEED))

    show("1. THE SAME REQUESTS, FOUR RULES: TIME SPENT WAITING IN A QUEUE")
    print(f"  {'rule':>13} {'mean, ms':>10} {'p50, ms':>9} {'p99, ms':>9} {'worst, ms':>11}")
    for rule in RULES:
        r = results[rule]
        print(
            f"  {rule:>13} {r['mean']:>10.1f} {r['p50']:>9.1f}"
            f" {r['p99']:>9.1f} {r['max']:>11.1f}"
        )
    print()
    print("  Every rule sees the same arrivals and the same service times. What")
    print("  differs is only where each request was sent, and the tail moves by")
    print("  a factor, not by a percent.")

    show("2. HOW MUCH EACH RULE NEEDS TO KNOW")
    print(f"  {'rule':>13} {'servers inspected':>19} {'p99, ms':>9} {'p99 improvement':>17}")
    inspected = {"round-robin": 0, "random": 0, "least-work": SERVERS, "two-choices": 2}
    base = results["round-robin"]["p99"]
    for rule in RULES:
        r = results[rule]
        print(
            f"  {rule:>13} {inspected[rule]:>19} {r['p99']:>9.1f}"
            f" {base / r['p99'] if r['p99'] else 0:>16.1f}x"
        )
    print()
    print("  Improvement is round-robin's p99 divided by the rule's own, so")
    print("  below 1.0 means worse. Inspecting two servers out of sixteen")
    print("  recovers a large part of what inspecting all sixteen buys, while")
    print("  the cost of knowing grows with the fleet and the benefit does not.")

    show("3. WITH UNIFORM REQUESTS, ROUND-ROBIN TIES WITH THE BEST RULE")
    even = []
    rng = random.Random(SEED)
    now = 0.0
    for _ in range(REQUESTS):
        now += rng.expovariate(1 / MEAN_GAP_MS)
        even.append((now, MEAN_SERVICE_MS))
    for rule in RULES:
        r = simulate(rule, even, random.Random(DECISION_SEED))
        row(f"{rule}: p99 with even service, ms", f"{r['p99']:.1f}")
    print()
    print("  Same load, same mean service time, no spread - and round-robin")
    print("  now matches least-work exactly. When every request costs the same,")
    print("  'pick the one that frees up first' IS going round the circle:")
    print("  servers free up in the order they were given work. Random stays")
    print("  bad, and two-choices is now worse than round-robin: two random")
    print("  probes cannot beat a guaranteed sweep when there is nothing to")
    print("  choose between.")
    print()
    print("  So a benchmark built on uniform requests says round-robin is as")
    print("  good as anything. Block 1 says what happens when requests differ.")


if __name__ == "__main__":
    main()