Ограничение частоты запросов — это средство безопасности, а не счётчик

Поэтому прежде чем называть пять алгоритмов, задайте первый вопрос: что именно вы пытаетесь сгладить и чьи запросы вы считаете?

Итак, начнём с публичного endpoint для сброса пароля. Он может запускать работу с базой данных, отправку email и создавать риск перечисления аккаунтов. Аутентифицированные вызывающие стороны могут иметь стабильные идентификаторы аккаунтов; анонимные вызывающие стороны могут использовать общий корпоративный NAT-адрес; ботнет может распределять запросы между тысячами IP-адресов.

Поэтому выбирайте limiter, режим отказа которого вы можете себе позволить. Это руководство идёт от ресурса и модели угроз к поведению при всплесках, идентификации, распределённому состоянию, обработке перегрузки и HTTP-сигнализации.

В этой статье

• Ограничение частоты запросов начинается с идентификатора и бюджета отказов
• Пять алгоритмов главным образом различаются тем, что они разрешают на границах
• Обычный трафик показывает компромисс, который скрывают диаграммы
• Самые сложные ошибки обычно связаны с идентификацией, перегрузкой и семантикой
• Распределённая корректность стоит дороже, чем добавление Redis
• Клиентам нужен договор об ограничении частоты запросов, которому они могут следовать
• Выбирайте режим отказа, который можете себе позволить

Ограничение частоты запросов начинается с идентификатора и бюджета отказов

RFC 6585 определяет 429 следующим образом: «Код состояния 429 означает, что пользователь отправил слишком много запросов за определённый период времени (“rate limiting”)». Протокол предоставляет вам код состояния и оставляет опасные решения на усмотрение вашей архитектуры.

Поэтому выберите субъект, область подсчёта и поведение при отказе. HTTP 429 ничего из этого за вас не выбирает. RFC прямо говорит, что не определяет, как origin идентифицирует пользователя или считает запросы.

Перед выбором алгоритма запишите три ответа:

1. Какой ресурс или поведение вы защищаете?
2. Какие всплески являются легитимными?
3. Какой идентификатор атакующему дорого размножать?

Для endpoint сброса пароля дорогим действием может быть отправка сообщений для сброса или проверка существования аккаунтов. Лимиты на аккаунт могут защищать аутентифицированные идентификаторы или запрошенные идентификаторы аккаунтов. Лимиты по IP предоставляют отдельный сигнал для анонимного трафика. Скомпрометированные аккаунты остаются отдельной проблемой: атакующий, контролирующий действительные аккаунты, может пройти проверку по ключу аккаунта.

Но ограничение по IP — лишь полезный запасной вариант для анонимных запросов. Корпоративная сеть может размещать множество легитимных пользователей за одним адресом, тогда как ботнет может дёшево размножать исходные адреса.

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

Пять алгоритмов главным образом различаются тем, что они разрешают на границах

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

Алгоритм	Состояние	Поведение при всплеске	Основное преимущество	Основной режим отказа
Фиксированное окно	O(1)	До 2× на границе	Простейшая реализация	Всплеск на границе
Лог скользящего окна	O(N) временных меток	Точный скользящий лимит	Точность	Рост памяти
Счётчик скользящего окна	O(1)	Приближённый скользящий лимит	Компактный компромисс	Ошибка оценки
Token bucket	O(1)	Явная ёмкость всплеска	Средняя скорость плюс всплески	Всплеск может перегрузить downstream
Leaky bucket	O(1) виртуального состояния; O(queue) с очередью запросов	Сглаженный вывод	Контролируемая скорость выпуска	Семантика очереди и отклонения

Безопасность зависит от ключа и пути отказа не меньше, чем от самого алгоритма. Таблица даёт фиксированным окнам их главный аргумент — простоту — и показывает их стоимость на границе.

Фиксированные окна обменивают точность на дешёвое состояние

Разделите время на фиксированные интервалы, например на одну минуту, и храните счётчик для каждого ключа. Счётчику фиксированного окна требуется состояние O(1) на ключ; Redis может реализовать его с помощью атомарной операции со счётчиком и временем истечения.

При лимите 100 запросов за 60-секундное окно 60-секундный скользящий интервал, пересекающий границу фиксированного окна, может содержать до 200 запросов: 100 непосредственно перед сбросом и 100 сразу после него. Это определённое поведение. Это не загадочная ошибка реализации. Используйте фиксированные окна, когда важна простота и downstream-ёмкость может поглотить граничный всплеск.

Скользящие окна хранят больше истории или оценивают её

Лог скользящего окна хранит каждую временную метку запроса для ключа. При каждом запросе он удаляет временные метки, которые старше интервала, подсчитывает оставшиеся и принимает или отклоняет новый запрос. Семантика точная. Цена — состояние O(N).

Высокочастотные ключи, умноженные на множество клиентов, могут сделать историю временных меток дорогой даже в Redis sorted set. Используйте этот вариант, когда важна точная скользящая семантика, а объём трафика и количество ключей позволяют хранить историю.

Счётчик скользящего окна хранит только количество запросов в предыдущем и текущем окне. Он оценивает скользящий итог, взвешивая предыдущее количество:

estimate = previous × (1 − elapsed / window) + current

Здесь elapsed измеряется от начала текущего окна, а elapsed и window должны использовать одинаковые единицы измерения, например миллисекунды. В середине одноминутного окна половина предыдущего количества вносит вклад в оценку.

Метод использует состояние O(1), но трафик, сгруппированный в конце предыдущего окна, может вызвать отклонение оценки. Cloudflare описывает привлекательность двух чисел и простой арифметики. Счётчик скользящего окна — практический компромисс, когда границы фиксированного окна слишком либеральны, а точная история временных меток обходится слишком дорого.

Token bucket по замыслу допускает всплески

Token bucket пополняется со скоростью r и хранит не более b токенов. Каждый запрос расходует один токен. Неиспользованные токены создают возможность для немедленного всплеска.

Скорость пополнения управляет долгосрочным средним значением; ёмкость управляет мгновенным всплеском. Bucket, настроенный на 10 токенов в секунду и ёмкость 20, может немедленно принять 20 запросов, когда bucket полон, при условии, что на запрос требуется один токен. После этого токены возвращаются со скоростью 10 в секунду.

Такая модель подходит для обычных чтений API и скачков трафика. Stripe использует token bucket для ограничения частоты запросов к API, поскольку модель поддерживает стабильную среднюю скорость и одновременно допускает всплески.

Token bucket обеспечивает такую же безопасность, как скользящее окно, только когда его намеренно разрешённый всплеск соответствует модели угроз. Для операций сброса пароля или связанных со входом задавайте ёмкость исходя из допустимой нагрузки downstream и риска злоупотребления. Общая политика API может разрешать слишком много.

Leaky bucket сглаживает выпуск, а не приём

Token bucket управляет допуском. Leaky bucket управляет скоростью, с которой принятая работа выпускается или обрабатывается. Это различие объясняет разное поведение при всплесках.

Реализация на основе очереди хранит работу в очереди, тогда как GCRA компактно представляет расписание; выбирайте проверенную реализацию, а не предполагайте эквивалентность поведения.

nginx документирует limiter скорости запросов с параметрами rate, burst и необязательным поведением задержки. При rate=1r/s и burst=5 nginx разрешает пять запросов сверх стабильной скорости. Эти запросы присоединяются к разрешённому всплеску. С nodelay nginx выпускает всплеск немедленно, продолжая со временем соблюдать настроенную скорость. По умолчанию nginx отклоняет избыточные запросы с 503, а не с 429.

Выбирайте исходя из отказа downstream, который вы можете выдержать, а не из знакомой вам диаграммы.

Обычный трафик показывает компромисс, который скрывают диаграммы

Воспроизводимый эксперимент от Yuhi-sa использовал следующие настройки:

• Лимит окна: 10 запросов в секунду
• Token bucket: 10 токенов в секунду, ёмкость 20
• Leaky bucket: 10 запросов в секунду, ёмкость 20
• Трафик: пуассоновские поступления со скоростью 6 запросов в секунду
• Длительность: 30 секунд
• Запросы: 184
• Случайное начальное значение: 42

Результаты были следующими:

• Фиксированное окно: 178 разрешённых, 6 отклонённых, или 96.74%
• Счётчик скользящего окна: 178 разрешённых, 6 отклонённых, или 96.74%
• Token bucket: 184 разрешённых, 0 отклонённых, или 100%
• Leaky bucket: 184 разрешённых, 0 отклонённых, или 100%

При 60% от настроенной средней скорости пуассоновские поступления всё равно группируются. Ёмкость bucket поглощает этот джиттер. Методы на основе окон отклоняют некоторые сгруппированные запросы, поскольку их счётчики видят локальные пики.

Это демонстрирует одну рабочую нагрузку, конфигурацию, длительность и начальное значение. Вывести из этого производственную ёмкость или влияние на пользователей невозможно; это ничего не говорит о задержке вашего хранилища, стоимости endpoint или схеме повторных попыток клиента. Измеряйте их отдельно.

Самые сложные ошибки обычно связаны с идентификацией, перегрузкой и семантикой

«Почему мой лимит 100 запросов в минуту разрешил 200?»

Граница фиксированного окна сделала именно то, для чего была создана. Принимайте такое поведение, когда limiter является грубым средством обеспечения справедливости, а downstream-ёмкость может поглотить граничный всплеск. Используйте счётчик скользящего окна для состояния постоянного размера с меньшим искажением на границе или лог, когда точная история оправдывает затраты памяти.

«Почему защита по IP не остановила атаку?»

Ограничение по IP — полезный запасной вариант для анонимного трафика на сетевом уровне.

BackendBytes описывает limiter с фиксированным окном на 100 запросов в минуту, использующий IP в качестве ключа, который атакующий обошёл, распределив трафик по 1 000 IP-адресов.

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

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

Ограничения по ключу аккаунта также имеют границу: скомпрометированный аккаунт может отправлять запросы, выглядящие легитимно. Limiter сокращает один путь злоупотребления; он не устанавливает, что вызывающая сторона безвредна.

«Почему limiter увеличил нагрузку во время атаки?»

Сервер на уровне приложения всё ещё может быть вынужден принять запрос. Затем он запускает limiter, формирует ответ и отправляет его. Во время атаки формирование ответа для каждого отклонённого запроса добавляет нагрузку на систему, которую вы пытаетесь защитить.

RFC 6585 разрешает сбрасывать соединения, когда ответ на каждый запрос потреблял бы слишком много ресурсов. Это не делает сброс соединений универсально предпочтительным. Фильтрация на edge, сброс соединений или upstream-контроли могут потребоваться до генерации 429 на уровне приложения.

Рассматривайте ваши средства защиты от DDoS и web application firewall как часть того же пути отказа, если эти средства присутствуют в вашем развёртывании.

«Почему мой клиент повторил не то действие?»

Поскольку Retry-After является необязательным, клиенты должны определить запасной вариант. Фактическую процедуру повторной попытки рассмотрим в HTTP-договоре ниже.

«Почему CDN отдал ответ об ограничении частоты запросов?»

RFC 6585 говорит, что ответы 429 MUST NOT be cached. Убедитесь, что уровни CDN и proxy соблюдают это правило, особенно когда ответы содержат сведения, связанные с аккаунтом или конкретной повторной попыткой.

Распределённая корректность стоит дороже, чем добавление Redis

Компромиссы алгоритмов объяснимы, но безопасные лимиты нельзя выбрать только на основе теории. Измеряйте стоимость endpoint, размер легитимного всплеска и поведение хранилища limiter под вашей нагрузкой.

Счётчик в памяти работает, когда один процесс принимает все решения о применении ограничений или когда ограничения на каждый экземпляр являются намеренными. При наличии нескольких экземпляров API каждый процесс видит лишь часть трафика, если состояние не является общим или политика намеренно не разделена.

Используйте следующую последовательность:

1. Выберите ключ. Документируйте идентичность, запасное поведение и границу доверия.
2. Выберите модель состояния. Счётчики, оценки по двум окнам, временные метки, балансы токенов и виртуальные дедлайны имеют разную стоимость хранения.
3. Используйте общее состояние. Redis или эквивалентное хранилище не позволяет точкам применения ограничений расходиться.
4. Сделайте решение атомарным. Проверка и обновление должны происходить вместе. Redis Lua scripts — распространённый практический подход; атомарные серверные операции или эквивалентные примитивы могут выполнять ту же задачу.
5. Определите поведение при отказе. Решите, что происходит, когда хранилище работает медленно или недоступно: fail open, fail closed или использование более грубого аварийного контроля. Также определите время истечения, работу с часами и региональное поведение.
6. Измеряйте limiter. Отслеживайте задержку принятия решения, ошибки хранилища, отклонённые запросы и количество ключей.

Для семантики leaky bucket GCRA может компактно представлять виртуальное расписание. Используйте проверенную реализацию; выбор алгоритма сам по себе не гарантирует его производительность или корректность для вашего хранилища.

Клиентам нужен договор об ограничении частоты запросов, которому они могут следовать

Код состояния является частью поверхности атаки, когда атакующий контролирует количество отклонённых запросов, которые вы обрабатываете.

Сервер, возвращающий 429, должен включать полезное объяснение, не содержащее чувствительных данных. RFC 6585 говорит, что ответ должен содержать подробности и может включать Retry-After.

Retry-After имеет два формата

Заголовок может содержать delta-seconds:

Retry-After: 3600

Это означает 3 600 секунд. Он также может содержать дату HTTP:

Retry-After: Wed, 21 Oct 2015 07:28:00 GMT

Клиенты должны разбирать оба формата, как описано в справочнике MDN по Retry-After.

Политика клиента должна:

1. Соблюдать корректный Retry-After.
2. В противном случае использовать экспоненциальную задержку.
3. Добавлять полный jitter.
4. Ограничивать максимальную задержку.
5. Прекращать повторные попытки, когда операция больше не имеет смысла.

Многие API используют фактически ставшие стандартными поля X-RateLimit-Limit, X-RateLimit-Remaining и X-RateLimit-Reset. Поля RateLimit-* из черновика IETF предназначены для стандартизации эквивалентной информации, но их внедрение остаётся неравномерным. Документируйте поля, которые действительно поддерживает ваш сервис.

Документированное поведение nginx limit_req по умолчанию выдаёт 503 для отклонённых избыточных запросов. Клиенты, получающие 503, могут повторять запрос, как если бы сервис был недоступен, тогда как клиенты, получающие 429, используют поведение ограничения частоты запросов. Проверяйте ответ на edge, а не только в коде приложения.

Выбирайте режим отказа, который можете себе позволить

• Фиксированное окно: выбирайте максимально простой контроль и принимайте его поведение на границе.
• Лог скользящего окна: выбирайте точную скользящую семантику, когда состояние временных меток доступно по стоимости.
• Счётчик скользящего окна: выбирайте приближение O(1), когда границы фиксированного окна требуют коррекции.
• Token bucket: выбирайте долгосрочное среднее значение с легитимными всплесками.
• Leaky bucket: выбирайте плавную обработку и проверяйте, ставит ли реализация запросы в очередь или отклоняет их.

Перед выпуском ответьте на пять вопросов:

1. Является ли ключ идентичностью или лишь сетевым местоположением?
2. Какой всплеск разрешает алгоритм?
3. Где хранится общее состояние и является ли обновление атомарным?
4. Что происходит, когда limiter или хранилище перегружены?
5. Согласованы ли сервер и клиент относительно статуса, Retry-After, заголовков, кэширования и повторных попыток?

Для выборочного набора запросов регистрируйте тип ключа, алгоритм, решение, оставшийся доступный объём, задержку хранилища и статус ответа. Если вы не можете объяснить отклонение, limiter не готов.