Last month our trending-videos endpoint started returning garbage latency numbers. Not because the queries got slower, but because a handful of clients discovered they could hammer /api/v1/trending?region=DE a few thousand times a minute and our fixed-window rate limiter happily let them through in bursts. The window would reset at the top of each minute, every scraper on the planet would fire at :00, and our SQLite WAL readers would spike hard enough to blow through the LiteSpeed request budget. Legitimate European users refreshing their feed got throttled as collateral damage.
The fix was not a bigger box. It was a better algorithm. Fixed windows are cheap and wrong; sliding windows are cheap enough and right. This post walks through how we replaced our naive limiter with a Redis-backed sliding window log, then a sliding window counter, and how we kept it GDPR-clean for the European traffic that makes up almost all of what we serve at ViralVidVault. Everything here runs in production against PHP 8.4, with a Cloudflare Worker doing edge pre-filtering and Redis holding the state.
Why the Fixed Window Fails
The fixed-window counter is the first thing everyone builds. You pick a bucket key like rl:{ip}:{minute}, INCR it, set a TTL of 60 seconds, and reject when the count crosses a threshold. It is one round trip and constant memory. It is also exploitable.
Imagine a limit of 100 requests per minute. A client sends 100 requests at 12:00:59 and another 100 at 12:01:00. Both windows are individually within the limit, but you just served 200 requests in a two-second span. The boundary is a free burst doorway, and once a scraper learns where the boundary is, it will camp on it. For a video discovery API this is exactly the traffic shape you do not want: synchronized spikes that map onto expensive ORDER BY view_velocity DESC scans.
The sliding window fixes the boundary problem by making the window move continuously with the current request instead of snapping to clock minutes. There are two common implementations. The sliding window log stores a timestamp for every request and counts how many fall inside the trailing window. It is exact but memory-heavy. The sliding window counter approximates by weighting the previous fixed window's count. It is cheap and accurate enough. We ended up running both, for different tiers.
The Sliding Window Log With a Sorted Set
Redis sorted sets are the natural fit for the log approach. Each member is a unique request identifier, and its score is the request timestamp in microseconds. To decide whether a request is allowed you:
- Remove every member older than
now - windowwithZREMRANGEBYSCORE. - Count the remaining members with
ZCARD. - If the count is under the limit, add the new request with
ZADD. - Refresh the key TTL so idle clients get garbage collected.
The trap is that steps 1 through 4 must be atomic. If two requests interleave between the ZCARD and the ZADD, both can read a count under the limit and both get admitted, blowing past the ceiling. You cannot solve this with a MULTI/EXEC transaction alone because the admit decision depends on the read result. You need a Lua script, which Redis runs atomically as a single unit.
-- sliding_window_log.lua
-- KEYS[1] = rate limit key
-- ARGV[1] = now (microseconds)
-- ARGV[2] = window (microseconds)
-- ARGV[3] = limit (max requests in window)
-- ARGV[4] = unique member id for this request
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local member = ARGV[4]
-- 1. drop everything outside the trailing window
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
-- 2. how many requests are left inside the window
local count = redis.call('ZCARD', key)
if count < limit then
-- 3. admit: record this request
redis.call('ZADD', key, now, member)
-- 4. let the key expire once the window fully drains
redis.call('PEXPIRE', key, math.ceil(window / 1000))
return {1, limit - count - 1} -- allowed, remaining
else
redis.call('PEXPIRE', key, math.ceil(window / 1000))
return {0, 0} -- denied, remaining 0
end
Because the whole script executes atomically on the Redis thread, there is no interleaving window. The return value is a two-element array: an allow flag and the remaining budget, which we hand straight to the client in headers.
Here is the PHP 8.4 wrapper we use. Note the script is loaded once with SCRIPT LOAD and thereafter called by SHA with EVALSHA, so we are not shipping the source on every request.
<?php
declare(strict_types=1);
final class SlidingWindowLog
{
private string $sha;
public function __construct(
private readonly Redis $redis,
private readonly int $limit,
private readonly int $windowSeconds,
) {
$script = file_get_contents(__DIR__ . '/sliding_window_log.lua');
$this->sha = $this->redis->script('load', $script);
}
/**
* @return array{allowed: bool, remaining: int}
*/
public function check(string $identity): array
{
$nowMicros = (int) (microtime(true) * 1_000_000);
$windowMicros = $this->windowSeconds * 1_000_000;
// Unique member: timestamp + random suffix avoids score collisions
$member = $nowMicros . ':' . bin2hex(random_bytes(4));
/** @var array{0:int,1:int} $result */
$result = $this->redis->evalSha(
$this->sha,
[
"rl:log:{$identity}",
(string) $nowMicros,
(string) $windowMicros,
(string) $this->limit,
$member,
],
1, // number of KEYS
);
return [
'allowed' => $result[0] === 1,
'remaining' => $result[1],
];
}
}
One subtlety: the member must be unique. If you use the bare timestamp as the member and two requests land in the same microsecond, the second ZADD overwrites the first instead of adding a new entry, and you undercount. The random suffix guarantees distinct members even under a microsecond collision.
The Memory Problem, and the Counter Alternative
The log is exact, but it stores one sorted-set entry per request inside the window. At 100 requests per minute per client that is fine. At our real traffic — thousands of distinct European IPs, some pulling the /api/v1/feed endpoint aggressively — the memory adds up, and the ZREMRANGEBYSCORE cost grows with the number of expired entries it has to sweep. For high-volume identities we switched to the sliding window counter, which uses two integers instead of a set of timestamps.
The idea: keep a counter for the current fixed window and the previous one. Weight the previous window by how much of it still overlaps the trailing sliding window. If you are 25% of the way into the current minute, then 75% of the previous minute still counts.
estimated = current_count + previous_count * (1 - elapsed_ratio)
If estimated is below the limit, admit and increment the current counter. This is an approximation — it assumes requests were spread evenly across the previous window — but the error is bounded and small in practice. Cloudflare published numbers years ago showing well under 1% of requests get a wrong decision at real traffic distributions, and that matches what we see. The payoff is two counters per identity instead of an unbounded log.
-- sliding_window_counter.lua
-- KEYS[1] = current window counter key
-- KEYS[2] = previous window counter key
-- ARGV[1] = limit
-- ARGV[2] = elapsed ratio in current window (0.0 - 1.0)
-- ARGV[3] = current window TTL in seconds
local curr = tonumber(redis.call('GET', KEYS[1]) or '0')
local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
local limit = tonumber(ARGV[1])
local elapsed = tonumber(ARGV[2])
local ttl = tonumber(ARGV[3])
local estimated = curr + math.floor(prev * (1 - elapsed))
if estimated < limit then
local newCount = redis.call('INCR', KEYS[1])
if newCount == 1 then
-- keep two windows worth of data so the previous key survives
redis.call('EXPIRE', KEYS[1], ttl * 2)
end
return {1, limit - estimated - 1}
else
return {0, 0}
end
The caller computes which fixed window it is in and the elapsed ratio, then passes both window keys. The current window key derives from floor(now / window) and the previous from floor(now / window) - 1.
<?php
declare(strict_types=1);
final class SlidingWindowCounter
{
private string $sha;
public function __construct(
private readonly Redis $redis,
private readonly int $limit,
private readonly int $windowSeconds,
) {
$script = file_get_contents(__DIR__ . '/sliding_window_counter.lua');
$this->sha = $this->redis->script('load', $script);
}
/**
* @return array{allowed: bool, remaining: int}
*/
public function check(string $identity): array
{
$now = microtime(true);
$windowIndex = (int) floor($now / $this->windowSeconds);
$elapsed = ($now - ($windowIndex * $this->windowSeconds)) / $this->windowSeconds;
$currKey = "rl:cnt:{$identity}:{$windowIndex}";
$prevKey = "rl:cnt:{$identity}:" . ($windowIndex - 1);
/** @var array{0:int,1:int} $result */
$result = $this->redis->evalSha(
$this->sha,
[$currKey, $prevKey, (string) $this->limit, (string) $elapsed, (string) $this->windowSeconds],
2, // two KEYS
);
return [
'allowed' => $result[0] === 1,
'remaining' => max(0, $result[1]),
];
}
}
Choosing the Identity Key Without Breaking GDPR
This is the part most rate-limiter tutorials skip, and it is the part that matters most when your entire audience is European. A rate limiter has to identify the caller, and the obvious identifier is the raw IP address. Under GDPR a raw IP is personal data, and storing it — even for 60 seconds in Redis — needs a lawful basis and a retention story you can defend.
Our approach is to never store the raw IP. We derive a rotating pseudonymous key by hashing the IP with a daily salt, so the limiter can still distinguish clients but the stored value is not reversible back to a person and does not persist beyond its purpose.
<?php
declare(strict_types=1);
function rateLimitIdentity(string $ip, string $endpoint): string
{
// Daily-rotating salt kept out of the request path (env / KV).
// Rotating it means yesterday's hashes cannot be correlated to today's.
$salt = getenv('RL_DAILY_SALT') ?: 'fallback-not-for-prod';
$day = gmdate('Y-m-d');
// Truncated keyed hash: enough to separate clients,
// not enough to be a durable identifier.
$digest = hash_hmac('sha256', $ip . '|' . $day, $salt);
return substr($digest, 0, 24) . ':' . $endpoint;
}
Three properties make this defensible. The salt rotates daily, so the pseudonym is not stable long enough to build a profile. The value is keyed-hashed, so it is not reversible without the salt. And the Redis TTL means the data is gone within a window or two of the last request — data minimization by construction. We document this in our processing records as transient abuse-prevention state, which is a well-established legitimate interest. Nothing about the limiter lands in our SQLite WAL analytics store, which we keep aggregate-only anyway.
Edge Pre-Filtering With a Cloudflare Worker
Even an atomic Lua script costs a round trip to Redis. For obviously abusive clients we do not want to pay that. We run a coarse first-pass limiter at the Cloudflare edge using the Workers Rate Limiting binding, which absorbs the worst offenders before they ever reach origin. The Worker handles the crude ceiling; Redis at origin handles the precise per-endpoint budgets.
// wrangler.toml declares a binding:
// [[unsafe.bindings]]
// name = "API_LIMITER"
// type = "ratelimit"
// namespace_id = "1001"
// simple = { limit = 600, period = 60 }
export default {
async fetch(request, env, ctx) {
const url = new URL(request.url);
if (!url.pathname.startsWith('/api/')) {
return fetch(request);
}
// Coarse edge ceiling keyed on CF-Connecting-IP.
// The origin still runs the precise sliding window.
const ip = request.headers.get('CF-Connecting-IP') ?? 'unknown';
const { success } = await env.API_LIMITER.limit({ key: ip });
if (!success) {
return new Response(
JSON.stringify({ error: 'rate_limited', scope: 'edge' }),
{
status: 429,
headers: {
'Content-Type': 'application/json',
'Retry-After': '10',
},
},
);
}
return fetch(request);
},
};
The edge limiter is intentionally loose — 600 per minute — because it is a blunt instrument keyed on IP with no endpoint granularity. Its job is to shed the DoS-shaped traffic so origin Redis only sees plausibly legitimate clients. The origin then applies tighter, endpoint-specific sliding windows: 100/min for /api/v1/trending, 30/min for the heavier /api/v1/feed, 10/min for search.
Wiring It Into the Request Lifecycle
At origin the limiter runs before any query executes. The response carries the standard headers so well-behaved clients can back off on their own instead of retrying blindly.
<?php
declare(strict_types=1);
$limiter = new SlidingWindowCounter($redis, limit: 100, windowSeconds: 60);
$identity = rateLimitIdentity($_SERVER['HTTP_CF_CONNECTING_IP'] ?? $_SERVER['REMOTE_ADDR'], 'trending');
$verdict = $limiter->check($identity);
header('X-RateLimit-Limit: 100');
header('X-RateLimit-Remaining: ' . $verdict['remaining']);
if (!$verdict['allowed']) {
http_response_code(429);
header('Retry-After: 30');
header('Content-Type: application/json');
echo json_encode(['error' => 'rate_limited', 'scope' => 'origin']);
exit;
}
// ...only now do we touch SQLite
One operational note: when Redis is unreachable, decide your failure mode deliberately. We fail open for the origin limiter — if Redis is down, requests pass — because the Cloudflare edge ceiling is still standing between us and a real flood, and failing closed would turn a Redis blip into a full outage. If you have no edge tier, fail closed instead. Never leave it undefined; a try/catch that silently swallows the exception is a fail-open you did not choose on purpose.
What We Measured Afterward
The boundary bursts disappeared, which was the whole point. Our p99 latency on /api/v1/trending dropped by roughly a third because the synchronized :00 spikes no longer collided on the SQLite WAL readers. Redis memory for the limiter sits in the low single-digit megabytes because the counter approach stores two integers per active identity and everything expires on its own. And the GDPR posture is clean: no raw IPs at rest, salted daily rotation, TTL-driven minimization, nothing bleeding into analytics.
If you take three things from this:
- Sliding beats fixed whenever the boundary burst is a real threat, and for any public API it is.
- Use the log for exactness, the counter for scale. The counter's approximation error is small enough to ignore and the memory savings are large enough to matter.
- Make the atomic decision atomic. Read-then-write across two commands is a race; a Lua script makes admit-or-reject a single indivisible step.
And if your users are European, treat the identity key as personal data from the first line, not as an afterthought once legal asks. It is far easier to salt and truncate up front than to retrofit compliance onto a limiter that has been quietly logging raw IPs into Redis for a year.
Top comments (0)