<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P118-cache-stampede/ | updated: 2026-10-16 -->

# P118 Cache stampede

One hot key with a time to live: naive, single flight, early refresh and serve stale, tick by tick and side by side, counting fetches, waiting and stale answers as the traffic grows.

EML-P project `projects/cache-stampede` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/cache-stampede` runs it and `eml project verify projects/cache-stampede` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: cache-stampede-single-flight (https://efficientnewlanguage.org/cases/276-cache-stampede-single-flight/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
2

2
fast
5

5
0
5
21
5
x
5
5

5
5
0
5
5
10
6

6
0
6
31
6
10

6
10
0
6
10
10
6
10
4

6
10
4
0
6
10
4
10
6
1
4
1
6
3
4
5
5
2
6
6
3
4
2
3
7
```

Screen:

```text
== Cache stampede ==
One hot key in a cache with a time to live. When it expires, every request that misses can start a fetch of its own from the origin.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 0
Pick a number from 1 to 7.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> x
Pick a number from 1 to 7.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 2
policy (naive, single flight, early refresh or serve stale)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 2
policy (naive, single flight, early refresh or serve stale)> fast
Type naive, single flight, early refresh or serve stale.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 0
Type a whole number from 1 to 20.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 21
Type a whole number from 1 to 20.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> x
Type a whole number from 1 to 20.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 5
every (1 to 9 ticks)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 5
every (1 to 9 ticks)> 0
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 5
every (1 to 9 ticks)> 10
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 0
Type a whole number from 1 to 30.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 31
Type a whole number from 1 to 30.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 0
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 10
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 
Cancelled.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 0
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 10
Type a whole number from 1 to 9.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 1
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 1
The margin must be shorter than the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 3
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 5
The margin must be shorter than the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 2
every (1 to 9 ticks)> 6
Traffic: 2 requests every 6 ticks, for 40 ticks.
Cache: a TTL of 10 ticks, a fetch of 4 ticks, early refresh within 2 ticks of the end of the TTL.
The cache starts empty, and a fetch that lands makes the value fresh for the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 3
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 2
Traffic: 2 requests every 6 ticks, for 40 ticks.
Cache: a TTL of 3 ticks, a fetch of 4 ticks, early refresh within 2 ticks of the end of the TTL.
The cache starts empty, and a fetch that lands makes the value fresh for the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 3
Over 40 ticks:
  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL
  naive                8             2       8            32             0              0
  single flight        4             1       8            32             0              0
  early refresh        7             1       2             8             0              0
  serve stale          4             1       2             8             6              5
  most past TTL: how many ticks the oldest stale answer had been expired.
Naive starts 8 fetches where single flight starts 4, with up to 2 running at once.
Early refresh starts at most 2 ticks before the end of the TTL, and a fetch takes 4 ticks, so the value expires before the new one lands.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 7
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
3
2
single flight
4
6
10
4
4
3
2
early refresh
5
1
3
3
7
```

Screen:

```text
== Cache stampede ==
One hot key in a cache with a time to live. When it expires, every request that misses can start a fetch of its own from the origin.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 1
Traffic: 5 requests every tick, for 40 ticks.
Cache: a TTL of 10 ticks, a fetch of 4 ticks, early refresh within 2 ticks of the end of the TTL.
The cache starts empty, and a fetch that lands makes the value fresh for the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 3
Over 40 ticks:
  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL
  naive               60            20      60           240             0              0
  single flight        3             1      60           150             0              0
  early refresh        4             1      50            95             0              0
  serve stale          3             1      20            50            40              3
  most past TTL: how many ticks the oldest stale answer had been expired.
Naive starts 60 fetches where single flight starts 3, with up to 20 running at once.
Each time the value expires, naive starts a fetch for every request until the first one lands: 20 fetches, where single flight starts 1.
Early refresh starts at most 2 ticks before the end of the TTL, and a fetch takes 4 ticks, so the value expires before the new one lands.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 2
policy (naive, single flight, early refresh or serve stale)> single flight
Tick by tick, single flight:
  tick  requests  hits  waited  stale  started  running
     0         5     0       5      0        1        1
     1         5     0       5      0        0        1
     2         5     0       5      0        0        1
     3         5     0       5      0        0        1
     4         5     5       0      0        0        0
     5         5     5       0      0        0        0
     6         5     5       0      0        0        0
     7         5     5       0      0        0        0
     8         5     5       0      0        0        0
     9         5     5       0      0        0        0
    10         5     5       0      0        0        0
    11         5     5       0      0        0        0
    12         5     5       0      0        0        0
    13         5     5       0      0        0        0
    14         5     0       5      0        1        1
    15         5     0       5      0        0        1
    16         5     0       5      0        0        1
    17         5     0       5      0        0        1
    18         5     5       0      0        0        0
    19         5     5       0      0        0        0
    20         5     5       0      0        0        0
    21         5     5       0      0        0        0
    22         5     5       0      0        0        0
    23         5     5       0      0        0        0
    24         5     5       0      0        0        0
    25         5     5       0      0        0        0
    26         5     5       0      0        0        0
    27         5     5       0      0        0        0
    28         5     0       5      0        1        1
    29         5     0       5      0        0        1
    30         5     0       5      0        0        1
    31         5     0       5      0        0        1
    32         5     5       0      0        0        0
    33         5     5       0      0        0        0
    34         5     5       0      0        0        0
    35         5     5       0      0        0        0
    36         5     5       0      0        0        0
    37         5     5       0      0        0        0
    38         5     5       0      0        0        0
    39         5     5       0      0        0        0
single flight: 3 fetches, at most 1 running at once; 60 requests waited, 150 ticks in all; 0 served stale.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 4
Fetches in 40 ticks, with a TTL of 10 ticks and a fetch of 4 ticks:
  requests every tick    naive  at once  single flight
                    1       12        4              3
                    2       24        8              3
                    5       60       20              3
                   10      120       40              3
                   20      240       80              3
  one request every      naive  at once  single flight
               1 tick       12        4              3
              2 ticks        6        2              3
              3 ticks        6        2              3
              4 ticks        3        1              3
              5 ticks        3        1              3
              6 ticks        3        1              3
              7 ticks        3        1              3
              8 ticks        3        1              3
              9 ticks        3        1              3
Naive and single flight run alike, tick by tick, once requests are 4 ticks apart, the time a fetch takes: then each fetch lands before the next request.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 6
TTL (1 to 30 ticks)> 10
fetch time (1 to 9 ticks)> 4
early refresh margin (1 to 9 ticks)> 4
Traffic: 5 requests every tick, for 40 ticks.
Cache: a TTL of 10 ticks, a fetch of 4 ticks, early refresh within 4 ticks of the end of the TTL.
The cache starts empty, and a fetch that lands makes the value fresh for the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 3
Over 40 ticks:
  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL
  naive               60            20      60           240             0              0
  single flight        3             1      60           150             0              0
  early refresh        4             1      20            50             0              0
  serve stale          3             1      20            50            40              3
  most past TTL: how many ticks the oldest stale answer had been expired.
Naive starts 60 fetches where single flight starts 3, with up to 20 running at once.
Each time the value expires, naive starts a fetch for every request until the first one lands: 20 fetches, where single flight starts 1.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 2
policy (naive, single flight, early refresh or serve stale)> early refresh
Tick by tick, early refresh:
  tick  requests  hits  waited  stale  started  running
     0         5     0       5      0        1        1
     1         5     0       5      0        0        1
     2         5     0       5      0        0        1
     3         5     0       5      0        0        1
     4         5     5       0      0        0        0
     5         5     5       0      0        0        0
     6         5     5       0      0        0        0
     7         5     5       0      0        0        0
     8         5     5       0      0        0        0
     9         5     5       0      0        0        0
    10         5     5       0      0        1        1
    11         5     5       0      0        0        1
    12         5     5       0      0        0        1
    13         5     5       0      0        0        1
    14         5     5       0      0        0        0
    15         5     5       0      0        0        0
    16         5     5       0      0        0        0
    17         5     5       0      0        0        0
    18         5     5       0      0        0        0
    19         5     5       0      0        0        0
    20         5     5       0      0        1        1
    21         5     5       0      0        0        1
    22         5     5       0      0        0        1
    23         5     5       0      0        0        1
    24         5     5       0      0        0        0
    25         5     5       0      0        0        0
    26         5     5       0      0        0        0
    27         5     5       0      0        0        0
    28         5     5       0      0        0        0
    29         5     5       0      0        0        0
    30         5     5       0      0        1        1
    31         5     5       0      0        0        1
    32         5     5       0      0        0        1
    33         5     5       0      0        0        1
    34         5     5       0      0        0        0
    35         5     5       0      0        0        0
    36         5     5       0      0        0        0
    37         5     5       0      0        0        0
    38         5     5       0      0        0        0
    39         5     5       0      0        0        0
early refresh: 4 fetches, at most 1 running at once; 20 requests waited, 50 ticks in all; 0 served stale.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 5
requests at a time (1 to 20)> 1
every (1 to 9 ticks)> 3
Traffic: 1 request every 3 ticks, for 40 ticks.
Cache: a TTL of 10 ticks, a fetch of 4 ticks, early refresh within 4 ticks of the end of the TTL.
The cache starts empty, and a fetch that lands makes the value fresh for the TTL.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 3
Over 40 ticks:
  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL
  naive                6             2       6            24             0              0
  single flight        3             1       6            15             0              0
  early refresh        4             1       5             8             0              0
  serve stale          3             1       2             5             4              4
  most past TTL: how many ticks the oldest stale answer had been expired.
Naive starts 6 fetches where single flight starts 3, with up to 2 running at once.
Each time the value expires, naive starts a fetch for every request until the first one lands: 2 fetches, where single flight starts 1.

1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit
choice> 7
Bye.
```

## Modules

### main.eml

```eml
# P118 cache stampede: one hot key with a TTL, four policies tick by tick
# and side by side, and the fetches as the traffic grows.
import stampede

def plain(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def pad(s, n):
    s => out
    while len(out) < n:
        out + " " => out
    return out

def lpad(s, n):
    s => out
    while len(out) < n:
        " " + out => out
    return out

def is_digits(s):
    if len(s) == 0:
        return False
    for c in s:
        if c < "0" or c > "9":
            return False
    return True

def ticks_text(n):
    if n == 1:
        return "1 tick"
    return str(n) + " ticks"

def requests_text(n):
    if n == 1:
        return "1 request"
    return str(n) + " requests"

def show(st):
    if st[1] == 1:
        ("Traffic: " + requests_text(st[0]) + " every tick, for " + str(st[5]) + " ticks.") ^0
    else:
        ("Traffic: " + requests_text(st[0]) + " every " + ticks_text(st[1]) + ", for " + str(st[5]) + " ticks.") ^0
    ("Cache: a TTL of " + ticks_text(st[2]) + ", a fetch of " + ticks_text(st[3]) + ", early refresh within " + ticks_text(st[4]) + " of the end of the TTL.") ^0
    "The cache starts empty, and a fetch that lands makes the value fresh for the TTL." ^0

def tick_by_tick(st):
    plain(input("policy (naive, single flight, early refresh or serve stale)> ")) => p
    if p == "":
        "Cancelled." ^0
        return
    False => known
    for x in stampede.policies():
        if x == p:
            True => known
    if not known:
        "Type naive, single flight, early refresh or serve stale." ^0
        return
    stampede.run(p, st[0], st[1], st[2], st[3], st[4], st[5]) => res
    ("Tick by tick, " + p + ":") ^0
    "  tick  requests  hits  waited  stale  started  running" ^0
    for row in res[0]:
        ("  " + lpad(str(row[0]), 4) + lpad(str(row[1]), 10) + lpad(str(row[2]), 6) + lpad(str(row[3]), 8) + lpad(str(row[4]), 7) + lpad(str(row[5]), 9) + lpad(str(row[6]), 9)) ^0
    totals_line(p, res[1])

def totals_line(p, x):
    (p + ": " + str(x[0]) + " fetches, at most " + str(x[1]) + " running at once; " + str(x[2]) + " requests waited, " + str(x[3]) + " ticks in all; " + str(x[4]) + " served stale.") ^0

def compare(st):
    ("Over " + str(st[5]) + " ticks:") ^0
    "  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL" ^0
    [] => results
    for p in stampede.policies():
        stampede.run(p, st[0], st[1], st[2], st[3], st[4], st[5])[1] => x
        results + [x] => results
        ("  " + pad(p, 13) + lpad(str(x[0]), 9) + lpad(str(x[1]), 14) + lpad(str(x[2]), 8) + lpad(str(x[3]), 14) + lpad(str(x[4]), 14) + lpad(str(x[5]), 15)) ^0
    "  most past TTL: how many ticks the oldest stale answer had been expired." ^0
    ("Naive starts " + str(results[0][0]) + " fetches where single flight starts " + str(results[1][0]) + ", with up to " + str(results[0][1]) + " running at once.") ^0
    0 => burst
    for t in [0:st[3] - 1]:
        if t % st[1] == 0:
            burst + st[0] => burst
    if st[1] <= st[2]:
        ("Each time the value expires, naive starts a fetch for every request until the first one lands: " + str(burst) + " fetches, where single flight starts 1.") ^0
    if st[4] < st[3]:
        ("Early refresh starts at most " + ticks_text(st[4]) + " before the end of the TTL, and a fetch takes " + ticks_text(st[3]) + ", so the value expires before the new one lands.") ^0

def more_traffic(st):
    ("Fetches in " + str(st[5]) + " ticks, with a TTL of " + ticks_text(st[2]) + " and a fetch of " + ticks_text(st[3]) + ":") ^0
    "  requests every tick    naive  at once  single flight" ^0
    for r in [1, 2, 5, 10, 20]:
        stampede.run("naive", r, 1, st[2], st[3], st[4], st[5])[1] => a
        stampede.run("single flight", r, 1, st[2], st[3], st[4], st[5])[1][0] => b
        ("  " + lpad(str(r), 19) + lpad(str(a[0]), 9) + lpad(str(a[1]), 9) + lpad(str(b), 15)) ^0
    "  one request every      naive  at once  single flight" ^0
    for g in [1:9]:
        stampede.run("naive", 1, g, st[2], st[3], st[4], st[5])[1] => a
        stampede.run("single flight", 1, g, st[2], st[3], st[4], st[5])[1][0] => b
        ("  " + lpad(ticks_text(g), 19) + lpad(str(a[0]), 9) + lpad(str(a[1]), 9) + lpad(str(b), 15)) ^0
    stampede.agree_gap(st[3], st[2], st[5]) => gap
    if gap == 0:
        "Naive and single flight run differently at every gap up to 9 ticks." ^0
    elif gap == st[3]:
        ("Naive and single flight run alike, tick by tick, once requests are " + ticks_text(gap) + " apart, the time a fetch takes: then each fetch lands before the next request.") ^0
    else:
        ("Naive and single flight run alike, tick by tick, once requests are " + ticks_text(gap) + " apart.") ^0

def ask_number(prompt, low, high):
    # the number typed, 0 to cancel, -1 when it is not from low to high
    plain(input(prompt)) => t
    if t == "":
        "Cancelled." ^0
        return 0
    if not is_digits(t) or len(t) > 2 or int(t) < low or int(t) > high:
        ("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
        return 0 - 1
    return int(t)

def traffic(st):
    ask_number("requests at a time (1 to 20)> ", 1, 20) => r
    if r <= 0:
        return st
    ask_number("every (1 to 9 ticks)> ", 1, 9) => g
    if g <= 0:
        return st
    [r, g, st[2], st[3], st[4], st[5]] => out
    show(out)
    return out

def cache(st):
    ask_number("TTL (1 to 30 ticks)> ", 1, 30) => ttl
    if ttl <= 0:
        return st
    ask_number("fetch time (1 to 9 ticks)> ", 1, 9) => f
    if f <= 0:
        return st
    ask_number("early refresh margin (1 to 9 ticks)> ", 1, 9) => m
    if m <= 0:
        return st
    if m >= ttl:
        "The margin must be shorter than the TTL." ^0
        return st
    [st[0], st[1], ttl, f, m, st[5]] => out
    show(out)
    return out

# [requests at a time, every so many ticks, TTL, fetch time, early margin, ticks]
[5, 1, 10, 4, 2, 40] => st

"== Cache stampede ==" ^0
"One hot key in a cache with a time to live. When it expires, every request that misses can start a fetch of its own from the origin." ^0
True => running
while running:
    "" ^0
    "1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit" ^0
    plain(input("choice> ")) => choice
    if choice == "1":
        show(st)
    elif choice == "2":
        tick_by_tick(st)
    elif choice == "3":
        compare(st)
    elif choice == "4":
        more_traffic(st)
    elif choice == "5":
        traffic(st) => st
    elif choice == "6":
        cache(st) => st
    elif choice == "7":
        False => running
    else:
        "Pick a number from 1 to 7." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import stampede

def plain(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def pad(s, n):
    out = s
    while len(out) < n:
        out = out + " "
    return out

def lpad(s, n):
    out = s
    while len(out) < n:
        out = " " + out
    return out

def is_digits(s):
    if len(s) == 0:
        return False
    for c in s:
        if c < "0" or c > "9":
            return False
    return True

def ticks_text(n):
    if n == 1:
        return "1 tick"
    return str(n) + " ticks"

def requests_text(n):
    if n == 1:
        return "1 request"
    return str(n) + " requests"

def show(st):
    if st[1] == 1:
        print("Traffic: " + requests_text(st[0]) + " every tick, for " + str(st[5]) + " ticks.")
    else:
        print("Traffic: " + requests_text(st[0]) + " every " + ticks_text(st[1]) + ", for " + str(st[5]) + " ticks.")
    print("Cache: a TTL of " + ticks_text(st[2]) + ", a fetch of " + ticks_text(st[3]) + ", early refresh within " + ticks_text(st[4]) + " of the end of the TTL.")
    print("The cache starts empty, and a fetch that lands makes the value fresh for the TTL.")

def tick_by_tick(st):
    p = plain(input("policy (naive, single flight, early refresh or serve stale)> "))
    if p == "":
        print("Cancelled.")
        return
    known = False
    for x in stampede.policies():
        if x == p:
            known = True
    if not known:
        print("Type naive, single flight, early refresh or serve stale.")
        return
    res = stampede.run(p, st[0], st[1], st[2], st[3], st[4], st[5])
    print("Tick by tick, " + p + ":")
    print("  tick  requests  hits  waited  stale  started  running")
    for row in res[0]:
        print("  " + lpad(str(row[0]), 4) + lpad(str(row[1]), 10) + lpad(str(row[2]), 6) + lpad(str(row[3]), 8) + lpad(str(row[4]), 7) + lpad(str(row[5]), 9) + lpad(str(row[6]), 9))
    totals_line(p, res[1])

def totals_line(p, x):
    print(p + ": " + str(x[0]) + " fetches, at most " + str(x[1]) + " running at once; " + str(x[2]) + " requests waited, " + str(x[3]) + " ticks in all; " + str(x[4]) + " served stale.")

def compare(st):
    print("Over " + str(st[5]) + " ticks:")
    print("  policy         fetches  most at once  waited  ticks waited  served stale  most past TTL")
    results = []
    for p in stampede.policies():
        x = stampede.run(p, st[0], st[1], st[2], st[3], st[4], st[5])[1]
        results = results + [x]
        print("  " + pad(p, 13) + lpad(str(x[0]), 9) + lpad(str(x[1]), 14) + lpad(str(x[2]), 8) + lpad(str(x[3]), 14) + lpad(str(x[4]), 14) + lpad(str(x[5]), 15))
    print("  most past TTL: how many ticks the oldest stale answer had been expired.")
    print("Naive starts " + str(results[0][0]) + " fetches where single flight starts " + str(results[1][0]) + ", with up to " + str(results[0][1]) + " running at once.")
    burst = 0
    for t in range(0, st[3]):
        if t % st[1] == 0:
            burst = burst + st[0]
    if st[1] <= st[2]:
        print("Each time the value expires, naive starts a fetch for every request until the first one lands: " + str(burst) + " fetches, where single flight starts 1.")
    if st[4] < st[3]:
        print("Early refresh starts at most " + ticks_text(st[4]) + " before the end of the TTL, and a fetch takes " + ticks_text(st[3]) + ", so the value expires before the new one lands.")

def more_traffic(st):
    print("Fetches in " + str(st[5]) + " ticks, with a TTL of " + ticks_text(st[2]) + " and a fetch of " + ticks_text(st[3]) + ":")
    print("  requests every tick    naive  at once  single flight")
    for r in [1, 2, 5, 10, 20]:
        a = stampede.run("naive", r, 1, st[2], st[3], st[4], st[5])[1]
        b = stampede.run("single flight", r, 1, st[2], st[3], st[4], st[5])[1][0]
        print("  " + lpad(str(r), 19) + lpad(str(a[0]), 9) + lpad(str(a[1]), 9) + lpad(str(b), 15))
    print("  one request every      naive  at once  single flight")
    for g in range(1, 10):
        a = stampede.run("naive", 1, g, st[2], st[3], st[4], st[5])[1]
        b = stampede.run("single flight", 1, g, st[2], st[3], st[4], st[5])[1][0]
        print("  " + lpad(ticks_text(g), 19) + lpad(str(a[0]), 9) + lpad(str(a[1]), 9) + lpad(str(b), 15))
    gap = stampede.agree_gap(st[3], st[2], st[5])
    if gap == 0:
        print("Naive and single flight run differently at every gap up to 9 ticks.")
    elif gap == st[3]:
        print("Naive and single flight run alike, tick by tick, once requests are " + ticks_text(gap) + " apart, the time a fetch takes: then each fetch lands before the next request.")
    else:
        print("Naive and single flight run alike, tick by tick, once requests are " + ticks_text(gap) + " apart.")

def ask_number(prompt, low, high):
    t = plain(input(prompt))
    if t == "":
        print("Cancelled.")
        return 0
    if not is_digits(t) or len(t) > 2 or int(t) < low or int(t) > high:
        print("Type a whole number from " + str(low) + " to " + str(high) + ".")
        return 0 - 1
    return int(t)

def traffic(st):
    r = ask_number("requests at a time (1 to 20)> ", 1, 20)
    if r <= 0:
        return st
    g = ask_number("every (1 to 9 ticks)> ", 1, 9)
    if g <= 0:
        return st
    out = [r, g, st[2], st[3], st[4], st[5]]
    show(out)
    return out

def cache(st):
    ttl = ask_number("TTL (1 to 30 ticks)> ", 1, 30)
    if ttl <= 0:
        return st
    f = ask_number("fetch time (1 to 9 ticks)> ", 1, 9)
    if f <= 0:
        return st
    m = ask_number("early refresh margin (1 to 9 ticks)> ", 1, 9)
    if m <= 0:
        return st
    if m >= ttl:
        print("The margin must be shorter than the TTL.")
        return st
    out = [st[0], st[1], ttl, f, m, st[5]]
    show(out)
    return out

st = [5, 1, 10, 4, 2, 40]
print("== Cache stampede ==")
print("One hot key in a cache with a time to live. When it expires, every request that misses can start a fetch of its own from the origin.")
running = True
while running:
    print("")
    print("1) settings  2) tick by tick  3) compare policies  4) more traffic  5) traffic  6) cache  7) quit")
    choice = plain(input("choice> "))
    if choice == "1":
        show(st)
    elif choice == "2":
        tick_by_tick(st)
    elif choice == "3":
        compare(st)
    elif choice == "4":
        more_traffic(st)
    elif choice == "5":
        st = traffic(st)
    elif choice == "6":
        st = cache(st)
    elif choice == "7":
        running = False
    else:
        print("Pick a number from 1 to 7.")
print("Bye.")
```

### stampede.eml

```eml
# P118 cache stampede - one hot key in a cache with a time to live (TTL).
# Requests arrive every few ticks; a fetch from the origin takes a few
# ticks, and when it lands the value is fresh for the TTL. As in the corpus
# case cache-stampede-single-flight, every request that misses while the
# value is being fetched starts a fetch of its own, unless the cache lets
# one fetch serve them all.
#
# The policies:
#   naive          every miss starts its own fetch and waits for it;
#   single flight  a miss joins the fetch already running, if there is one;
#   early refresh  like single flight, and a hit within the margin of the
#                  end of the TTL starts a fetch before the value expires;
#   serve stale    a miss is served the expired value while one fetch runs;
#                  only with no value at all does a request wait.

def policies():
    return ["naive", "single flight", "early refresh", "serve stale"]

def run(policy, r, g, ttl, fetch, margin, ticks):
    # [rows, totals]: a row per tick [tick, requests, hits, waited, stale,
    # fetches started, fetches running]; totals [fetches, most running at
    # once, requests that waited, ticks waited in all, served stale, most
    # ticks past the TTL]
    False => has_value
    0 => fresh_until
    [] => flights
    0 => fetches
    0 => most
    0 => waited
    0 => wait_total
    0 => stale
    0 => past
    [] => rows
    for t in [0:ticks - 1]:
        [] => left
        for d in flights:
            if d <= t:
                True => has_value
                if d + ttl > fresh_until:
                    d + ttl => fresh_until
            else:
                left + [d] => left
        left => flights
        0 => n
        0 => hits
        0 => w
        0 => s
        0 => started
        if t % g == 0:
            r => n
        for q in [1:n]:
            if has_value and t < fresh_until:
                hits + 1 => hits
                if policy == "early refresh" and len(flights) == 0 and fresh_until - t <= margin:
                    flights + [t + fetch] => flights
                    started + 1 => started
            elif policy == "naive":
                flights + [t + fetch] => flights
                started + 1 => started
                w + 1 => w
                wait_total + fetch => wait_total
            elif policy == "serve stale" and has_value:
                s + 1 => s
                if t - fresh_until > past:
                    t - fresh_until => past
                if len(flights) == 0:
                    flights + [t + fetch] => flights
                    started + 1 => started
            else:
                if len(flights) == 0:
                    flights + [t + fetch] => flights
                    started + 1 => started
                w + 1 => w
                wait_total + flights[0] - t => wait_total
        fetches + started => fetches
        waited + w => waited
        stale + s => stale
        if len(flights) > most:
            len(flights) => most
        rows + [[t, n, hits, w, s, started, len(flights)]] => rows
    return [rows, [fetches, most, waited, wait_total, stale, past]]

def agree_gap(fetch, ttl, ticks):
    # the smallest gap between single requests from which naive and single
    # flight run alike, tick by tick, at every larger gap to 9; 0 if none
    0 => found
    for g in [1:9]:
        run("naive", 1, g, ttl, fetch, 1, ticks)[0] == run("single flight", 1, g, ttl, fetch, 1, ticks)[0] => same
        if same and found == 0:
            g => found
        if not same:
            0 => found
    return found
```

Python projection of stampede.eml:

```python
def policies():
    return ["naive", "single flight", "early refresh", "serve stale"]

def run(policy, r, g, ttl, fetch, margin, ticks):
    has_value = False
    fresh_until = 0
    flights = []
    fetches = 0
    most = 0
    waited = 0
    wait_total = 0
    stale = 0
    past = 0
    rows = []
    for t in range(0, ticks):
        left = []
        for d in flights:
            if d <= t:
                has_value = True
                if d + ttl > fresh_until:
                    fresh_until = d + ttl
            else:
                left = left + [d]
        flights = left
        n = 0
        hits = 0
        w = 0
        s = 0
        started = 0
        if t % g == 0:
            n = r
        for q in range(1, n+1):
            if has_value and t < fresh_until:
                hits = hits + 1
                if policy == "early refresh" and len(flights) == 0 and fresh_until - t <= margin:
                    flights = flights + [t + fetch]
                    started = started + 1
            elif policy == "naive":
                flights = flights + [t + fetch]
                started = started + 1
                w = w + 1
                wait_total = wait_total + fetch
            elif policy == "serve stale" and has_value:
                s = s + 1
                if t - fresh_until > past:
                    past = t - fresh_until
                if len(flights) == 0:
                    flights = flights + [t + fetch]
                    started = started + 1
            else:
                if len(flights) == 0:
                    flights = flights + [t + fetch]
                    started = started + 1
                w = w + 1
                wait_total = wait_total + flights[0] - t
        fetches = fetches + started
        waited = waited + w
        stale = stale + s
        if len(flights) > most:
            most = len(flights)
        rows = rows + [[t, n, hits, w, s, started, len(flights)]]
    return [rows, [fetches, most, waited, wait_total, stale, past]]

def agree_gap(fetch, ttl, ticks):
    found = 0
    for g in range(1, 10):
        same = run("naive", 1, g, ttl, fetch, 1, ticks)[0] == run("single flight", 1, g, ttl, fetch, 1, ticks)[0]
        if same and found == 0:
            found = g
        if not same:
            found = 0
    return found
```

## README

# P118 - Cache stampede

One hot key in a cache with a time to live (TTL). When the value expires,
every request that misses can start a fetch of its own from the origin,
and a hot key has the most requests to miss.

- `main.eml` - the menu, the settings, one policy tick by tick, the four
  policies side by side, and the fetches as the traffic grows
- `stampede.eml` - the four policies over the ticks, and the gap at which
  naive and single flight run alike

How each part works:

- Requests arrive a few at a time, every so many ticks, for 40 ticks. A
  fetch takes a set number of ticks; when it lands, the value is fresh
  for the TTL. The cache starts empty.
- The four policies, as in the corpus case `cache-stampede-single-flight`:
  - naive: every miss starts its own fetch and waits for it;
  - single flight: a miss joins the fetch already running;
  - early refresh: like single flight, and a hit near the end of the TTL
    starts a fetch before the value expires;
  - serve stale: a miss gets the expired value while one fetch runs; only
    with no value at all does a request wait.
- Each time the value expires, naive starts a fetch for every request
  until the first one lands, where single flight starts one: at 5
  requests a tick and a fetch of 4 ticks, 20 fetches against 1, and 20
  running at once. This holds whenever a request comes at least once a
  TTL; the program says it only then.
- With single requests further apart, naive and single flight run alike,
  tick by tick, from a gap of exactly the fetch time: each fetch lands
  before the next request. Below that, naive has two or more running.
- No policy is free: single flight still makes requests wait, early
  refresh fetches before it must (and with a margin shorter than a fetch,
  the value expires before the new one lands), and serve stale answers
  with an expired value.

What is checked: menu choices 1 to 7; one of the four policies; 1 to 20
requests at a time, every 1 to 9 ticks; a TTL from 1 to 30 ticks, a fetch
and a margin from 1 to 9, the margin shorter than the TTL. An empty
answer cancels.

Sessions: `sessions/basic.in` gives:
- the settings and the four policies: 60 fetches for naive, 3 for single
  flight;
- single flight tick by tick, and the fetches as the traffic grows;
- an early refresh margin of 4, the fetch time: then requests wait only
  at the start, and early refresh tick by tick;
- 1 request every 3 ticks, and the four policies again.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- policies: a cancel and fast;
- traffic: a cancel, 0, 21 and x, then 5 with a cancel, 0 and 10;
- the cache: a cancel, 0 and 31, then a TTL of 10 with a cancel, 0 and
  10 for the fetch, then a fetch of 4 with a cancel, 0 and 10 for the
  margin, and margins of 1 for a TTL of 1 and 5 for a TTL of 3;
- 2 requests every 6 ticks with a TTL of 3, where the naive sentence is
  left out.

Built on the verified corpus case `cache-stampede-single-flight` (every
miss at an expiry recomputes the same value, and one shared fetch removes
the duplicates).