Разработка ограничителя скорости

Вот мои заметки о разработке ограничителя скорости.

Что такое ограничитель скорости?

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

• Пользователи могут создавать 1 тикет каждые 5 минут.
• Пользователи могут создавать 2 учетные записи в день с одним и тем же IP-адресом.
• Пользователи могут совершать 5 неудачных попыток входа в систему в час с одного и того же IP-адреса в день.

• Ограничитель скорости предотвращает DoS-атаки
• Остановить злоупотребление системой
• Снижает стоимость
• Это предотвращает перегрузку серверов. Также снижает нагрузку на сервер
• Улучшите пользовательский опыт с меньшим трафиком

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

• Существуют различные способы реализации ограничителя скорости. Это; Реализация на стороне клиента, реализация на стороне сервера и альтернативный способ с использованием стороннего шлюза API.
• Как правило, клиентская сторона — ненадежное место для принудительного ограничения скорости.
• Реализация на стороне сервера имеет некоторые внутренние преимущества, поскольку вы можете изменить логику на своей стороне.
• Использование стороннего API-шлюза иногда полезно, потому что для его внедрения требуется время.

1- Ведро с жетонами

• Два основных параметра; Размер ковша и скорость наполнения.
• Размер корзины: максимально допустимое количество токенов.
• Скорость пополнения: количество токенов, помещаемых в ведро с любым интервалом, например каждую секунду.
• Предполагая, что у нас есть ведро, емкость определяется как количество токенов, которое оно может вместить. Всякий раз, когда потребитель хочет получить доступ к конечной точке API, он должен получить токен из корзины. Токен удаляется из корзины, если он доступен, и принимает запрос. Если токен недоступен, сервер отклоняет запрос.
• Через каждый фиксированный интервал нам нужно пополнять запасы.
• Если нам нужно регулировать HTTP-запросы на основе IP-адресов, для каждого IP-адреса требуется ведро.
• Может вызвать состояние гонки в распределенной среде (недостаток)

2- Протекающее ведро

• Когда приходит HTTP-запрос, система проверяет очередь. Если очередь не заполнена, запрос добавляется в очередь. В противном случае запрос блокируется.
• HTTP-запросы извлекаются из очереди и обрабатываются через равные промежутки времени.
• Обработка первого элемента в очереди происходит через регулярные промежутки времени или в порядке поступления (FIFO).

• Разделяет временную шкалу на временные окна фиксированного размера.
• Каждый запрос увеличивает счетчик.
• Временное окно считается от начала единицы времени до конца единицы времени.
• Пространственная сложность: O(1) — Сохранение текущего количества окон. Временная сложность: O(1) — Получение и простая операция атомарного приращения.

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

• у алгоритма фиксированного окна есть проблема, как я писал. Это позволяет большему количеству запросов проходить по краям окна. Скользящее окно журнала решает эту проблему.
• сохраняет время запросов, отсортированное в наборе или таблице (например, Redis)
• Каждую минуту мы ищем старые запросы и отфильтровываем их. Затем рассчитать доступность. Если запрос превысит пороговую скорость, он удерживается, в противном случае он обслуживается.
• Потребляет много памяти.
• Дорого хранить неограниченное количество журналов для каждого запроса.
• Сложность пространства: O (максимальное количество запросов за время окна) — сохраняет все временные метки запросов во временном окне.
• Сложность времени: O (максимальное количество запросов за время окна) — удаление подмножества временных меток.

1. Подсчитайте общее количество элементов в отсортированном наборе. Отклонить запрос, если это значение больше, чем наш предел регулирования «3».
2. Вставьте текущее время в отсортированный набор и примите запрос.

• сочетает в себе низкую стоимость обработки алгоритма фиксированного окна и улучшенные граничные условия скользящего журнала.
• Сложность пространства: O (количество ведер)
• Сложность по времени: O(1) — извлекает последний сегмент, увеличивает и проверяет общую сумму сегментов (может храниться в переменной totalCount).
• Подробности реализации вы можете прочитать в этой статье.
• Еще одна статья для лучшего понимания.

1. Удалите все счетчики старше 1 минуты.
2. увеличить счетчик, если запрос поступает в текущем сегменте.
3. Заблокированный запрос, если текущее ведро уже превысило лимит горла.

использованная литература

• https://www.quinbay.com/blog/rate-limiter-implementation-token-bucket-algorithm
• https://betterprogramming.pub/4-rate-limit-algorithms-every-developer-should-know-7472cb482f48
• https://codeminion.hashnode.dev/rate-limiting-algorithms
• https://goalgorithm.wordpress.com/2019/06/08/designing-an-api-rate-limiter/