Что такое ограничение скорости и как его правильно использовать

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

Есть много разных причин, по которым мы иногда хотим блокировать запросы. Назвать несколько:

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

Независимо от причин, в этом посте мы рассмотрим, как мы можем реализовать ограничение скорости, чтобы предотвратить возникновение этих нежелательных сценариев.

Мы рассмотрим три темы:

  1. Что мы используем для идентификации клиентов;
  2. Некоторые известные алгоритмы ограничения скорости;
  3. Масштабирование с более чем одним сервером приложений.

Цель ограничения скорости

Прежде чем даже говорить об алгоритмах ограничения скорости, мы должны знать, как идентифицировать пользователей — для кого мы устанавливаем ограничения скорости?

Ограничение скорости на основе IP-адреса

IP-адрес — это числовая метка, которую мы используем для идентификации устройства в Интернете. Для нас кажется естественным установить лимит на IP-адреса.

Вопрос — можно ли подменить IP-адрес? Ну, это так, но это нетривиально.

Чтобы клиент и сервер установили соединение, клиент и сервер должны пройти процесс трехэтапного рукопожатия:

  1. Клиент отправляет пакет SYN на сервер, чтобы установить соединение.
  2. Сервер отправляет пакет SYN-ACK обратно клиенту, чтобы подтвердить, что он готов установить соединение.
  3. Клиент получает пакет и отправляет обратно еще один ACK для запуска соединения.

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

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

Для других законных случаев использования, почему мы не всегда выполняем ограничение скорости на основе IP-адреса?

Другое ограничение IP-адресов заключается в том, что они не уникальны. У нас есть известная проблема исчерпания IPv4-адреса. Несколько пользователей могут использовать один и тот же IP-адрес. Пользователи одного и того же интернет-провайдера (интернет-провайдера) могут использовать один и тот же общедоступный IP-адрес. То же самое может произойти, если пользователи используют VPN. Наконец, для мобильных пользователей поставщики мобильных услуг также имеют ограниченный список известных IP-адресов.

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

Ограничение скорости на основе идентификатора пользователя

Помимо IP-адреса, мы также можем рассмотреть ограничение скорости на основе идентификатора пользователя.

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

Ограничение скорости на основе ключа API

Для критически важных услуг мы можем назначить ключ API каждому клиенту. Также принято назначать разную скорость доступа к каждому ключу API, например, 300 запросов в день.

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

Алгоритмы ограничения скорости

В этом разделе мы обсудим несколько часто используемых алгоритмов ограничения скорости, их различия и компромиссы:

  • Фиксированный оконный счетчик
  • Скользящие журналы
  • Счетчик раздвижных окон
  • Сегменты токенов

Фиксированный оконный счетчик

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

Вот пример 5 запросов за 5 секунд. Каждое поле представляет запрос клиента. Зеленое поле означает, что это разрешено, а красное поле означает, что оно заблокировано. В момент времени 5 мы сбрасываем счетчик на 0, поскольку он входит в новое временное окно.

Скользящие журналы

Нетрудно заметить, что приведенный выше алгоритм счетчика фиксированных окон не очень точен. Есть два очевидных недостатка:

  • Для клиента со стабильно высоким объемом запросов. Запросы, скорее всего, разрешены ближе к началу окна; заблокирован в конце окна.
  • Для клиента с резким трафиком у нас может быть ситуация, когда мы получаем большое количество за короткий период. Например, если клиент делает 5 запросов в конце окна и делает 5 запросов в начале следующего окна, сервер может получить 10 запросов (2x) в течение короткого периода времени.

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

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

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

Например, предположив, что у нас есть 1 миллион клиентов, мы хотим разрешить каждому клиенту 1 тысячу запросов в день. Без учета накладных расходов на хеш-карту память, необходимая для отслеживания этих запросов, составляет:

1 million * 1 thousand * 4 bytes = 4 gigabytes.

Счетчик раздвижных окон

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

Продолжите пример из предыдущего раздела. Мы можем разделить окно (один день) на 24 меньших окна, каждое из которых соответствует часу. Теперь вместо того, чтобы отслеживать 1 тысячу меток времени для каждого клиента, нам нужно отслеживать только 24 счетчика.

Чтобы проверить, должны ли мы разрешить новый запрос, нам нужно просуммировать все 24 счетчика и посмотреть, меньше ли сумма 1 тысячи (лимит).

Ведро жетонов

Алгоритм Token Bucket аналогичен приведенному выше алгоритму счетчика фиксированного окна в том смысле, что счетчик фиксированного окна ведет счет вверх, тогда как счетчик Token Bucket ведет обратный отсчет.

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

Вот пример ведра, которое пополняется двумя жетонами каждые 2 секунды. Размер сегмента равен 5. Интересно, что эффективная скорость этой конфигурации такая же, как и у двух других анимаций выше для фиксированного счетчика окон и скользящего журнала. Все они со скоростью 1 QPS (запросов в секунду).

До сих пор ведро никогда не было полным (с 5 жетонами). Это потому, что у нас стабильно высокие показатели запросов. Представьте, что если сервер на какое-то время перестанет получать запросы, корзина со временем переполнится. Размер ведра по существу определяет, насколько скачкообразным мы позволяем быть трафику.

В целом алгоритм Token Buckets более гибкий. У него также нет определенного окна, и поэтому он может лучше распределять всплески запросов от нескольких клиентов.

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

Алгоритм Token Buckets широко используется в отрасли. Например, DynamoDB использует блок токенов для ограничения скорости чтения (RCU).

Состояния хранения

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

Хранить состояния в сервере приложений

Часто у нас есть балансировщик нагрузки перед серверами приложений. Существуют различные подходы к балансировке нагрузки. Для целей этой статьи мы обсудим два:

  • По-круговой
  • Закрепленная сессия

Дополнительные сведения о прикрепленных разделах хорошо описаны в следующей документации AWS: Прикрепленные сеансы для вашего балансировщика нагрузки приложений. Дополнительную информацию о циклическом переборе и различных вариантах можно найти в книге Google — Site Reliability Engineering Глава 20: Балансировка нагрузки в центре обработки данных.

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

Один из подходов к Round Robin состоит в том, чтобы разделить лимит на количество серверов. Например, если мы хотим ограничить скорость клиента до 1000 запросов в секунду и у нас есть 10 серверов, каждый сервер может независимо ограничить скорость клиента до 100 запросов в секунду. Теперь это не даст нам детерминированных результатов, поскольку запрос может быть заблокирован одним сервером и принят другим сервером. Однако это очень хорошее приближение, и мы можем сохранить простоту реализации.

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

С Sticky Session это проще. Мы можем продолжать хранить счетчики на сервере приложений, поскольку в идеале каждый сервер обрабатывает запросы от подмножества клиентов.

Сохранить состояния во внешнем хранилище данных

Вместо того, чтобы хранить данные на сервере приложений, мы могли бы также хранить информацию в отдельном хранилище данных, таком как Redis. В этом есть несколько преимуществ:

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

Однако использование внешнего хранилища также сопряжено с компромиссами.

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

Выводы

В этом посте мы обсудили различные аспекты ограничения скорости.

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

Затем мы обсудили 4 алгоритма ограничения скорости, от простейшего счетчика фиксированных окон до более сложных сегментов токенов. Для полноты важно также указать на другой алгоритм, который здесь не рассматривается, — алгоритм дырявого ведра. Он похож на Token Bucket. Для тех, кто хочет узнать больше, Википедия подробно объяснит.

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

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

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

Что дальше

Хотите больше поиграть с различными типами алгоритмов ограничения скорости? Исходный код симуляции выше опубликован на GitHub. Не стесняйтесь изменять конфигурации и играть с ними больше.

Это все на сегодня. Спасибо за чтение и надеюсь, что это поможет!