Сравнение алгоритмов ограничения частоты запросов

▍ Зачем ограничивать частоту?

Представьте чат в Twitch со множеством активных пользователей и одним спамером. Без ограничения частоты сообщений единственный спамер может запросто заполнить всю беседу сообщениями. При ограничении частоты у каждого пользователя появляется равная возможность участия.

Ограничитель частоты позволяет управлять частотой обрабатываемого вашим сервисом трафика, блокируя запросы, превосходящие заданное пороговое значение за период времени. И это полезно не только для борьбы со спамом в чатах. Например, ограничение частоты отправки формы логина позволяет защититься от брутфорс-атак, оставляя при этом пользователю право на ошибку.

Конечные точки API тоже часто ограничивают по частоте запросов, чтобы их ресурсы не монополизировал единственный пользователь. Представьте, что вам нужно, чтобы пользователи могли обращаться к затратной конечной точке не чаще ста раз в минуту. Это можно отслеживать при помощи счётчика, обнуляющегося каждую минуту. Все запросы после сотого в пределах этой минуты будут блокироваться. Это один из простейших алгоритмов ограничения частоты, называющийся fixed window limiter (ограничитель с фиксированным окном). Это распространённый способ управления трафиком к сервису.

Но не всегда всё так просто.

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

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

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

В течение заданного временного окна возможна отправка установленного количества запросов. Отправка запросов приводит к инкременту счётчика, обнуляющегося в начале каждого окна.

Разрешаем 6 запросов в день (24-часовые окна):

Каждая зелёная точка — это разрешённый запрос, а красный минус — это запрос, заблокированный ограничителем частоты. В оригинале статьи можно добавлять запросы кнопкой Hit, приостанавливающей автоматический поток.

• Плюсы
  • Простота реализации и понятность
  • Предсказуемость для пользователей
• Минусы
  • Допускает резкие скачки в два раза больше limit, когда запрос начинается ближе к концу окна
• Пример из реального мира
  • В API GitHub используется ограничитель частоты с фиксированным окном, имеющий значения limit = 5000, windowDuration = 1h. Его windowStart установлен на начало каждого системного часа, что позволяет пользователям выполнять 5000 запросов в час.

Фиксированное окно с определяемым пользователем началом

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

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

▍ Скользящие окна

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

• Плюсы
  • Сглаживают распределение трафика запросов
  • Хорошо подходят для высоких нагрузок
• Минусы
  • Менее предсказуемы для пользователей, чем фиксированные окна
  • Хранение временных меток для каждого запроса требует дополнительных ресурсов

Так как скользящие окна (sliding window) обычно оказываются самыми полезными в ситуациях с большим объёмом трафика, активное потребление ресурсов наивным алгоритмом контрпродуктивно. Разве не должен ограничитель частоты при большом трафике использовать эффективный алгоритм? По этой причине большинство реально используемых ограничителей частоты со скользящим окном, например, Upstash или Cloudflare, используют аппроксимацию, часто называемую плавающим окном (floating window). Благодаря этой аппроксимации мы сохраняем все плюсы, но избавляемся от необходимости активной траты ресурсов. Вот, как это работает:

1. Считаем количество разрешённых запросов в предыдущем фиксированном окне.
2. Считаем количество разрешённых запросов в текущем фиксированном окне.
3. Придаём количеству разрешённых запросов предыдущего окна вес, пропорциональный пересечению этого окна с плавающим окном, завершающимся в текущий момент.
4. Суммируем взвешенные запросы из (3) с невзвешенными запросами из (2).

Иными словами, вычисления выглядят так:

approximation = (prevWindowCount * prevWindowWeight) + currentWindowCount

На практике, эта аппроксимация ограничивает запросы примерно с той же пропорцией, но гораздо эффективнее, чем при отслеживании временных меток всех запросов. Посмотрите сами на сравнение:

• Пример из реального мира
  • В конфигурируемом ограничителе частоты Cloudflare используется аппроксимированное скользящее окно.

▍ Бакеты токенов

Забудем окна с их длительностями и представим бакет («ведро»), с постоянной частотой заполняемый «токенами». Каждый запрос извлекает один токен из бакета, а когда бакет оказывается пустым, следующий запрос блокируется. Такая методика бакета токенов (token bucket) обладает некоторыми полезными свойствами.

1. Ёмкость бакета — это максимальное количество запросов, который может обеспечить резкий скачок запросов (не считая токенов, которые восполняются в процессе этого скачка).
2. Интервал между пополнениями бакета представляет собой долговременный интервал среднего количества разрешённых запросов.

Наличие ограничения резких скачков и средних количеств запросов без необходимости использования нескольких ограничителей частот — одно из основных преимуществ этого алгоритма.

• Плюсы
  • Обеспечивает возможность резких скачков высокого трафика, но сохраняет долговременную среднюю частоту запросов
  • Более гибок для пользователей, обеспечивая возможность всплесков трафика в допустимом интервале
• Минусы
  • Сложнее донести до пользователей лимиты и время восстановления, чем в случае фиксированных окон
• Примеры из реального мира
  • Бакет токенов используется в Stripe: каждый пользователь получает бакет с limit = 500, refillInterval = 0.01s, что обеспечивает возможность стабильной активности в 100 запросов за секунду, а также всплесков до 500 запросов. (Подробности реализации.)
  • Бесплатный тариф GPT-3.5 у OpenAI ограничен 200 запросами в день; используется бакет токенов с limit = 200 и refillInterval = 86400s / 200; бакет восстанавливается таким образом, что к концу дня (86400 секунд) он будет заполнен на 100%. Восполняется бакет по одному токену за раз.

  В демо чата Twitch ограничение реализовано на основе бакета размером 3, что позволяет обеспечивать всплески до 3 запросов; интервал восполнения равен 4 секундам, что в среднем позволяет отправлять по 1 сообщению раз в 4 секунды.

  Благодаря своей гибкости бакеты токенов могут имитировать свойства некоторых других алгоритмов. Например, если присвоить refillRate значение, равное limit, то мы получим эквивалент ограничителя частоты с фиксированным окном, где начало определяется пользователем.

▍ Прочие аспекты

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

• Создание хранилища для ограничителя частоты. Если в дальнейшем вы намереваетесь выполнять горизонтальное масштабирование сервера (или даже просто перезапускать его), то хранилище данных ограничителя частоты не может находиться в памяти. Чаще всего данные ограничения частоты сохраняют в хранилище пар «ключ-значение» наподобие Redis, имеющее встроенные функции для завершения срока действия ключей; само хранилище находится на отдельной от приложения машине. Однако когда ограничитель работает активно, можно использовать для блокирования запросов динамический кэш в памяти без сохранения в Redis.
• Открытое положение при отказе. При сбое соединения сервера с постоянным хранилищем следует допускать все запросы, а не блокировать полностью доступ к серверу.
• Опциональный тротлинг всплесков. Чтобы снизить эффект всплесков трафика, вместе с ограничением частоты можно использовать тротлинг.
• Выбор подходящих ключей. В общем случае частота запросов ограничивается для конкретных пользователей. В большинстве приложений для этого в качестве ключей применяются ID пользователей. В случае API ключом становится ключ API. Хороших вариантов ограничения частоты запросов неаутентифицированных пользователей не очень много; самые популярные из них — IP-адрес запроса, фингерпринт устройства, уникальный ID установленного приложения или просто общий ограничитель на всех.
• Отображение полезных сообщений об ошибках ограничения частоты. Сообщайте пользователям, как долго им нужно ждать до следующего запроса. В случае API при блокировке запроса используйте код состояния HTTP 429 и добавляйте соответствующие заголовки ответов x-ratelimit-*. У GitHub есть хорошие примеры заголовков для его ограничителя на основе фиксированного окна, а у OpenAI есть примеры для ограничителя на основе бакета токенов.

▍ Подведём итог

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

▍ Интерактивное демо

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