К содержимому
Войти

Python Road Map

🚦 Rate limiting и распределённые блокировки

Redis часто держит не только кэш, но и два служебных механизма: ограничение частоты запросов и распределённую блокировку. Rate limiter защищает API от парсера, от клиента с бесконечным ретраем и от собственного сервиса, который после деплоя зовёт соседа в десять раз чаще. Блокировка нужна, когда из десяти реплик задачу должна выполнить одна: отправить отчёт, пересчитать баланс, загрузить ключ в кэш. Оба механизма на собеседовании спрашивают с подвохом: интервьюер ждёт, что ты назовёшь, где они ломаются. Цифры ниже сняты на ноутбуке: Redis 7.4 и PostgreSQL 16 в Docker, клиент на Go 1.27

🧠 Четыре алгоритма ограничения

Задача одна: пропускать не больше N запросов за период от одного ключа. Ключ — id пользователя, API-ключ или IP. Алгоритмы различаются тем, как они считают период и что делают со всплеском

АлгоритмЧто хранитТочностьВсплеск
Фиксированное окноодин счётчик на окнона стыке окон пропускает до 2Nразрешён в начале окна
Скользящий журналвремя каждого запросаточныйне больше N за любые 60 секунд
Скользящий счётчикдва счётчика: текущее и прошлое окноприближённыйсглажен
Token bucketчисло токенов и время последнего пополненияточныйдо размера ведра, потом ровный темп

Фиксированное окно

Самый простой вариант: ключ rl:user42:<номер минуты>, на каждый запрос INCR, при первом инкременте EXPIRE. Если значение больше лимита, отказ. Это один ключ на пользователя и одна команда на запрос

Слабое место — стык окон. Лимит 10 в минуту, клиент шлёт 10 запросов в 12:00:59 и ещё 10 в 12:01:00. Каждое окно видит свои 10 и пропускает всё:

fixed window: пропущено за 2 секунды 20

Двойной лимит за две секунды — обычно терпимо, если лимит защищает от злоупотребления, а не держит хрупкую систему. Для внешнего API с квотами по тарифу этого уже мало

Скользящий журнал

Каждый запрос пишется в sorted set с временем в score. Перед проверкой из множества удаляются записи старше окна, ZCARD даёт число запросов за последние 60 секунд. Тот же сценарий на стыке пропустил ровно 10 из 20

Цена — память. 10 000 запросов в журнале одного клиента заняли в Redis 1,27 МБ, около 127 байт на запрос. Счётчик фиксированного окна весит 48 байт. Журнал берут, когда лимит маленький и важна точность: 5 попыток входа за 15 минут, 3 письма восстановления пароля в час

Скользящий счётчик

Компромисс, который описал Cloudflare. Хранятся только два счётчика, текущей и прошлой минуты, а число запросов за скользящую минуту оценивается так:

оценка = прошлое окно × (доля прошлого окна внутри скользящего) + текущее окно

Лимит 50 в минуту, в прошлой минуте было 42 запроса, текущая идёт 15 секунд и набрала 18. Скользящая минута захватывает 45 секунд прошлой: 42 × 45/60 + 18 = 49,5, следующий запрос уже превысит лимит. Алгоритм считает, что запросы прошлой минуты шли равномерно. Cloudflare проверил его на 400 млн запросов: ошибочно пропущены или отклонены 0,003%

Token bucket

Token bucket — ведро на burst токенов, которое пополняется со скоростью rate в секунду. Запрос забирает токен, пустое ведро значит отказ. Хранить нужно два числа: сколько токенов осталось и когда ведро пополняли. Пополнение считается лениво, при следующем запросе: tokens = min(burst, tokens + прошло_секунд × rate)

Ведро даёт то, что нужно живым клиентам: после паузы можно отправить пачку, а дальше темп ровный. В замере ведро на 5 в секунду с размером 10: из 15 запросов разом прошли 10, затем при долбёжке раз в 10 мс за 2 секунды прошло 9–10, то есть ровно темп пополнения. Этот алгоритм использует Stripe для своего главного лимитера, и он же лежит в golang.org/x/time/rate

Родственник ведра — GCRA (generic cell rate algorithm): хранит одно число, теоретическое время прибытия следующего запроса, и даёт то же поведение с одной записью вместо двух. На нём построена библиотека github.com/go-redis/redis_rate

🛠️ На практике

Внутри одного процесса

Если лимит нужен на исходящие вызовы, например не долбить чужой API чаще 5 раз в секунду, Redis не нужен:

lim := rate.NewLimiter(5, 10) // 5 в секунду, всплеск до 10

if !lim.Allow() { // не ждать: сразу отказ
	return ErrTooManyRequests
}

if err := lim.Wait(ctx); err != nil { // ждать токен, пока не отменят ctx
	return err
}

Allow не блокирует, Wait ждёт токен и уважает отмену контекста. В замере после пустого ведра 5 вызовов Wait заняли ровно секунду. Limiter безопасен для одновременного вызова из многих горутин. Ограничение такого лимитера — он свой у каждой реплики: пять подов с rate.NewLimiter(5, 10) вместе дадут 25 в секунду

Общий лимит на все реплики

Когда лимит должен быть общим, состояние уезжает в Redis, и главное правило здесь — проверка и изменение в одной атомарной операции. Наивный код «прочитать счётчик, сравнить, увеличить» из 100 горутин при лимите 10 пропустил в разных прогонах от 20 до 89 запросов: все читали одно и то же значение до того, как кто-то успел его увеличить. Тот же лимит через Lua-скрипт пропустил ровно 10 во всех прогонах, потому что скрипт выполняется в Redis целиком, без чужих команд посередине

Go · Token bucket в Redis через Lua

var tokenBucket = redis.NewScript(`
local rate, burst = tonumber(ARGV[1]), tonumber(ARGV[2])
local t = redis.call('TIME')
local now = t[1] * 1000 + math.floor(t[2] / 1000)
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens, ts = tonumber(b[1]) or burst, tonumber(b[2]) or now
tokens = math.min(burst, tokens + (now - ts) * rate / 1000)
local ok = 0
if tokens >= 1 then tokens = tokens - 1; ok = 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(burst / rate * 1000))
return ok`)

func allow(ctx context.Context, user string) bool {
	ok, err := tokenBucket.Run(ctx, rdb, []string{"rl:tb:" + user}, 5, 10).Int()
	if err != nil {
		return true // Redis недоступен: пропускаем, а не роняем API
	}
	return ok == 1
}

Время берётся командой TIME внутри скрипта, а не с машины клиента: часы на двадцати подах расходятся на десятки миллисекунд, и ведро считало бы по-разному. PEXPIRE убирает ведро, которое успело наполниться до краёв: хранить его дальше незачем, отсутствие ключа и так значит «полное ведро»

Что отвечает API

Отказ по лимиту — статус 429 Too Many Requests (RFC 6585). Ответ может нести заголовок Retry-After со временем до следующей попытки. Кэшам такой ответ хранить запрещено. Хороший клиент ждёт Retry-After, а без него ретраит с экспоненциальной задержкой и случайным разбросом, иначе все отказанные клиенты вернутся в одну и ту же секунду. Сколько запросов осталось, часто сообщают заголовками X-RateLimit-Remaining и похожими. Стандартные RateLimit и RateLimit-Policy пока в черновике IETF, но некоторые API их уже отдают

🔒 Распределённая блокировка

Блокировка в Redis — это ключ, который может создать только один клиент:

SET lock:report 7f3a9c... NX PX 30000

NX создаёт ключ, только если его нет. PX 30000 задаёт срок жизни 30 секунд, чтобы упавший держатель не заблокировал ресурс навсегда. Значение — случайный токен, уникальный для каждого захвата. Он нужен при снятии

Снимать только свою блокировку

Сценарий, который запущен в замере. Клиент A берёт блокировку на 100 мс и замирает на 200 мс: пауза GC, медленный запрос, своп. Ключ истекает, блокировку берёт клиент B. A просыпается и делает DEL lock:report, удаляя чужую блокировку. Сразу после этого её взял клиент C, и B с C работают одновременно:

A взял: true B взял после истечения: true
DEL: после снятия A блокировку B взял ещё и C: true

Поэтому снимают блокировку сравнением токена и удалением в одной атомарной операции. В Redis 8.4 для этого есть команда DELEX lock:report IFEQ <токен>, в более ранних версиях — Lua-скрипт:

var unlock = redis.NewScript(`
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
end
return 0`)

tok := randomToken() // 16 случайных байт
ok, err := rdb.SetNX(ctx, "lock:report", tok, 30*time.Second).Result()
if err != nil || !ok {
	return ErrBusy
}
defer unlock.Run(context.WithoutCancel(ctx), rdb, []string{"lock:report"}, tok)

С проверкой токена A получил 0 удалённых ключей, блокировка осталась у B

Проблема, которую токен не решает

Проверка токена спасает чужую блокировку, но не данные. A проснулся после паузы, не знает, что его блокировка истекла, и пишет в базу. B в это время пишет туда же. Проверять «блокировка ещё моя?» перед записью бесполезно: пауза может случиться между проверкой и записью

Против этого Мартин Клеппман описывает fencing token — номер, который растёт при каждом захвате. Хранилище помнит последний номер, с которым в него писали, и отклоняет запись со старым. В замере токен выдаёт INCR fence:report, а Postgres проверяет его в самом UPDATE:

update reports set body = $1, fence = $2
where id = 1 and fence < $2
запись B с токеном 2: строк 1
запись A с токеном 1: строк 0
в базе: B

Защита работает, только если хранилище само проверяет токен. Если блокировка охраняет отправку письма или вызов чужого API, проверить токен там негде, и остаётся делать сами операции идемпотентными

Redlock и споры о нём

Один Redis — единая точка отказа, а реплика не спасает: репликация асинхронная. A взял блокировку на мастере, мастер упал до того, как запись ушла на реплику, реплику повысили, и B берёт ту же блокировку. Для этого в документации Redis описан Redlock: пять независимых мастеров, блокировка считается взятой, если клиент захватил ключ хотя бы на трёх быстрее, чем истекает срок

Клеппман разобрал Redlock и показал, что его безопасность держится на допущениях о времени: паузы короткие, сеть быстрая, часы не прыгают. Redis считает срок ключа по системным часам, и в документации Redis прямо сказано, что сдвиг часов может отдать блокировку двум процессам. Автор Redis antirez ответил, что прыжков часов можно избежать настройкой NTP, а пауза после захвата грозит любой блокировке с автоснятием. На практике выбор зависит от того, что сломается, если работу выполнят двое:

Зачем блокировкаЧто выбрать
Не делать работу дважды: пересчитать кэш, сгенерировать отчётодин Redis, SET NX PX и снятие по токену
Двойное выполнение портит данные: деньги, остатки, уникальные номератранзакция и блокировка в самой базе или etcd и ZooKeeper, плюс fencing token

Клеппман называет первые блокировками ради эффективности, вторые — ради корректности. На собеседовании это различение стоит назвать раньше, чем шаги Redlock

Если данные уже лежат в Postgres, часто проще не выносить блокировку наружу. SELECT ... FOR UPDATE блокирует строку до конца транзакции, pg_try_advisory_xact_lock(42) берёт блокировку по числу и снимает её сам при коммите или откате. Такая блокировка не истечёт посреди работы, а при обрыве соединения база снимет её сама

Длинная работа

Если задача может идти дольше срока блокировки, срок продлевают: фоновая горутина раз в треть TTL выполняет PEXPIRE через такой же скрипт со сравнением токена. Так работает watchdog в Java-клиенте Redisson и продление в Go-библиотеке redsync. Продление не отменяет fencing: если горутина продления застряла в той же паузе, блокировка всё равно истечёт

⚠️ Где ошибаются

Читают счётчик и увеличивают его отдельными командами. Под конкурентной нагрузкой лимит 10 превращается в 20–89. Проверка и инкремент живут в одном Lua-скрипте или в INCR, результат которого сравнивают после

Ставят INCR и EXPIRE двумя вызовами без транзакции. Если процесс упал между ними, ключ остаётся без срока, и пользователь заблокирован навсегда. Обе команды кладут в один скрипт или в MULTI

Роняют API, когда недоступен Redis лимитера. Stripe советует обратное: ошибки лимитера ловить и пропускать запрос. Упавший лимитер не должен ронять сервис, который он защищает

Снимают блокировку простым DEL. Истёкшая и перехваченная блокировка удаляется чужим клиентом, и ресурс получают двое. Снимать только по совпадению токена

Считают, что блокировка с TTL гарантирует единственного исполнителя. Пауза дольше TTL отдаёт её второму, пока первый ещё работает. Если двойное выполнение портит данные, нужен fencing token или блокировка в базе

Ограничивают по IP. За одним IP мобильного оператора или офисного NAT сидят сотни пользователей, а у парсера сотни IP. Для авторизованных запросов ключ — пользователь или API-ключ, IP оставляют для входа и регистрации

🎯 Вопросы с собеседований

Какие алгоритмы rate limiting знаешь и чем они отличаются?

Фиксированное окно хранит один счётчик на минуту, оно дешёвое, но на стыке двух окон пропускает двойной лимит. Скользящий журнал хранит время каждого запроса в sorted set и точен, но памяти нужно на каждый запрос. Скользящий счётчик приближает журнал двумя счётчиками с взвешиванием прошлого окна. Token bucket хранит число токенов и время пополнения, разрешает всплеск до размера ведра и держит средний темп

Как сделать общий лимит для нескольких реплик сервиса?

Вынести состояние в Redis и делать проверку с изменением атомарно: одной командой INCR с проверкой результата или Lua-скриптом, который Redis выполняет без вмешательства других команд. Время для расчёта брать на стороне Redis, чтобы часы реплик не влияли. Если Redis недоступен, пропускать запросы и писать метрику, а не отдавать ошибку всем

Почему token bucket популярнее фиксированного окна?

Он не даёт двойного всплеска на границе окон и при этом разрешает короткую пачку после простоя, как ведут себя живые клиенты. Хранит всего два числа на ключ. Параметры понятны продукту: средняя скорость и допустимый всплеск. Фиксированное окно проще и годится, когда двойной лимит на стыке не страшен

Что вернуть клиенту, который превысил лимит?

Статус 429 Too Many Requests и заголовок Retry-After с тем, через сколько секунд можно повторить. Полезно сообщать остаток квоты в заголовках, чтобы клиент притормозил сам. Клиент должен ретраить с экспоненциальной задержкой и случайным разбросом, иначе отказанные запросы вернутся одной волной

Как сделать распределённую блокировку на Redis?

SET key token NX PX ttl: ключ создаётся, только если его нет, и сам истечёт, если держатель упал. Токен — случайная строка на каждый захват. Снимают блокировку атомарным сравнением токена и удалением через Lua-скрипт или DELEX ... IFEQ в Redis 8.4, чтобы не удалить блокировку, которую уже взял другой клиент после истечения

Блокировка взята с TTL 30 секунд. Может ли ресурс оказаться у двух клиентов сразу?

Да. Если держатель замер дольше TTL на паузе GC или в сети, ключ истечёт, блокировку возьмёт второй, а первый проснётся и продолжит работу. Ещё один сценарий — падение мастера Redis до того, как ключ ушёл на реплику. Если двойное выполнение портит данные, нужен fencing token, который проверяет само хранилище, или блокировка внутри базы

Что такое fencing token?

Число, которое растёт с каждым захватом блокировки и передаётся вместе с записью в хранилище. Хранилище помнит последнее принятое значение и отвергает запись со старым. Тогда клиент, проснувшийся после истёкшей блокировки, ничего не испортит: его токен меньше, чем у нового держателя. Работает, только если хранилище умеет такую проверку, например условием в UPDATE

Что такое Redlock и почему о нём спорят?

Алгоритм из документации Redis: блокировка берётся на большинстве из N независимых мастеров, обычно трёх из пяти, и считается действующей, пока не истёк срок минус время захвата. Клеппман показал, что его безопасность зависит от допущений о паузах, задержках сети и часах, и что он не выдаёт fencing token. Поэтому для задач, где двойная работа просто лишняя, хватает одного Redis, а для корректности данных берут базу или систему на консенсусе вроде etcd

📚 Что почитать