Сервис должен поддерживать среднюю скорость 100 запросов в секунду, но кратковременно принимать до 200 запросов. Объясните механизм ограничения в конфигурации ниже.
capacity = 200
rate = 100
tokens = capacity
last_time = 0
def allow(now):
global tokens, last_time
tokens = min(capacity, tokens + (now - last_time) * rate)
last_time = now
if tokens < 1:
return False
tokens -= 1
return True
Это token bucket — алгоритм ведра токенов. Токены пополняются со скоростью 100 в секунду до максимума 200, а каждый запрос расходует один токен. Поэтому накопленный запас разрешает краткий всплеск до 200 запросов, но длительная средняя скорость не может превышать 100 запросов в секунду.
Жёсткое ограничение по фиксированным временным окнам плохо учитывает границы интервалов: запросы могут集中ироваться на стыке двух окон и давать кратковременный скачок нагрузки. Token bucket появился как более гибкий способ одновременно контролировать среднюю скорость и разрешать безопасные короткие bursts.
Подход особенно полезен перед дорогими ресурсами: базой данных, внешним API или пулом рабочих потоков. Он защищает ресурс от длительного превышения мощности, не отклоняя каждый кратковременный пик.
Если принимать все входящие запросы, краткий всплеск может заполнить очереди, увеличить задержку и привести к исчерпанию соединений или памяти. Если ограничивать поток строго до 100 запросов в каждую секунду, сервис будет использовать доступную мощность слишком консервативно и отклонять часть безвредных всплесков.
Нужно различать среднюю скорость и мгновенный burst. Неверный выбор размера ведра может либо не защитить зависимость, либо создать слишком большой пик, который она не способна обработать.
В начале работы ведро содержит 200 токенов. Каждый токен представляет право обработать один запрос. При поступлении запроса алгоритм сначала добавляет токены за время, прошедшее с предыдущей проверки:
capacity ограничивает размер накопленного запаса, а rate задаёт долгосрочную скорость пополнения. Если токен есть, запрос допускается и один токен списывается; если токенов нет, запрос отклоняется или помещается в очередь.
В приведённой конфигурации полностью пустое ведро восстановится за две секунды: 200 токенов делятся на скорость пополнения 100 токенов в секунду. При постоянном потоке выше 100 запросов в секунду запас постепенно исчерпается, после чего новые запросы начнут отклоняться.
Это не означает, что любой клиент может постоянно отправлять 200 запросов в секунду. Значение 200 — только начальный или накопленный запас, а не устойчивая пропускная способность. Формально допустимая нагрузка за интервал ограничена начальным запасом плюс токены, накопленные за этот интервал.
В распределённой системе отдельное ведро на каждом экземпляре даёт общий лимит, умноженный примерно на число экземпляров. Для единого лимита используют общий координатор или распределённый счётчик, но это добавляет сетевые задержки, конкуренцию и новую зависимость. Локальные лимиты проще и надёжнее, однако требуют учитывать распределение трафика между экземплярами.
Важно определить, что именно ограничивается: все запросы, отдельный клиент, ключ API, маршрут или класс операций. Для дорогих операций запрос может расходовать несколько токенов. При отказе хранилища лимитов нужно заранее выбрать политику fail-open или fail-closed: первая сохраняет доступность ценой возможной перегрузки, вторая лучше защищает ресурс, но может сама стать источником отказов.
Клиенту следует возвращать понятный ответ об ограничении, например HTTP 429, и при возможности указывать время ожидания. Если вместо отклонения применяется очередь, она тоже должна быть ограниченной: иначе rate limiting лишь перенесёт переполнение из входного потока в память и увеличит задержку.
Публичный API получает обычные 70–90 запросов в секунду, но после публикации рекламной кампании возникают всплески до 180 запросов в секунду длительностью несколько секунд. Команда рассмотрела фиксированное окно на 100 запросов в секунду, очередь без ограничения и token bucket с параметрами 100 и 200.
Фиксированное окно было простым, но создавало резкие границы интервалов и отклоняло часть короткого безопасного всплеска. Неограниченная очередь сохраняла запросы, но при длительной перегрузке увеличивала задержку и расход памяти. Выбрали token bucket: ведро на 200 запросов поглощало короткий пик, а длительный поток выше 100 запросов в секунду ограничивался.
Лимит применили отдельно к ключу клиента и дополнительно оставили общий защитный лимит на экземпляр. Это предотвратило ситуацию, когда один клиент расходует весь общий запас, но сохранило возможность быстро обслуживать краткие всплески легитимного трафика.
1. Чем token bucket отличается от leaky bucket?
Ответ: Token bucket разрешает bursts размером до текущего количества токенов, ограничивая среднюю скорость пополнения. В классической модели leaky bucket поток выходит с более ровной скоростью; лишние запросы либо ждут в очереди, либо отклоняются. Поэтому token bucket лучше подходит, когда краткие пики допустимы, а leaky bucket — когда важна сглаженная нагрузка на downstream-систему.
2. Почему одинаковый лимит на каждом экземпляре не равен единому лимиту сервиса?
Ответ: Если лимит 100 запросов в секунду установлен локально на десяти экземплярах, суммарно система может пропустить примерно 1000 запросов в секунду. При изменении маршрутизации или числа экземпляров эффективный общий лимит также меняется. Единый лимит требует координации состояния либо централизованного распределителя квот, что повышает точность, но добавляет задержку и зависимость.
3. Как выбрать размер ведра?
Ответ: Размер должен соответствовать безопасному кратковременному объёму нагрузки, который защищаемый ресурс способен принять без исчерпания очередей, соединений и памяти. Слишком маленькое ведро будет отклонять нормальные bursts, а слишком большое позволит сформировать пик, опасный для зависимости. Размер оценивают вместе с пополнением, допустимой задержкой и реальной ёмкостью downstream-системы, а не выбирают независимо от них.