День 1780. #ЗаметкиНаПолях
Сравниваем Алгоритмы Ограничения Обработки Запросов. Окончание
Начало

3. Дырявое ведро
Представьте себе ведро с отверстием в дне. Ведро наполняется водой (что символизирует поступающие запросы) с разной скоростью, но вода постоянно вытекает из отверстия. Если ведро уже заполнено и добавляется дополнительная вода, она выливается, что означает отказ от дополнительных запросов.

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

Алгоритм может быть реализован с использованием очереди FIFO (First In, First Out). В очереди хранится список запросов, и фиксированное количество запросов извлекается из очереди с постоянной скоростью, а затем обрабатывается.

Например: каждый запрос заполняет одну ячейку в ведре, и одна ячейка извлекается через постоянные промежутки времени. Если размер ведра 100 запросов, а скорость утечки — 5 запросов в секунду, то, если будет поступать более 5 запросов в секунду, ведро заполнится, а входящие запросы будут блокироваться до тех пор, пока не освободится место.

4. Корзина токенов
Аналогичен алгоритму дырявого ведра, но вместо заполнения слотов запросами он потребляет токены из корзины. Каждому клиенту выделяется определённое количество токенов, которые он может использовать. Он может использовать их все сразу или постепенно.

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

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

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

См. также «Промежуточное ПО для ограничений в .NET 7»

Источник: https://www.code4it.dev/architecture-notes/rate-limiting-algorithms/