Project P096
Rate limiter
One list of request times through three limiters set to the same limit of L per W seconds - a fixed window, a sliding log and a token bucket - showing which requests each lets through and the most each really lets into any W seconds, with the token bucket's exact worst case.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
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
"At most L requests per W seconds", enforced three ways on one list of request times: a fixed window, a sliding log and a token bucket. The program shows which requests each lets through, and the most each really lets into any W seconds. It starts with a burst against 10 per 60 seconds: 10 requests at second 59 and 10 at second 60.
main.eml- the menu, traces, limits and the two tableslimits.eml- the three limiters, the busiest window, the token bucket's worst case and the random trace
How each part works:
- A fixed window counts the requests in each window [kW, (k+1)W) and refuses once the count reaches L. As in the corpus case
rate-limit-window-shape, the count starts again at each boundary. So L requests just before a boundary and L just after all get through: 2L in two seconds. - A sliding log keeps the times it let through. It lets a request through when fewer than L of them are in the last W seconds, so no W seconds ever hold more than L.
- A token bucket starts full with S tokens and gains L tokens every W seconds, never holding more than S. A request takes a token or is refused. Tokens are counted in units of 1/W token, so the refill stays whole. The bucket bounds the burst (S) and the rate over time (L per W), but not each window. Start full, spend each token as it refills, and S plus what refills over the next W - 1 seconds gets through. That is at most S + floor((W - 1) L / W), and less when refilling from one second to the next would overflow the bucket. The program works the number out second by second.
- The busiest window: two pointers over the times let through give the most in any W seconds in a row, and the earliest second such a window starts.
- The random trace: a linear congruential generator, each request 0 to 6 seconds after the one before.
What is checked: menu choices 1 to 5; a trace name; a seed from 0 to 999999; 2 to 60 request times, whole seconds up to 99999, each no earlier than the one before; a limit of 1 to 100 per 1 to 3600 seconds, and a bucket of 1 to the limit. An empty answer cancels.
Sessions: sessions/basic.in gives: - the burst: the fixed window lets all 20 through within two seconds; - each request of the burst; - a steady trace, one every 4 seconds: the bucket lets 15 into the first 60 seconds; - a random trace (seed 7), where the bucket reaches its worst case of 19, and its first 40 requests one by one; then the same trace with a bucket of 3; - typed times against 3 per 10 seconds with a bucket of 2, then a burst at those limits.
sessions/bad-input.in gives: - menu choices 0 and x; the trace lizard; - typed times out of order, with letters, too few, and too large; - seeds x and 1000000; limits 0 and 101, windows 0 and 3601, and a bucket bigger than the limit; then cancels.
Built on the verified corpus case rate-limit-window-shape (a fixed window lets twice the limit through at a boundary; a sliding window does not; a token bucket bounds the burst, not each window).
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== Rate limiter ==
One list of requests, three limiters set to the same limit - and what each really lets through.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 0
Pick a number from 1 to 5.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> x
Pick a number from 1 to 5.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> lizard
Type burst, steady, random or own.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> own
request times in seconds, in order (2 to 60)> 5 3
Type 2 to 60 whole numbers of seconds, each no earlier than the one before.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> own
request times in seconds, in order (2 to 60)> abc 4
Type 2 to 60 whole numbers of seconds, each no earlier than the one before.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> own
request times in seconds, in order (2 to 60)> 7
Type 2 to 60 whole numbers of seconds, each no earlier than the one before.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> own
request times in seconds, in order (2 to 60)> 1 123456
Type 2 to 60 whole numbers of seconds, each no earlier than the one before.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> random
seed (0 to 999999)> x
Type a whole number from 0 to 999999.
seed (0 to 999999)> 1000000
Type a whole number from 0 to 999999.
seed (0 to 999999)>
Cancelled.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 4
requests allowed per window (1 to 100)> 0
Type a whole number from 1 to 100.
requests allowed per window (1 to 100)> 101
Type a whole number from 1 to 100.
requests allowed per window (1 to 100)> 5
window in seconds (1 to 3600)> 0
Type a whole number from 1 to 3600.
window in seconds (1 to 3600)> 3601
Type a whole number from 1 to 3600.
window in seconds (1 to 3600)> 60
token bucket size, the largest burst (1 to 5)> 6
Type a whole number from 1 to 5.
token bucket size, the largest burst (1 to 5)>
Cancelled.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)>
Cancelled.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 2
request second fixed sliding bucket
1 59 yes yes yes
2 59 yes yes yes
3 59 yes yes yes
4 59 yes yes yes
5 59 yes yes yes
6 59 yes yes yes
7 59 yes yes yes
8 59 yes yes yes
9 59 yes yes yes
10 59 yes yes yes
11 60 yes no no
12 60 yes no no
13 60 yes no no
14 60 yes no no
15 60 yes no no
16 60 yes no no
17 60 yes no no
18 60 yes no no
19 60 yes no no
20 60 yes no no
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 5
Bye.
What was typed (34 lines)
0
x
3
lizard
3
own
5 3
3
own
abc 4
3
own
7
3
own
1 123456
3
random
x
1000000
4
0
101
5
0
3601
60
6
3
2
5
basic
interpreter: byte-equal== Rate limiter ==
One list of requests, three limiters set to the same limit - and what each really lets through.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
20 requests from second 59 to 60; the limit is 10 per 60 seconds (bucket of 10):
limiter through refused most in any 60 s
fixed window 20 0 20 over the limit, from second 59
sliding log 10 10 10
token bucket 10 10 10
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 19 through in 60 seconds - the most it ever can.
The sliding log holds every 60 seconds to 10.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 2
request second fixed sliding bucket
1 59 yes yes yes
2 59 yes yes yes
3 59 yes yes yes
4 59 yes yes yes
5 59 yes yes yes
6 59 yes yes yes
7 59 yes yes yes
8 59 yes yes yes
9 59 yes yes yes
10 59 yes yes yes
11 60 yes no no
12 60 yes no no
13 60 yes no no
14 60 yes no no
15 60 yes no no
16 60 yes no no
17 60 yes no no
18 60 yes no no
19 60 yes no no
20 60 yes no no
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> steady
75 requests, one every 4 seconds.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
75 requests from second 0 to 296; the limit is 10 per 60 seconds (bucket of 10):
limiter through refused most in any 60 s
fixed window 50 25 10
sliding log 50 25 10
token bucket 59 16 15 over the limit, from second 0
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 19 through in 60 seconds - the most it ever can.
The sliding log holds every 60 seconds to 10.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> random
seed (0 to 999999)> 7
60 requests, each 0 to 6 seconds after the one before.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
60 requests from second 3 to 181; the limit is 10 per 60 seconds (bucket of 10):
limiter through refused most in any 60 s
fixed window 32 28 13 over the limit, from second 5
sliding log 30 30 10
token bucket 39 21 19 over the limit, from second 3
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 19 through in 60 seconds - the most it ever can.
The sliding log holds every 60 seconds to 10.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 2
request second fixed sliding bucket
1 3 yes yes yes
2 5 yes yes yes
3 7 yes yes yes
4 11 yes yes yes
5 17 yes yes yes
6 17 yes yes yes
7 21 yes yes yes
8 22 yes yes yes
9 28 yes yes yes
10 34 yes yes yes
11 38 no no yes
12 43 no no yes
13 45 no no yes
14 45 no no yes
15 48 no no yes
16 50 no no yes
17 55 no no yes
18 56 no no yes
19 61 yes no yes
20 61 yes no no
21 64 yes yes yes
22 64 yes no no
23 69 yes yes yes
24 73 yes yes no
25 73 yes yes no
26 78 yes yes yes
27 81 yes yes yes
28 84 yes yes no
29 89 no yes yes
30 94 no yes yes
31 95 no yes no
32 96 no no no
33 99 no no yes
34 102 no no no
35 105 no no yes
36 108 no no no
37 111 no no yes
38 116 no no no
39 121 yes no yes
40 124 yes yes yes
... and 20 more
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 4
requests allowed per window (1 to 100)> 10
window in seconds (1 to 3600)> 60
token bucket size, the largest burst (1 to 10)> 3
10 per 60 seconds, bucket of 3.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
60 requests from second 3 to 181; the limit is 10 per 60 seconds (bucket of 3):
limiter through refused most in any 60 s
fixed window 32 28 13 over the limit, from second 5
sliding log 30 30 10
token bucket 32 28 12 over the limit, from second 3
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 12 through in 60 seconds - the most it ever can.
The sliding log holds every 60 seconds to 10.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> own
request times in seconds, in order (2 to 60)> 0 0 0 5 5 5 9 10 11 12 19 20
12 requests.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 4
requests allowed per window (1 to 100)> 3
window in seconds (1 to 3600)> 10
token bucket size, the largest burst (1 to 3)> 2
3 per 10 seconds, bucket of 2.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
12 requests from second 0 to 20; the limit is 3 per 10 seconds (bucket of 2):
limiter through refused most in any 10 s
fixed window 7 5 3
sliding log 7 5 3
token bucket 7 5 4 over the limit, from second 0
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 4 through in 10 seconds - the most it ever can.
The sliding log holds every 10 seconds to 3.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 2
request second fixed sliding bucket
1 0 yes yes yes
2 0 yes yes yes
3 0 yes yes no
4 5 no no yes
5 5 no no no
6 5 no no no
7 9 no no yes
8 10 yes yes yes
9 11 yes yes no
10 12 yes yes no
11 19 no no yes
12 20 yes yes yes
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 3
Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.
trace (burst, steady, random or own)> burst
6 requests: 3 at second 9 and 3 at second 10.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 1
6 requests from second 9 to 10; the limit is 3 per 10 seconds (bucket of 2):
limiter through refused most in any 10 s
fixed window 6 0 6 over the limit, from second 9
sliding log 3 3 3
token bucket 2 4 2
A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.
A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets 4 through in 10 seconds - the most it ever can.
The sliding log holds every 10 seconds to 3.
1) compare 2) request by request 3) new trace 4) limits 5) quit
choice> 5
Bye.
What was typed (28 lines)
1
2
3
steady
1
3
random
7
1
2
4
10
60
3
1
3
own
0 0 0 5 5 5 9 10 11 12 19 20
4
3
10
2
1
2
3
burst
1
5
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# P096 rate limiter: one list of requests through a fixed window, a sliding
# log and a token bucket, each set to "L per W seconds" - and the most each
# actually lets through in any W seconds.
import limits
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 seconds(n):
if n == 1:
return "1 second"
return str(n) + " seconds"
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, 6) => n
if n >= low and n <= high:
return n
("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0
def results(times, cfg):
[limits.fixed_window(times, cfg[0], cfg[1]), limits.sliding_log(times, cfg[0], cfg[1]), limits.token_bucket(times, cfg[0], cfg[1], cfg[2])] => out
return out
def summary(times, cfg):
results(times, cfg) => rs
["fixed window", "sliding log", "token bucket"] => names
(str(len(times)) + " requests from second " + str(times[0]) + " to " + str(times[len(times) - 1]) + "; the limit is " + str(cfg[0]) + " per " + seconds(cfg[1]) + " (bucket of " + str(cfg[2]) + "):") ^0
" limiter through refused most in any " + str(cfg[1]) + " s" => head
head ^0
for k in [0:2]:
0 => n
for b in rs[k]:
if b:
n + 1 => n
limits.busiest(times, rs[k], cfg[1]) => m
"" => note
if m[0] > cfg[0]:
" over the limit, from second " + str(m[1]) => note
(" " + pad(names[k], 15) + lpad(str(n), 7) + lpad(str(len(times) - n), 9) + lpad(str(m[0]), 13) + note) ^0
"A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through." ^0
("A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets " + str(limits.bucket_most(cfg[0], cfg[1], cfg[2])) + " through in " + seconds(cfg[1]) + " - the most it ever can.") ^0
("The sliding log holds every " + seconds(cfg[1]) + " to " + str(cfg[0]) + ".") ^0
def steps(times, cfg):
results(times, cfg) => rs
" request second fixed sliding bucket" ^0
for i in [0:len(times) - 1]:
if i < 40:
"" => row
for k in [0:2]:
" no" => mark
if rs[k][i]:
" yes" => mark
row + lpad(mark, 8) => row
(" " + lpad(str(i + 1), 7) + lpad(str(times[i]), 8) + row) ^0
if len(times) > 40:
(" ... and " + str(len(times) - 40) + " more") ^0
def burst(cfg):
# the limit's worth in the last second of a window and again in the
# first second of the next
[] => out
for i in [1:cfg[0]]:
out + [cfg[1] - 1] => out
for i in [1:cfg[0]]:
out + [cfg[1]] => out
return out
def new_trace(times, cfg):
"Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times." ^0
plain(input("trace (burst, steady, random or own)> ")) => s
if s == "burst":
burst(cfg) => out
(str(len(out)) + " requests: " + str(cfg[0]) + " at second " + str(cfg[1] - 1) + " and " + str(cfg[0]) + " at second " + str(cfg[1]) + ".") ^0
return out
if s == "steady":
[] => out
for i in [0:74]:
out + [4 * i] => out
"75 requests, one every 4 seconds." ^0
return out
if s == "random":
ask("seed", 0, 999999) => seed
if seed == -1:
"Cancelled." ^0
return times
limits.lcg_times(60, 3, seed) => out
"60 requests, each 0 to 6 seconds after the one before." ^0
return out
if s == "own":
plain(input("request times in seconds, in order (2 to 60)> ")) => t
[] => out
"" => w
True => ok
for c in t + " ":
if c == " ":
if w != "":
number(w, 5) => v
if v < 0 or (len(out) > 0 and v < out[len(out) - 1]):
False => ok
out + [v] => out
"" => w
else:
w + c => w
if ok and len(out) >= 2 and len(out) <= 60:
(str(len(out)) + " requests.") ^0
return out
"Type 2 to 60 whole numbers of seconds, each no earlier than the one before." ^0
return times
if s == "":
"Cancelled." ^0
else:
"Type burst, steady, random or own." ^0
return times
def settings(cfg):
ask("requests allowed per window", 1, 100) => l
if l == -1:
"Cancelled." ^0
return cfg
ask("window in seconds", 1, 3600) => w
if w == -1:
"Cancelled." ^0
return cfg
ask("token bucket size, the largest burst", 1, l) => b
if b == -1:
"Cancelled." ^0
return cfg
(str(l) + " per " + seconds(w) + ", bucket of " + str(b) + ".") ^0
return [l, w, b]
[10, 60, 10] => cfg
burst(cfg) => times
"== Rate limiter ==" ^0
"One list of requests, three limiters set to the same limit - and what each really lets through." ^0
True => running
while running:
"" ^0
"1) compare 2) request by request 3) new trace 4) limits 5) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
summary(times, cfg)
elif choice == "2":
steps(times, cfg)
elif choice == "3":
new_trace(times, cfg) => times
elif choice == "4":
settings(cfg) => cfg
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import limits
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 seconds(n):
if n == 1:
return "1 second"
return str(n) + " seconds"
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, 6)
if n >= low and n <= high:
return n
print("Type a whole number from " + str(low) + " to " + str(high) + ".")
def results(times, cfg):
out = [limits.fixed_window(times, cfg[0], cfg[1]), limits.sliding_log(times, cfg[0], cfg[1]), limits.token_bucket(times, cfg[0], cfg[1], cfg[2])]
return out
def summary(times, cfg):
rs = results(times, cfg)
names = ["fixed window", "sliding log", "token bucket"]
print(str(len(times)) + " requests from second " + str(times[0]) + " to " + str(times[len(times) - 1]) + "; the limit is " + str(cfg[0]) + " per " + seconds(cfg[1]) + " (bucket of " + str(cfg[2]) + "):")
head = " limiter through refused most in any " + str(cfg[1]) + " s"
print(head)
for k in range(0, 3):
n = 0
for b in rs[k]:
if b:
n = n + 1
m = limits.busiest(times, rs[k], cfg[1])
note = ""
if m[0] > cfg[0]:
note = " over the limit, from second " + str(m[1])
print(" " + pad(names[k], 15) + lpad(str(n), 7) + lpad(str(len(times) - n), 9) + lpad(str(m[0]), 13) + note)
print("A fixed window starts counting again at each boundary, so a burst just before it and another just after both get through.")
print("A token bucket bounds the burst and the rate over time, not each window: full, then spending each token as it refills, it lets " + str(limits.bucket_most(cfg[0], cfg[1], cfg[2])) + " through in " + seconds(cfg[1]) + " - the most it ever can.")
print("The sliding log holds every " + seconds(cfg[1]) + " to " + str(cfg[0]) + ".")
def steps(times, cfg):
rs = results(times, cfg)
print(" request second fixed sliding bucket")
for i in range(0, len(times)):
if i < 40:
row = ""
for k in range(0, 3):
mark = " no"
if rs[k][i]:
mark = " yes"
row = row + lpad(mark, 8)
print(" " + lpad(str(i + 1), 7) + lpad(str(times[i]), 8) + row)
if len(times) > 40:
print(" ... and " + str(len(times) - 40) + " more")
def burst(cfg):
out = []
for i in range(1, cfg[0]+1):
out = out + [cfg[1] - 1]
for i in range(1, cfg[0]+1):
out = out + [cfg[1]]
return out
def new_trace(times, cfg):
print("Traces: burst (the limit's worth just before a boundary and just after), steady, random, or your own times.")
s = plain(input("trace (burst, steady, random or own)> "))
if s == "burst":
out = burst(cfg)
print(str(len(out)) + " requests: " + str(cfg[0]) + " at second " + str(cfg[1] - 1) + " and " + str(cfg[0]) + " at second " + str(cfg[1]) + ".")
return out
if s == "steady":
out = []
for i in range(0, 75):
out = out + [4 * i]
print("75 requests, one every 4 seconds.")
return out
if s == "random":
seed = ask("seed", 0, 999999)
if seed == -1:
print("Cancelled.")
return times
out = limits.lcg_times(60, 3, seed)
print("60 requests, each 0 to 6 seconds after the one before.")
return out
if s == "own":
t = plain(input("request times in seconds, in order (2 to 60)> "))
out = []
w = ""
ok = True
for c in t + " ":
if c == " ":
if w != "":
v = number(w, 5)
if v < 0 or len(out) > 0 and v < out[len(out) - 1]:
ok = False
out = out + [v]
w = ""
else:
w = w + c
if ok and len(out) >= 2 and len(out) <= 60:
print(str(len(out)) + " requests.")
return out
print("Type 2 to 60 whole numbers of seconds, each no earlier than the one before.")
return times
if s == "":
print("Cancelled.")
else:
print("Type burst, steady, random or own.")
return times
def settings(cfg):
l = ask("requests allowed per window", 1, 100)
if l == -1:
print("Cancelled.")
return cfg
w = ask("window in seconds", 1, 3600)
if w == -1:
print("Cancelled.")
return cfg
b = ask("token bucket size, the largest burst", 1, l)
if b == -1:
print("Cancelled.")
return cfg
print(str(l) + " per " + seconds(w) + ", bucket of " + str(b) + ".")
return [l, w, b]
cfg = [10, 60, 10]
times = burst(cfg)
print("== Rate limiter ==")
print("One list of requests, three limiters set to the same limit - and what each really lets through.")
running = True
while running:
print("")
print("1) compare 2) request by request 3) new trace 4) limits 5) quit")
choice = plain(input("choice> "))
if choice == "1":
summary(times, cfg)
elif choice == "2":
steps(times, cfg)
elif choice == "3":
times = new_trace(times, cfg)
elif choice == "4":
cfg = settings(cfg)
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
limits.eml
eml# P096 rate limiter - "at most L requests per W seconds", enforced three
# ways on one list of request times (whole seconds, in order), as in the
# corpus case rate-limit-window-shape: a fixed window, a sliding log, and a
# token bucket. Each returns, for every request, True (let through) or
# False (refused).
def quotient(a, b):
# a // b for a >= 0, b > 0; the numbers here are small, so the float
# division is exact.
return int((a - a % b) / b)
def fixed_window(times, limit, w):
# Count requests per window [kW, (k+1)W) and refuse once the count
# reaches the limit; the count starts again at each boundary.
[] => out
-1 => current
0 => count
for t in times:
quotient(t, w) => k
if k != current:
k => current
0 => count
if count < limit:
count + 1 => count
out + [True] => out
else:
out + [False] => out
return out
def sliding_log(times, limit, w):
# Keep the times of the requests let through; let a request through when
# fewer than `limit` of them are in the last W seconds (t - W, t].
[] => out
[] => kept
0 => first
for t in times:
while first < len(kept) and kept[first] <= t - w:
first + 1 => first
if len(kept) - first < limit:
kept + [t] => kept
out + [True] => out
else:
out + [False] => out
return out
def token_bucket(times, limit, w, size):
# A bucket of `size` tokens, starting full, refilled at `limit` tokens
# per W seconds; a request takes a token or is refused. Tokens are kept
# in units of 1/W token, so the refill (elapsed x limit) stays whole.
size * w => tokens
size * w => full
-1 => last
[] => out
for t in times:
if last >= 0:
tokens + (t - last) * limit => tokens
if tokens > full:
full => tokens
t => last
if tokens >= w:
tokens - w => tokens
out + [True] => out
else:
out + [False] => out
return out
def bucket_most(limit, w, size):
# The most a token bucket ever lets through in W seconds: start full,
# spend every whole token at once, then each one as it refills - a
# request every second. The bucket never holds more than `size`, so
# refill that would overflow it is lost.
size * w => tokens
0 => most
for t in [0:w - 1]:
if t > 0:
tokens + limit => tokens
if tokens > size * w:
size * w => tokens
quotient(tokens, w) => k
most + k => most
tokens - k * w => tokens
return most
def busiest(times, through, w):
# The most requests let through in any W seconds in a row, and when
# that window starts: the real limit a client meets.
[] => ok
for i in [0:len(times) - 1]:
if through[i]:
ok + [times[i]] => ok
0 => most
-1 => at
0 => j
for i in [0:len(ok) - 1]:
while ok[i] - ok[j] >= w:
j + 1 => j
if i - j + 1 > most:
i - j + 1 => most
ok[j] => at
return [most, at]
def lcg_times(n, gap, seed):
# n request times, each a random 0 to 2 x gap seconds after the one
# before (a linear congruential generator, top 16 bits).
[] => out
seed => x
0 => t
for i in [1:n]:
(1664525 * x + 1013904223) % 4294967296 => x
t + quotient(x, 65536) % (2 * gap + 1) => t
out + [t] => out
return out
Python projection (limits.py)
def quotient(a, b):
return int((a - a % b) / b)
def fixed_window(times, limit, w):
out = []
current = -1
count = 0
for t in times:
k = quotient(t, w)
if k != current:
current = k
count = 0
if count < limit:
count = count + 1
out = out + [True]
else:
out = out + [False]
return out
def sliding_log(times, limit, w):
out = []
kept = []
first = 0
for t in times:
while first < len(kept) and kept[first] <= t - w:
first = first + 1
if len(kept) - first < limit:
kept = kept + [t]
out = out + [True]
else:
out = out + [False]
return out
def token_bucket(times, limit, w, size):
tokens = size * w
full = size * w
last = -1
out = []
for t in times:
if last >= 0:
tokens = tokens + (t - last) * limit
if tokens > full:
tokens = full
last = t
if tokens >= w:
tokens = tokens - w
out = out + [True]
else:
out = out + [False]
return out
def bucket_most(limit, w, size):
tokens = size * w
most = 0
for t in range(0, w):
if t > 0:
tokens = tokens + limit
if tokens > size * w:
tokens = size * w
k = quotient(tokens, w)
most = most + k
tokens = tokens - k * w
return most
def busiest(times, through, w):
ok = []
for i in range(0, len(times)):
if through[i]:
ok = ok + [times[i]]
most = 0
at = -1
j = 0
for i in range(0, len(ok)):
while ok[i] - ok[j] >= w:
j = j + 1
if i - j + 1 > most:
most = i - j + 1
at = ok[j]
return [most, at]
def lcg_times(n, gap, seed):
out = []
x = seed
t = 0
for i in range(1, n+1):
x = (1664525 * x + 1013904223) % 4294967296
t = t + quotient(x, 65536) % (2 * gap + 1)
out = out + [t]
return out