Low-level design
Part 3 of 3 · LLM Gateway Rate LimiterRate Limiter - Concurrency, Retry-After & Composition
Why one RLock around the composed check still counts an RPM event when the burst denies, how retry_after_ms is computed, and how this round maps onto Redis Lua.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What does the gateway lock cover?
Answer
Both allows. Another thread cannot pass the RPM check while this thread is still in the bucket.
L2
What does the lock not undo?
Answer
The timestamp SlidingWindowLog appended before returning allowed.
L3
How does the bucket compute retry_after_ms?
Answer
The deficit divided by refill_per_sec, times 1000. A zero refill returns 0.
L4
How does the window compute retry_after_ms?
Answer
Milliseconds until the oldest timestamp plus the window length, and at least 0.
L5
Why not only atomics?
Answer
A deque of timestamps is a structural update. Atomics fit a single counter.
L6
How do you limit by API key and model?
Answer
A composite key, or a hierarchy of limiters with separate budgets.
L7
What is the production shape of this composition?
Answer
One Redis Lua script so the RPM debit and the burst debit commit or abort together.
Failure modes
RPM slot spent on a burst deny
The window allow returns before the bucket runs. The timestamp remains.
Retry of 0
A client that treats 0 as try again immediately will hammer a bucket that cannot refill.
Lock only inside each component
Without the gateway lock, one thread can pass RPM while another spends the last burst token between the two calls.
Misconceptions
The gateway lock makes the two budgets one transaction.
It makes the two calls atomic with respect to other gateway callers. It does not roll back the first allow.
An RWLock is the default upgrade.
Both checks write. A short exclusive lock matches the mutation.
Atomics replace the deque.
They replace a single counter. The log still needs a lock or a script.
Interviewer traps
Claim the deny is free.
RPM_LIMIT is free. BURST_LIMIT is not, in this composition.
Paste a second Lua script on this page.
Name the Redis page. Keep this page on the in-process order.
Design scenario
Same prompt for every reader.
Requirements
One gateway RLock, retry_after_ms from the denying component, a follow-up that would keep the RPM slot.
Traffic / scale
Two threads, one tenant, one token left in the bucket, room left in the window.
Latency
The critical section is two in-process structures.
Consistency
Callers of GatewayLimiter do not interleave between the two allows.
Availability
Both denials are Decisions.
Failure assumptions
- The window has room and the bucket does not.
- The refill rate is 0, so the bucket retry is 0.
Constraints
- Do not describe the RPM event as rolled back.
- Do not replace the deque with an atomic counter.
Prompt
Explain the composed allow, including the RPM event that survives a burst deny.
API
Which reason leaves a timestamp in the window?
Data
Which component computes retry from a deficit, and which from the oldest event?
Architecture
What would a single Lua script change about that order?
What the gateway lock guarantees
Prefer
One lock, RPM then burst
Other callers cannot slip between the two allows. The first allow still sticks.
- RPM_LIMIT returns before the bucket runs.
- BURST_LIMIT returns after the timestamp is stored.
- retry_after_ms is copied from the deny.
Alternative
Reserve, then commit
Peek both budgets, then append and spend only if both allow.
- A burst deny would leave the window alone.
- That is a follow-up, not this module.
- One Lua script is the distributed form of that follow-up.
Composition
GatewayLimiter.allow holds self._lock and then calls the two components. Each component also takes its own RLock. The gateway lock is what stops another gateway caller from entering between them.
def allow(self, tenant: str, tokens: float = 1.0) -> Decision:
with self._lock:
d1 = self.rpm.allow(tenant)
if not d1.allowed:
return Decision(False, d1.remaining, d1.retry_after_ms, "RPM_LIMIT")
d2 = self.burst.allow(tenant, tokens)
if not d2.allowed:
return Decision(False, d2.remaining, d2.retry_after_ms, "BURST_LIMIT")
return Decision(True, min(d1.remaining, d2.remaining), 0, "OK")If the RPM check is counted before the burst fails, you spent an RPM slot without serving the call. The interview follow-up is reserve-then-commit, check the burst first, or use a single Lua script in Redis.
The timestamp that sticks
Diagram 1. BURST_LIMIT is a deny that already wrote the window.
- 1
Acquire
The gateway RLock is held for both component calls. - 2
RPM allow
A full window returns RPM_LIMIT and does not touch the bucket. - 3
Append
A window that has room appends now before it returns. - 4
Burst deny
The bucket returns BURST_LIMIT. The timestamp is still in the deque. - 5
Retry
retry_after_ms is the bucket deficit, or 0 when the refill rate is 0.
Decisions
- 1
1. Acquire gateway lock
- next2. RPM allow
- 2
2. RPM allow
- next3. Allowed?
- ?
3. Allowed?
- No4. Return RPM_LIMIT with retry
- Yes5. Burst allow
- 4
4. Return RPM_LIMIT with retry
- 5
5. Burst allow
- next6. Allowed?
- ?
6. Allowed?
- No7. Failure: BURST_LIMIT, RPM already counted
- Yes8. Return OK
- 7
7. Failure: BURST_LIMIT, RPM already counted
- 8
8. Return OK
Lesson map
Rate Limiter - Concurrency, Retry-After & Composition
Why one RLock around the composed check still counts an RPM event when the burst denies, how retry_after_ms is computed, and how this round maps onto Redis Lua.
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. Acquire gateway lock"] b["2. RPM allow"] c["3. Allowed?"] d["4. Return RPM_LIMIT with retry"] e["5. Burst allow"] f["6. Allowed?"] g["7. Failure: BURST_LIMIT, RPM already counted"] h["8. Return OK"] a -->|continues| b b -->|continues| c c -->|No| d c -->|Yes| e e -->|continues| f f -->|No| g f -->|Yes| h
Flow
- 1
Two structures change?
- deque and tokensGateway RLock around both allows
- 2
Gateway RLock around both allows
- 3
Must both commit or neither?
- ProductionOne Redis Lua script
- 4
One Redis Lua script
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 only atomics?
Answer
Per-key maps of deques need structural mutations. Atomics shine for single counters, not window logs.
How do you limit by API key and model?
Answer
Use a composite key of the API key and the model, with separate budgets, or a hierarchy of limiters.
Why is RPM_LIMIT different from BURST_LIMIT?
Answer
RPM_LIMIT returns before any new timestamp is the deny itself: the window refused to append. BURST_LIMIT returns after a successful append.
What would checking the burst first change?
Answer
A short bucket would deny before the window appends. You can still oversell the window if you then append without a second look. Reserve-then-commit closes that.
Why copy retry_after_ms instead of adding the two waits?
Answer
Only the denying component has a wait. The other component allowed. Adding a zero does nothing, and adding two denials cannot happen in this order because the second call is skipped when the first denies.
Why map this onto Lua instead of N local limiters?
Answer
N processes each enforce their own deques. The Lua page is the atomic shared debit. This page stops at the in-process order.
Related
The series pager also walks these pages.