SD11.5 · LESSON 5 OF 6

Rate limits

Place authentication, object authorization and resource limits at explicit application boundaries.

THE IDEA

Rate limits

A token bucket (capacity C, refill r per second) allows bursts up to C and a steady rate r: with C = 10 and r = 2, an 8-token request leaves 2, two seconds later there are 6, a 7-token request is denied (and leaves 6) and a 6-token request is accepted. A fixed window resets on a boundary, so 100 requests at 0:59 plus 100 at 1:00 all pass; a sliding window does not. Several instances need a shared counter or an accepted approximation.

t=0s cost 8: accepted → 2 tokens left t=2s cost 7: DENIED → 6 tokens left t=2s cost 6: accepted → 0 tokens left a denied request does not take or create tokens

Different algorithms give different burst contracts. A limit shared by several instances needs coordination (a shared counter) and a policy for when that store is unavailable; independent per-instance counters can both over- and under-enforce.

Compare the two contracts.

Predict first. Can independent per-instance counters enforce one exact global limit without coordination?

Chapter context

A distributed application must identify callers and control which resources and effects they may access. Tenant boundaries and resource budgets must be enforced by trusted components rather than inferred from client-supplied identifiers.

TRY IT YOURSELF

Part 1. Do it hands-on

Run the bucket by hand, then write token-bucket, fixed-window and sliding-window limiters.

t=0s cost 8: accepted → 2 tokens left t=2s cost 7: DENIED → 6 tokens left t=2s cost 6: accepted → 0 tokens left a denied request does not take or create tokens

tokens after 2 s cost 7 accepted? (yes/no) tokens left after accepting 6 fixed-window burst independent counters enforce a global limit? (yes/no)

To do: A token bucket holds at most 10 tokens and refills 2 per second. An 8-token request at time 0 leaves 2. Tokens two seconds later?
To do: A request costing 7 arrives then. Accepted? Type yes or no
To do: A request costing 6 then arrives. Accepted, and the tokens left?
To do: A FIXED window allows 100 requests per minute. A client sends 100 at 0:59 and 100 more at 1:00. Requests accepted within those two seconds?
To do: Can independent per-instance counters enforce one exact global limit without coordination? Type yes or no

Part 2. Do it in code

class TokenBucket(capacity, rate): starts full. allow(cost, now): refill min(capacity, tokens + rate × (now − last)), set last = now; if tokens >= cost subtract it and return True, else return False and leave the tokens unchanged (no negative credit). ValueError for cost <= 0 or time going backwards.
class FixedWindow(limit, window): allow(now): the window index is int(now // window); the count resets in a new window; allow while count < limit.
class SlidingWindow(limit, window): allow(now): keep the timestamps of accepted requests; allow if fewer than `limit` accepted requests have a timestamp in (now − window, now].
split_limit(global_limit, n_instances): the per-instance limit when each instance enforces global_limit // n_instances independently.
wrongly_denied(global_limit, per_instance_counts): with independent per-instance limits (split_limit), how many requests are denied even though the GLOBAL total is within the limit: sum over instances of max(0, count − per-instance limit), but only if the total of all counts <= global_limit.

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = 0

    def allow(self, cost, now):
        pass

class FixedWindow:
    def __init__(self, limit, window):
        self.limit = limit
        self.window = window
        self.index = None
        self.count = 0

    def allow(self, now):
        pass

class SlidingWindow:
    def __init__(self, limit, window):
        self.limit = limit
        self.window = window
        self.times = []

    def allow(self, now):
        pass

def split_limit(global_limit, n_instances):
    pass

def wrongly_denied(global_limit, per_instance_counts):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can independent per-instance counters enforce one exact global limit without coordination?

ANot by themselves; each instance sees only its own traffic, so a shared counter or accepted approximation is needed.BYes, because summing the instance limits always gives the global limit.CYes, as long as every instance uses the same clock.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For a token bucket with capacity C, refill rate r, previous tokens b and elapsed time dt:

b'=\min(C,b+r\,dt).

Accept cost k only when $b'\ge k$ , then subtract k atomically. Clock behavior, concurrency and shared enforcement are additional implementation requirements.

Worked example

A bucket holds at most 10 tokens and refills 2/s. An 8-token request at time zero leaves 2. Two seconds later it has 6. A request costing 7 is denied and leaves 6; a request costing 6 is accepted and leaves zero. Rejected operations should not accidentally create negative credit under this contract.

Reference code

The following example uses the Python standard library and does not call a remote service.

capacity,rate,tokens=10,2,10
tokens-=8
assert tokens == 2
tokens=min(capacity,tokens+rate*2)
assert tokens == 6
assert tokens < 7
assert tokens >= 6
tokens-=6
assert tokens == 0

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Authentication is not object-level authorization. Cache and worker paths can cross tenant boundaries too. A global rate limit requires a stated distributed enforcement contract.