Rate Limiter

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

В посте про API Gateway упоминалось, что одной из его функций является rate limiting. Предлагаю сегодня разобраться с этим подробнее.

🫧 Что такое Rate Limiter

Rate Limiter — это механизм, который контролирует количество запросов, которые система может обработать за определённый промежуток времени. Его задача заключается в защите ресурсов от чрезмерной нагрузки при массовых обращениях к API.

В настройках рейт лимитера задают лимиты количества запросов в единицу времени. Например, у нас есть публичное API, на которое могут обращаться авторизованные пользователи, и мы настраиваем лимит 20 запросов/сек от одного пользователя. Определять пользователя можно по JWT токену, по IP, по API-ключу.

Пока заданный лимит не исчерпан, рейт лимитер передает запрос дальше на бэк.
Если лимит превышен, рейт лимитер не пропускает запрос и отдает ошибку 429 Too Many Requests.

Rate limiter предназначен для ограничения количества запросов от "хороших" клиентов, чтобы конкретный клиент не перегрузил сервис. При суровой DDoS-атаке только он не спасет, так как атака может идти с тысяч разных IP-адресов.

🫧 Место Rate Limiter в микросервисной архитектуре

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

Рейт лимитеру нужно хранить состояние, чтобы посчитать, сколько запросов уже было за период. Эти данные он может хранить у себя в памяти или в отдельном хранилище (например, Redis). Отдельное хранение нужно, когда используется несколько инстансов API Gateway. Redis помогает обеспечить атомарность операций, чтобы все инстансы гейтвеев видели общее состояние, и не возникало гонок и рассинхронизации.

🫧 Алгоритмы rate limiting

🤍 Fixed window (фиксированное окно)

Как работает:

Представим, что у нас есть лимит 10 запросов в минуту. Например: 09:00:00 → 09:00:59 — это одно окно.

Окно не обязано быть минутой, это может быть и 10 миллисекунд.

Считаем, сколько запросов пришло в этом окне.

Пока запросов меньше 10 → пропускаем их ✅
Если уже больше 10 → отклоняем ❌

Когда наступает новая минута — счётчик сбрасывается.

Проблема fixed window заключается во всплесках (burst) на границе окон: если пришло 10 запросов в 09:00:59, а потом еще 10 запросов в 09:01:01, то получается 20 запросов за 2 секунды, а должно быть не больше 10 в минуту.

🤍 Sliding window (скользящее окно)

Этот алгоритм решает проблему со всплесками на границе окон.

Как работает:

Если лимит 10 запросов в минуту, то храним временные метки всех запросов за последние 60 секунд.

На практике это оптимизируют, чтобы не хранить всё.

Для каждого запроса проверяем, сколько за последние 60 секунд уже пришло запросов от этого пользователя.

Если прошлых запросов меньше 10 → пропускаем ✅
Если за последние 60 секунд уже было 10 запросов → отклоняем ❌

Запросы старше 60 секунд убираем из списка.

Sliding window обеспечивает равномерное распределение, но у него выше требования к памяти (нужно хранить временные метки запросов) и выше вычислительная сложность (нужно перебирать и удалять устаревшие временные метки из списка).

Давайте посмотрим более гибкий алгоритм, который используется во многих API Gateway ⬇️

🤍 Token Bucket (ведро с токенами)

Это популярный алгоритм для рейт лимитинга. Например, он используется в API Gateway Tyk.

Как работает:

Как следует из названия, у нас есть ведро с токенами 🪣

Приходит запрос. Чтобы пропустить запрос на бэк, используем один токен из ведра ✅
Если токенов в ведре не осталось → запрос отклоняем ❌

Максимальное количество токенов в ведре называется capacity.
Скорость, с которой токены добавляются в корзину, называется fillRate.

Ведро пополняется равномерно.

Например, если capacity = 60, то 60 токенов не будут подсыпаны разом в 09:00:00 (как счетчик в Fixed Window), а будут добавляться
постепенно со скоростью fillRate. Если fillRate = 5 токенов в секунду, и прошло только 2 секунды, то в ведре будет 10 токенов и только 10 запросов смогут пройти на бэк.

На практике добавление стараются делать максимально плавным, не раз в секунду, а использовать доли секунды

Если расходующих токены запросов не будет, то через 12 секунд (5 * 12 = 60) ведро наполнится до максимальной capacity в 60 токенов, и новые токены в него поступать не будут. Но и сбрасываться не будут. Все 60 токенов будут ждать свои запросы. И это может привести к кратковременному всплеску нагрузки, так как все 60 запросов смогут пройти одновременно 🔥

Token Bucket допускает всплески трафика, но не больше capacity.

По сравнению со Sliding window алгоритм Token bucket проще и требует меньше памяти.

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

Минус: может быть сложно выбрать capacity и fillRate.

🤍 Leaky Bucket (протекающее ведро)

Как работает:

В Leaky Bucket в ведре лежат не токены, а сами запросы.

Приходит запрос. Если ведро не переполнено → кладём запрос в ведро (в очередь) ✅
Если переполнено → отклоняем запрос ❌

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

То есть Leaky Bucket — это как очередь First In First Out фиксированного размера.

Кто в очередь не поместился, тому до свидания, приходите попозже.

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

Недостаток Leaky Bucket является продолжением его достоинства: он не пропускает всплески, поэтому при резком увеличении трафика если очередь уже заполнена старыми запросами, это лишит систему возможности обрабатывать более свежие запросы.

На практике Rate Limiter обычно написан за нас, но мне кажется, эту тему полезно повторить перед System Design собесом.

➡️Как улучшить RAG?

Наткнулся на статью про базы знаний. На русском!

В ней рассмотрены различные стратегии повышения качества ответов. Объяснено достаточно понятно.

Конечно, после прочтения вы не станете КМСом по RAG, но на любой технарской тусовке уже сможете прокатить за своего и втереться в доверие😄