Project P107
Retry planner
Waits between retries under fixed, exponential, full jitter, equal jitter and decorrelated policies; a crowd of clients coming back after an outage, with the busiest slot under each; and a job runner whose ledger checks that its finally block ran on every attempt.
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
How long to wait between retries, under five policies. The program shows one client's waits, a crowd of clients coming back after an outage, and a job runner whose ledger checks its own retry loop.
main.eml- the menu, one client's schedule, the crowd table, retries over time, jobs with a ledger, and the settingsretry.eml- the random numbers, the five policies, the crowd, the busiest slot, and the job runner with its ledger
How each part works:
- Waits are whole milliseconds, for retries 1, 2, ...: - fixed: the first wait every time; - exponential: the first wait doubled each time, up to the longest; - full jitter: a random wait from 0 to the exponential one; - equal jitter: half the exponential wait, plus a random wait up to the other half; - decorrelated: a random wait from the first wait to three times the last one, up to the longest.
The random numbers come from a linear congruential generator seeded by the seed and the client's number. - The crowd: every client fails when the outage starts, at 0 ms, and a retry at or after its end gets through. Retries are counted per 100 ms. As in the corpus case backoff-thundering-herd, fixed and exponential waits are the same for every client, so each round of retries lands in a single slot. A wait that depends on the client spreads each round over the whole wait. That lowers the busiest slot only when the waits are long against the slot. In the session, with a first wait of 100 ms, full jitter's busiest slot holds more than exponential's. - Full and equal jitter wait on average about a half and three quarters of the exponential wait. So with the same attempts, more clients can give up before the service is back. - Jobs with a ledger, as in the corpus case retry-with-backoff-ledger: a job fails a given number of times, or cannot be retried at all. Every attempt is counted inside a try whose finally block counts again. A job that cannot be retried stops at once, and one that runs out of attempts raises. The ledger checks that finally ran on every attempt: after a return, after a raise and after a failure alike.
What is checked: menu choices 1 to 6; a policy name; a client number; jobs written as name:failures or name:fatal, up to 8; settings in their ranges (first wait 1 to 10,000 ms, longest from the first up to 600,000, attempts 2 to 12, clients 1 to 1,000, outage up to 600,000 ms, seed up to 999,999). An empty answer cancels.
Sessions: sessions/basic.in gives: - client 1 under exponential, full jitter and decorrelated waits, and client 2 under full jitter; - the crowd of 200: the busiest slot holds 200 under fixed and exponential waits, and 28, 44 and 15 under the other three; - retries over time, second by second, for exponential and equal jitter; - four jobs: one done at once, one after two failures, one that gives up, one that cannot be retried, with the ledger; - a first wait of 100 ms and the crowd again, where full jitter's busiest slot is worse than exponential's.
sessions/bad-input.in gives: - menu choices 0 and x; - a cancel, a policy slow, client numbers 0 and 201, then a cancel; - a cancel for retries over time; - jobs: a cancel, no colon, a word for the failures, no name, nine jobs; - settings: first waits 0 and 10,001, a longest wait below the first, one attempt, and cancels.
Built on the verified corpus cases backoff-thundering-herd (the same waits for every client bring them back together) and retry-with-backoff-ledger (a retry loop audited by counting its finally blocks).
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== Retry planner ==
Waits between retries under five policies, a crowd coming back after an outage, and a job runner whose ledger checks itself.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 0
Pick a number from 1 to 6.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> x
Pick a number from 1 to 6.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> slow
Type fixed, exponential, full jitter, equal jitter or decorrelated.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> exponential
client number (1 to 200)> 0
Type a whole number from 1 to 200.
client number (1 to 200)> 201
Type a whole number from 1 to 200.
client number (1 to 200)>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 3
policy (fixed, exponential, full jitter, equal jitter or decorrelated)>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs> alpha
Type each job as name:number or name:fatal.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs> alpha:x
Type each job as name:number or name:fatal.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs> :3
Type each job as name:number or name:fatal.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs> a:1 b:1 c:1 d:1 e:1 f:1 g:1 h:1 i:1
Up to 8 jobs.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 5
first wait in ms (1 to 10000)> 0
Type a whole number from 1 to 10000.
first wait in ms (1 to 10000)> 10001
Type a whole number from 1 to 10000.
first wait in ms (1 to 10000)> 500
longest wait in ms (500 to 600000)> 499
Type a whole number from 500 to 600000.
longest wait in ms (500 to 600000)>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 5
first wait in ms (1 to 10000)> 1000
longest wait in ms (1000 to 600000)> 16000
attempts per client (2 to 12)> 1
Type a whole number from 2 to 12.
attempts per client (2 to 12)>
Cancelled.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 6
Bye.
What was typed (35 lines)
0
x
1
1
slow
1
exponential
0
201
3
4
4
alpha
4
alpha:x
4
:3
4
a:1 b:1 c:1 d:1 e:1 f:1 g:1 h:1 i:1
5
0
10001
500
499
5
1000
16000
1
6
basic
interpreter: byte-equal== Retry planner ==
Waits between retries under five policies, a crowd coming back after an outage, and a job runner whose ledger checks itself.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> exponential
client number (1 to 200)> 1
Client 1, exponential: attempt 1 at 0 ms, then
attempt 2 after 1000 ms, at 1000 ms
attempt 3 after 2000 ms, at 3000 ms
attempt 4 after 4000 ms, at 7000 ms
attempt 5 after 8000 ms, at 15000 ms
attempt 6 after 16000 ms, at 31000 ms
In all 31000 ms before the last attempt.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> full jitter
client number (1 to 200)> 1
Client 1, full jitter: attempt 1 at 0 ms, then
attempt 2 after 152 ms, at 152 ms
attempt 3 after 1365 ms, at 1517 ms
attempt 4 after 2280 ms, at 3797 ms
attempt 5 after 5697 ms, at 9494 ms
attempt 6 after 4600 ms, at 14094 ms
In all 14094 ms before the last attempt.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> full jitter
client number (1 to 200)> 2
Client 2, full jitter: attempt 1 at 0 ms, then
attempt 2 after 178 ms, at 178 ms
attempt 3 after 1306 ms, at 1484 ms
attempt 4 after 1622 ms, at 3106 ms
attempt 5 after 122 ms, at 3228 ms
attempt 6 after 274 ms, at 3502 ms
In all 3502 ms before the last attempt.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 1
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> decorrelated
client number (1 to 200)> 1
Client 1, decorrelated: attempt 1 at 0 ms, then
attempt 2 after 1183 ms, at 1183 ms
attempt 3 after 2524 ms, at 3707 ms
attempt 4 after 4995 ms, at 8702 ms
attempt 5 after 12745 ms, at 21447 ms
attempt 6 after 16000 ms, at 37447 ms
In all 37447 ms before the last attempt.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 2
200 clients fail at 0 ms; the service is back at 10000 ms; each tries 6 times at most. Retries counted per 100 ms:
policy retries most in a slot the slot from all through by gave up
fixed 1000 200 1000 ms - 200
exponential 800 200 1000 ms 15000 ms 0
full jitter 962 28 400 ms 24563 ms 36
equal jitter 848 44 600 ms 25666 ms 0
decorrelated 770 15 2400 ms 25330 ms 19
Fixed and exponential waits are the same for every client, so each round of retries lands in a single slot. A wait that depends on the client spreads each round over the whole wait, which lowers the busiest slot only when the waits are long against the slot: here 28, 44 and 15 against 200.
Full and equal jitter wait on average about a half and three quarters of the exponential wait, so with the same attempts 36 and 0 clients gave up, against 0 with exponential waits.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 3
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> exponential
exponential: retries in each second, # for every 5:
1000 ms 200 ########################################
3000 ms 200 ########################################
7000 ms 200 ########################################
15000 ms 200 ########################################
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 3
policy (fixed, exponential, full jitter, equal jitter or decorrelated)> equal jitter
equal jitter: retries in each second, # for every 5:
0 ms 200 ########################################
1000 ms 53 ###########
2000 ms 147 ##############################
3000 ms 4 #
4000 ms 72 ###############
5000 ms 96 ####################
6000 ms 28 ######
8000 ms 11 ###
9000 ms 37 ########
10000 ms 36 ########
11000 ms 50 ##########
12000 ms 42 #########
13000 ms 21 #####
14000 ms 3 #
16000 ms 1 #
17000 ms 4 #
18000 ms 8 ##
19000 ms 6 ##
20000 ms 7 ##
21000 ms 4 #
22000 ms 2 #
23000 ms 5 #
24000 ms 6 ##
25000 ms 5 #
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 4
Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.
jobs> alpha:0 bravo:2 charlie:9 delta:fatal
alpha: done on attempt 1
bravo: done on attempt 3
charlie: gave up after 6 attempts
delta: cannot be retried
Ledger:
alpha attempt 1: done
bravo attempt 1: failed, retry after 1000 ms
bravo attempt 2: failed, retry after 2000 ms
bravo attempt 3: done
charlie attempt 1: failed, retry after 1000 ms
charlie attempt 2: failed, retry after 2000 ms
charlie attempt 3: failed, retry after 4000 ms
charlie attempt 4: failed, retry after 8000 ms
charlie attempt 5: failed, retry after 16000 ms
charlie attempt 6: failed, no attempts left
delta attempt 1: cannot be retried, stopped
Attempts 11: 2 done, 9 failed. The finally block ran 11 times. Waited 34000 ms in all.
Jobs done, given up, refused: 2, 1, 1.
Every attempt was counted once, and finally ran on each - after a return, after a raise, and after a failure alike.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 5
first wait in ms (1 to 10000)> 100
longest wait in ms (100 to 600000)> 16000
attempts per client (2 to 12)> 6
clients (1 to 1000)> 200
outage in ms (0 to 600000)> 10000
seed (0 to 999999)> 7
First wait 100 ms, longest 16000 ms, 6 attempts, 200 clients, outage 10000 ms, seed 7.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 2
200 clients fail at 0 ms; the service is back at 10000 ms; each tries 6 times at most. Retries counted per 100 ms:
policy retries most in a slot the slot from all through by gave up
fixed 1000 200 100 ms - 200
exponential 1000 200 100 ms - 200
full jitter 1000 250 0 ms - 200
equal jitter 1000 195 0 ms - 200
decorrelated 1000 119 200 ms 20286 ms 192
Fixed and exponential waits are the same for every client, so each round of retries lands in a single slot. A wait that depends on the client spreads each round over the whole wait, which lowers the busiest slot only when the waits are long against the slot: here 250, 195 and 119 against 200.
1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit
choice> 6
Bye.
What was typed (28 lines)
1
exponential
1
1
full jitter
1
1
full jitter
2
1
decorrelated
1
2
3
exponential
3
equal jitter
4
alpha:0 bravo:2 charlie:9 delta:fatal
5
100
16000
6
200
10000
7
2
6
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# P107 retry planner: one client's waits under five policies, a crowd of
# clients coming back after an outage, and jobs run with a ledger that
# checks the retry loop.
import retry
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 number(s, most):
if len(s) == 0 or len(s) > most:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def lpad(s, n):
while len(s) < n:
" " + s => s
return s
def ask(prompt, low, high):
while True:
plain(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => a
if a == "":
return -1
number(a, 7) => n
if n >= low and n <= high:
return n
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
def policies():
return ["fixed", "exponential", "full jitter", "equal jitter", "decorrelated"]
def ask_policy():
plain(input("policy (fixed, exponential, full jitter, equal jitter or decorrelated)> ")) => p
if p == "":
return ""
for q in policies():
if q == p:
return p
"Type fixed, exponential, full jitter, equal jitter or decorrelated." ^0
return "!"
def one_client(cfg):
ask_policy() => p
if p == "":
"Cancelled." ^0
return
if p == "!":
return
ask("client number", 1, cfg[3]) => c
if c == -1:
"Cancelled." ^0
return
("Client " + str(c) + ", " + p + ": attempt 1 at 0 ms, then") ^0
0 => t
2 => n
for w in retry.waits(p, cfg, c):
t + w => t
(" attempt " + lpad(str(n), 2) + " after " + lpad(str(w), 6) + " ms, at " + lpad(str(t), 7) + " ms") ^0
n + 1 => n
("In all " + str(t) + " ms before the last attempt.") ^0
def crowd(cfg):
(str(cfg[3]) + " clients fail at 0 ms; the service is back at " + str(cfg[4]) + " ms; each tries " + str(cfg[2]) + " times at most. Retries counted per " + str(cfg[6]) + " ms:") ^0
" policy retries most in a slot the slot from all through by gave up" ^0
{} => gave
{} => top
for p in policies():
retry.herd(p, cfg) => h
h[4] => gave[p]
retry.peak(h[0])[0] => top[p]
retry.peak(h[0]) => m
"-" => last
if h[3] >= 0:
str(h[3]) + " ms" => last
(" " + pad(p, 14) + lpad(str(h[1]), 9) + lpad(str(m[0]), 17) + lpad(str(m[1] * cfg[6]) + " ms", 16) + lpad(last, 17) + lpad(str(h[4]), 10)) ^0
("Fixed and exponential waits are the same for every client, so each round of retries lands in a single slot. A wait that depends on the client spreads each round over the whole wait, which lowers the busiest slot only when the waits are long against the slot: here " + str(top["full jitter"]) + ", " + str(top["equal jitter"]) + " and " + str(top["decorrelated"]) + " against " + str(top["exponential"]) + ".") ^0
if gave["full jitter"] > gave["exponential"] or gave["equal jitter"] > gave["exponential"]:
("Full and equal jitter wait on average about a half and three quarters of the exponential wait, so with the same attempts " + str(gave["full jitter"]) + " and " + str(gave["equal jitter"]) + " clients gave up, against " + str(gave["exponential"]) + " with exponential waits.") ^0
def histogram(cfg):
ask_policy() => p
if p == "":
"Cancelled." ^0
return
if p == "!":
return
[cfg[0], cfg[1], cfg[2], cfg[3], cfg[4], cfg[5], 1000] => by_second
retry.herd(p, by_second) => h
retry.peak(h[0]) => m
(p + ": retries in each second, # for every " + str(scale(m[0])) + ":") ^0
for i in [0:len(h[0]) - 1]:
if h[0][i] > 0:
"" => bar
for k in [1:bars(h[0][i], m[0])]:
bar + "#" => bar
(" " + lpad(str(i * 1000), 7) + " ms " + lpad(str(h[0][i]), 5) + " " + bar) ^0
def scale(most):
# one # stands for this many retries, so the longest bar fits in 40
1 => s
while most > 40 * s:
s + 1 => s
return s
def bars(n, most):
scale(most) => s
return int((n + s - 1 - (n + s - 1) % s) / s)
def jobs(cfg):
"Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal." ^0
plain(input("jobs> ")) => t
if t == "":
"Cancelled." ^0
return
[] => list
"" => w
for c in t + " ":
if c == " ":
if w != "":
list + [w] => list
"" => w
else:
w + c => w
[] => parsed
for item in list:
-1 => colon
for i in [0:len(item) - 1]:
if colon == -1 and item[i] == ":":
i => colon
if colon < 1 or colon == len(item) - 1:
"Type each job as name:number or name:fatal." ^0
return
item[0:colon] => name
item[colon + 1:len(item)] => rest
if rest == "fatal":
parsed + [[name, 0, True]] => parsed
else:
number(rest, 3) => n
if n < 0:
"Type each job as name:number or name:fatal." ^0
return
parsed + [[name, n, False]] => parsed
if len(parsed) > 8:
"Up to 8 jobs." ^0
return
retry.Ledger() => ledger
0 => done
0 => gave_up
0 => refused
for job in parsed:
try:
retry.run_job(ledger, cfg, job[0], job[1], job[2]) => result
done + 1 => done
(" " + result) ^0
except TypeError as e:
refused + 1 => refused
(" " + str(e)) ^0
except ValueError as e:
gave_up + 1 => gave_up
(" " + str(e)) ^0
"Ledger:" ^0
for entry in ledger.log:
(" " + entry) ^0
("Attempts " + str(ledger.attempts) + ": " + str(ledger.successes) + " done, " + str(ledger.failures) + " failed. The finally block ran " + str(ledger.finally_runs) + " times. Waited " + str(ledger.waited) + " ms in all.") ^0
("Jobs done, given up, refused: " + str(done) + ", " + str(gave_up) + ", " + str(refused) + ".") ^0
if ledger.finally_runs == ledger.attempts and ledger.successes + ledger.failures == ledger.attempts:
"Every attempt was counted once, and finally ran on each - after a return, after a raise, and after a failure alike." ^0
def settings(cfg):
ask("first wait in ms", 1, 10000) => b
if b == -1:
"Cancelled." ^0
return cfg
ask("longest wait in ms", b, 600000) => c
if c == -1:
"Cancelled." ^0
return cfg
ask("attempts per client", 2, 12) => a
if a == -1:
"Cancelled." ^0
return cfg
ask("clients", 1, 1000) => n
if n == -1:
"Cancelled." ^0
return cfg
ask("outage in ms", 0, 600000) => o
if o == -1:
"Cancelled." ^0
return cfg
ask("seed", 0, 999999) => s
if s == -1:
"Cancelled." ^0
return cfg
("First wait " + str(b) + " ms, longest " + str(c) + " ms, " + str(a) + " attempts, " + str(n) + " clients, outage " + str(o) + " ms, seed " + str(s) + ".") ^0
return [b, c, a, n, o, s, cfg[6]]
[1000, 16000, 6, 200, 10000, 7, 100] => cfg
"== Retry planner ==" ^0
"Waits between retries under five policies, a crowd coming back after an outage, and a job runner whose ledger checks itself." ^0
True => running
while running:
"" ^0
"1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
one_client(cfg)
elif choice == "2":
crowd(cfg)
elif choice == "3":
histogram(cfg)
elif choice == "4":
jobs(cfg)
elif choice == "5":
settings(cfg) => cfg
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import retry
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 number(s, most):
if len(s) == 0 or len(s) > most:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def lpad(s, n):
while len(s) < n:
s = " " + s
return s
def ask(prompt, low, high):
while True:
a = plain(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if a == "":
return -1
n = number(a, 7)
if n >= low and n <= high:
return n
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
def policies():
return ["fixed", "exponential", "full jitter", "equal jitter", "decorrelated"]
def ask_policy():
p = plain(input("policy (fixed, exponential, full jitter, equal jitter or decorrelated)> "))
if p == "":
return ""
for q in policies():
if q == p:
return p
print("Type fixed, exponential, full jitter, equal jitter or decorrelated.")
return "!"
def one_client(cfg):
p = ask_policy()
if p == "":
print("Cancelled.")
return
if p == "!":
return
c = ask("client number", 1, cfg[3])
if c == -1:
print("Cancelled.")
return
print("Client " + str(c) + ", " + p + ": attempt 1 at 0 ms, then")
t = 0
n = 2
for w in retry.waits(p, cfg, c):
t = t + w
print(" attempt " + lpad(str(n), 2) + " after " + lpad(str(w), 6) + " ms, at " + lpad(str(t), 7) + " ms")
n = n + 1
print("In all " + str(t) + " ms before the last attempt.")
def crowd(cfg):
print(str(cfg[3]) + " clients fail at 0 ms; the service is back at " + str(cfg[4]) + " ms; each tries " + str(cfg[2]) + " times at most. Retries counted per " + str(cfg[6]) + " ms:")
print(" policy retries most in a slot the slot from all through by gave up")
gave = {}
top = {}
for p in policies():
h = retry.herd(p, cfg)
gave[p] = h[4]
top[p] = retry.peak(h[0])[0]
m = retry.peak(h[0])
last = "-"
if h[3] >= 0:
last = str(h[3]) + " ms"
print(" " + pad(p, 14) + lpad(str(h[1]), 9) + lpad(str(m[0]), 17) + lpad(str(m[1] * cfg[6]) + " ms", 16) + lpad(last, 17) + lpad(str(h[4]), 10))
print("Fixed and exponential waits are the same for every client, so each round of retries lands in a single slot. A wait that depends on the client spreads each round over the whole wait, which lowers the busiest slot only when the waits are long against the slot: here " + str(top["full jitter"]) + ", " + str(top["equal jitter"]) + " and " + str(top["decorrelated"]) + " against " + str(top["exponential"]) + ".")
if gave["full jitter"] > gave["exponential"] or gave["equal jitter"] > gave["exponential"]:
print("Full and equal jitter wait on average about a half and three quarters of the exponential wait, so with the same attempts " + str(gave["full jitter"]) + " and " + str(gave["equal jitter"]) + " clients gave up, against " + str(gave["exponential"]) + " with exponential waits.")
def histogram(cfg):
p = ask_policy()
if p == "":
print("Cancelled.")
return
if p == "!":
return
by_second = [cfg[0], cfg[1], cfg[2], cfg[3], cfg[4], cfg[5], 1000]
h = retry.herd(p, by_second)
m = retry.peak(h[0])
print(p + ": retries in each second, # for every " + str(scale(m[0])) + ":")
for i in range(0, len(h[0])):
if h[0][i] > 0:
bar = ""
for k in range(1, bars(h[0][i], m[0])+1):
bar = bar + "#"
print(" " + lpad(str(i * 1000), 7) + " ms " + lpad(str(h[0][i]), 5) + " " + bar)
def scale(most):
s = 1
while most > 40 * s:
s = s + 1
return s
def bars(n, most):
s = scale(most)
return int((n + s - 1 - (n + s - 1) % s) / s)
def jobs(cfg):
print("Jobs as name:failures, or name:fatal for a job that cannot be retried, such as alpha:0 bravo:2 charlie:9 delta:fatal.")
t = plain(input("jobs> "))
if t == "":
print("Cancelled.")
return
lst = []
w = ""
for c in t + " ":
if c == " ":
if w != "":
lst = lst + [w]
w = ""
else:
w = w + c
parsed = []
for item in lst:
colon = -1
for i in range(0, len(item)):
if colon == -1 and item[i] == ":":
colon = i
if colon < 1 or colon == len(item) - 1:
print("Type each job as name:number or name:fatal.")
return
name = item[0:colon]
rest = item[colon + 1:len(item)]
if rest == "fatal":
parsed = parsed + [[name, 0, True]]
else:
n = number(rest, 3)
if n < 0:
print("Type each job as name:number or name:fatal.")
return
parsed = parsed + [[name, n, False]]
if len(parsed) > 8:
print("Up to 8 jobs.")
return
ledger = retry.Ledger()
done = 0
gave_up = 0
refused = 0
for job in parsed:
try:
result = retry.run_job(ledger, cfg, job[0], job[1], job[2])
done = done + 1
print(" " + result)
except TypeError as e:
refused = refused + 1
print(" " + str(e))
except ValueError as e:
gave_up = gave_up + 1
print(" " + str(e))
print("Ledger:")
for entry in ledger.log:
print(" " + entry)
print("Attempts " + str(ledger.attempts) + ": " + str(ledger.successes) + " done, " + str(ledger.failures) + " failed. The finally block ran " + str(ledger.finally_runs) + " times. Waited " + str(ledger.waited) + " ms in all.")
print("Jobs done, given up, refused: " + str(done) + ", " + str(gave_up) + ", " + str(refused) + ".")
if ledger.finally_runs == ledger.attempts and ledger.successes + ledger.failures == ledger.attempts:
print("Every attempt was counted once, and finally ran on each - after a return, after a raise, and after a failure alike.")
def settings(cfg):
b = ask("first wait in ms", 1, 10000)
if b == -1:
print("Cancelled.")
return cfg
c = ask("longest wait in ms", b, 600000)
if c == -1:
print("Cancelled.")
return cfg
a = ask("attempts per client", 2, 12)
if a == -1:
print("Cancelled.")
return cfg
n = ask("clients", 1, 1000)
if n == -1:
print("Cancelled.")
return cfg
o = ask("outage in ms", 0, 600000)
if o == -1:
print("Cancelled.")
return cfg
s = ask("seed", 0, 999999)
if s == -1:
print("Cancelled.")
return cfg
print("First wait " + str(b) + " ms, longest " + str(c) + " ms, " + str(a) + " attempts, " + str(n) + " clients, outage " + str(o) + " ms, seed " + str(s) + ".")
return [b, c, a, n, o, s, cfg[6]]
cfg = [1000, 16000, 6, 200, 10000, 7, 100]
print("== Retry planner ==")
print("Waits between retries under five policies, a crowd coming back after an outage, and a job runner whose ledger checks itself.")
running = True
while running:
print("")
print("1) one client 2) the crowd 3) retries over time 4) jobs with a ledger 5) settings 6) quit")
choice = plain(input("choice> "))
if choice == "1":
one_client(cfg)
elif choice == "2":
crowd(cfg)
elif choice == "3":
histogram(cfg)
elif choice == "4":
jobs(cfg)
elif choice == "5":
cfg = settings(cfg)
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
retry.eml
eml# P107 retry planner - waits between retries, in whole milliseconds:
# fixed the base every time
# exponential base x 2^(k-1) for retry k, up to the cap
# full jitter a random wait from 0 to the exponential one
# equal jitter half the exponential one, plus a random wait up to the
# other half
# decorrelated a random wait from the base to three times the last one,
# up to the cap
# As in the corpus case backoff-thundering-herd, a policy that gives every
# client the same waits sends them back all at once; only a wait that
# depends on the client spreads them. A job runner with a ledger, as in the
# corpus case retry-with-backoff-ledger, shows every attempt and checks
# that its finally ran on every one.
#
# cfg is [base, cap, attempts, clients, outage, seed, bucket].
def next_random(state, lo, hi):
# a whole number from lo to hi, from a linear congruential generator
# (top 16 bits); state is a one-element list
(1664525 * state[0] + 1013904223) % 4294967296 => state[0]
return lo + int((state[0] - state[0] % 65536) / 65536) % (hi - lo + 1)
def exponential(cfg, k):
cfg[0] => w
for i in [2:k]:
if w < cfg[1]:
w * 2 => w
if w > cfg[1]:
cfg[1] => w
return w
def waits(policy, cfg, client):
# the waits before retries 1 .. attempts - 1
[cfg[5] * 1000 + client] => state
[] => out
cfg[0] => last
for k in [1:cfg[2] - 1]:
exponential(cfg, k) => e
if policy == "fixed":
cfg[0] => w
elif policy == "exponential":
e => w
elif policy == "full jitter":
next_random(state, 0, e) => w
elif policy == "equal jitter":
int((e - e % 2) / 2) => half
half + next_random(state, 0, e - half) => w
else:
next_random(state, cfg[0], last * 3) => w
if w > cfg[1]:
cfg[1] => w
w => last
out + [w] => out
return out
def herd(policy, cfg):
# every client fails at time 0 when the outage starts; a retry at or
# after the outage's end gets through. [bucket counts, retries,
# through, last through, gave up]
[] => counts
0 => retries
0 => through
-1 => last
0 => gave_up
for c in [1:cfg[3]]:
0 => t
False => ok
for w in waits(policy, cfg, c):
if not ok:
t + w => t
retries + 1 => retries
int((t - t % cfg[6]) / cfg[6]) => b
while len(counts) <= b:
counts + [0] => counts
counts[b] + 1 => counts[b]
if t >= cfg[4]:
True => ok
through + 1 => through
if t > last:
t => last
if not ok:
gave_up + 1 => gave_up
return [counts, retries, through, last, gave_up]
def peak(counts):
# [most retries in one bucket, the first bucket with that many]
0 => most
-1 => at
for i in [0:len(counts) - 1]:
if counts[i] > most:
counts[i] => most
i => at
return [most, at]
class Ledger:
def __init__(self):
[] => self.log
0 => self.attempts
0 => self.successes
0 => self.failures
0 => self.finally_runs
0 => self.waited
def record(self, entry):
self.log + [entry] => self.log
def attempt(name, n, fails, fatal):
# the n-th call of a job that fails `fails` times, or for good
if fatal:
raise TypeError(name + ": cannot be retried")
if n <= fails:
raise ValueError(name + ": failed on attempt " + str(n))
return name + ": done on attempt " + str(n)
def run_job(ledger, cfg, name, fails, fatal):
0 => n
while n < cfg[2]:
n + 1 => n
ledger.attempts + 1 => ledger.attempts
try:
attempt(name, n, fails, fatal) => result
ledger.successes + 1 => ledger.successes
ledger.record(name + " attempt " + str(n) + ": done")
return result
except TypeError as e:
ledger.failures + 1 => ledger.failures
ledger.record(name + " attempt " + str(n) + ": cannot be retried, stopped")
raise
except ValueError as e:
ledger.failures + 1 => ledger.failures
if n < cfg[2]:
exponential(cfg, n) => w
ledger.waited + w => ledger.waited
ledger.record(name + " attempt " + str(n) + ": failed, retry after " + str(w) + " ms")
else:
ledger.record(name + " attempt " + str(n) + ": failed, no attempts left")
finally:
ledger.finally_runs + 1 => ledger.finally_runs
raise ValueError(name + ": gave up after " + str(cfg[2]) + " attempts")
Python projection (retry.py)
def next_random(state, lo, hi):
state[0] = (1664525 * state[0] + 1013904223) % 4294967296
return lo + int((state[0] - state[0] % 65536) / 65536) % (hi - lo + 1)
def exponential(cfg, k):
w = cfg[0]
for i in range(2, k+1):
if w < cfg[1]:
w = w * 2
if w > cfg[1]:
w = cfg[1]
return w
def waits(policy, cfg, client):
state = [cfg[5] * 1000 + client]
out = []
last = cfg[0]
for k in range(1, cfg[2]):
e = exponential(cfg, k)
if policy == "fixed":
w = cfg[0]
elif policy == "exponential":
w = e
elif policy == "full jitter":
w = next_random(state, 0, e)
elif policy == "equal jitter":
half = int((e - e % 2) / 2)
w = half + next_random(state, 0, e - half)
else:
w = next_random(state, cfg[0], last * 3)
if w > cfg[1]:
w = cfg[1]
last = w
out = out + [w]
return out
def herd(policy, cfg):
counts = []
retries = 0
through = 0
last = -1
gave_up = 0
for c in range(1, cfg[3]+1):
t = 0
ok = False
for w in waits(policy, cfg, c):
if not ok:
t = t + w
retries = retries + 1
b = int((t - t % cfg[6]) / cfg[6])
while len(counts) <= b:
counts = counts + [0]
counts[b] = counts[b] + 1
if t >= cfg[4]:
ok = True
through = through + 1
if t > last:
last = t
if not ok:
gave_up = gave_up + 1
return [counts, retries, through, last, gave_up]
def peak(counts):
most = 0
at = -1
for i in range(0, len(counts)):
if counts[i] > most:
most = counts[i]
at = i
return [most, at]
class Ledger:
def __init__(self):
self.log = []
self.attempts = 0
self.successes = 0
self.failures = 0
self.finally_runs = 0
self.waited = 0
def record(self, entry):
self.log = self.log + [entry]
def attempt(name, n, fails, fatal):
if fatal:
raise TypeError(name + ": cannot be retried")
if n <= fails:
raise ValueError(name + ": failed on attempt " + str(n))
return name + ": done on attempt " + str(n)
def run_job(ledger, cfg, name, fails, fatal):
n = 0
while n < cfg[2]:
n = n + 1
ledger.attempts = ledger.attempts + 1
try:
result = attempt(name, n, fails, fatal)
ledger.successes = ledger.successes + 1
ledger.record(name + " attempt " + str(n) + ": done")
return result
except TypeError as e:
ledger.failures = ledger.failures + 1
ledger.record(name + " attempt " + str(n) + ": cannot be retried, stopped")
raise
except ValueError as e:
ledger.failures = ledger.failures + 1
if n < cfg[2]:
w = exponential(cfg, n)
ledger.waited = ledger.waited + w
ledger.record(name + " attempt " + str(n) + ": failed, retry after " + str(w) + " ms")
else:
ledger.record(name + " attempt " + str(n) + ": failed, no attempts left")
finally:
ledger.finally_runs = ledger.finally_runs + 1
raise ValueError(name + ": gave up after " + str(cfg[2]) + " attempts")