Для чего нужно ограничение скорости API
Ограничение скорости помогает защитить сервисы от злонамеренных поведений, нацеленных на протоколы прикладного уровня. К числу таких поведений относятся DoS-атаки (атаки типа «отказ в обслуживании»), транзакции или попытки входа в систему путём полного перебора вариантов пароля и т. д. Эти атаки обычно выполняются через HTTP/HTTPS-запросы, которые могут выглядеть так, будто исходят от реальных пользователей, но генерируются в основном ботами или какими-то скриптами. Поэтому их так сложно обнаружить. В результате сервис или приложение легко выводятся из строя.
Если задействовать rate limiter (ограничитель скорости), то вредоносный скрипт не сможет осуществить злонамеренных действий с сервисом или приложением. Это предотвратит перегруженность сервиса лишним трафиком или запросами и приведёт к большей удовлетворённости пользователей.
Алгоритмы ограничения скорости
В целом под скоростью здесь понимается простое число вхождений (запросов) за определённое время. Существует несколько различных методов измерения и ограничения скорости, у каждого из которых свои особенности применения и последствия.
«Ведро» с токенами
Допустим, у нас есть «ведро», полное токенов. При поступлении запроса для его дальнейшей обработки необходимо взять из «ведра» токен. Если токена в «ведре» нет, запрос будет отклонен. «Ведро» токенов заполняется в зависимости от единицы времени.
Количество запросов на одного пользователя в единицу времени можно ограничить, выделив каждому пользователю «ведро» с фиксированным количеством токенов. Когда у пользователя в какой-то момент все токены оказываются израсходованными (это означает, что он превысил лимит), его запросы отбрасываются, пока «ведро» не будет заполнено.
Протекающее «ведро»
Этот алгоритм тесно связан с первым алгоритмом («ведро» с токенами). К ограничению скорости здесь применяется простой подход через очередь, которую можно считать «ведром», содержащим запросы. При регистрации запрос добавляется в конец очереди. Через определённый промежуток времени обрабатывается первый элемент в очереди. Если очередь заполнена, то дополнительные запросы отбрасываются (или «просачиваются»).
Преимущество этого алгоритма
Сглаживаются всплески запросов, которые обрабатываются практически со средней скоростью. К тому же, алгоритм легко реализовать на одном сервере или балансировщике нагрузки. При этом он экономичен в потреблении памяти для каждого пользователя с учётом ограниченного размера очереди.
Фиксированное окно
В этом алгоритме для отслеживания скорости используется размер окна в N секунд (например, 60 или 600 секунд). Каждый входящий запрос увеличивает счётчик для окна. Если счётчик превышает пороговое значение, запрос отбрасывается. Окна обычно определяются округлением вниз текущей метки времени. Так, значение 10:00:06 при длине окна в 60 секунд будет в окне 10:00:00.
Преимущество этого алгоритма
Обеспечивает обработку более поздних запросов, не зависая на старых. Но единичный всплеск трафика вблизи границы окна может привести к удвоению скорости обрабатываемых запросов. Ведь в течение небольшого промежутка времени он разрешает запросы как для текущего, так и для следующего окна. Кроме того, большое количество пользователей, ожидающих сброса счётчика окна в пиковый период, может одновременно обратиться к API.
Скользящий журнал
Ограничение скорости с использованием этого алгоритма предполагает отслеживание записей с метками времени для каждого запроса. Эти записи обычно сохраняются в hash set (хеш-множестве) или хеш-таблице и сортируются там по времени. Записи с метками времени, выходящими за пределы порогового значения, отбрасываются. Когда поступает новый запрос, суммируется количество записей и таким образом определяется скорость запросов. Если запрос превысит пороговое значение скорости, то он задерживается.
Преимущество этого алгоритма
Отсутствие проблем предыдущего алгоритма, возникающих вблизи границы окон. Будет обеспечено точное соблюдение ограничения скорости. И никакого эффекта одновременного обращения к API большого количества пользователей, так как скользящий журнал отслеживается для каждого их запроса. Однако хранить неограниченное количество записей для каждого запроса — очень дорогое удовольствие. Недёшево обходится и суммирование количества предыдущих запросов при поступлении каждого нового. Причём потенциально такое суммирование будет выполняться на кластере серверов. В результате применение этого алгоритма плохо масштабируется для обработки больших всплесков трафика или атак типа «отказ в обслуживании».
Скользящее окно
А это гибридный подход, в котором низкая стоимость обработки запросов, характерная для алгоритма фиксированного окна, сочетается с отсутствием проблем вблизи границы окон алгоритма скользящего журнала. Как и в алгоритме фиксированного окна, здесь отслеживается счётчик для каждого окна. Затем для сглаживания всплесков трафика берётся взвешенное значение скорости запросов предыдущего окна с учётом текущей метки времени.
Например, если текущее окно пройдено на 25 %, то числу предыдущего окна присваивается вес 75 %. Относительно небольшое количество точек данных, необходимых для отслеживания на ключ, позволяет масштабировать и распределять данные по большим кластерам.
API rate limiter (ограничитель скорости для API) разворачивается как отдельный сервис, взаимодействующий с веб-сервером. Ограничитель скорости запрашивает у веб-сервера, передавать запрос на сервер API или нет. Если предельное количество запросов превышает пороговое значение, то сервер в ответ на запрос пришлёт код состояния http 429.
Читайте также:
- Как освоить алгоритмы?
- Графы: основы теории, алгоритмы поиска
- Алгоритмы поиска, которые должен знать каждый специалист по обработке и анализу данных
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Nataraj Srikantaiah: Understanding Rate Limiting Algorithms
