#!/usr/bin/env python3
"""Tail-latency amplification, DDIA 2e Chapter 2.

A single backend call is "slow" only 1% of the time. An end-user request
fans out to N of those calls in parallel and can only return once the
SLOWEST has returned. How often is the end-user request slow?

We model one backend call's latency as a right-skewed (lognormal)
distribution: median ~10 ms, p99 ~100 ms. Then an end-user request that
fans out to N calls has latency = max(N draws). We measure what that does
to the percentiles, and to the fraction of requests that cross the
threshold only 1-in-100 individual calls cross.

Pure standard library, fixed seed -> reproducible.
"""
import math
import random
from statistics import quantiles

SEED = 42
POOL = 1_000_000      # single-call latency samples
REQUESTS = 200_000    # end-user requests simulated per fan-out N
FANOUTS = [1, 10, 100]

# lognormal tuned so median = exp(mu) = 10 ms, p99 = exp(mu + 2.326*sigma) = 100 ms
MU = math.log(10)
SIGMA = (math.log(100) - MU) / 2.326  # ~0.99


def pct(sorted_vals, p):
    """The p-th percentile (0..100) of an already-sorted list."""
    if p <= 0:
        return sorted_vals[0]
    if p >= 100:
        return sorted_vals[-1]
    k = (len(sorted_vals) - 1) * (p / 100)
    lo = math.floor(k)
    hi = math.ceil(k)
    if lo == hi:
        return sorted_vals[int(k)]
    return sorted_vals[lo] * (hi - k) + sorted_vals[hi] * (k - lo)


def main():
    rng = random.Random(SEED)

    # One big pool of individual backend-call latencies.
    pool = [rng.lognormvariate(MU, SIGMA) for _ in range(POOL)]
    pool.sort()

    s50 = pct(pool, 50)
    s90 = pct(pool, 90)
    s99 = pct(pool, 99)
    s999 = pct(pool, 99.9)
    threshold = s99  # the "slow" line only 1% of individual calls cross

    print(f"single backend call (n={POOL:,}, lognormal mu={MU:.3f} sigma={SIGMA:.3f}):")
    print(f"    p50 = {s50:7.1f} ms")
    print(f"    p90 = {s90:7.1f} ms")
    print(f"    p99 = {s99:7.1f} ms   <- 'slow' threshold: 1 in 100 calls cross it")
    print(f"    p999= {s999:7.1f} ms")
    print()
    print(f"end-user request = max of N parallel calls (n={REQUESTS:,} requests each):")
    print(f"    {'N':>4}  {'p50':>9}  {'p99':>9}  {'% slower than single-call p99':>30}")

    randrange = rng.randrange
    for n in FANOUTS:
        maxes = []
        slow = 0
        for _ in range(REQUESTS):
            m = 0.0
            for _ in range(n):
                x = pool[randrange(POOL)]
                if x > m:
                    m = x
            maxes.append(m)
            if m > threshold:
                slow += 1
        maxes.sort()
        p50 = pct(maxes, 50)
        p99 = pct(maxes, 99)
        frac = 100 * slow / REQUESTS
        print(f"    {n:>4}  {p50:7.1f}ms  {p99:7.1f}ms  {frac:29.1f}%")

    print()
    p_slow = 1 - (0.99 ** 100)
    print(f"analytic check: P(>=1 slow call | N=100) = 1 - 0.99^100 = {p_slow*100:.1f}%")


if __name__ == "__main__":
    main()