#!/usr/bin/env python3
"""Averaging percentiles is meaningless, DDIA 2e Chapter 2.

Each machine behind a load balancer reports its own p99. The tempting move
is to average those per-machine p99s into a single "fleet p99." DDIA says
that is mathematically meaningless -- the right way to aggregate is to add
the histograms (i.e. pool the raw requests) and take the percentile of the
whole.

We build a fleet of 10 servers, each serving the same number of requests.
Nine are healthy; one is degraded (4x slower). We compute:

  - each server's own p99,
  - the NAIVE fleet p99 = the mean of those ten per-server p99s,
  - the TRUE fleet p99 = the p99 of all requests pooled together
    (== adding the histograms).

...and measure how far apart the naive and true numbers are, plus how much
of the real tail comes from the single degraded server.

Same lognormal shape as tail_latency.py. Pure standard library, fixed seed.
"""
import math
import random

SEED = 42
SERVERS = 10
PER_SERVER = 100_000  # requests per server; equal load balancing

# healthy server: median 10 ms, p99 ~100 ms (same shape as the other exercises)
MU_OK = math.log(10)
SIGMA = (math.log(100) - MU_OK) / 2.326  # ~0.99
# degraded server: 4x slower median (40 ms), same spread -> whole curve shifted up
MU_BAD = math.log(40)
DEGRADED = {0}  # server index 0 is the sick one


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)

    pooled = []              # (latency, is_degraded) for every request in the fleet
    per_server_p99 = []
    for s in range(SERVERS):
        mu = MU_BAD if s in DEGRADED else MU_OK
        bad = s in DEGRADED
        reqs = [rng.lognormvariate(mu, SIGMA) for _ in range(PER_SERVER)]
        reqs.sort()
        per_server_p99.append(pct(reqs, 99))
        pooled.extend((x, bad) for x in reqs)

    pooled.sort(key=lambda t: t[0])
    latencies = [x for x, _ in pooled]

    naive = sum(per_server_p99) / len(per_server_p99)  # average the p99s
    true = pct(latencies, 99)                          # p99 of the pool

    # Of the slowest 1% of all requests, how many came from the one bad server?
    tail = pooled[-(len(pooled) // 100):]
    tail_from_degraded = sum(1 for _, bad in tail if bad)
    tail_share = 100 * tail_from_degraded / len(tail)

    print(f"fleet of {SERVERS} servers, {PER_SERVER:,} requests each "
          f"({SERVERS * PER_SERVER:,} total); server 0 is degraded (4x slower):")
    print("    per-server p99 (ms):")
    for s, v in enumerate(per_server_p99):
        tag = "  <- degraded" if s in DEGRADED else ""
        print(f"        server {s}: {v:7.1f}{tag}")
    print()
    print(f"    NAIVE fleet p99  = mean(per-server p99s)     = {naive:7.1f} ms")
    print(f"    TRUE  fleet p99  = p99(all requests pooled)  = {true:7.1f} ms")
    off = 100 * (naive - true) / true
    print(f"    the averaged number is off by {off:+.1f}%  "
          f"({'under' if naive < true else 'over'}states the real tail)")
    print()
    print(f"    slowest 1% of all requests: {tail_share:.0f}% of them came from the")
    print(f"    single degraded server -- which is only {100 // SERVERS}% of the traffic.")


if __name__ == "__main__":
    main()