Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-16
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 growsstampede.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (67 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (17 lines)
1
3
2
single flight
4
6
10
4
4
3
2
early refresh
5
1
3
3
7
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (stampede.py)
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