Rate limiting: алгоритмы, всплеск на границе и счётчик в Redis

Лимит — «100 запросов в минуту на API-ключ», и дашборд клянётся, что он работает. Потом клиент проталкивает 380 запросов за две секунды, и каждый возвращает 200 OK. В коде лимитера ничего не сломано — на одном узле он работает идеально. Проблема: за балансировщиком четыре сервера приложения, и каждый держит свой счётчик в памяти, так что реальный лимит — 400/мин. Лишние 180 пришли от клиента, который ударил в границу окна сразу по всем четырём узлам. Лимит никогда не был настоящим; это были четыре отдельных лимита, которые случайно делили имя.

Fixed window: дёшево — и пропускает 2x-всплеск

Простейший лимитер ключует счётчик по {key}:{minute} и делает INCR; если значение превысило лимит — отказ. Один integer на ключ, O(1), легко рассуждать. И на нём же обжёгся каждый сеньор — из-за границы.

Fixed window сбрасывается на ребре по настенным часам. Если лимит 100/мин, клиент может отправить 100 запросов в 12:00:59.9 и ещё 100 в 12:01:00.1 — 200 запросов внутри 200мс, и оба всплеска легальны, потому что попадают в разные окна. Худший случай — ровно 2x от заданного лимита, сконцентрированные на шве между двумя окнами. Для грубого внутреннего тротлинга это нормально. Для защиты от злоупотреблений или для чувствительного downstream эти 2x — разница между «защищено» и «упало».

Sliding window: log точен, counter — дешёвое приближение

Sliding window log чинит границу, сохраняя timestamp на каждый запрос (sorted set в Redis), отбрасывая записи старше окна и считая остаток. Он точен — лимит соблюдается на любых скользящих 60с, а не на фиксированной минуте. Цена — память: клиент на 10k req/min держит 10k timestamp-ов, и ты платишь ZADD плюс trim ZREMRANGEBYSCORE на каждый вызов. На масштабе log — пожиратель памяти, о котором жалеешь.

Sliding window counter — продакшен-компромисс. Держи два fixed-window счётчика — текущий и предыдущий — и оценивай скользящий счёт как current + previous * (доля перекрытия). Это приближение, но знаменито хорошее: Cloudflare измерил примерно 0.003% ошибки на ~400 миллионах запросов, два integer-а на ключ вместо тысяч timestamp-ов. Эта точность почти даром — причина, по которой он дефолт в большинстве edge-лимитеров.

Token bucket: моделируй всплеск, а не борись с ним

Реальный трафик API бёрстовый — пользователь открывает страницу и выстреливает двенадцать запросов разом, потом простаивает. Token bucket это принимает. Ведро держит до capacity токенов и пополняется с ровной скоростью (скажем, 100 токенов/мин); каждый запрос тратит токен, и отказ только когда ведро пусто. Клиент, который простаивал, накапливает токены до потолка, поэтому может выстрелить всплеск мгновенно, а дальше тротлится до скорости пополнения. Ты соблюдаешь среднюю скорость, разрешая короткие всплески — ровно то, чего хочет дружелюбный API. Нужно лишь два хранимых значения (текущие токены, timestamp последнего пополнения), поэтому Stripe и AWS используют его как общий дефолт.

Leaky bucket — зеркало: запросы вытекают с фиксированной скоростью независимо от того, как пришли, сглаживая трафик ради защиты хрупкого downstream. Цена — он добавляет латентность очереди на стороне клиента и отказывается пропускать легитимные всплески. Бери его, когда тому, что за тобой, ровная предсказуемая скорость важнее отзывчивости.

Distributed: счётчик должен быть общим и атомарным

Баг из Hook — тот, что кусает в продакшене. Лимитер в памяти корректен в одном процессе и молча неверен в момент, когда ты масштабируешься горизонтально — каждый из N узлов соблюдает лимит независимо, так что эффективный лимит — N раз от заданного, и клиент, размазывающий запросы по узлам, проходит насквозь. Фикс — перенести счётчик в общий стор, почти всегда Redis, чтобы каждый узел читал и писал одно и то же число.

Но «общий» недостаточно — он должен быть атомарным. Наивный fixed-window подход — INCR, потом EXPIRE, и это гонка: два запроса могут оба сделать INCR, а если процесс умрёт между INCR и EXPIRE, ключ так и не получит TTL, и счётчик протечёт навсегда. Надёжный паттерн — один Lua-скрипт, который Redis выполняет атомарно — весь цикл прочитать-решить-обновить идёт без вклинивания других команд, поэтому конкурентные запросы не могут дважды потратить токены. Проверка token bucket на Lua — горстка операций, и работает за меньше миллисекунды, достаточно дёшево, чтобы стоять на синхронном пути запроса даже при миллионах запросов в секунду.

-- token_bucket.lua  — KEYS[1] = ключ ведра, ARGV = rate, capacity, now, requested
local key       = KEYS[1]
local rate      = tonumber(ARGV[1])   -- токенов в секунду
local capacity  = tonumber(ARGV[2])   -- макс токенов (размер всплеска)
local now       = tonumber(ARGV[3])   -- текущее время, секунды
local requested = tonumber(ARGV[4])   -- сколько токенов стоит запрос

local bucket    = redis.call("HMGET", key, "tokens", "ts")
local tokens    = tonumber(bucket[1]) or capacity
local ts        = tonumber(bucket[2]) or now

-- пополнение по прошедшему времени, с потолком capacity
local elapsed   = math.max(0, now - ts)
tokens          = math.min(capacity, tokens + elapsed * rate)

local allowed   = tokens >= requested
if allowed then tokens = tokens - requested end

redis.call("HSET", key, "tokens", tokens, "ts", now)
redis.call("EXPIRE", key, math.ceil(capacity / rate) * 2)
-- возвращаем флаг allowed + retry-after в секундах для 429
local retry = allowed and 0 or math.ceil((requested - tokens) / rate)
return { allowed and 1 or 0, retry }

Контракт 429 и thundering herd

Когда отказываешь, ответ — это контракт, а не просто статус. Верни 429 Too Many Requests с Retry-After (секунды, посчитанные из того, когда освободится следующий токен), чтобы воспитанные клиенты отступали, а не ретраили в тугом цикле. Добавь поля RateLimit-*, которые стандартизирует IETF — RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset — чтобы клиенты сами держали темп до того, как упрутся в стену. Важно: черновик задаёт RateLimit-Reset как delta-секунды, а не UNIX-timestamp: timestamp требовал бы синхронизации часов клиента и говорил бы каждому затротленному клиенту ретраить в один и тот же абсолютный момент — самонаведённый thundering herd на границе сброса.

Этот herd — вторая продакшен-ловушка. С fixed window и жёстким Retry-After «32 секунды» тысячи затротленных клиентов просыпаются и ретраят в один момент, долбя тебя на границе. Митигации: предпочитай sliding/token-bucket модель, где ёмкость освобождается непрерывно, а не разом, и добавь jitter — разбрось значения Retry-After по небольшому случайному диапазону, чтобы клиенты возвращались вразнобой, а не синхронной волной. Решай и про измерение на ключ осознанно: per-API-key честен к платящим клиентам, per-IP ловит анонимные злоупотребления, но наказывает всех за корпоративным NAT, а per-endpoint даёт защитить дорогой роут, не тротля дешёвые.