Ограничение трафика может быть реализовано с помощью разных алгоритмов, у каждого из которых есть определенные преимущества и недостатки. - алгоритм маркерной корзины (token bucket); - алгоритм дырявого ведра (leaking bucket); - счетчик фиксированных интервалов (fixed window counter); - журнал скользящих интервалов (sliding window log); - счетчик скользящих интервалов (sliding window counter). ## Алгоритм маркерной корзины Алгоритм маркерной корзины работает следующим образом. * Маркерная корзина — это контейнер с заранее определенной емкостью. В нее регулярно помещают маркеры. Когда она окончательно заполняется, маркеры больше не добавляются. Когда корзина заполняется, последующие маркеры отбрасываются. * Каждый запрос потребляет один маркер. При поступлении запроса мы проверяем, достаточно ли маркеров в корзине. * если маркеров достаточно, мы удаляем по одному из них для каждого запроса, и запрос проходит дальше; * если маркеров недостаточно, запрос отклоняется. ## Алгоритм дырявого ведра Обычно его реализуют с использованием очереди типа FIFO. Этот алгоритм работает так: - при поступлении запроса система проверяет, заполнена ли очередь. Запрос добавляется в очередь при наличии места; - в противном случае запрос отклоняется; - запросы извлекаются из очереди и обрабатываются через равные промежутки времени. Алгоритм дырявого ведра принимает два параметра: 1. размер ведра: равен размеру очереди; очередь хранит запросы, которые обрабатываются с постоянной скоростью; 2. скорость утечки: определяет, сколько запросов можно обработать за определенный промежуток времени (обычно за 1 секунду). ## Счетчик фиксированных интервалов Счетчик фиксированных интервалов работает так. - Алгоритм делит заданный период времени на одинаковые интервалы и назначает каждому из них счетчик. - Каждый запрос инкрементирует счетчик на 1. - Как только счетчик достигнет заранее заданного лимита, новые запросы начинают отклоняться, пока не начнется следующий интервал. ## Журнал скользящих интервалов Как уже упоминалось ранее, у счетчика фиксированных интервалов есть серьезная проблема: на границах интервала может быть принято больше запросов. С этим помогает справиться журнал скользящих интервалов. Вот как он работает. - Алгоритм следит за временными метками запросов. Временные метки обычно хранятся в кэше, например, в упорядоченных множествах Redis. - Когда поступает новый запрос, все просроченные запросы отбрасываются. - Просроченными считают запросы раньше начала текущего временного интервала. - Временные метки новых запросов заносятся в журнал. - Если количество записей в журнале не превышает допустимое, запрос принимается, а если нет — отклоняется. ## Счетчик скользящих интервалов Счетчик скользящих интервалов — это гибридный подход, сочетающий в себе два предыдущих алгоритма. Предположим, ограничитель трафика допускает не больше 7 запросов в минуту. У нас 5 запросов за предыдущий интервал и 3 в текущем. На отметке в 30 % от текущего интервала количество запросов на скользящем интервале вычисляется по следующей формуле: * запросы на текущем интервале + запросы на предыдущем интервале * процент предыдущего интервала, который занимает скользящий интервал; * используя эту формулу, мы получаем 3 + 5 * 0,7% = 6,5 запроса. В зависимости от ситуации это число можно округлить к большему или меньшему значению. В нашем примере оно округляется до 6. Так как ограничитель трафика допускает не больше 7 запросов в минуту, текущий запрос может быть принят. Но после получения еще одного запроса лимит будет исчерпан.