Implement a sliding-window rate limiter using a Redis Sorted Set — which commands run, in what order, and what are the failure modes you have to design around?
answer
- ZREMRANGEBYSCORE → ZCARD → ZADD → PEXPIRE
- member must be unique, not the bare timestamp
- whole sequence in one Lua script or it fails open
- memory = one entry per allowed request in window
- fixed-window counter = O(1) memory, 2x boundary burst
basics
~20 sPer subject, keep a Sorted Set whose scores are request timestamps. On each request: ZREMRANGEBYSCORE to drop entries older than the window, ZCARD to count, ZADD a uniquely-named entry if under the limit, and PEXPIRE the key. Run all four atomically in one Lua script.
solid answer
~60 sKey per subject, e.g. `rl:user:42`. Scores are request timestamps in milliseconds; members must be **unique** per request. Per request, atomically: 1. `ZREMRANGEBYSCORE key 0 (now - windowMs)` — evict entries that left the window. 2. `ZCARD key` — how many remain. 3. If below the limit: `ZADD key now <uniqueId>` and allow; otherwise deny. 4. `PEXPIRE key windowMs` — idle subjects evaporate instead of leaking memory. Wrap it in a Lua script (or `MULTI`) so a burst of concurrent requests cannot all read the same count and all be allowed. **Failure modes.** - **Non-unique members**: using the raw timestamp as the member means two requests in the same millisecond collapse into one entry and you undercount. Use `now:random` or a counter. - **Memory**: one member per allowed request per window — limit × active subjects. A 1000/min limit over a million users is a very different footprint from an `INCR` counter. - **Clock source**: pass one clock (server `TIME` or a single trusted client clock); mixed app-server clocks make windows wobble. - **Availability**: decide fail-open vs fail-closed when Redis is unreachable, and say so explicitly.
code
lua · 19 lineslocal key = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local member = ARGV[3] -- must be unique per request
local t = redis.call('TIME') -- {seconds, microseconds}
local now = (tonumber(t[1]) * 1000) + math.floor(tonumber(t[2]) / 1000)
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
local used = redis.call('ZCARD', key)
if used < limit then
redis.call('ZADD', key, now, member)
redis.call('PEXPIRE', key, window)
return {1, limit - used - 1} -- allowed, remaining
end
redis.call('PEXPIRE', key, window)
return {0, 0} -- deniedgo deeper
Describe the shape: scores are timestamps, remove old entries, count what is left, add a new entry if under the limit.
Give the exact command order including PEXPIRE, explain why the member must be unique, and state that the sequence has to be atomic.
Lead with the atomicity failure mode, name the clock-source decision, quantify the memory cost against a fixed-window counter, and handle Redis unavailability explicitly.
Position exact sliding windows as the precise-but-expensive point on a spectrum that includes approximated windows and token buckets, and decide based on limit size, subject count, precision requirements and the blast radius of a hot subject.
## The idea A sliding window asks: *how many requests has this subject made in the last W milliseconds, counted from right now?* A Sorted Set answers it directly because the score can be the request's timestamp and the structure supports range removal and counting by score. One key per rate-limited subject — user, API key, IP — keeps every operation single-key, which also means the whole limiter works unchanged in a clustered deployment since each subject's key lives entirely on one node. ## The command sequence With `now` in milliseconds and a window of `W`: 1. **`ZREMRANGEBYSCORE key 0 (now - W)`** — remove every entry whose timestamp has fallen out of the window. This is the "sliding" part; the window's trailing edge moves with each call. Cost is O(log N + M) for M removed entries. 2. **`ZCARD key`** — the number of requests still inside the window, O(1). 3. **If `count < limit`**: `ZADD key now <uniqueMember>` and allow the request. Otherwise deny and do **not** add — denied requests normally must not extend the window, or a client hammering you stays blocked forever. 4. **`PEXPIRE key W`** — refresh a key-level TTL so a subject that goes quiet has its key reclaimed automatically rather than sitting in memory until eviction pressure notices it. ### Why it must be atomic Steps 2 and 3 are a classic check-then-act. If ten concurrent requests each run `ZCARD` before any of them runs `ZADD`, all ten see a count below the limit and all ten are allowed — the limiter silently fails open under exactly the load it exists to control. Putting the whole sequence in a **Lua script** makes it a single server-side operation, so no other command interleaves. A `MULTI`/`EXEC` transaction also serialises the block, but a script is preferable here because the *decision* (allow or deny) depends on an intermediate result, which a plain transaction cannot branch on. ## Choosing the member The member is the part people get wrong. Members are unique in a Sorted Set: if you use `now` as both score and member, two requests arriving in the same millisecond produce one entry, and your counter undercounts — the limiter leaks requests precisely during bursts. The member must be unique per request: `"<now>-<random>"`, a UUID, or an `INCR`-derived sequence. It carries no other meaning, so its content is free; only its uniqueness matters. ## The clock Every timestamp must come from one clock. Two options: - **Server clock** — call `redis.call('TIME')` inside the script. All decisions use the Redis node's clock, so app-server skew disappears. Modern Redis replicates a script's *effects*, so a non-deterministic `TIME` call no longer breaks replicas or the AOF the way it did on very old versions. - **Client clock** — pass `now` as an argument. Simpler and keeps the script deterministic, but the window jitters by the spread of your fleet's clock skew, and a badly skewed host can grant itself a fresh window. Pick one and document it. Mixing them is how you get limits that behave differently depending on which pod served the request. ## Memory: the real trade-off This limiter stores **one Sorted Set member per allowed request inside the window**. Its footprint is roughly `activeSubjects × min(limit, requestsInWindow)` members, each costing member string plus per-entry overhead. A 100-per-minute limit across 100 000 active users is fine. A 10 000-per-minute limit across a million API keys is gigabytes, and you will discover that during a traffic spike. The alternatives sit on a spectrum: - **Fixed-window counter** (`INCR` + `EXPIRE`): O(1) memory per subject, but permits up to 2× the limit across a window boundary — a client can send `limit` requests at the end of one window and `limit` at the start of the next. - **Approximated sliding window**: keep the current and previous fixed-window counters and interpolate by how far into the current window you are. Two integers per subject, and the boundary burst largely disappears. This is what most large-scale limiters actually run. - **Token bucket / leaky bucket**: a couple of fields per subject (tokens, last-refill timestamp) updated in a script; O(1) memory, natural burst allowance, and usually the best fit when limits are large. The exact sorted-set window is the right answer when limits are small, precision matters, and you want the per-request audit trail the entries give you. Say that trade-off out loud — an interviewer asking for this design is usually probing whether you know it is the expensive option. ## Other failure modes to name - **Redis unavailable.** Fail open (allow traffic, lose protection) or fail closed (reject, risk an outage)? There is no universal answer; the point is that it must be a decision with an owner, plus a local in-process fallback limiter if the answer is fail-open. - **Distributed hot subject.** All requests for one subject hit one key on one node. A single extremely hot API key concentrates load; sharding it (`rl:user:42:{0..3}` with the limit divided) trades precision for spread. - **Cost of the eviction step.** `ZREMRANGEBYSCORE` is O(log N + M); after a long idle period the first request may remove many entries at once. Bounded by the limit, so it is usually fine, but it is why an oversized limit hurts twice. - **Denied requests and retries.** Return the time until the window frees a slot (derivable from the oldest entry via `ZRANGE key 0 0 WITHSCORES`) so clients can back off intelligently instead of spinning.
- What breaks if you run the four commands as separate round trips instead of one script?The count and the insert stop being atomic, so concurrent requests can all read a below-limit count before any of them writes, and all are allowed — the limiter fails open exactly under burst load. A Lua script executes as a single unit on the server, so no other client's commands interleave with the sequence. A MULTI/EXEC block also serialises the commands, but it cannot branch on the intermediate count, so the allow/deny decision would still have to happen in the client.
- Compare this design with an INCR-plus-EXPIRE fixed-window counter.The fixed-window counter stores one integer per subject, so its memory is constant regardless of the limit, but it allows up to twice the limit across a window boundary because the counter resets abruptly. The sorted-set version is exact at any instant but stores one member per allowed request in the window, so memory scales with limit times active subjects. The common middle ground keeps the current and previous window counters and interpolates, giving near-sliding accuracy at two integers per subject.
- Should a denied request be recorded in the sorted set?Normally no — if denials are added, a client that keeps retrying continuously refreshes the window and can never recover, turning a rate limit into a permanent block. Record only allowed requests so the window drains naturally as time passes. If you want to penalise abusive clients you should do it explicitly with a separate blocklist and its own TTL, rather than as an accidental side effect of the counting logic.
A bouncer with a stack of timestamped tickets: before each entry they throw away tickets older than an hour, count what is left, and only add a new ticket if the count is under capacity — and every ticket needs its own serial number or two guests arriving together share one.
saying these in an interview costs you the question
- Using the timestamp itself as the member, so requests in the same millisecond collapse into one entry
- Running the count and the insert as separate commands, letting concurrent bursts all pass the check
- Forgetting to expire the key, so every subject ever seen stays in memory forever
- Recording denied requests in the window, which makes a throttled client permanently blocked
- Ignoring the memory cost and claiming this scales the same as an INCR counter