Каталог статей:

1. Предисловие 2. Введение в алгоритм — метод счетчика 3. Введение в алгоритм — скользящее окно 4. Введение в алгоритм — алгоритм дырявого ведра 5. Введение в алгоритм — алгоритм ведра маркеров

предисловие

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

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

Введение алгоритма

встречный метод

Метод счетчика является самым простым и легко реализуемым в алгоритме ограничения тока. Например, мы оговариваем, что для интерфейса А количество посещений, которые мы можем совершить за одну минуту, не может превышать 100. Тогда мы можем сделать так: в начале мы можем установить счетчик счетчика, и каждый раз, когда приходит запрос, счетчик увеличивается на 1, если значение счетчика больше 100 и интервал между запросом и первым запросом все еще В течение 1 минуты, это означает, что слишком много запросов, если интервал между запросом и первым запросом больше 1 минуты, а значение счетчика все еще находится в пределах текущего предела, то сбросить счетчик. Схематическая диаграмма конкретного алгоритма выглядит следующим образом:

Интервьюер спросил, как интерфейс Spring Boot должен ограничивать ток, и что ответить?

Конкретный псевдокод выглядит следующим образом:

Хотя этот алгоритм прост, у него есть очень фатальная проблема, то есть критическая проблема.Давайте посмотрим на следующий рисунок:

Как мы видим из приведенного выше рисунка, предположим, что есть злоумышленник, который мгновенно отправляет 100 запросов в 0:59, и 100 запросов мгновенно в 1:00, то на самом деле этот пользователь в течение 1 секунды, 200 запросов было отправлено в мгновенное. То, что мы только что оговорили, — это максимум 100 запросов в минуту, то есть максимум 1,7 запроса в секунду Пользователи могут мгновенно превысить наш лимит скорости, отправив пакетные запросы в узле сброса временного окна. Через эту лазейку в алгоритме пользователи могут мгновенно перегрузить наше приложение.

Умные друзья, возможно, заметили, что сейчас проблема в том, что точность нашей статистики слишком низкая. Так как же хорошо справиться с этой проблемой? Другими словами, как уменьшить влияние критических проблем? Мы можем посмотреть на алгоритм скользящего окна ниже.

раздвижное окно

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

Как интерфейс Spring Boot ограничивает ток? Интервьюер спросил, как ответить

На изображении выше весь красный прямоугольник представляет временное окно, которое в нашем случае составляет одну минуту. Затем мы делим временное окно.Например, на рисунке мы делим скользящее окно на 6 сеток, поэтому каждая сетка представляет 10 секунд. Каждые 10 секунд наше временное окно сдвигается на одну позицию вправо. Каждая сетка имеет свой независимый счетчик, например, когда запрос поступает в 0:35 секунды, счетчик, соответствующий 0:30~0:39, будет увеличен на 1.

Так как же скользящее окно решает критическую проблему прямо сейчас? Мы можем посмотреть на картинку выше, 100 запросов, поступающих в 0:59, попадают в серую сетку, а запросы, поступающие в 1:00, попадают в оранжевую сетку. Когда время достигнет 1:00, наше окно сдвинется на одну позицию вправо, тогда общее количество запросов во временном окне составит 200, что превышает лимит в 100, поэтому можно обнаружить, что текущий лимит срабатывает в на этот раз. .

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

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

image.png

алгоритм дырявого ведра

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

image.png

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

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

Алгоритм ведра токенов

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

image.png

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

Конкретная реализация псевдокода выглядит следующим образом:

Как интерфейс Spring Boot ограничивает ток? Интервьюер спросил, как ответить

Реализация RateLimiter

Для кодовой реализации сегмента токенов можно напрямую использовать RateLimiter в пакете Guava.

Как интерфейс Spring Boot ограничивает ток? Интервьюер спросил, как ответить

Связанные варианты

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

критическая проблема

Давайте снова рассмотрим сценарий критической проблемы. В 0:59 секунды, поскольку ведро заполнено 100 токенами, эти 100 запросов могут быть переданы мгновенно. Однако, поскольку токены наполняются с низкой скоростью, в 1:00, количество токенов в ведре не может достигать 100, поэтому в это время невозможно пройти еще 100 запросов. Таким образом, алгоритм ведра токенов может хорошо решить критическую проблему. На приведенном ниже графике сравнивается изменение скорости в критической точке для счетчика (слева) и алгоритма корзины токенов (справа). Мы видим, что, хотя алгоритм ведра токенов допускает всплеск скорости, следующий всплеск не может произойти, пока в ведре не будет достаточно токенов:

Суммировать

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

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

Алгоритм дырявого ведра VS Алгоритм ведра токена

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

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

Если статья была вам полезна, ставьте палец вверх и переходите