ЁЯПл The SchoolтА║ЁЯУР System DesignтА║ЁЯЪж рдзрдбрд╛ 12 тАФ Rate limiting: рдХрд╛рд░реНрдпрд╛рд▓рдпрд╛рдЪреНрдпрд╛ рдЦрд┐рдбрдХреАрд╡рд░реАрд▓ рдмрд░рдгреАрддрд▓реЗ tokens
ЁЯЦ╝я╕П See the drawing + lab ЁЯПа Course home ЁЯМ┐ Branch on GitHub тЬПя╕П View source
ЁЯЦ╝я╕П рдЖрдХреГрддреА рдЖрдгрд┐ labThe drawing + lab рдкреВрд░реНрдг рдкрд╛рдирд╛рд╡рд░ рдЙрдШрдбрд╛ тЖЧOpen full page тЖЧ

ЁЯЪж рдзрдбрд╛ 12 тАФ Rate limiting: рдХрд╛рд░реНрдпрд╛рд▓рдпрд╛рдЪреНрдпрд╛ рдЦрд┐рдбрдХреАрд╡рд░реАрд▓ рдмрд░рдгреАрддрд▓реЗ tokens

ЁЯУН рддреБрдореНрд╣реА рдЗрдереЗ рдЖрд╣рд╛рдд: 18 рдкреИрдХреА рдзрдбрд╛ 12 ┬╖ рдкреБрдвреАрд▓: lesson-13-resilience


ЁЯУж рдпрд╛ рдмреНрд░рдБрдЪрдордзреНрдпреЗ рдХрд╛рдп рдЖрд╣реЗ

рдзрдбреЗ 01тАУ11, рдЖрдгрд┐ рд▓реЛрдВрдвреНрдпрд╛рдВрдкрд╛рд╕реВрди рд╕рдВрд░рдХреНрд╖рдг: loop рдордзреНрдпреЗ рдЕрдбрдХрд▓реЗрд▓реЗ рд╕рджреЛрд╖ app, scraper, login рд╣рд▓реНрд▓рд╛, рдХрд┐рдВрд╡рд╛ рдлрдХреНрдд рдЦреВрдк рдЬрд╛рд╕реНрдд рдкрд╛рдард╡рдгрд╛рд░реА рдПрдЦрд╛рджреА рд╢рд╛рд│рд╛. рддреБрдореНрд╣реА рд╢рд┐рдХрддрд╛ token bucket, leaky bucket, fixed рдЖрдгрд┐ sliding windows, limit рдХреБрдареЗ рд▓рд╛рдЧреВ рдХрд░рд╛рдпрдЪрд╛ (edge, gateway, API, рдкреНрд░рддрд┐ user, рдкреНрд░рддрд┐ key, global), 429 + Retry-After, рдЖрдгрд┐ Redis рдордзреАрд▓ counters.

ЁЯзТ 5 рд╡рд░реНрд╖рд╛рдВрдЪреНрдпрд╛ рдореБрд▓рд╛рд▓рд╛ рд╕рдордЬрд╛рд╡рд▓реНрдпрд╛рд╕рд╛рд░рдЦреЗ

рдирд┐рдпреЛрдЬрди рдХрд╛рд░реНрдпрд╛рд▓рдпрд╛рдд рдкреНрд░рд╢реНрдирд╛рдВрд╕рд╛рдареА рдПрдХ рдЦрд┐рдбрдХреА рдЖрд╣реЗ. рдПрдХреЗ рджрд┐рд╡рд╢реА рдПрдХрд╛ рдкрд╛рд▓рдХрд╛рдЪреНрдпрд╛ рдлреЛрдирдордзреНрдпреЗ bug рдпреЗрддреЛ. рддреЛ рддреЛрдЪ рдкреНрд░рд╢реНрди рдкреБрдиреНрд╣рд╛ рдкреБрдиреНрд╣рд╛, рд╢реЗрдХрдбреЛ рд╡реЗрд│рд╛ рд╡рд┐рдЪрд╛рд░рддреЛ. рдЗрддрд░ рдкрд╛рд▓рдХ рдЦрд┐рдбрдХреАрдкрд░реНрдпрдВрдд рдкреЛрд╣реЛрдЪреВрдЪ рд╢рдХрдд рдирд╛рд╣реАрдд.

рдРрд╢реНрд╡рд░реНрдпрд╛ рдЦрд┐рдбрдХреАрд╡рд░ tokens рдЪреА рдПрдХ рдмрд░рдгреА рдареЗрд╡рддреЗ. рдмрд░рдгреАрдд рдЬрд╛рд╕реНрддреАрдд рдЬрд╛рд╕реНрдд 10 tokens рдорд╛рд╡рддрд╛рдд. рдкреНрд░рддреНрдпреЗрдХ рдкреНрд░рд╢реНрдирд╛рд▓рд╛ рдПрдХ token рд▓рд╛рдЧрддреЛ. рдПрдХ рдорджрддрдиреАрд╕ рдмрд░рдгреАрдд рд╕реЗрдХрдВрджрд╛рд▓рд╛ 5 рд╡реЗрд│рд╛ рдПрдХ рдирд╡рд╛ token рдЯрд╛рдХрддреЛ. рдмрд░рдгреА рд░рд┐рдХрд╛рдореА рдЭрд╛рд▓реА рдХреА рдЙрддреНрддрд░ рдЕрд╕рддреЗ "рдХреГрдкрдпрд╛ рдереЛрдбреЗ рдерд╛рдВрдмрд╛" тАФ error рдирд╛рд╣реА, рдПрдХ рд╕рднреНрдп рдерд╛рдВрдмрд╛.

рдореНрд╣рдгрдЬреЗ рдкрд╛рд▓рдХ рдПрдХрджрдо 10 рдЭрдЯрдкрдЯ рдкреНрд░рд╢реНрди рд╡рд┐рдЪрд╛рд░реВ рд╢рдХрддреЛ (рдмрд░рдгреАрддрд▓реЗ tokens), рдЖрдгрд┐ рдордЧ рддреНрдпрд╛рдирдВрддрд░ рд╕реБрдорд╛рд░реЗ рд╕реЗрдХрдВрджрд╛рд▓рд╛ 5. рд╕рд╛рдорд╛рдиреНрдп рдкрд╛рд▓рдХрд╛рд▓рд╛ рдмрд░рдгреА рдХрдзреА рдЬрд╛рдгрд╡рддрд╣реА рдирд╛рд╣реА. рдмрд┐рдШрдбрд▓реЗрд▓рд╛ рдлреЛрди рдордВрдж рдХреЗрд▓рд╛ рдЬрд╛рддреЛ, рдЖрдгрд┐ рдмрд╛рдХреА рд╕рдЧрд│реНрдпрд╛рдВрдЪреЗ рдХрд╛рдо рд╣реЛрддреЗ.

рдХрддрд░рд┐рдирд╛ рд╡рд┐рдЪрд╛рд░рддреЗ: "рдШрдбреНрдпрд╛рд│рд╛рдкреНрд░рдорд╛рдгреЗ рд╕реЗрдХрдВрджрд╛рд▓рд╛ 10 рдЕрд╕реЗ рдХрд╛ рдореЛрдЬрдд рдирд╛рд╣реА?" рдРрд╢реНрд╡рд░реНрдпрд╛ рддрд┐рд▓рд╛ рджрд╛рдЦрд╡рддреЗ: 0.9 рд╕реЗрдХрдВрджрд╛рд▓рд╛ 10 рдкреНрд░рд╢реНрди рдЖрдгрд┐ 1.1 рд╕реЗрдХрдВрджрд╛рд▓рд╛ рдЖрдгрдЦреА 10. рдШрдбреНрдпрд╛рд│рд╛рдЪреНрдпрд╛ рдкреНрд░рддреНрдпреЗрдХ рд╕реЗрдХрдВрджрд╛рдд рдлрдХреНрдд 10 рдЖрд╣реЗрдд. рдкрдг 0.2 рд╕реЗрдХрдВрджрд╛рдВрдд 20 рдЖрд▓реЗ. рд╡реЗрд│реЗрд╕реЛрдмрдд рд╕рд░рдХрдгрд╛рд▒реНрдпрд╛ рдореЛрдЬрдгреА-рдЦрд┐рдбрдХреАрдд рд╣реЗ рдЫрд┐рджреНрд░ рдирд╕рддреЗ.

ЁЯЧ║я╕П рдЖрдХреГрддреА

flowchart LR
    app["ЁЯУ▒ parent's app<br/>12 requests at 0 s<br/>5 more at 0.5 s"]
    subgraph tb["ЁЯлЩ token bucket: 5 per s, burst 10"]
      jar["10 tokens at start<br/>+2.5 by 0.5 s"]
    end
    subgraph sw["ЁЯкЯ sliding window: 10 per 1 s"]
      log["log of the last 1 s<br/>still 10 at 0.5 s"]
    end
    app --> jar
    app --> log
    jar -->|"12 of 17 allowed"| api["ЁЯзй notice API"]
    log -->|"10 of 17 allowed"| api
    jar -.->|"empty"| no["ЁЯЪж 429 Too Many Requests<br/>Retry-After: 1"]

ЁЯЧ║я╕П рдХрд╛рдврд▓реЗрд▓реА рдЖрд╡реГрддреНрддреА + рдПрдХ lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l12

тЭУ рдХрд╛рдп

ЁЯдФ рдХрд╛

рдХрд╛рд░рдг рдПрдХрд╛ caller рдиреЗ рдмрд╛рдХреА рд╕рдЧрд│реНрдпрд╛рдВрдХрдбреВрди service рд╣рд┐рд╕рдХрд╛рд╡реВрди рдШреЗрддрд╛ рдХрд╛рдорд╛ рдирдпреЗ. рдзрдбрд╛ 02 рдиреЗ app рдЪреЗ рдорд╛рдк peak рд▓рд╛ 3,507 req/s рдЕрд╕реЗ рдард░рд╡рд▓реЗ тАФ рд╕рдЧрд│реНрдпрд╛рдВрд╕рд╛рдареА рдорд┐рд│реВрди. Limit рдирд╕реЗрд▓ рддрд░ retry loop рдордзреАрд▓ рдПрдХрдЯреЗ app рдПрд╡рдвреНрдпрд╛рдкреЗрдХреНрд╖рд╛ рдЬрд╛рд╕реНрдд рдкрд╛рдард╡реВ рд╢рдХрддреЗ. Limit рдкреИрд╕реЗ рдкрдг рд╡рд╛рдЪрд╡рддреЗ: 5M рддрд╛рддрдбреАрдЪреНрдпрд╛ SMS рд▓рд╛ рдЦрд░реЗ рдкреИрд╕реЗ рд▓рд╛рдЧрддрд╛рдд, рдЖрдгрд┐ рдЪреЛрд░рд▓реЗрд▓реНрдпрд╛ рд╢рд┐рдХреНрд╖рд┐рдХрд╛-account рдиреЗ рддреЗ рджрд╣рд╛ рд╡реЗрд│рд╛ рдкрд╛рдард╡рддрд╛ рдХрд╛рдорд╛ рдирдпреЗрдд.

ЁЯФз рдХрд╕реЗ (рдпрд╛ repo рдордзреНрдпреЗ)

design/blocks.py рдордзреНрдпреЗ:

design/demo.py рдордзреАрд▓ ratelimit() t = 0 s рд▓рд╛ 12 requests рдЖрдгрд┐ t = 0.5 s рд▓рд╛ 5 requests рджреЛрдиреНрд╣реАрдВрдордзреВрди рдкрд╛рдард╡рддреЛ. рдЦрд╛рд▓рдЪрд╛ snippet edge рд╡рд░рдЪреЗ рдЫрд┐рджреНрд░ рджрд╛рдЦрд╡рдгреНрдпрд╛рд╕рд╛рдареА, inline рд▓рд┐рд╣рд┐рд▓реЗрд▓рд╛ рдПрдХ рдЫреЛрдЯрд╛ fixed-window counter рдЬреЛрдбрддреЛ.

ЁЯзк рдХрд░реВрди рдкрд╛рд╣рд╛

python3 design/demo.py ratelimit
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import TokenBucket, SlidingWindow
burst = [0.0] * 12 + [0.5] * 5
for rate, b in ((5, 10), (5, 20), (10, 10), (1, 5)):
    tb = TokenBucket(rate, b); print(f"token bucket rate {rate:>2}/s burst {b:>2} тЖТ {sum(tb.allow(t) for t in burst):>2} of 17")
steady = [i * 0.1 for i in range(30)]          # one request every 100 ms for 3 s = 10 per second
tb, sw = TokenBucket(5, 10), SlidingWindow(10, 1.0)
print("steady 10/s for 3 s тЖТ bucket", sum(tb.allow(t) for t in steady), "of 30 ┬╖ window", sum(sw.allow(t) for t in steady), "of 30")
edge = [0.9] * 10 + [1.1] * 10                  # 10 just before a minute-mark, 10 just after
def fixed(times, limit=10, window=1.0):
    counts, ok = {}, 0
    for t in times:
        k = int(t // window)
        if counts.get(k, 0) < limit: counts[k] = counts.get(k, 0) + 1; ok += 1
    return ok
sw = SlidingWindow(10, 1.0)
print("20 requests around t=1.0 s тЖТ fixed window lets", fixed(edge), "in 0.2 s ┬╖ sliding window lets", sum(sw.allow(t) for t in edge))
EOF

тЬЕ рддрдкрд╛рд╕рд╛ тАФ рддреБрдореНрд╣рд╛рд▓рд╛ рдХрд╛рдп рджрд┐рд╕рд╛рдпрд▓рд╛ рд╣рд╡реЗ

ratelimit рд╣реЗ рдЫрд╛рдкрддреЛ:

тФАтФА one parent's app sends 12 requests at t=0 s and 5 more at t=0.5 s
   token bucket (5/s, burst 10) тЖТ 12 of 17 allowed ┬╖ sliding window (10 per 1 s) тЖТ 10 of 17
   the bucket refilled 2.5 tokens in 0.5 s, so 2 more got in; the window still counts the first 10 until t=1.0 s
   token bucket: smooth rate + a burst allowance ┬╖ window: a hard count per period
   limit per user, per API key and globally; answer 429 with Retry-After; keep the counters in Redis

рддреБрдордЪрд╛ snippet рд╣реЗ рдЫрд╛рдкрддреЛ:

token bucket rate  5/s burst 10 тЖТ 12 of 17
token bucket rate  5/s burst 20 тЖТ 17 of 17
token bucket rate 10/s burst 10 тЖТ 15 of 17
token bucket rate  1/s burst  5 тЖТ  5 of 17
steady 10/s for 3 s тЖТ bucket 24 of 30 ┬╖ window 30 of 30
20 requests around t=1.0 s тЖТ fixed window lets 20 in 0.2 s ┬╖ sliding window lets 10

Tests рдордзреНрдпреЗ тЬЕ L12 the token bucket refills, the window still counts рдЕрд╕рддреЗ.

ЁЯПБ рддреБрдореНрд╣реА рдЖрддреНрддрд╛рдЪ рдХрд╛рдп рд╕рд┐рджреНрдз рдХреЗрд▓реЗ

Burst рдкрд╣рд┐рд▓рд╛ рдХреНрд╖рдг рдард░рд╡рддреЛ (10 tokens тЖТ рдПрдХрджрдо 10; 20 тЖТ рд╕рдЧрд│реНрдпрд╛ 17 рдЬрд╛рддрд╛рдд), рдЖрдгрд┐ rate рдкреБрдврдЪреЗ рдард░рд╡рддреЛ (10/s рд╣рд╛ 0.5 s рдордзреНрдпреЗ 5 tokens рднрд░рддреЛ тЖТ 15). рд╕реЗрдХрдВрджрд╛рд▓рд╛ рд╕реНрдерд┐рд░ 10 рд╣реЗ "рд╕реЗрдХрдВрджрд╛рд▓рд╛ 10" window рд╕рд╛рдареА рдареАрдХ рдЖрд╣реЗ (30 рдкреИрдХреА 30), рдкрдг 5/s рдЪреЗ bucket рдлрдХреНрдд 24 рдЖрдд рд╕реЛрдбрддреЗ: burst рдХреНрд╖рдгрднрд░ рд╣реА рддрдлрд╛рд╡рдд рд▓рдкрд╡рддреЛ, рдордЧ rate рдЪреЗ рд░рд╛рдЬреНрдп рдЪрд╛рд▓рддреЗ. рдЖрдгрд┐ fixed window рдиреЗ рджреЛрди windows рдЪреНрдпрд╛ рд╕реАрдореЗрд╡рд░ 0.2 s рдордзреНрдпреЗ 20 requests рдЖрдд рд╕реЛрдбрд▓реНрдпрд╛ тАФ рддреНрдпрд╛рдЪреНрдпрд╛ limit рдЪреНрдпрд╛ рджреБрдкреНрдкрдЯ; sliding window рдиреЗ 10 рд╕реЛрдбрд▓реНрдпрд╛.

тЪая╕П рдиреЗрд╣рдореАрдЪреНрдпрд╛ рдЪреБрдХрд╛

ЁЯПн рдкреНрд░рддреНрдпрдХреНрд╖ рд╡рд╛рдкрд░рд╛рдд

рдЦрд▒реНрдпрд╛ account рд╡рд░ тАФ API Gateway usage plan: token bucket (rate + burst) рдЖрдгрд┐ рдкреНрд░рддрд┐ API key рд░реЛрдЬрдЪрд╛ quota:

aws apigateway create-usage-plan --name parents-app \
    --throttle burstLimit=10,rateLimit=5 \
    --quota limit=100000,period=DAY \
    --api-stages apiId=a1b2c3d4e5,stage=prod

Edge рд╡рд░ AWS WAF rate-based rule тАФ 5 рдорд┐рдирд┐рдЯрд╛рдВрдд 2,000 рдкреЗрдХреНрд╖рд╛ рдЬрд╛рд╕реНрдд requests рдкрд╛рдард╡рдгрд╛рд░рд╛ IP address block рдХрд░рд╛ (web ACL рдЪреНрдпрд╛ Rules рдЪрд╛ рднрд╛рдЧ):

{ "Name": "per-ip-flood", "Priority": 1, "Action": { "Block": {} },
  "Statement": { "RateBasedStatement": { "Limit": 2000, "EvaluationWindowSec": 300, "AggregateKeyType": "IP" } },
  "VisibilityConfig": { "SampledRequestsEnabled": true, "CloudWatchMetricsEnabled": true, "MetricName": "per-ip-flood" } }

API рд╕рдореЛрд░ NGINX тАФ рдкреНрд░рддрд┐ client address рдПрдХ leaky bucket, burst рд╕рд╣, 429 рдЙрддреНрддрд░ рджреЗрдгрд╛рд░рд╛:

limit_req_zone $binary_remote_addr zone=perip:10m rate=5r/s;
server {
    location /api/ {
        limit_req zone=perip burst=10 nodelay;
        limit_req_status 429;
        proxy_pass http://notice_api;
    }
}

Redis рдордзреНрдпреЗ рдкреНрд░рддреНрдпреЗрдХ рдкрд╛рд▓рдХрд╛рд╕рд╛рдареА sliding-window log, рдПрдХрд╛рдЪ Lua script рдордзреНрдпреЗ atomic (keys рдЖрдкреЛрдЖрдк expire рд╣реЛрддрд╛рдд):

-- KEYS[1] = "rl:parent:42"  ARGV = now_ms, window_ms, limit, request_id
redis.call("ZREMRANGEBYSCORE", KEYS[1], 0, ARGV[1] - ARGV[2])
if redis.call("ZCARD", KEYS[1]) < tonumber(ARGV[3]) then
  redis.call("ZADD", KEYS[1], ARGV[1], ARGV[4])
  redis.call("PEXPIRE", KEYS[1], ARGV[2])
  return 1
end
return 0

ЁЯПн рдкреНрд░рддреНрдпрдХреНрд╖ рд╡рд╛рдкрд░рд╛рдд рд╣реЗ рдХрд╛ рдорд╣рддреНрддреНрд╡рд╛рдЪреЗ: limits API рдХрд░рд╛рд░рд╛рдд (рдзрдбрд╛ 03) рдПрдХрд╛ table рдЪреНрдпрд╛ рд╕реНрд╡рд░реВрдкрд╛рдд рд▓рд┐рд╣рд╛: рдкреНрд░рддрд┐ IP, рдкреНрд░рддрд┐ key, рдкреНрд░рддрд┐ user, рдкреНрд░рддрд┐ endpoint, global. рдордЧ 429 рдЙрддреНрддрд░рд╛рдВрдЪреНрдпрд╛ рд╕рдВрдЦреНрдпреЗрдЪрд╛ graph рдХрд╛рдврд╛. рдЕрдЪрд╛рдирдХ рд╡рд╛рдв рдореНрд╣рдгрдЬреЗ рдПрдХрддрд░ рд╣рд▓реНрд▓рд╛ рдХрд┐рдВрд╡рд╛ рдЦрд▒реНрдпрд╛ рдкрд╛рд▓рдХрд╛рдВрд╕рд╛рдареА рдЦреВрдк рдХрдбрдХ limit тАФ рджреЛрдиреНрд╣реАрдВрдордзреНрдпреЗ рдПрдЦрд╛рджреНрдпрд╛ рдорд╛рдгрд╕рд╛рдиреЗ рдкрд╛рд╣рд╛рдпрд▓рд╛ рд╣рд╡реЗ.

тПня╕П рдкреБрдвреЗ

Limits рдмрд╛рд╣реЗрд░реВрди рдпреЗрдгрд╛рд░реЗ рд▓реЛрдВрдвреЗ рдерд╛рдВрдмрд╡рддрд╛рдд. рдкрдг рдЖрддрд▓рд╛ рдПрдЦрд╛рджрд╛ рднрд╛рдЧ рдЕрдкрдпрд╢реА рдЭрд╛рд▓рд╛ рддрд░ тАФ photo service, database, рд╕рдВрдкреВрд░реНрдг data centre? Design рдордзреВрдирдЪ resilience.

git checkout lesson-13-resilience

ЁЯЪж Lesson 12 тАФ Rate limiting: tokens in a jar at the office window

ЁЯУН You are here: Lesson 12 of 18 ┬╖ Next: lesson-13-resilience


ЁЯУж What's in this branch

Lessons 01тАУ11, plus protection against floods: a buggy app in a loop, a scraper, a login attack, or simply one school that sends too much. You learn the token bucket, the leaky bucket, fixed and sliding windows, where to enforce a limit (edge, gateway, API, per user, per key, global), 429 + Retry-After, and counters in Redis.

ЁЯзТ Explain like I'm 5

The planning office has one window for questions. One day a parent's phone has a bug. It asks the same question again and again, hundreds of times. Other parents cannot reach the window.

Aishwarya puts a jar of tokens at the window. The jar holds at most 10 tokens. Every question costs one token. A helper drops a new token into the jar 5 times a second. When the jar is empty, the answer is "please wait a moment" тАФ not an error, a polite stop.

So a parent can ask 10 quick questions at once (the tokens in the jar), and then about 5 a second after that. A normal parent never notices the jar. The broken phone is slowed down, and everyone else is served.

Katrina asks: "Why not just count 10 per second on the clock?" Aishwarya shows her: 10 questions at 0.9 seconds and 10 more at 1.1 seconds. Each clock second has only 10. But 20 arrived in 0.2 seconds. A counting window that slides with time does not have this hole.

ЁЯЧ║я╕П Diagram

flowchart LR
    app["ЁЯУ▒ parent's app<br/>12 requests at 0 s<br/>5 more at 0.5 s"]
    subgraph tb["ЁЯлЩ token bucket: 5 per s, burst 10"]
      jar["10 tokens at start<br/>+2.5 by 0.5 s"]
    end
    subgraph sw["ЁЯкЯ sliding window: 10 per 1 s"]
      log["log of the last 1 s<br/>still 10 at 0.5 s"]
    end
    app --> jar
    app --> log
    jar -->|"12 of 17 allowed"| api["ЁЯзй notice API"]
    log -->|"10 of 17 allowed"| api
    jar -.->|"empty"| no["ЁЯЪж 429 Too Many Requests<br/>Retry-After: 1"]

ЁЯЧ║я╕П Drawn version + a lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l12

тЭУ What

ЁЯдФ Why

Because one caller must not be able to take the service from everyone else. Lesson 02 sized the app for 3,507 req/s at peak тАФ for everyone. A single app in a retry loop, with no limit, can send more than that alone. A limit also protects money: 5M urgent SMS cost real money, and a stolen teacher account must not be able to send them ten times.

ЁЯФз How (in this repo)

In design/blocks.py:

ratelimit() in design/demo.py sends 12 requests at t = 0 s and 5 at t = 0.5 s through both. The snippet below adds a small fixed-window counter, written inline, to show the edge hole.

ЁЯзк Try it

python3 design/demo.py ratelimit
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import TokenBucket, SlidingWindow
burst = [0.0] * 12 + [0.5] * 5
for rate, b in ((5, 10), (5, 20), (10, 10), (1, 5)):
    tb = TokenBucket(rate, b); print(f"token bucket rate {rate:>2}/s burst {b:>2} тЖТ {sum(tb.allow(t) for t in burst):>2} of 17")
steady = [i * 0.1 for i in range(30)]          # one request every 100 ms for 3 s = 10 per second
tb, sw = TokenBucket(5, 10), SlidingWindow(10, 1.0)
print("steady 10/s for 3 s тЖТ bucket", sum(tb.allow(t) for t in steady), "of 30 ┬╖ window", sum(sw.allow(t) for t in steady), "of 30")
edge = [0.9] * 10 + [1.1] * 10                  # 10 just before a minute-mark, 10 just after
def fixed(times, limit=10, window=1.0):
    counts, ok = {}, 0
    for t in times:
        k = int(t // window)
        if counts.get(k, 0) < limit: counts[k] = counts.get(k, 0) + 1; ok += 1
    return ok
sw = SlidingWindow(10, 1.0)
print("20 requests around t=1.0 s тЖТ fixed window lets", fixed(edge), "in 0.2 s ┬╖ sliding window lets", sum(sw.allow(t) for t in edge))
EOF

тЬЕ Verify тАФ what you should see

ratelimit prints:

тФАтФА one parent's app sends 12 requests at t=0 s and 5 more at t=0.5 s
   token bucket (5/s, burst 10) тЖТ 12 of 17 allowed ┬╖ sliding window (10 per 1 s) тЖТ 10 of 17
   the bucket refilled 2.5 tokens in 0.5 s, so 2 more got in; the window still counts the first 10 until t=1.0 s
   token bucket: smooth rate + a burst allowance ┬╖ window: a hard count per period
   limit per user, per API key and globally; answer 429 with Retry-After; keep the counters in Redis

Your snippet prints:

token bucket rate  5/s burst 10 тЖТ 12 of 17
token bucket rate  5/s burst 20 тЖТ 17 of 17
token bucket rate 10/s burst 10 тЖТ 15 of 17
token bucket rate  1/s burst  5 тЖТ  5 of 17
steady 10/s for 3 s тЖТ bucket 24 of 30 ┬╖ window 30 of 30
20 requests around t=1.0 s тЖТ fixed window lets 20 in 0.2 s ┬╖ sliding window lets 10

The tests include тЬЕ L12 the token bucket refills, the window still counts.

ЁЯПБ What you just proved

The burst decides the first moment (10 tokens тЖТ 10 at once; 20 тЖТ all 17 pass), and the rate decides what follows (10/s refills 5 tokens in 0.5 s тЖТ 15). A steady 10 per second is fine for a window of "10 per second" (30 of 30), but a bucket of 5/s lets only 24 through: the burst hides the gap for a moment, then the rate rules. And the fixed window let 20 requests in 0.2 s тАФ twice its limit тАФ at the edge of two windows; the sliding window let 10.

тЪая╕П Common mistakes

ЁЯПн In production

On a real account тАФ an API Gateway usage plan: a token bucket (rate + burst) and a daily quota per API key:

aws apigateway create-usage-plan --name parents-app \
    --throttle burstLimit=10,rateLimit=5 \
    --quota limit=100000,period=DAY \
    --api-stages apiId=a1b2c3d4e5,stage=prod

AWS WAF rate-based rule at the edge тАФ block an IP address that sends more than 2,000 requests in 5 minutes (part of a web ACL's Rules):

{ "Name": "per-ip-flood", "Priority": 1, "Action": { "Block": {} },
  "Statement": { "RateBasedStatement": { "Limit": 2000, "EvaluationWindowSec": 300, "AggregateKeyType": "IP" } },
  "VisibilityConfig": { "SampledRequestsEnabled": true, "CloudWatchMetricsEnabled": true, "MetricName": "per-ip-flood" } }

NGINX in front of the API тАФ a leaky bucket per client address, with a burst, answering 429:

limit_req_zone $binary_remote_addr zone=perip:10m rate=5r/s;
server {
    location /api/ {
        limit_req zone=perip burst=10 nodelay;
        limit_req_status 429;
        proxy_pass http://notice_api;
    }
}

A sliding-window log per parent in Redis, atomic in one Lua script (keys expire by themselves):

-- KEYS[1] = "rl:parent:42"  ARGV = now_ms, window_ms, limit, request_id
redis.call("ZREMRANGEBYSCORE", KEYS[1], 0, ARGV[1] - ARGV[2])
if redis.call("ZCARD", KEYS[1]) < tonumber(ARGV[3]) then
  redis.call("ZADD", KEYS[1], ARGV[1], ARGV[4])
  redis.call("PEXPIRE", KEYS[1], ARGV[2])
  return 1
end
return 0

ЁЯПн Why this matters in production: write the limits into the API contract (lesson 03) as a table: per IP, per key, per user, per endpoint, global. Then graph the number of 429 answers. A sudden rise is either an attack or a limit that is too tight for real parents тАФ both need a person to look.

тПня╕П Next

Limits stop floods from outside. But what happens when a part inside fails тАФ the photo service, the database, a whole data centre? Resilience by design.

git checkout lesson-13-resilience
тЖР Previousdistributed transactionsNext тЖТresilience

This page is the lesson's README from the lesson-12-rate-limiting branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.