Ограничение частоты (rate limiting)

В прошлом уроке блокировка пускала к делу только одного. Сегодня задача мягче: пускать всех, но не слишком часто. Поиск по каталогу магазина тяжёлый, каждый запрос гоняет базу. Однажды чей-то скрипт присылает тысячу поисков в минуту, и сайт тормозит у всех. Нужно правило: не больше пяти поисков в минуту на покупателя. Такое правило называют ограничением частоты, и Redis для него подходит почти идеально: он быстрый, общий для всех копий сервиса и сам удаляет старые ключи по сроку.

Справки в окошке

В окошке выдают справки, не больше пяти в час одному человеку. Сотрудница ведёт тетрадку: на каждый час отдельная страница, на ней палочки напротив фамилий. Пришёл человек, она смотрит его палочки на этой странице. Меньше пяти: выдаёт справку и ставит палочку. Пять: «Приходите в следующем часу». Новый час, новая страница, все начинают с нуля.

Это первый и самый простой способ, фиксированное окно. Страница тетрадки это ключ Redis, палочки это счётчик.

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

Ключ складываем из покупателя и номера минуты: rl:user:7:1205 значит «покупатель 7, минута 12:05». На каждый запрос делаем INCR и сравниваем ответ с лимитом. Чтобы старые страницы не копились вечно, ставим ключу срок в одну минуту:

127.0.0.1:6379> INCR rl:user:7:1205
(integer) 1
127.0.0.1:6379> EXPIRE rl:user:7:1205 60 NX
(integer) 1
127.0.0.1:6379> INCR rl:user:7:1205
(integer) 2
127.0.0.1:6379> EXPIRE rl:user:7:1205 60 NX
(integer) 0
127.0.0.1:6379> TTL rl:user:7:1205
(integer) 60

INCR атомарный, как мы помним из урока про счётчики: даже если три копии сервиса одновременно получат запросы от покупателя 7, каждая увидит своё число, и шестой запрос никто не пропустит.

Флаг NX у EXPIRE появился в Redis 7 и значит «поставь срок, только если его ещё нет». Второй EXPIRE ответил 0 и срок не тронул. Без NX каждый запрос продлевал бы ключ на минуту заново, и активный покупатель держал бы ключ живым бесконечно.

Ловушка: INCR без срока

Частая ошибка выглядит так: «если INCR вернул 1, поставь EXPIRE». Две команды, между ними щель. Процесс упал после INCR и до EXPIRE, и ключ остался без срока:

127.0.0.1:6379> INCR rl:user:9:1205
(integer) 1
127.0.0.1:6379> TTL rl:user:9:1205
(integer) -1

-1 значит «срока нет». Такой ключ будет лежать в памяти вечно. А если номер окна в ключ не входит, например ключ просто rl:user:9, всё ещё хуже: счётчик дорастёт до пяти, и покупатель 9 больше никогда ничего не найдёт.

Лечится тремя способами:

• отправлять INCR и EXPIRE ... NX вместе в одной MULTI, как в уроке про транзакции;
• сначала создать ключ со сроком, SET rl:user:7:1206 0 EX 60 NX, а потом делать INCR. Если процесс упадёт между ними, ключ уже со сроком;
• сделать оба шага одним скриптом Lua.

Слабое место: граница окна

Фиксированное окно легко обмануть. Покупатель делает пять поисков в 12:05:59 и ещё пять в 12:06:00. Это две разные страницы тетрадки, и обе в пределах лимита. Но на деле прошло десять запросов за одну секунду, вдвое больше задуманного. Для защиты от случайной перегрузки это не страшно. Если лимит должен держаться строго, нужно окно, которое едет вместе со временем.

Скользящее окно на sorted set

Идея такая: хранить время каждого запроса и на каждый новый считать, сколько запросов было за последние 60 секунд, отсчитывая от «сейчас». Такое окно называют скользящим.

Журнал запросов удобно держать в отсортированном множестве: элемент это идентификатор запроса, вес это время в миллисекундах. Лимит для примера возьмём 3 запроса в 60 секунд, а время будем задавать руками. На каждый запрос четыре шага: выбросить записи старше минуты, добавить текущую, посчитать, продлить ключ.

127.0.0.1:6379> ZREMRANGEBYSCORE rl:log:user:7 -inf 1791599940000
(integer) 0
127.0.0.1:6379> ZADD rl:log:user:7 1791600000000 r1
(integer) 1
127.0.0.1:6379> ZCARD rl:log:user:7
(integer) 1

Первый запрос в момент 1791600000000. Граница «минуту назад» это 1791599940000, удалять нечего, в журнале одна запись. Пропускаем. Дальше запросы на 10-й и 20-й секунде, их тоже пропускаем. На 30-й секунде приходит четвёртый:

127.0.0.1:6379> ZREMRANGEBYSCORE rl:log:user:7 -inf 1791599970000
(integer) 0
127.0.0.1:6379> ZADD rl:log:user:7 1791600030000 r4
(integer) 1
127.0.0.1:6379> ZCARD rl:log:user:7
(integer) 4
127.0.0.1:6379> ZREM rl:log:user:7 r4
(integer) 1

Четыре больше трёх: отказ. Отклонённый запрос убираем из журнала через ZREM, чтобы он не занимал место в лимите. На 65-й секунде первый запрос выпадает из окна:

127.0.0.1:6379> ZREMRANGEBYSCORE rl:log:user:7 -inf 1791600005000
(integer) 1
127.0.0.1:6379> ZADD rl:log:user:7 1791600065000 r5
(integer) 1
127.0.0.1:6379> ZCARD rl:log:user:7
(integer) 3

ZREMRANGEBYSCORE удалил запись r1, в журнале три запроса, пропускаем. Четыре шага отправляют одной MULTI, чтобы между ними не вклинились запросы из соседних копий сервиса. Элементы должны быть уникальными: два запроса в одну миллисекунду с одинаковым именем схлопнутся в один. Поэтому в имя добавляют случайный хвост.

Окно точное, но за точность платят памятью: одна запись на каждый запрос. Для лимита «100 в минуту» это сотня записей на покупателя, терпимо. Для «10 000 в минуту» журнал станет тяжёлым.

Скользящий счётчик: компромисс

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

Пример: в прошлой минуте было 4 запроса, в текущей 2, и прошло 15 секунд текущей минуты. Окно «последние 60 секунд» захватывает 45 секунд прошлой минуты, это три четверти. Оценка: 4 × 0,75 + 2 = 5. При лимите 5 следующий запрос отклоняем. Это приближение, оно считает, что запросы прошлой минуты шли равномерно. Зато памяти нужно как у фиксированного окна, а граница почти не обманывается.