Алгоритмы, связанные с ограничителем тока
Как правило, существует пять алгоритмов для текущего ограничителя, а именно: ведро с маркерами, ведро с воронкой, фиксированное окно, скользящий журнал (имеется в виду скользящее окно в широком смысле), скользящее окно (Это относится к алгоритму, который сочетает в себе скользящий журнал + фиксированное окно).
1. Ведро токена
Алгоритм Token Bucket используется для управления объемом данных, отправляемых в сеть в течение определенного периода времени, и для разрешения отправки пакетов данных.
Алгоритм примерно такой:Предположим, что разрешенная частота запросов равнаrраз в секунду, затем каждый1/rSeconds добавит токен в корзину. Максимальный размер ведраb. когда размерnПри поступлении запроса проверяем, достаточно ли количество ведер, если достаточно, чтобы уменьшить количество картn, просьба пройти. Недостаточно вызовет политику отклонения.
Ведро токенов имеет фиксированный размер, предполагая, что каждый запрос также имеет размер, когда запрос должен быть проверен на соответствие определенному пределу, ведро проверяется, чтобы определить, содержит ли оно достаточное количество токенов на данный момент. Если они есть, эти токены удаляются, и запрос проходит. В противном случае будут предприняты другие действия, обычно отказ. Токены в ведре токенов будут восстанавливаться с определенной скоростью, которая является скоростью, разрешенной для запросов (конечно, в зависимости от конфигурации размера она может фактически превышать эту скорость, но по мере использования ведра токенов она будет корректироваться). вернуться к этой скорости восстановления).
Если токены не потребляются или потребляются быстрее, чем производятся, токены будут увеличиваться до тех пор, пока ведро не будет заполнено. Видно, что корзина маркеров допускает некоторую степень разрыва при сохранении общей скорости запросов.
При реализации сегментов токенов в распределенной среде необходимо учитывать следующие проблемы:
- Как именно хранится текущий размер корзины токенов? Следует ли хранить только размер текущего сегмента токенов (например, с помощью пары ключ-значение в redis) или хранить временную метку каждого проходящего запроса (например, с помощью реализации zset в redis размер zset равен максимальный размер ведра) ?
- Кто пополняет ведро токенов для ведра токенов? Для реализаций, в которых хранится размер текущего сегмента токенов, требуется процесс со скоростью
rПродолжайте добавлять к нему токены,Так как же сделать так, чтобы в распределенной среде был только один такой процесс, что делать, если этот процесс завис?? Для этой реализации, которая хранит метку времени поступления каждого переданного запроса,Итак, как контролировать количество запросов на запись, точно не каждую запись,иКак каждый раз судить о количестве оставшихся токенов по текущему запросу и метке времени
2. Дырявое ведро
Запрос контроля ковша воронки должен быть использован по определенной максимальной скорости. Так же, как воронка, количество водного ввода может быть большим или небольшим, но максимальная скорость может достигать определенной суммы. У него не будет маленьких шипов, таких как токен ведро.,
Алгоритм примерно такой:Основная реализация осуществляется через очередь FIFO (First in first out), которая представляет собой ограниченную очередь размеромb, если запрос накапливает очередь, сработает политика отбрасывания. Предположим, что разрешенная частота запросов равнаrраз в секунду, то запросы в этой очереди будут потребляться с этой скоростью.
При реализации дырявых корзин в распределенной среде необходимо учитывать следующие проблемы:
** 1. Как сохранить очередь дырявого ведра? ** В этой очереди должен храниться каждый переданный запрос и соответствующая метка времени потребления, чтобы обеспечить стабильное потребление. В то же время эта очередь предпочтительно является очередью без блокировки, потому что будет распределенное получение блокировки. И этот размер очереди должен быть установлен наb, и каждый раз, когда поступает запрос, он ставится в очередь и одновременно очищается. **2.Как осуществляется потребление? ** То есть запрос хранится в очереди, как его потреблять? Когда приходит запрос, вы можете судить о том, как долго должно быть текущее время выполнения запроса, исходя из запроса в очереди, а затем войти в очередь и выполнить запрос после большой задержки. Его также можно реализовать с помощью очереди, реализованной с собственным временем задержки.
3. Фиксированное окно
Фиксированное временное окно относительно простое, то есть время делится на несколько временных отрезков, и в каждом временном отрезке фиксируется несколько запросов. Эта реализация не очень строгая, но благодаря простоте реализации подходит для некоторых сценариев с менее строгими требованиями.Алгоритм примерно такой:Предположение
nБольше всего обрабатывается за секундыbзапросы, то каждыйnВторой счетчик сбрасывается наb. При поступлении запроса, если значение счетчика достаточное, оно будет вычтено и запрос будет пройден, а если недостаточно, сработает политика отклонения.
Фиксированное временное окно является наиболее легко реализуемым алгоритмом, но есть и существенный недостаток: во многих случаях, особенно если отказ в запросе поставлен в очередь, запрос быстро потребляется в начале временного окна. В следующий раз не занимается никаким запросом, это не желательно. Кроме того, в некоторых пределах фактический расход может вдвое превышать предельный расход. Например, ограничить до 100 запросов в течение 1 секунды. Предполагается, что за 0,99 секунды доступно 100 запросов, а через 1,01 секунды будет 100 запросов.На самом деле за 0,99 секунды до 1,01 секунды имеется 200 запросов.Это не строгий смысл каждую секунду.Обрабатывать 100 запросов. Для достижения строгого ограничения тока запроса существует два алгоритма.
4. Скользящее бревно
Скользящий журнал вычисляется по отметке времени, соответствующей принятому запросу до кэширования, и отметке времени текущего запроса для управления скоростью. Это строго ограничивает скорость запроса. Алгоритм скользящего окна, упомянутый в Интернете, также относится здесь к алгоритму скользящего журнала.Но скользящее окно, которое мы имеем здесь, — это еще один оптимизированный алгоритм, о котором будет сказано позже..
Алгоритм примерно такой:ПредположениеnБольше всего обрабатывается за секундыbзапрос. тогда самый кешbПереданные запросы и соответствующие метки времени, при условии, что этот набор кешаB. Всякий раз, когда приходит запрос, отBудалено вnВсе запросы до секунд, проверьте, заполнена ли коллекция, если нет, передайте запрос и поместите его в коллекцию, если она заполнена, активируйте политику отклонения.
При реализации скользящих журналов в распределенной среде необходимо учитывать следующие вопросы:
- Наш алгоритм на самом деле упростил хранение, но для сценариев с высокой степенью параллелизма может быть много запросов, которые нужно кэшировать (например, если ограничение 100 000 запросов в секунду, должен ли размер этого кеша хранить 100 000 запросов?), как должен ли этот кеш быть реализован?
- В сценариях с высокой степенью параллелизма удалите эту коллекцию.
nЭта операция должна быть очень быстрой для всех запросов до секунд. Если ваша реализация коллекции кеша медленно удаляется в соответствии с меткой времени, вы можете кэшировать немного больше запросов и регулярно очищать и удалять.nВсе запросы старше секунд удаляются вместо каждого входящего запроса. Когда придет запрос, проверьтеbСуществуют ли предыдущие запросы и разница во времени меньшеnСекунды, существует и меньше, чем текущая политика лимита должна быть активирована.
Скользящее окно (фиксированное скольжение окна + журнал)
Ранее в скользящем журнале мы упоминали о проблеме — запросов к кэшированию может быть много. Возможно, в нашей архитектуре невозможно использовать правильный кеш, мы можем уменьшить количество запросов для хранения, раздвигая окна и уменьшая размер коллекции, чтобы уменьшить параллелизм в одной и той же коллекции.
Алгоритм примерно такой:ПредположениеnБольше всего обрабатывается за секундыbзапрос. мы можем поставитьnСекунды делятся на каждый размер какmMs доступный временной интервал, временной интервал - только метка времени последнего запроса кэша, а в пределах предыдущего временного интервала - только одна цифра запрошенной суммы. Это может значительно оптимизировать хранение, небольшое увеличение объема вычислений. Для критического состояния, которое было ранееn/mквант времени, рассчитатьnПроцент прошедшего времени в текущем временном интервале можно рассчитать, когда объем запросов находится в пределах секунд.Предполагая, что он равен 25%, то для расчета берется 75% от объема запросов первого временного интервала в начале.