"""
Retry-storm simulation for "Resilience Patterns Cheat Sheet" (conceptualise.de).

    /opt/anaconda3/bin/python retry_storm_sim.py            # full run, updates the JSON
    /opt/anaconda3/bin/python retry_storm_sim.py --quick    # fewer seeds, prints only

What it models (deliberately small, so anyone can read and rerun it)
--------------------------------------------------------------------
Scenario 1: a synchronised retry storm.
  * N clients all lose their in-flight request at the same moment (t = 0), for
    example because a dependency restarted or a load balancer dropped every
    connection. Each client must get ONE successful response.
  * One server with a FIFO queue serves MU requests per second (10 ms ticks).
    Three server configurations are compared:
      bounded       queue limited to QMAX requests (0.5 s of work); arrivals
                    beyond it are rejected at once, for free (load shedding)
      unbounded     queue everything, never look at deadlines
      unbounded_dd  queue everything, but drop expired requests at dequeue
                    (deadline propagation)
    A rejected client sleeps per its retry policy and tries again.
  * A client gives up on an attempt after TIMEOUT seconds and then sleeps
    according to its retry policy before trying again. It retries until it
    succeeds or the horizon ends.
  * The server does NOT know the client gave up: it still spends capacity on
    expired requests ("wasted work"), unless the run sets deadline_drop=True,
    in which case expired requests are discarded for free at dequeue.
  * A request succeeds only if it is served within TIMEOUT of being sent.

Retry policies (sleep after the k-th failed attempt, k = 0, 1, 2, ...):
  none          0                                   (retry immediately)
  fixed         BASE
  expo          min(CAP, BASE * 2**k)               (no jitter)
  equal         v/2 + U(0, v/2),  v = min(CAP, BASE * 2**k)
  full          U(0, min(CAP, BASE * 2**k))
  decorrelated  min(CAP, U(BASE, prev * 3))         (prev starts at BASE)
These are the variants Marc Brooker described on the AWS Architecture Blog
(2015). Our server model differs from his (queue + client timeout instead of
optimistic-concurrency contention), so results are comparable in shape only.

Metrics, per policy, median over SEEDS random seeds:
  attempts_per_client   total attempts / N  (work amplification)
  t_all                 seconds until every client has succeeded (None = not
                        within HORIZON)
  wasted_pct            share of server capacity spent on expired requests
  peak_ratio            peak arrivals in any 100 ms window / capacity per 100 ms

Scenario 2 (analytical, checked by Monte Carlo): load amplification on the
bottom dependency when every one of L layers retries up to R times and the
bottom fails independently with probability p. Optional per-layer retry
budget (retries <= B * requests at that layer), the Google SRE 10% rule.

Everything is seeded and deterministic. Runtime: a few minutes on a laptop.
Pure standard library; no numpy needed.
"""
import json
import math
import os
import random
import statistics
import sys
from collections import deque

HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(os.path.dirname(os.path.dirname(HERE)))
SRC = os.path.join(ROOT, "marketing", "source", "blog", "resilience-patterns-cheat-sheet.json")

TICK = 0.01          # 10 ms
MU = 500.0           # server capacity, requests per second
TIMEOUT = 1.0        # client attempt timeout, seconds
BASE = 0.5           # retry base delay, seconds
CAP = 20.0           # retry delay cap, seconds
HORIZON = 120.0      # seconds simulated
SEEDS = 25

POLICIES = ["none", "fixed", "expo", "equal", "full", "decorrelated"]


def sleep_for(policy, k, prev, rng):
    v = min(CAP, BASE * 2 ** k)
    if policy == "none":
        return 0.0, prev
    if policy == "fixed":
        return BASE, prev
    if policy == "expo":
        return v, prev
    if policy == "equal":
        return v / 2 + rng.uniform(0, v / 2), prev
    if policy == "full":
        return rng.uniform(0, v), prev
    if policy == "decorrelated":
        s = min(CAP, rng.uniform(BASE, prev * 3))
        return s, s
    raise ValueError(policy)


def run(policy, n, seed, deadline_drop=False, series=False, qmax=None):
    rng = random.Random(seed)
    T = int(round(HORIZON / TICK))
    to = int(round(TIMEOUT / TICK))
    k_per_tick = MU * TICK                      # 5 per tick
    arrivals = [[] for _ in range(T + 1)]
    timeouts = [[] for _ in range(T + to + 2)]
    done = [False] * n
    cur = [0] * n                                # current attempt id
    fails = [0] * n
    prev = [BASE] * n
    waiting = [False] * n                        # an attempt is outstanding
    rejected = 0
    attempts = 0
    for c in range(n):                           # synchronised trigger at t = 0
        arrivals[0].append(c)
    q = deque()
    budget = 0.0
    served_total = wasted = 0
    remaining = n
    t_all = None
    per_tick_arr = [0] * (T + 1)
    per_tick_ok = [0] * (T + 1)
    q_peak = 0
    for t in range(T + 1):
        for c in arrivals[t]:
            if done[c]:
                continue
            cur[c] += 1
            attempts += 1
            per_tick_arr[t] += 1
            if qmax is not None and len(q) >= qmax:
                # bounded queue: shed the request at once (fast, free reject)
                rejected += 1
                s, prev[c] = sleep_for(policy, fails[c], prev[c], rng)
                fails[c] += 1
                nt = t + max(1, int(round(s / TICK)))
                if nt <= T:
                    arrivals[nt].append(c)
                continue
            waiting[c] = True
            q.append((c, cur[c], t))
            timeouts[t + to].append((c, cur[c]))
        q_peak = max(q_peak, len(q))
        budget += k_per_tick
        while q and budget >= 1.0:
            c, aid, sent = q.popleft()
            expired = t - sent > to
            if expired and deadline_drop:
                continue                         # free drop at dequeue
            budget -= 1.0
            served_total += 1
            if expired or done[c] or aid != cur[c]:
                wasted += 1
                continue
            done[c] = True
            per_tick_ok[t] += 1
            waiting[c] = False
            remaining -= 1
            if remaining == 0 and t_all is None:
                t_all = t * TICK
        if not q:
            budget = min(budget, 1.0)            # capacity does not bank up
        for c, aid in timeouts[t]:
            if done[c] or aid != cur[c] or not waiting[c]:
                continue
            waiting[c] = False
            s, prev[c] = sleep_for(policy, fails[c], prev[c], rng)
            fails[c] += 1
            nt = t + max(1, int(round(s / TICK)))
            if nt <= T:
                arrivals[nt].append(c)
        if t_all is not None and not q:
            break
    # peak arrivals per 100 ms window vs capacity per 100 ms
    w = int(round(0.1 / TICK))
    peak = max(sum(per_tick_arr[i:i + w]) for i in range(0, T + 1, w))
    out = {
        "attempts_per_client": attempts / n,
        "t_all": t_all,
        "wasted_pct": 100.0 * wasted / served_total if served_total else 0.0,
        "peak_ratio": peak / (MU * 0.1),
        "q_peak": q_peak,
        "rejected_per_client": rejected / n,
    }
    if series:
        # arrivals per 100 ms, as a multiple of capacity, first 60 s
        out["series"] = [round(sum(per_tick_arr[i:i + w]) / (MU * 0.1), 3)
                         for i in range(0, int(60 / TICK), w)]
        # cumulative share of clients served (%), sampled every 100 ms
        cum, acc = [], 0
        for i in range(0, int(60 / TICK), w):
            acc += sum(per_tick_ok[i:i + w])
            cum.append(round(100.0 * acc / n, 2))
        out["served_pct"] = cum
    return out


def med(xs):
    xs = [x for x in xs if x is not None]
    return statistics.median(xs) if xs else None


N_CLIENTS = 2000     # burst = 4 s of server capacity, 4x the client timeout
QMAX = 250           # bounded queue = 0.5 s of work (load shedding beyond it)

# name -> (qmax, deadline_drop)
CONFIGS = {
    "bounded": (QMAX, False),       # server sheds load beyond a short queue
    "unbounded": (None, False),     # server queues everything, no deadlines
    "unbounded_dd": (None, True),   # queues everything, drops expired at dequeue
}


def scenario1(seeds):
    res = {}
    for cname, (qm, dd) in CONFIGS.items():
        res[cname] = {}
        for pol in POLICIES:
            runs = [run(pol, N_CLIENTS, s, deadline_drop=dd, qmax=qm) for s in range(seeds)]
            unfinished = sum(1 for r in runs if r["t_all"] is None)
            res[cname][pol] = {
                "attempts_per_client": round(med([r["attempts_per_client"] for r in runs]), 2),
                "t_all_s": (round(med([r["t_all"] for r in runs]), 1)
                            if unfinished < len(runs) / 2 else None),
                "unfinished_runs": unfinished,
                "wasted_pct": round(med([r["wasted_pct"] for r in runs]), 1),
                "peak_ratio": round(med([r["peak_ratio"] for r in runs]), 1),
                "rejected_per_client": round(med([r["rejected_per_client"] for r in runs]), 2),
            }
            print(cname, pol, res[cname][pol])
    return res


def scenario1_series():
    """Per 100 ms, seed 0, bounded queue: arrivals as a multiple of capacity
    and cumulative % of clients served."""
    out = {"arrivals": {}, "served_pct": {}}
    for pol in ("none", "expo", "full", "decorrelated"):
        r = run(pol, N_CLIENTS, 0, qmax=QMAX, series=True)
        out["arrivals"][pol] = r["series"]
        out["served_pct"][pol] = r["served_pct"]
    return out


def scenario1_sweep(seeds):
    """Work amplification as the number of synchronised clients grows."""
    ns = [250, 500, 1000, 2000, 3000, 5000]
    out = {"n": ns}
    for pol in ("none", "expo", "full", "decorrelated"):
        out[pol] = [round(med([run(pol, n, s, qmax=QMAX)["attempts_per_client"]
                               for s in range(seeds)]), 2) for n in ns]
        print("sweep", pol, out[pol])
    return out


# ---------------------------------------------------------------- scenario 2
def layer_amp(p, R, budget=None):
    """Expected attempts on the layer below per call, and the failure
    probability this layer passes up.

    Without a budget: attempts = 1 + p + ... + p**R, failure up = p**(R+1).
    With a budget B (retries <= B x requests at this layer, steady state):
    if the retries the layer wants (attempts - 1) fit inside B it behaves as
    unbudgeted; otherwise only a fraction f = B / wanted of failed calls get
    their retry chain, so attempts = 1 + B and
    failure up = (1 - f) * p + f * p**(R+1). Approximation, checked by
    mc_amplification() below."""
    want = (1 - p ** (R + 1)) / (1 - p) if p < 1 else R + 1.0
    full_fail = p ** (R + 1)
    if budget is None or want - 1 <= budget:
        return want, full_fail
    f = budget / (want - 1)
    return 1 + budget, (1 - f) * p + f * full_fail


def amplification(p, R, L, budget=None):
    total, q = 1.0, p
    for _ in range(L):
        a, q = layer_amp(q, R, budget)
        total *= a
    return total


def mc_amplification(p, R, L, budget, n=20000, seed=7):
    """Monte Carlo check: L nested layers, each retrying up to R times; with a
    budget, each layer earns `budget` retry tokens per call it receives (token
    bucket capped at 10) and spends one per retry."""
    rng = random.Random(seed)
    calls_bottom = 0
    tokens = {lv: 0.0 for lv in range(1, L + 1)}

    def call(level):
        nonlocal calls_bottom
        if level == 0:
            calls_bottom += 1
            return rng.random() >= p
        if budget is not None:
            tokens[level] = min(tokens[level] + budget, 10.0)
        for k in range(R + 1):
            if k > 0 and budget is not None:
                if tokens[level] < 1.0:
                    return False
                tokens[level] -= 1.0
            if call(level - 1):
                return True
        return False

    for _ in range(n):
        call(L)
    return calls_bottom / n


def scenario2():
    ps = [round(x * 0.01, 2) for x in range(0, 101)]
    out = {"p": ps}
    cfg = {"r3_l1": (3, 1, None), "r3_l3": (3, 3, None),
           "r3_l3_budget10": (3, 3, 0.1), "r2_l2": (2, 2, None)}
    for k, (R, L, b) in cfg.items():
        out[k] = [round(amplification(p, R, L, b), 3) for p in ps]
    checks = {}
    for p in (0.1, 0.5, 0.9, 1.0):
        checks[str(p)] = {
            "r3_l3_formula": round(amplification(p, 3, 3), 2),
            "r3_l3_mc": round(mc_amplification(p, 3, 3, None, n=4000), 2),
            "r3_l3_budget10_formula": round(amplification(p, 3, 3, 0.1), 2),
            "r3_l3_budget10_mc": round(mc_amplification(p, 3, 3, 0.1, n=20000), 2),
        }
    out["mc_check"] = checks
    print("scenario2 @p=1:", {k: out[k][-1] for k in cfg})
    print("mc check", checks)
    return out


def main():
    quick = "--quick" in sys.argv
    seeds = 5 if quick else SEEDS
    result = {
        "params": {"tick_s": TICK, "capacity_rps": MU, "client_timeout_s": TIMEOUT,
                   "retry_base_s": BASE, "retry_cap_s": CAP, "horizon_s": HORIZON,
                   "clients": N_CLIENTS, "queue_limit": QMAX, "seeds": seeds},
        "scenario1": scenario1(seeds),
        "series": scenario1_series(),
        "sweep": scenario1_sweep(max(5, seeds // 2)),
        "scenario2": scenario2(),
    }
    if quick:
        return
    with open(SRC, encoding="utf-8") as f:
        d = json.load(f)
    d["sim"] = result
    with open(SRC, "w", encoding="utf-8") as f:
        json.dump(d, f, ensure_ascii=False, indent=1)
    print("updated", SRC)


if __name__ == "__main__":
    main()
