Low-level design
Part 1 of 3 · LLM Gateway Rate LimiterRate Limiter for an LLM Gateway - LLD Spec & Concepts
Machine-coding LLD for an in-process LLM gateway limiter: a per-tenant token bucket, an exact sliding-window log, and a composed decision with remaining and retry_after_ms.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does allow return?
Answer
allowed, remaining, retry_after_ms, and a reason such as OK, RPM_LIMIT, or BURST_LIMIT.
L2
What is the key?
Answer
The tenant id. A later composite can add the model.
L3
How does the bucket refill?
Answer
Before the spend, tokens become min(capacity, tokens + elapsed * refill_per_sec).
L4
How does the sliding window decide?
Answer
Append now, drop timestamps older than the window, and reject when the deque is already at the limit.
L5
Which check runs first?
Answer
The RPM sliding window, then the token bucket.
L6
What does a burst deny leave behind?
Answer
The RPM allow already appended a timestamp. That slot was counted.
L7
Which ideas stay on other pages?
Answer
Leaky versus token versus sliding, the Redis Lua script, and a limit that must not grow with pod count.
Failure modes
Wall clock in the test
Refill and the window edge depend on the scheduler unless the clock is injected.
Refill after the spend
The bucket drifts because elapsed time is applied too late.
One bucket for every tenant
A hot tenant drains a neighbor.
Misconceptions
A local counter is the fleet quota.
Each process has its own deques and buckets. The distributed gateway page is that gap.
The window log is the approximate counter.
This coding round stores timestamps. The weighted counter is the concept page.
A deny rolls back the RPM event.
GatewayLimiter records the RPM allow before it asks the bucket.
Interviewer traps
Open with the Redis script.
Ship TokenBucket, SlidingWindowLog, and the tests. Then name the Lua page.
Return 200 with an empty body.
Return the Decision. The reason is RPM_LIMIT or BURST_LIMIT.
Design scenario
Same prompt for every reader.
Requirements
Token bucket with an injected clock, exact sliding-window log, composed Decision, RLock, tests.
Traffic / scale
One process, many tenants, one hot tenant in the flood test.
Latency
A lock, a short deque, and two floats. No network hop in this round.
Consistency
Two threads cannot both spend the last burst token.
Availability
A deny is a Decision. A non-positive cost is an error.
Failure assumptions
- The burst check fails after the RPM check has already recorded the event.
- Eighty threads share one tenant and a burst of 50.
Constraints
- Do not share one bucket across tenants.
- Do not call the wall clock from the tests.
Prompt
Admit an LLM call for a tenant only when the RPM window and the burst bucket both allow it.
API
Which fields are on Decision?
Data
What does SlidingWindowLog store per key?
Architecture
Why is the gateway RLock held across both allows?
What this coding round ships
Prefer
In-process bucket and window log
Fast to test. The fake clock makes refill and the window edge deterministic.
- Decision carries remaining and retry_after_ms.
- One RLock covers the composed allow.
- Keys do not share a bucket.
Alternative
Redis plus Lua
Atomic across replicas, and a network hop.
- That script is its own study.
- This page does not paste it.
- N local copies are not one quota.
Overview
This cluster is the limiter you implement in one process. TokenBucket.allow(key, cost) refills, then spends. SlidingWindowLog.allow(key) keeps timestamps. GatewayLimiter.allow(tenant, tokens) asks the RPM window first and the burst bucket second. The comparison of token, leaky, and sliding windows, the Redis script, and the multi-pod quota are already studies. Link them. Do not rewrite them.
Spec summary
| Component | Contract |
|---|---|
| TokenBucket | capacity, refill per second, allow(key, cost) |
| SlidingWindowLog | limit, window seconds, allow(key) |
| GatewayLimiter | RPM window, then burst bucket |
| Decision | allowed, remaining, retry_after_ms, reason |
| Concurrency | RLock so a concurrent allow cannot oversell the burst |
Step-by-step design
- Key by tenant id. A later key can append the model.
- Store tokens and a last-update time. Refill with min(capacity, tokens + elapsed * rate) before the spend.
- Append now on the window log and drop timestamps older than the window. Reject when the deque is already full.
- Hold one lock across the RPM check and the burst check.
- Return retry_after_ms from the token deficit or from the oldest timestamp.
- Test with a fake clock and a thread flood.
RPM, then burst
Diagram 1. The window records the event before the bucket can deny.
- 1
Request
The caller passes a tenant and a positive token cost. - 2
Gateway lock
One RLock covers both component allows. - 3
RPM window
Drop old timestamps. Reject with RPM_LIMIT when the deque is full. - 4
Burst bucket
Refill, then spend. A short bucket returns BURST_LIMIT. - 5
Allow
Both checks passed. Remaining is the smaller of the two leftovers.
Decisions
- 1
1. Request tenant and cost
- next2. Sliding window RPM check
- 2
2. Sliding window RPM check
- next3. Under RPM?
- ?
3. Under RPM?
- No4. Failure: RPM_LIMIT
- Yes5. Token bucket burst check
- 4
4. Failure: RPM_LIMIT
- 5
5. Token bucket burst check
- next6. Tokens enough?
- ?
6. Tokens enough?
- No7. Failure: BURST_LIMIT
- Yes8. Success: deduct and allow
- 7
7. Failure: BURST_LIMIT
- 8
8. Success: deduct and allow
Lesson map
Rate Limiter for an LLM Gateway - LLD Spec & Concepts
Machine-coding LLD for an in-process LLM gateway limiter: a per-tenant token bucket, an exact sliding-window log, and a composed decision with remaining and retry_after_ms.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1. Request tenant and cost"] b["2. Sliding window RPM check"] c["3. Under RPM?"] d["4. Failure: RPM_LIMIT"] e["5. Token bucket burst check"] f["6. Tokens enough?"] g["7. Failure: BURST_LIMIT"] h["8. Success: deduct and allow"] a -->|continues| b b -->|continues| c c -->|No| d c -->|Yes| e e -->|continues| f f -->|No| g f -->|Yes| h
Flow
- 1
Which limiter?
- Requests per minuteSliding window log
- Burst tokensToken bucket
- 2
Sliding window log
- nextCompose: RPM then burst
- 3
Token bucket
- nextCompose: RPM then burst
- 4
Compose: RPM then burst
Pitfalls
- Calling the wall clock inside the test instead of injecting a clock.
- Refilling after the spend, so elapsed time is applied too late.
- Sharing one bucket across tenants.
- Returning HTTP 200 with an empty body instead of a Decision.
Concepts used, learn more
Read the underlying idea on its own study page. This lesson applies it. It does not replace those pages.
- Rate Limiting: Token Bucket, Leaky Bucket & Sliding Window
- Token Bucket vs Leaky Bucket vs Sliding Window
- Redis + Lua Atomic Rate Limiters
- Distributed Rate Limits Across Gateways
- Mutexes, Condition Variables, Deadlocks & Happens-Before
- Mutex vs RWLock
- When Locks Win — Contention, Fairness & Hybrid Designs
- Atomics vs Locks
- Low-Level Design Under Time — Interfaces, State & Tradeoffs
Interview Q&A
Why not key only by IP?
Answer
Many users share a NAT. The tenant names the budget that spends tokens. A later key can be the API key plus the model.
Why a deque instead of a weighted counter?
Answer
This round wants an exact count of timestamps inside the window. The weighted counter is the approximate design on the concept page.
What is wrong with refilling after the deduct?
Answer
The elapsed time belongs to the tokens you are about to spend. Applying it afterward drifts the bucket.
Where does Redis belong?
Answer
When more than one process must share one quota. The Lua page is that atomic debit. This page is the single-process contract.
Why can BURST_LIMIT still consume an RPM slot?
Answer
GatewayLimiter calls the window allow before the bucket allow. The window appends before it returns. The follow-up is to check burst first, reserve then commit, or move both checks into one script.
Why an RLock instead of two atomics?
Answer
The window is a deque and the bucket is a pair of fields. Atomics fit a single counter. They do not fit a structural log.
Related
The series pager also walks these pages.