<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P096-rate-limiter/ | updated: 2026-10-15 -->

# 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.

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

Built on verified corpus cases: rate-limit-window-shape (https://efficientnewlanguage.org/cases/257-rate-limit-window-shape/).

## Sessions

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

Input:

```text
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
```

Screen:

```text
== 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.
```

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

Input:

```text
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
```

Screen:

```text
== 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.
```

## Modules

### main.eml

```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 of main.eml:

```python
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 of limits.eml:

```python
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
```

## README

# P096 - Rate limiter

"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 tables
- `limits.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).