API Gateway Rate Limiter

API Gateway Rate Limiter

You've joined the Platform team that owns the public API gateway. Every request carries an API key and passes through ratelimit before it reaches a backend. Today there is a single fixed-window limiter with one global policy. This sprint you have a bug report from support, then three tickets: a sliding-window algorithm, per-plan tiers with cleanup of idle keys, and bulk requests that must stay fast at scale.

Codebase

How your code is run

run(operations: list) -> list creates a fresh gateway, executes each operation in order and returns exactly one output per operation. Timestamps (now) are integer epoch seconds and never decrease from one operation to the next.

Unknown operations return "error: unknown operation: <name>".

Existing behaviour.

• A *policy* is {"algorithm": "fixed_window" | "sliding_log", "limit": int, "window_s": int}; limit and window_s are positive integers (booleans are not integers). The default policy is 5 requests per 60 seconds, fixed window. configure replaces the default policy and discards the state of keys that use it; an invalid policy is rejected and changes nothing.
• A key may be sent bare or as "Bearer <key>" (prefix case-insensitive, surrounding whitespace ignored). Keys are otherwise case-sensitive. An empty or non-string key is "error: missing api key".
• Keys in config.EXEMPT_KEYS are never limited and never tracked: request returns {"allowed": true, "remaining": null, "retry_after": 0} and counts as allowed in stats.
• Fixed window. Windows are aligned to the epoch: with window_s = 60 they are [0, 60), [60, 120), ... A key may make limit requests per window; rejected requests are not counted. remaining is how many more requests the key can make in the current window after this one. retry_after is 0 when allowed, otherwise the seconds from now until the current window ends. A rejected request has remaining: 0.
• stats.allowed / stats.rejected count requests. tracked_keys is the number of non-exempt keys currently holding limiter state.

Worked example (default policy):

[["request", "Bearer sk_a", 120], ["request", "sk_a", 121], ["request", "sk_b", 130], ["stats", 130]]

returns

[{"allowed": true, "remaining": 4, "retry_after": 0},
 {"allowed": true, "remaining": 3, "retry_after": 0},
 {"allowed": true, "remaining": 4, "retry_after": 0},
 {"tracked_keys": 2, "allowed": 3, "rejected": 0}]

Part 1 — Customers who were idle get a burst of free requests

Goal: make the fixed-window limiter enforce limit per window for every key, and report remaining as specified above.

Support ticket: *"One of our integrations sat idle over the weekend. When it came back it sent about a dozen calls in a few seconds and none were throttled. Separately, our dashboard shows the header X-RateLimit-Remaining one higher than it should be."*

Example. With the default policy, five requests at T..T+4 are allowed, then seven requests at T+600..T+606 (where T is a multiple of 60) must return remaining 4, 3, 2, 1, 0, then two rejections with retry_after 55 and 54.

Part 2 — Sliding-window log (RL-88)

Goal: implement SlidingLogLimiter so that policies with "algorithm": "sliding_log" work through configure.

Rules

1. A request made at time t counts against the limit while now - window_s < t; it stops counting at now == t + window_s. So with limit = 2, window_s = 10, requests at 100 and 105 are both counted at 109, and the request at 100 has left the window at 110.
2. A request is allowed if fewer than limit requests are counted. Rejected requests are not logged and never extend the block.
3. remaining is limit minus the number of counted requests after this one (0 when rejected).
4. When rejected, retry_after is the seconds from now until the oldest counted request leaves the window (oldest + window_s - now). It is 0 when allowed.
5. reset, tracked_keys and stats behave as for fixed windows (a key has state once it has made a request). Keys are independent.

Example. configure {"algorithm": "sliding_log", "limit": 2, "window_s": 10}, then requests from one key at 100, 105, 109, 110. Results: allowed (remaining 1), allowed (0), rejected (retry_after 1), allowed (0).

Part 3 — Plan tiers and idle-key eviction (RL-102)

Goal: enforce the per-plan policies in config.TIERS, and stop remembering keys that have gone quiet.

Rules

1. A key assigned to a tier in TierDirectory uses that tier's policy from config.TIERS (its own algorithm, limit and window) instead of the default policy. Keys with no tier, or tier "default", use the gateway's default policy. Each tier keeps its own separate state; configure never changes tier policies.
2. assign_tier returns the tier name that was passed (including "default"). Exempt keys may be assigned a tier but are still never limited or tracked. Existing validation is unchanged.
3. Changing a key's tier (including to or from default) discards its limiter state, so it starts fresh under the new policy. Assigning the tier it already has does not discard anything.
4. configure discards state only for keys on the default policy. Keys on a tier keep their state, and their tier assignment is never touched.
5. Eviction. A key is *idle* once now - last_request >= config.EVICT_AFTER_SECONDS (3600), where last_request is the time of its most recent request and rejected requests count. Idle keys lose all limiter state, as if reset had been called. Eviction happens at the start of every request and stats operation, using that operation's now, so tracked_keys never includes idle keys. A key at exactly 3599 seconds idle is kept.
6. Eviction forgets limiter state only. A key's tier assignment survives eviction.
7. reset forgets a key's state in whatever limiter it is in, and returns true only if it had state.

Example. Assign sk_pro to pro (20 per 60s, sliding). Twenty-one requests at T return remaining 19 down to 0, then a rejection with retry_after 60. A request from the untiered sk_free at T is allowed with remaining 4. Assigning sk_pro to enterprise returns "enterprise"; its next request at T+1 has remaining 999. Assigning tier "gold" returns "error: unknown tier: gold".

Part 4 — Bulk requests (stretch)

Goal: add ["request_batch", key, now, units] so a client can submit units requests that arrive together, without the run taking a minute when units is in the millions.

Rules

1. units must be an integer of at least 1 (booleans are not integers); otherwise "error: invalid units". A bad key is reported first ("error: missing api key").
2. A batch behaves exactly like units consecutive single requests at the same now: the first ones that fit are allowed, the rest are rejected, and rejected ones are not logged or counted by the limiter.
3. It returns {"allowed": int, "rejected": int, "remaining": int, "retry_after": int}. remaining and retry_after are the values the last of the units requests would have returned: remaining is the room left afterwards, and retry_after is 0 when every unit was allowed, otherwise the same wait a single rejected request would report.
4. Tiers, eviction and reset apply exactly as for request. A batch counts as activity for eviction (once, at now). stats counts units, not batches. An exempt key returns {"allowed": units, "rejected": 0, "remaining": null, "retry_after": 0}.
5. Hidden tests send batches of up to millions of units, for every algorithm and tier, and the whole suite shares a few seconds. Memory and time per batch must not depend on units or on how many requests are already logged.

Example. Default policy: ["request_batch", "sk_a", 600, 7] returns {"allowed": 5, "rejected": 2, "remaining": 0, "retry_after": 60}. A later ["request", "sk_a", 601] is rejected with retry_after 59. ["request_batch", "sk_a", 660, 3] returns {"allowed": 3, "rejected": 0, "remaining": 2, "retry_after": 0}, and ["stats", 660] then returns {"tracked_keys": 1, "allowed": 8, "rejected": 3}.

Notes

• keys.py, policy.py, registry.py, metrics.py and tiers.py are known-good.
• You may use the AI assistant freely. Say what you're asking it and check what it gives you.
• Later parts must not break earlier ones; hidden tests re-check Part 1-3 behaviour. Parts 1-3 is a strong result; Part 4 is a stretch.
• The files in tests/ are not run by the grader. Use them, extend them, or ignore them.