Блог

Я ищу алгоритм для ограничения скорости входящих запросов на HTTP-сервер REST. Я прошел через «Дырявое ведро» и «Общий алгоритм скорости ячейки: виртуальное планирование»

Согласно моему пониманию, дырявое ведро имеет следующие ограничения:-

1. Если очередь / корзина пуста, и запрос поступает до тика часов (когда мы фактически обрабатываем запрос), тогда запрос должен ждать времени, пока часы не тикают.
2. Пакет переменной длины в сетевом домене

Я просмотрел этот блог, в котором реализован «Общий алгоритм скорости ячейки: виртуальное планирование».

Может ли кто-нибудь объяснить мне следующее:-

1. Как GCRA решает ограничение дырявого ведра, упомянутое в # 1?
2. В моем случае использования, если я установлю тактовый такт на низкий (может проверяться каждые наносекунды), не следует ли устранить проблему с дырявым ведром?

Алгоритм «дырявого ведра» имеет два варианта: счетчик и очередь. Здесь более уместен измерительный, поэтому давайте сосредоточимся на нем.

Идея заключается в том, что ведру назначается скорость капель (либо одинаковая для всех сегментов, либо основанная на некотором уровне). Входящее задание имеет некоторый «объем», связанный с ним. Он может либо поместиться в корзину, либо нет. Если это не так, он отбрасывается. Если он подходит, он передается для обработки (по крайней мере, в версии meter).

Кто отвечает за слив ведра? В упомянутом вами блоге утверждается, что обычно это выполняется фоновым процессом, который циркулирует вокруг ведер и сбрасывает их. В нем упоминается недостаток, заключающийся в том, что если скорость, с которой он может обрабатывать ведра, низкая (в крайнем случае, когда он переходит в автономный режим), задание может быть отброшено не потому, что в ведре недостаточно пустого объема, а потому, что процесс капания просто не обновил его. По сути, это ваш пункт 1; Я не вижу проблемы с вашим пунктом 2 (хотя вы, возможно, читали описание одной из миллиардов версий leaky bucket, которая ограничена равномерными объемами, но ничто из присущего алгоритму не требует этого).

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

Что касается ваших вопросов (которые связаны):

1. Поскольку с GCRA вы не полагаетесь на отдельный процесс для капания, вы не столкнетесь с проблемой, когда он умер или просто не смог идти в ногу. Это приводит к следующему пункту: в частности,

2. Если вы запускаете отдельный процесс с очень высокой частотой, то, пока процесс капания продолжается, все в порядке. Однако при высокой частоте есть вероятность, что процесс капания не будет продолжаться.

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