Видеоразбор этой задачи на русском языке можно посмотреть здесь - https://www.youtube.com/watch?v=D7sulsN-qJw

Проектирование Rate Limiter

Постановка задачи

🚦 Что такое Rate Limiter?

Rate Limiter контролирует количество запросов, которое клиент может сделать в течение определенного временного интервала. Это похоже на регулировщика движения для вашего API - например, позволяет клиенту отправлять максимум 100 запросов в минуту, отклоняя дополнительные запросы с кодом HTTP 429 (Too Many Requests).

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

Функциональные требования

В данном разборе мы спроектируем rate limiter уровня запросов (request-level rate limiter) для API социальной сети. Это означает, что мы будем ограничивать отдельные HTTP-запросы (например, публикацию сообщений, получение ленты новостей или загрузку фотографий), а не высокоуровневые операции или бизнес-процессы. Мы сосредоточимся на реализации ограничения на стороне сервера, которое управляет трафиком и защищает систему. Хотя ограничение скорости на стороне клиента также имеет ценность как дополнительный подход (об этом поговорим позже), ограничение скорости на стороне сервера является обязательным условием для обеспечения безопасности и защиты системы, поскольку клиентская часть системы может быть скомпрометирована.

Основные требования

1. Система должна идентифицировать клиентов по ID пользователя, IP-адресу или ключу API для применения соответствующих ограничений.

2. Система должна ограничивать HTTP-запросы на основании настраиваемых правил (например, разрешать 100 API-запросов в минуту на каждого пользователя).

3. При превышении установленных лимитов система должна отклонять избыточные запросы с ошибкой HTTP 429 (Too Many Requests) и включать полезные заголовки (количество оставшихся попыток, время сброса лимита).

За рамками задачи

• Сложные запросы или аналитика по данным об ограничениях запросов

• Долгосрочное хранение данных об ограничениях запросов

Нефункциональные требования

На данном этапе вы должны спросить интервьюера о масштабировании. Строим ли мы систему для стартапа с тысячами запросов в день или для крупной платформы, обрабатывающей миллионы запросов в секунду? Масштаб кардинально повлияет на наши проектные решения.

Предположим, что мы разрабатываем систему для значительного, но реалистичного объема нагрузки: 1 миллион запросов в секунду от 100 миллионов активных пользователей ежедневно.

1. Система должна добавлять минимально возможную дополнительную задержку (< 10 мс на проверку каждого запроса).

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

3. Система должна обрабатывать нагрузку в 1 млн запросов в секунду при наличии 100 млн ежедневных активных пользователей.

За рамками задачи

• Гарантии строгой согласованности между всеми узлами

На доске это могло бы выглядеть примерно так:

Подготовка

Планирование подхода

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

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

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

Проектирование API

Хотя rate limiter может показаться простым инфраструктурным компонентом, на самом деле он включает несколько важных сущностей, которые нам необходимо правильно смоделировать:

Rules (Правила): политики ограничения запросов, определяющие лимиты для различных ситуаций. Каждое правило определяет параметры, такие как количество запросов за временной интервал, к каким клиентам оно применяется и какие эндпоинты покрываются. Например: “авторизованные пользователи совершают 1000 запросов в час” или “API поиска допускает 10 запросов в минуту на каждый IP”.

Clients (Клиенты): объекты, подлежащие ограничению - это могут быть пользователи (идентифицируемые по ID пользователя), IP-адреса, ключи API или комбинации этих признаков. Каждый клиент имеет ассоциированное состояние, отслеживающее их текущее потребление относительно применимых правил.

Requests (Запросы): входящие API-запросы, которые необходимо оценить в соответствии с правилами ограничения. Каждый запрос несет контекст (такой как идентификационные данные клиента, эндпоинт и временная метка), который определяет, какие правила применяются и как отслеживать потребление.

Эти сущности работают совместно: когда поступает Запрос, мы идентифицируем Клиента, ищем соответствующие Правила, проверяем текущее потребление относительно этих правил и принимаем решение разрешить или отклонить запрос. Взаимодействие между этими сущностями обеспечивает работу нашего rate limiter-а.

Интерфейс системы

Rate limiter - это инфраструктурный компонент, к которому обращаются другие сервисы для проверки возможности обработки запроса. Интерфейс прост:

isRequestAllowed(clientId, ruleId) -> {
    passes: boolean,
    remaining: number,
    resetTime: timestamp
}

Этот метод принимает идентификатор клиента (ID пользователя, IP-адрес или ключ API) и идентификатор правила, затем возвращает разрешение или запрет на обработку запроса на основе текущего использования. Метод также предоставляет информацию для заголовков ответа, таких как X-RateLimit-Remaining и X-RateLimit-Reset.

Высокоуровневый дизайн

Мы начинаем с построения минимальной версии (MVP), которая удовлетворяет основным функциональным требованиям. Она не обязательно должна сразу поддерживать большие масштабы или быть идеальной. Это всего лишь основа, которую мы сможем развивать дальше. Мы пройдем по функциональным требованиям, убедившись, что каждое из них учтено в нашем high-level дизайне.

1. Система должна идентифицировать клиентов по User ID, IP-адресу или ключу API

Прежде чем мы сможем ограничить кого-либо, нам необходимо принять два ключевых решения. Во-первых, где именно в архитектуре системы должен находиться rate limiter? Это определяет, какой информацией мы располагаем и каким образом мы будем интегрироваться с остальной частью нашей системы. Во-вторых, как мы будем идентифицировать разных клиентов, чтобы применять правильные ограничения? Эти решения взаимосвязаны: выбор места размещения влияет на доступность информации о клиентах, а стратегия идентификации влияет на то, где стоит разместить rate limiter.

Где следует разместить rate limiter?

Здесь есть три основных варианта, каждый из которых имеет свои преимущества и недостатки:

Плохое решение: Внутри процесса

Подход

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

Проблемы

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

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

Хорошее решение: Выделенный сервис

Подход

Rate limiter становится отдельным сервисом, расположенным между клиентами и серверами приложений. Когда запрос поступает на сервер приложения, тот сначала отправляет API-запрос rate limiter-у: “Следует ли разрешить этот запрос от пользователя 69?” Rate limiter проверяет централизованные счетчики и возвращает либо “да, разрешен”, либо “нет, отклонен с ошибкой 429”.

Такая архитектура дает вам гораздо большую гибкость. Ваши серверы приложений могут передавать контекст при проверке лимита, например, уровень подписки пользователя, статус аккаунта, конкретный вызываемый эндпоинт API или даже сложную бизнес-логику вроде “разрешить дополнительные запросы в Черную пятницу”. Вы также можете иметь разные rate limiter-ы для разных частей вашей системы, каждый настроенный под конкретные потребности.

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

Проблемы

Самая большая проблема заключается в задержках обработки запросов. Теперь каждый отдельный запрос к вашей системе требует дополнительного цикла передачи данных по сети перед обработкой. Даже если rate limiter работает быстро (например, 10 мс), это все равно добавляет дополнительные 10 миллисекунд к каждому запросу. При увеличении масштаба эта задержка накапливается.

Мы также добавили еще одну точку отказа. Если rate limiter выйдет из строя, вам придется решить: либо разрешить обработку всех запросов (рискуя перегрузить систему), либо заблокировать все запросы (тем самым фактически отключив ваш API). Ни одно из решений не идеально. Кроме того, увеличивается операционная сложность системы. У вас теперь появился дополнительный сервис, который нужно разворачивать, мониторить, масштабировать и поддерживать. Сам rate limiter должен обладать высокой доступностью, что подразумевает необходимость наличия избыточности (redundancy), проверки работоспособности (health checks) и, вероятно, некоторого механизма репликации данных.

Наконец, нужно грамотно обрабатывать проблемы сети. Что делать, если rate limiter медленно отвечает? Ждать (увеличивая задержки) или завершать запрос по таймауту и действовать наугад? А что если возникает разделение сети между серверами приложения и rate limiter-ом?

Отличное решение: API-шлюз / Балансировщик нагрузки

Подход

Rate limiter располагается на самой границе вашей системы, интегрируясь в ваш API-шлюз или балансировщик нагрузки. Каждый поступающий запрос сначала попадает именно в rate limiter, прежде чем достигнуть ваших серверов приложения. Rate limiter исследует запрос (проверяет IP-адрес, заголовки аутентификации, ключи API), применяет соответствующие ограничения и либо перенаправляет запрос дальше, либо немедленно возвращает ответ с кодом HTTP 429.

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

Проблемы

Основная проблема заключается в отсутствии контекста. Rate limiter имеет доступ только к той информации, которая доступна непосредственно в самом HTTP-запросе - заголовкам, URL, IP-адресу и базовым токенам аутентификации. Он не видит бизнес-логику или контекст пользователя, который может существовать на уровне вашего приложения. Например, вам сложно реализовать правила вроде “премиальные пользователи получают лимиты в 10 раз больше”, если статус премиум-пользователя не закодирован в JWT-токене или аналогичном механизме.

Также возникает вопрос хранения состояния. API-шлюзу необходим быстрый доступ к счетчикам и временным меткам, что чаще всего означает использование хранилища типа Redis в оперативной памяти. Но теперь появляются внешние зависимости, и вам нужно учитывать ситуации, когда Redis работает медленно или вообще недоступен. Мы подробно обсудим все это далее!

Для нашего дизайна мы выберем подход с API-шлюзом. Это самый распространенный шаблон и он дает централизованный контроль без добавления лишних сетевых вызовов к каждому запросу. Теперь можно сосредоточиться на следующем вопросе: как идентифицировать клиентов?

Как мы идентифицируем клиентов?

Поскольку мы выбрали подход с использованием API-шлюза, наш rate limiter имеет доступ только к информации, содержащейся непосредственно в самом HTTP-запросе. Сюда входят URL запроса / путь, все заголовки HTTP (Authorization, User-Agent, X-API-Key и др.), параметры запроса и IP-адрес клиента. Хотя технически мы могли бы делать внешние вызовы к базам данных или другим сервисам, это добавляет задержку, которую мы хотим избежать, поэтому мы будем придерживаться самого запроса.

Сначала нам нужно решить, что именно делает “клиента” уникальным. Ключ, который мы используем, будет определять, каким образом будут применяться ограничения. У нас есть три основных варианта:

• User ID: идеально подходит для аутентифицированных API. Каждый вошедший пользователь получает свою собственную квоту ограничений скорости. Обычно этот идентификатор присутствует в заголовке Authorization в виде JWT-токена.

• IP-адрес: подходит для общедоступных API или ситуаций, когда отсутствуют учетные записи пользователей. Однако будьте осторожны с пользователями, находящимися за NAT или корпоративными файрволлами. IP-адрес чаще всего доступен в заголовке X-Forwarded-For.

• Ключ API: распространен среди API для разработчиков. Каждая учетная запись ключа имеет собственные лимиты. Чаще всего ключ находится в заголовке X-API-Key.

Это идеальное время задать вашему интервьюеру некоторые вопросы. Все ли пользователи проходят аутентификацию? Это API для разработчиков, которое требует ключей API? и т.п.

На практике вам, скорее всего, потребуется комбинация подходов. Например, аутентифицированные пользователи могут получать б`ольшие лимиты, чем анонимные IP-адреса, а премиум-пользователи могут иметь еще больше возможностей. Это отражает работу реальных систем, которые не ограничиваются глобальными лимитами, а накладывают многослойные правила. Например:

• Лимиты для пользователя: “Пользователь Алиса может сделать 1000 запросов в час.”

• Лимиты по IP: “Этот IP-адрес может отправлять максимум 100 запросов в минуту.”

• Глобальные лимиты: “Наш API способен обрабатывать суммарно до 50 000 запросов в секунду.”

• Лимиты по эндпоинтам: “API поиска ограничено 10 запросами в минуту, тогда как обновления профиля допускают до 100 запросов в минуту.”

Ваш rate limiter должен проверять все применимые правила и применять самое строгое ограничение. Если Алиса использовала лишь 50 из своих 1000 разрешенных запросов, но ее IP достиг лимита в 100 запросов, доступ ей будет заблокирован.

2. Система должна ограничивать запросы согласно настраиваемым правилам

Теперь мы переходим к сути ограничения частоты запросов: алгоритму, который решает, разрешить или отклонить запрос. Именно здесь принимаются реальные инженерные решения, однако это редко является центральной темой собеседования по System Design (в отличие от интервью по ООП проектированию). Вам следует продемонстрировать, что вы понимаете разные варианты и можете сделать выбор, но маловероятно, что вам придется реализовывать алгоритм даже на псевдокоде.

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

Фиксированное окно (Fixed Window)

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

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

Этот метод чрезвычайно прост в реализации. По сути, это хеш-таблица, сопоставляющая идентификаторы клиентов с парами (счетчик, начало_интервала). Основная проблема связана с граничными эффектами: пользователь мог бы отправить 100 запросов в 00:00:59, а сразу же после этого еще 100 запросов в 00:01:00, фактически получив возможность совершить 200 запросов всего за две секунды. Существует также риск возникновения ситуации, называемой “голоданием” (starvation), если пользователь достигает своего лимита в самом начале временного окна.

{
  "user1|00:00": 100,
  "user1|00:01": 5,
  "user2|00:00": 20,
  "user3|00:00": 0,
  "user4|00:00": 54,
  "user4|00:01": 12,
  "user5|00:00": 0
}

Лог скользящего окна (Sliding Window Log)

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

Такой подход обеспечивает абсолютную точность. Вы всегда смотрите именно на последние N минут запросов независимо от момента поступления текущего запроса. Нет проблем с границами окон, корректно обрабатываются всплески активности.

Недостатком является потребление памяти. Для пользователя, совершающего 1000 запросов в минуту, требуется хранить 1000 временных отметок. Масштабируйте это на миллионы пользователей, и вы быстро столкнетесь с проблемами нехватки памяти. Также существует вычислительная нагрузка при сканировании списка меток для каждого запроса.

Счетчик скользящего окна (Sliding Window Counter)

Это разумный гибридный подход, имитирующий работу скользящих окон с использованием математического приближения. Вы поддерживаете счетчики для текущего окна и предыдущего окна. Когда приходит запрос, вы оцениваете, сколько запросов пользователь “должен был” сделать в настоящем скользящем окне, находя взвешенную сумму счетчиков предыдущего и текущего окна в зависимости от того, насколько далеко вы продвинулись в текущем окне.

Например, если прошло 30% текущей минуты, вы учитываете 70% запросов предыдущей минуты плюс 100% текущих запросов.

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

Корзина токенов (Token Bucket)

Представьте себе каждого клиента с корзиной, которая способна вместить определенное количество токенов (burst capacity). Токены добавляются в корзину с постоянной скоростью (refill rate). Каждый запрос потребляет один токен. Если токенов нет, запрос отклоняется.

Например, корзина может содержать 100 токенов (позволяя всплеск до 100 запросов) и пополняться со скоростью 10 токенов в минуту (устойчивая скорость 10 запросов/минуту). Клиент может сразу сделать 100 запросов, а затем должен ждать пополнения токенов.

Это позволяет обрабатывать как устойчивые нагрузки (refill rate), так и временные всплески (burst capacity). Реализация также проста: достаточно отслеживать состояние (токены, последнее_пополнение) для каждого клиента. Основная сложность заключается в выборе правильного размера корзины и скорости пополнения, а также обработке ситуаций холодного старта, когда клиенты начинают работу с полной корзиной токенов.

Для нашей системы мы выберем алгоритм корзины токенов (Token Bucket). Он обеспечивает наилучший баланс между простотой реализации, эффективностью использования памяти и обработкой реальных паттернов трафика. Компании вроде Stripe используют этот подход, потому что он естественным образом учитывает импульсный характер трафика API, одновременно соблюдая общие ограничения частоты запросов.

Теперь перед нами новая проблема. Мы знаем, как работает алгоритм концептуально, но где и каким образом фактически хранить корзину каждого пользователя? Каждая корзина должна учитывать два элемента данных: текущее количество токенов и метку последнего пополнения. Это состояние должно быть доступно всем экземплярам нашего API-шлюза.

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

Например, если Алиса отправит 50 запросов, направленных на Шлюз А, и еще 50 запросов, направленных на Шлюз Б, каждый шлюз будет считать, что Алиса сделала всего 50 запросов и разрешит их все. Однако глобально Алиса совершила 100 запросов и должна была бы попасть под ограничение скорости. Наш алгоритм становится бесполезным без централизованного состояния.

Мы можем воспользоваться чем-то наподобие Redis. Redis представляет собой быстрое хранилище данных в оперативной памяти, доступное для всех наших экземпляров шлюза. Redis станет нашим централизованным источником истины относительно состояний всех корзин токенов. Когда любому шлюзу потребуется проверить или обновить счетчики лимитов конкретного пользователя, он обращается к Redis.

Вот полное описание того, как работает алгоритм Token Bucket с использованием Redis:

1. Запрос поступает в шлюз А для пользователя Алиса с идентификатором пользователя alice.

2. Шлюз обращается к Redis для извлечения текущего состояния корзины Алисы с помощью команды HMGET alice:bucket tokens last_refill. Команда HMGET извлекает значения нескольких ключей из Redis. В данном случае мы получаем текущее количество токенов и временную метку последнего пополнения корзины Алисы.

3. Шлюз рассчитывает, сколько токенов добавить в корзину Алисы, исходя из прошедшего времени с момента ее последнего пополнения. Если корзина Алисы была обновлена последний раз 30 секунд назад, а скорость пополнения составляет 1 токен в секунду, шлюз добавляет 30 токенов к текущему количеству, вплоть до максимальной емкости корзины.

4. Затем шлюз атомарно обновляет состояние корзины Алисы с помощью транзакции Redis, предотвращая состояние гонки (race condition).

MULTI
HSET alice:bucket tokens <new_token_count>
HSET alice:bucket last_refill <current_timestamp>
EXPIRE alice:bucket 3600
EXEC

Блок MULTI/EXEC гарантирует выполнение всех команд как единой атомарной операции. Команда HSET обновляет поля хэша новым количеством токенов и меткой времени, тогда как команда EXPIRE автоматически удаляет корзину через 1 час неактивности, предотвращая утечки памяти.

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

Но погодите - состояние гонки все равно есть!

Несмотря на транзакцию MULTI/EXEC, наша реализация все еще имеет состояние гонки. Проблема заключается в том, что операция чтения (HMGET) выполняется вне транзакции. Если два запроса для одного и того же пользователя поступают одновременно, оба шлюза считывают одинаковое начальное количество токенов, оба вычисляют, что могут разрешить запрос, и оба обновляют корзину. Это означает, что мы можем допустить два запроса, когда доступен всего лишь один токен.

Решение состоит в том, чтобы переместить всю логику чтения-вычисления-обновления в одну атомарную операцию. С использованием Redis это можно реализовать посредством так называемого Lua-скриптинга. Lua-скрипты в Redis выполняются атомарно, следовательно, все эти шаги становятся свободными от состояния гонки. Вместо отдельных операций чтения и записи мы отправляем Lua-скрипт в Redis, который читает текущее состояние, рассчитывает новое количество токенов и обновляет корзину за один атомарный шаг.

Состояния гонки (race conditions) в распределенных счетчиках являются классическим примером управления конкуренцией. Когда несколько потоков или процессов пытаются одновременно обновить один и тот же ресурс, мы можем потерять обновления, даже если отдельные операции атомарны. Решение заключается в расширении атомарной границы, включающей всю последовательность чтение- изменение-запись.

Почему Redis идеально подходит для этого:

• Скорость - ответы менее чем за миллисекунду для простых операций

• Автоматическая очистка - EXPIRE удаляет корзины пользователей спустя 1 час отсутствия активности

• Высокая доступность - может реплицироваться на множество экземпляров Redis

• Атомарные операции - транзакция MULTI/EXEC обеспечивает отсутствие состояния гонки между шлюзами

Итоговым результатом является точное и согласованное ограничение частоты запросов на всех экземплярах шлюзов. Независимо от того, поступает ли сотый запрос Алисы на шлюз A, B или C, все они видят одинаковое состояние корзины токенов и применяют одинаковые лимиты.

3. Когда лимит превышен, запросы отклоняются с кодом HTTP 429 и информативными заголовками

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

Следует отбрасывать запросы или ставить их в очередь?

Первым решением является выбор между немедленным отказом или помещением запросов в очередь для последующей обработки. Большинство rate limiter-ов используют подход “fail fast”: они немедленно возвращают статус-код HTTP 429, когда лимит превышен. Именно этот вариант мы будем реализовывать.

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

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

Как сделать ответ полезным?

429 - стандартный HTTP код для обозначения ситуации “слишком много запросов” (Too Many Requests). Он включен в спецификацию HTTP именно для этой цели.

При отклонении запроса мы возвращаем HTTP 429 Too Many Requests вместе с заголовками, помогающими клиентам понять, что произошло, и как восстановиться. Ключевыми заголовками являются:

• X-RateLimit-Limit: лимит ограничений для данного запроса (например, 100)

• X-RateLimit-Remaining: количество оставшихся запросов в текущем окне (например, 0)

• X-RateLimit-Reset: время сброса ограничения, заданное в виде Unix timestamp (например, 1770043766)

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

Вот пример полного ответа с кодом 429:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1770043766
Retry-After: 60
Content-Type: application/json

{
  "error": "Rate limit exceeded",
  "message": "You have exceeded the rate limit of 100 requests per minute. Try again in 60 seconds."
}

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

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

Потенциальные погружения в детали

На данный момент мы разработали простой rate limiter с одним экземпляром Redis. Но теперь нам нужно обсудить, как масштабировать его для обработки 1 млн запросов/секунду и 100 млн ежедневных пользователей, сохраняя высокую доступность и низкую задержку.

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

1. Как масштабироваться для обработки 1 миллиона запросов в секунду?

Наш текущий дизайн предусматривает наличие множества API-шлюзов, взаимодействующих с одним узлом Redis. Это работает хорошо для небольших нагрузок, однако все рушится при достижении нашей целевой нагрузки в 1 миллион запросов в секунду. Хорошо сконфигурированный экземпляр Redis способен обрабатывать около 100K – 200K операций в секунду в зависимости от сложности операции. Каждая проверка лимита требует нескольких операций Redis, минимум - получение состояния с помощью команды HMGET и обновление с помощью команды HSET. Таким образом, наш экземпляр Redis реалистично сможет обработать примерно 50K–100K проверок в секунду прежде чем станет узким местом.

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

Rate limiter-ы иллюстрируют классические проблемы масштабирования записи с миллионами обновлений счетчиков в секунду. Каждая проверка ограничения скорости требует атомарных операций чтения-изменения-записи для обновления корзин токенов или счетчиков запросов на распределенных шардах Redis.

Стратегия шардирования зависит от наших правил ограничения скорости. Напомним, ранее мы выделили несколько типов клиентов: User ID для аутентифицированных пользователей, IP-адреса для анонимных пользователей и ключи API для разработчиков. Нам необходимо обеспечить согласованное распределение данных между шардами, чтобы запросы каждого клиента всегда попадали на один и тот же экземпляр Redis. Если запросы пользователя “alice” иногда попадают на шард Redis #1, а иногда на шард Redis #2, состояние становится фрагментированным и бесполезным.

Нам необходим алгоритм распределения, подобный согласованному хешированию, чтобы решить эту проблему. Для аутентифицированных пользователей мы используем хеширование их User ID, чтобы определить, на каком шарде Redis хранятся их данные об ограничениях скорости. Для анонимных пользователей мы применяем хэширование их IP-адреса. Для запросов с ключами API мы хешируем сам ключ API. Это гарантирует, что состояние счетчиков каждого клиента хранится ровно на одном шарде, равномерно распределяя нагрузку между всеми шардами.

Каждый API-шлюз нуждается в логике маршрутизации для определения нужного шарда Redis. Когда приходит запрос, шлюз извлекает соответствующий идентификатор (User ID, IP-адрес или ключ API), применяет алгоритм распределения и направляет проверку ограничения скорости на правильный экземпляр Redis. Алгоритм ограничения остается точно таким же, единственное отличие заключается в том, что мы обращаемся к разным экземплярам Redis вместо одного.

Используя 10 шардов Redis, каждый из которых обрабатывает около 100 тысяч операций в секунду, мы сможем достичь цели в 1 миллион запросов в секунду.

В реальном проекте вы, вероятно, предпочтете использовать Redis Cluster вместо самостоятельного управления отдельными экземплярами Redis. Redis Cluster автоматически осуществляет шардирование данных, которое мы только что обсудили, путем деления ключей на 16 384 хеш-слота и распределения этих слотов по нескольким узлам Redis. Когда вы сохраняете ключ типа alice:bucket, Redis Cluster автоматически определяет, на каком узле он должен храниться, основываясь на слоте хеша ключа. Таким образом, вам не придется создавать собственную логику согласованного хеширования, достаточно лишь подключиться к Redis Cluster, и он самостоятельно обработает маршрутизацию.

2. Как обеспечить высокую доступность и устойчивость к сбоям?

Теперь, когда мы масштабировались до нескольких шардов Redis, каждый шард становится критически важным компонентом нашей системы. Если какой-либо шард Redis выходит из строя, все пользователи, чьи данные о счетчиках ограничения скорости хранятся на этом шарде, теряют функциональность rate limiter-а. Это создает проблемы с доступностью и может привести к каскадному сбою, если пользователи начнут агрессивно повторять запросы, когда не смогут получить правильные ответы по лимитам скорости.

Когда шард Redis становится недоступным, нам надо принять принципиальное решение о режиме поведения. У нас есть два варианта:

Оба варианта являются “хорошими” решениями, поскольку все зависит от конкретных требований вашей системы!

Для нашей социальной сети мы выберем режим Fail-Closed. Хотя это кажется нелогичным, учитывая нашу цель обеспечить высокую доступность, реальность такова, что сбои в работе rate limiter-а зачастую совпадают с резкими скачками трафика, когда защита особенно нам необходима. Во время вирусных событий, если Redis выйдет из строя и мы перейдем в открытый режим, внезапный поток сообщений, обновлений ленты и уведомлений мог бы завалить наши базы данных. Кратковременные периоды отклонения запросов предпочтительнее, чем каскадный сбой всей системы.

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

Хотя мы редко подробно останавливаемся на этом в наших разборах (просто потому, что обычно есть более интересные вещи, о которых стоит рассказать), мониторинг и алерты важны для поддержания высокой доступности нашей системы. Мы хотим отслеживать метрики Redis, такие как использование процессора, потребление памяти и сетевое соединение по всем шардам. Нам также необходим мониторинг на уровне приложения, включающий успешность операций ограничения скорости, время ответов и алерты, срабатывающие, когда система переходит в режим “Fail-Open”. Цель состоит в том, чтобы обнаружить и отреагировать на возникающие проблемы настолько быстро, чтобы пользователи не испытывали ухудшения качества обслуживания.

3. Как минимизировать накладные расходы и задержку?

Каждая проверка ограничения скорости требует сетевого обращения к Redis, что добавляет задержку к пользовательским запросам. Несмотря на то, что операции Redis обычно занимают менее миллисекунды, сетевые издержки могут добавить несколько миллисекунд на каждый запрос. При объеме в 1 миллион запросов в секунду такая задержка может стать проблемой.

Наиболее важная оптимизация - это пул соединений. Вместо установления нового TCP-соединения с Redis для каждой проверки ограничения скорости шлюзы API поддерживают пул постоянных соединений. Это устраняет накладные расходы на установление соединения TCP (которые могут составлять от 20 до 50 мс в зависимости от расстояния) и позволяет повторно использовать одно подключение для множества запросов. Большинство клиентов Redis автоматически управляют пулом соединений, но вам потребуется настроить размер пула исходя из объема ваших запросов и времени отклика Redis.

Географическая распределенность обеспечивает наибольший выигрыш в плане снижения задержки. Разверните инфраструктуру rate limiter-а рядом с пользователями, например, разместив API-шлюзы и Redis Cluster в нескольких зонах доступности. Пользователь во Владивостоке увидит гораздо меньшую задержку при обращении к экземпляру Redis в той же зоне, нежели к экземпляру в Москве. Обратной стороной медали является сложность поддержки согласованности данных между регионами, но для задач rate limiter-а вы можете принять режим конечной согласованности между регионами в обмен на уменьшение задержки.

Другие оптимизации, которые стоит кратко упомянуть, но в которые мы углубляться не будем: локальное кэширование состояния rate limiter-а возможно, но оно рискованно, так как устаревшие данные кэша могут приводить к неверным решениям по ограничениям. Cкрипты Lua позволяют объединять операции, уменьшая количество обращений. Пакетная обработка запросов полезна, когда одновременно поступает множество запросов от одного пользователя. Однако эти оптимизации добавляют сложность и обычно необязательны, если вы правильно настроили пул соединений и географическое распределение. На собеседовании можете не упоминать их, если только вас специально не попросят.

4. Как справляться с горячими ключами?

Горячие ключи (hot keys) часто упоминаются в дискуссиях по System Design, и мы рассматриваем техники их обработки в нашем паттерне масштабирование чтения. Применительно к rate limiter-у, горячие ключи могут возникать как вследствие злонамеренного трафика, так и от легитимных пользователей с высоким объемом запросов.

Хотя rate limiter преимущественно обрабатывает записи (обновления счетчиков), горячие ключи создают экстремальную нагрузку на чтение при масштабировании, когда тысячи запросов с одного и того же IP-адреса или пользователя одновременно попадают на проверку ограничений скорости, перегружая определенные шарды Redis.

Представьте себе ситуацию, которая привела бы к созданию горячего ключа в нашем ограничителе скорости. Один пользователь или IP-адрес должен создать достаточное количество запросов, чтобы перегрузить шард Redis - речь идет о десятках тысяч запросов в секунду от одного источника. Обычно это свидетельствует о злоупотреблении (атаки DDoS, неправильно настроенные боты), но иногда это может происходить и от легитимных пользователей с высокими объемами запросов, таких как аналитические системы, конвейеры данных или мобильные приложения с агрессивными схемами обновления.

Нам нужны разные стратегии для разных ситуаций:

Для легитимных пользователей с высоким объемом запросов:

• Ограничение скорости на стороне клиента: для добросовестных клиентов можно внедрять собственное ограничение скорости для сглаживания схемы трафика. Это предотвращает случайное создание горячих шардов легитимными пользователями и снижает нагрузку на сервер. Многие API SDK включают встроенное клиентское ограничение скорости, которое учитывает заголовки ответов сервера.

• Очередь запросов / пакетная обработка: позволяйте клиентам объединять несколько операций в единый запрос, сокращая общее число проверок ограничения скорости.

• Премиум-тарифы: предлагайте повышенные лимиты скорости для пользователей, которым они необходимы, возможно, с выделенной инфраструктурой.

Для случаев злонамеренного трафика:

• Автоматическая блокировка: когда клиент регулярно превышает лимиты (например, десять раз в минуту), временно заблокируйте его IP-адрес или ключ API целиком, добавив его в список блокировки.

• Защита от DDoS: используйте сервисы вроде Cloudflare или AWS Shield, способные распознавать и блокировать вредоносный трафик еще до того, как он достигнет вашего rate limiter-а.

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

Нельзя исключить вероятность того, что у вас действительно могут быть легитимные пользователи, совместно использующие одни и те же IP-адреса (корпоративные NAT, публичный Wi-Fi). Лучше заранее спроектировать свой rate limiter с учетом этого фактора, а не пытаться решать проблему горячих ключей постфактум.

5. Как управлять динамической настройкой правил?

До сих пор мы предполагали, что правила ограничения запросов статичны: пользователь Х получает Y запросов в минуту. Однако реальные системы требуют гибкости для изменения лимитов без развертывания нового кода. Возможно, вам понадобится временно увеличить лимиты во время запуска продукта, предоставить премиум-пользователям более высокий лимит или оперативно снизить лимиты, если наблюдаются необычные шаблоны трафика. Существует два основных подхода к обработке динамического обновления конфигурации:

Отличное решение: Конфигурация на основе Push

Подход

При данном подходе изменения конфигурации немедленно отправляются всем шлюзам API. Именно для этого был разработан ZooKeeper - распределенное управление конфигурацией с уведомлениями в реальном времени. ZooKeeper сохраняет данные конфигурации и сразу уведомляет всех подключенных клиентов (шлюзы API), когда происходят любые изменения конфигурации. Другие опции включают механизм публикации-подписки Redis или собственные службы конфигурации, поддерживающие постоянные подключения к шлюзам.

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

Проблемы

Этот подход значительно усложняет систему. Необходимо обрабатывать отказы соединений, убедиться, что все шлюзы получили обновления, и справляться с частичными сбоями, когда некоторые шлюзы успешно обновляются, а другие - нет. Также потребуются механизмы аварийного переключения на случай недоступности ZooKeeper.

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

Что ожидается на каждом уровне?

Middle

Кандидат Middle уровня должен сосредоточиться главным образом на широте охвата (80% против 20%) и он должен уметь разработать высокоуровневый дизайн, соответствующий функциональным требованиям, хотя многие компоненты будут абстракциями, понятными лишь поверхностно. Ваш интервьюер потратит время на подтверждение вашего понимания функций каждого компонента - если вы упомянете Redis, ожидайте вопросов о том, как он работает и почему вы выбрали именно его. Вы должны вести начальные этапы, такие как сбор требований и базовый выбор алгоритмов, однако не обязательно проактивно выявлять все недостатки дизайна. Для данного конкретного вопроса вам следует ясно объяснить один алгоритм ограничения запросов (например, “Корзина с токенами” вполне подойдет), разумно разместить ограничитель в архитектуре (API-шлюз), определить Redis как решение для совместного состояния и, когда вас спросят о масштабировании, указать на необходимость шардирования Redis с общим пониманием того, как это должно работать.

Senior

Для Senior кандидата ожидания смещаются в сторону большей технической глубины (60% широты, 40% глубины), где вы уверенно обсудите компромиссы между различными алгоритмами ограничения запросов и сможете обосновать свой выбор. Вам следует понимать концепции распределенных систем, такие как согласованное хеширование, кластеры Redis и пул соединений, знать, что операции Redis должны быть атомарными, и предложить транзакции типа MULTI/EXEC. От вас ожидают ясного объяснения компромиссов между открытыми и закрытыми режимами отказоустойчивости, обсуждения плюсов и минусов разных мест размещения ограничителей, активного выявления потенциальных проблем, таких как горячие ключи, проблемы доступности Redis и возможности оптимизации задержки. Что касается конкретно ограничения запросов, кандидаты этого уровня должны быстро пройти обсуждение базовых алгоритмов и потратить больше времени на проблемы распределенных систем, уверенно обсудить стратегии шардирования Redis и сценарии отказа, а также иметь представление относительно подходов к управлению конфигурацией.

Staff+

Кандидаты Staff+ уровня должны продемонстрировать глубокое понимание принципов распределенного ограничения запросов в производственных средах (40% широта, 60% глубина) и основывать свои рассуждения на реальном опыте работы с системами аналогичного масштаба. Ожидается исключительная инициативность. Вы должны выявить граничные случаи, обсудить требования к наблюдаемости системы и предложить эксплуатационные подходы без вмешательства интервьюера. У вас должны быть твердые взгляды на технологический выбор, основанные на опыте, решение для вопросов глобального развертывания и о компромиссах согласованности данных с учетом географического распределения. Специалисты высокого уровня нечасто получают эту задачу на собеседовании, но если это произошло, вы должны быстро спроектировать систему и большую часть времени посвятить вопросам эксплуатации, режимов сбоев и интеграционных сложностей, возникающих из реального опыта.

Разборы задач по System Design:

• Проектируем Ticketmaster, сервис бронирования билетов

• Проектируем Uber, сервис для заказа такси

• Проектируем Tinder, сервис быстрых знакомств

• Проектируем Dropbox, сервис для хранения и обмена файлами