SYS Системы и большие данные Алгоритм
Ограничение частоты запросов
Также: Rate limiting · rate limiter · ведро с токенами · token bucket · дырявое ведро · leaky bucket · скользящее окно · GCRA
Как пропускать не больше N запросов в единицу времени и не душить законные всплески: окно по часам, журнал, два счётчика и ведро с токенами. На настоящем потоке уведомлений о землетрясениях видно, кто из них что обещает на самом деле — и какое ведро нужно, чтобы за одиннадцать лет не потерять ни одного уведомления.
Служба уведомлений шлёт сообщение о каждом землетрясении магнитудой 5 и больше. Обычно это около пяти в сутки, и подписчик просит одно: не больше пяти в час. 29 июля 2025 года в 23:24 по UTC произошло землетрясение магнитудой 8,8, и за следующий час пришло 38 событий, а за двое суток — 189. Какие уведомления отправить, какие отбросить? Ниже четыре способа на этих двух сутках. Цветные черты прошли, серые отброшены, а скобка над шкалой показывает, сколько прошло за самые насыщенные 60 минут.
Только журнал держит обещание «не больше пяти за любые 60 минут». Окно по часам пропускает девять, два счётчика — семь, ведро — девять. Но ведро нарушает лимит не случайно: так оно устроено, и в этом его ценность. Разберёмся, кто что обещает.
Идея
Ограничитель стоит между потоком и тем, кого надо защитить, — сервером, подписчиком, каналом. На каждый запрос он отвечает «пропустить» или «отклонить», помня как можно меньше. Простейших способов четыре.
Окно по часам. Время делится на отрезки по часу, в каждом — счётчик, который обнуляется на границе. Одно число на клиента, но на границе отрезков проходит до 2N: N в последние секунды одного часа и N в первые секунды следующего. В сцене так и выходит: в первую ночь всплеска на стыке двух часов проходят девять уведомлений за 60 минут.
Журнал. Помним время каждого пропущенного запроса и пропускаем, если за последние 60 минут их меньше N. Обещание выполняется точно, но память — N моментов на клиента: на миллионе клиентов и лимите в тысячу это уже миллиард чисел.
Два счётчика. Компромисс, который Cloudflare описала в 2017 году: счётчик прошлого часа и текущего, и прошлый берётся с весом той доли окна, что ещё не вышла: оценка = прошлый·(1 − прошло/час) + текущий. Это журнал в предположении, что прошлый час был равномерным. На их собственных данных — 400 миллионах запросов от 270 тысяч источников — ошибочно пропущено или отклонено 0,003 %. На резком всплеске равномерности нет, и в сцене пропускается семь вместо пяти.
Ведро с токенами держит до b токенов и пополняется со скоростью r в секунду, вначале оно полное. Запрос проходит, если есть токен, и забирает его. Ведро разрешает всплеск до b запросов сразу, а дальше пропускает в среднем r в секунду — ровно то, что нужно живому трафику: тишина копит запас, всплеск его тратит.
Что обещает ведро
Ведро с запасом b и пополнением r за любой промежуток длиной T пропускает не больше b + r·T запросов. Поток проходит без потерь тогда и только тогда, когда для любых двух его запросов i ≤ j число запросов между ними включительно не больше b + r·(tj − ti).
В начале промежутка в ведре не больше b токенов, за время T приходит не больше r·T новых, а каждый пропущенный запрос забирает один токен. Значит, пропущенных не больше b + r·T. Отсюда же «только тогда» во второй части: если какие-то запросы с i-го по j-й не помещаются в эту оценку, кто-то из них потерян. Обратно, пусть потерян запрос j, первый такой. Возьмём последний момент перед ним, когда ведро было полным, и первый запрос i после этого момента. С тех пор ведро не переполнялось, то есть получило ровно b + r·(tj − ti) токенов, и их не хватило на j − i + 1 запросов — условие нарушено.
Первая часть — честная формулировка того, что видно в сцене: при b = 5 и пяти в час за любые 60 минут проходит не больше десяти. Вторая часть отвечает на вопрос, какой запас нужен, чтобы ничего не потерять. Обозначим aj = j/r − tj: условие становится b ≥ r·(aj − ai) + 1, и наибольшая разность ищется одним проходом с бегущим минимумом. На всех 19 073 событиях 2015–2025 годов это даёт:
При пяти уведомлениях в час нужно ведро на 74. Требование задал тот самый июльский всплеск: 105 событий за шесть с небольшим часов. Обратите внимание: за любой отдельный час их было не больше 38, а ведру нужно почти вдвое больше — длинный всплеск опустошает его постепенно, и за шесть часов пополнение даёт только 30 токенов. Ведро размером в пять токенов за одиннадцать лет потеряло бы 197 уведомлений, почти все — в несколько таких дней.
Ведро в целых числах
Дробное число токенов и таймер пополнения не нужны. Сетевые устройства считают ведро иначе, по алгоритму GCRA из стандартов ATM: хранят одно число tat — момент, когда ведро снова стало бы полным. При интервале I = 1/r запрос в момент t проходит, если t ≥ tat − (b − 1)·I, и тогда tat ← max(tat, t) + I. Каждый пропущенный запрос сдвигает «время полного ведра» на один интервал вперёд, а простой его догоняет. Одно целое число на клиента, без таймеров и без деления — так ведро и реализуют в листингах.
У этого же ведра есть второе имя — «дырявое»: если запросы в нём не отбрасываются, а ждут очереди и вытекают с постоянной скоростью, получается сглаживающая очередь. В роли счётчика, как в GCRA, «дырявое ведро» и ведро с токенами — одно и то же; nginx называет свою директиву limit_req дырявым ведром, и с параметром burst она ставит лишние запросы в очередь, а без него отклоняет.
Код
Четыре ограничителя на тех же двух сутках землетрясений, пять уведомлений в час, и расчёт наименьшего ведра для всех одиннадцати лет.
Окно по часам и ведро пропустили больше всех — 114 и 120 из 189, — но оба допускают девять за час. Журнал пропустил меньше всех, 107, зато ни разу не превысил пяти. Это не «лучше» и «хуже», а разные обещания: журнал обещает подписчику «не больше пяти за любой час», ведро — «в среднем не больше пяти в час и всплеск до пяти сверху».
Сколько это стоит
Окно по часам, два счётчика и ведро — O(1) времени на запрос и одно-два числа на клиента. Журнал — O(N) памяти на клиента и O(N) времени на запрос в простой реализации (или амортизированно O(1) с очередью, из которой выбрасываются устаревшие моменты). Для миллионов клиентов сами числа хранят в общей памяти — например, в Redis, где окно по часам делается командами INCR и EXPIRE, а ведро — коротким сценарием, который атомарно читает и пишет tat.
Если ограничителей много и они на разных серверах, точность упирается не в алгоритм, а в согласованность: у каждого сервера своё ведро, и вместе они пропускают больше. Тогда лимит делят между серверами или держат общий счётчик, мирясь с задержкой.
Где работает
Веб-серверы. В nginx ограничение задаётся парой директив: limit_req_zone описывает зону адресов и скорость, limit_req включает её для пути и задаёт запас burst.
API. Публичные API ограничивают клиентов почти всегда: у REST API GitHub, например, 5000 запросов в час для пользователя с ключом и 60 — без ключа. Остаток лимита сервис сообщает в заголовках ответа, чтобы клиент сам замедлялся, а не получал отказы. Отказавшему клиенту полезно повторять запрос не сразу и не все одновременно — об этом статья о повторах с джиттером.
Сети. Ведро в целых числах пришло из телефонных сетей с асинхронной передачей (ATM): там GCRA проверял, что абонент не превышает оговорённую скорость передачи ячеек, и стандарты описывают его как «ведро конечной ёмкости, из которого непрерывно вытекает».
История
Дырявое ведро как способ следить за скоростью потока описал в 1986 году Джонатан Тёрнер для сетей с коммутацией ячеек; позже ATM Forum и стандарт ITU-T I.371 закрепили его в виде GCRA. Ведро с токенами в нынешнем виде стало общим языком описания трафика в сетях с гарантированным качеством обслуживания, а с ростом публичных API в 2000-е — стандартным ограничителем запросов. Два счётчика Cloudflare описала в 2017 году как дешёвую замену журналу для миллионов доменов.
Задачи
В первой задаче нужно сравнить окно по часам и ведро на одном потоке и найти, сколько каждое пропускает за самые насыщенные W секунд. Во второй — найти наименьшее ведро, которое ничего не теряет, в том числе для всех землетрясений 2015–2025 годов.
Два ограничителя Запас ведраДанные: Землетрясения: каталог USGS, общественное достояние