Основные особенности

Levee — распределенная система ограничения потока запросов (rate limiting). Характеристики системы:

• линейное масштабирование при росте нагрузки;
• поддержка большого количества уникальных ключей;
• работа при неравномерной нагрузке;
• конфигурирование лимитов без перезапуска;
• отказоустойчивость;
• обслуживание компонентов без остановки системы.

Levee входит в дистрибутив, но не устанавливается по умолчанию.

Levee ограничивает интенсивность потока запросов к уникальному ресурсу. Применяется для:

• ограничения использования ресурсов;
• фильтрации всплесков нагрузки;
• сглаживания потока запросов;
• обеспечения стабильного режима работы систем.

Levee состоит из трех компонентов:

• limiter,
• observer,
• client-proxy.

Каждый компонент — отдельный статически скомпонованный исполняемый файл.

Компонент limiter:

• отслеживает топологию кластера Levee;
• принимает решение о доступе к ресурсу;
• реализует алгоритм лимитирования;
• хранит в памяти информацию о запрашиваемых ресурсах;
• отслеживает квоты и размер группы limiter (distribution factor);
• участвует в gossip-оверлее.

Компонент observer:

• отслеживает топологию кластера Levee;
• предоставляет доступ к ней подключенным клиентам в реальном времени;
• выполняет обнаружение изменений и распространение информации по кластеру через gossip-оверлей;
• предоставляет клиентский gRPC-интерфейс;
• служит бутстреп-нодой для gossip-оверлея.

Компонент client-proxy:

• разделяет поток входящих запросов и перенаправляет их на экземпляры компонента limiter, сохраняя гарантии лимитирования для каждого ресурса;
• отслеживает топологию кластера через компонент observer;
• отслеживает информацию о компоненте observer и размере группы limiter;
• хранит в памяти информацию о запрашиваемых ресурсах.

Levee поддерживает два варианта развертывания:

• Standalone limiter,
• кластер с client-proxy.

Состоит из единственного компонента limiter.

Компонент limiter, к которому приложения обращаются напрямую по HTTP, подходит для нагрузки до 50–60 тысяч запросов в секунду.

Для отказоустойчивости standby-экземпляры резервируют компонент limiter через разные протоколы, например VRRP (Virtual Router Redundancy Protocol).

Компоненты:

• limiter,
• observer,
• client-proxy.

Кластерное решение с горизонтальным масштабированием, отказоустойчивостью и обслуживанием компонентов без остановки. Клиентские приложения обращаются по HTTP к вспомогательному компоненту client-proxy, который маршрутизирует запросы на экземпляры компонента limiter.

HTTP-интерфейсы limiter и client-proxy одинаковы.

Интерфейс взаимодействия с Levee:

attempt(resource: str, prefix: Optional[str], method: Optional[str]) -> accepted|rejected|failed

Здесь:

• resource — уникальный ключ ресурса;
• prefix — путь внутри ресурса (опционально);
• method — зависимый подресурс (подключ) в рамках ресурса и префикса (опционально).

Клиенты взаимодействуют с Levee через HTTP-запросы. Поддерживаются HTTP/1.1 и HTTP/2 без шифрования. Клиент передает данные запроса в заголовках, ответ — HTTP-код. Тело ответа пустое, кроме случаев возврата ошибок. Эндпоинт /attempt принимает POST-запросы как на limiter, так и на client-proxy.

Квоты ресурсов, префиксов и методов хранятся в etcd и собираются в единый путь: <РЕСУРС>/<ПРЕФИКС>/<МЕТОД>: TimeQuota, где TimeQuota — конкретный лимит (подробнее — в разделе Квоты).

Здесь:

• <РЕСУРС> — идентификатор ресурса;
• <ПРЕФИКС> — путь внутри ресурса (опционально);
• <МЕТОД> — HTTP-метод запроса.

При обработке запроса limiter определяет применимую квоту в следующем порядке:

1. Ищет квоту по полному ключу <РЕСУРС>/<ПРЕФИКС>/<МЕТОД>.
2. Если не найдена — ищет стандартную квоту метода по ключу <РЕСУРС>/<МЕТОД>.
3. Если не найдена — использует общую квоту ресурса по ключу <РЕСУРС>.

Заголовки запроса:

• X-Resource — ключ ресурса;
• X-Prefix — путь внутри ресурса (опционально);
• X-Method — подресурс ресурса, зависимый ключ (опционально);
• X-Req-Id — идентификатор запроса для трассировки.

Примеры запросов в Levee:

 
# HTTP/1.1curl -v --request POST http://<ХОСТ>:<ПОРТ>/attempt \    -H 'X-Resource: <РЕСУРС>' \    -H 'X-Prefix: <ПРЕФИКС>' \    -H 'X-Method: <МЕТОД>' \    -H 'X-Req-Id: <ID_ТРАССИРОВКИ>'

 
# HTTP/2curl -v --http2-prior-knowledge --request POST http://<ХОСТ>:<ПОРТ>/attempt \    -H 'X-Resource: <РЕСУРС>' \    -H 'X-Prefix: <ПРЕФИКС>' \    -H 'X-Method: <МЕТОД>' \    -H 'X-Req-Id: <ID_ТРАССИРОВКИ>'

Здесь:

• <ХОСТ> — хост компонента limiter или client-proxy;
• <ПОРТ> — порт для приема входящих запросов;
• <РЕСУРС> — ключ ресурса;
• <ПРЕФИКС> — путь внутри ресурса;
• <МЕТОД> — подресурс ресурса;
• <ID_ТРАССИРОВКИ> — трассировочный идентификатор запроса.

Решение о доступе возвращается в виде значения HTTP-кода:

• 200 — accepted, доступ разрешен;
• 429 — rejected, доступ запрещен;
• 500 — failed, внутренняя ошибка.

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

Лимиты задаются квотой — парой (rate, burst) (подробнее — в разделе Принцип лимитирования):

• rate — максимальная интенсивность, запросов в секунду;
• burst — допустимая пульсация, запросов.

Формулы расчета:

$$rate = \text{RPS} \times 1{,}1$$ $$burst = \frac{rate}{\text{DF}} \times 0{,}1$$

Здесь:

• RPS — желаемое пользователем количество запросов в секунду (Requests Per Second);
• DF — размер группы limiter.

Пример: rate = 1000, DF = 4 →

$$burst = \frac{1000}{4} \times 0{,}1 = 25$$

Пример: требуется 6000 RPS → rate ≥ 6600, при DF = 4 →

$$burst = \frac{6600}{4} \times 0{,}1 = 165$$

Квоты для ключей и подключей хранятся в поддереве /<КОРНЕВОЙ_ПРЕФИКС>/limit. Значение каждого ключа — квота в виде JSON-объекта, сериализованного в строку.

Значения по умолчанию:

• default key limit: /<КОРНЕВОЙ_ПРЕФИКС>/limit/key_default — {"rate": rps, "burst": reqs};
• default sublimit: /<КОРНЕВОЙ_ПРЕФИКС>/limit/subkey_default/<ПОДКЛЮЧ> — {"rate": rps, "burst": reqs}.

Значения для конкретных ключей и подключей:

• limit for the key: /<КОРНЕВОЙ_ПРЕФИКС>/limit/key/<КЛЮЧ>/quota — {"rate": rps, "burst": reqs};
• sublimit for the key: /<КОРНЕВОЙ_ПРЕФИКС>/limit/key/<КЛЮЧ>/sublimit/<ПОДКЛЮЧ> — {"rate": rps, "burst": reqs}.

Здесь:

• <КОРНЕВОЙ_ПРЕФИКС> — корневой префикс дерева конфигураций в etcd;
• <ПОДКЛЮЧ> — идентификатор зависимого ресурса (подключа) внутри ключа;
• <КЛЮЧ> — идентификатор ресурса.

В кластерном режиме запросы распределяются между несколькими экземплярами limiter. Количество экземпляров limiter, обрабатывающих запросы по одному ключу, определяется размером группы limiter. Размер группы задается в поддереве /<КОРНЕВОЙ_ПРЕФИКС>/factor:

• default factor: /<КОРНЕВОЙ_ПРЕФИКС>/factor/default — uint;
• key-specific factor: /<КОРНЕВОЙ_ПРЕФИКС>/factor/key/<КЛЮЧ> — uint.

Здесь:

• <КОРНЕВОЙ_ПРЕФИКС> — корневой префикс дерева конфигураций в etcd;
• <КЛЮЧ> — идентификатор ресурса.

limiter нормализует квоты из etcd в соответствии с размером группы limiter.

Компонент observer служит бутстреп-нодой для новых участников кластера. Информация о каждом observer хранится в поддереве /<КОРНЕВОЙ_ПРЕФИКС>/observer и содержит уникальное имя и адреса.

Адреса — JSON-объект с полями:

• gossip — gossip-адрес в формате ip:port;
• service — адрес клиентского интерфейса в формате ip:port.

Пример:

 
/<КОРНЕВОЙ_ПРЕФИКС>/observer/<ИМЯ> => {"gossip": "1.2.3.4:7373", "service": "1.2.3.4:5454"}

Здесь:

• <КОРНЕВОЙ_ПРЕФИКС> — корневой префикс дерева конфигураций в etcd;
• <ИМЯ> — уникальное имя экземпляра observer.

Каждый компонент Levee при запуске принимает путь к YAML-файлу через опцию --config. Параметры можно задать в файле, переопределить переменными окружения или опциями командной строки.

Общие для всех компонентов:

• instance-id — уникальный идентификатор экземпляра.
• storage-prefix — префикс дерева конфигураций в etcd.
• storage-addrs — список адресов узлов etcd.
• graphite-addr — адрес graphite-коллектора метрик в формате ip:port. Транспорт — /udp или /tcp. Пустой адрес отключает отправку метрик.
• verbose — подробное логирование.

Параметры limiter:

• listen-addr — адрес приема входящих запросов (ip:port).
• gossip-addr — адрес в gossip-кластере (ip:port).
• standalone — автономный режим (без кластера).
• gc-max-keys — порог уникальных ключей для запуска сборки мусора. По умолчанию отключена.
• gc-collect — интервал отслеживания активности ключей при сборке мусора (s, m или h).
• gc-period — период запуска сборщика неактивных ключей (s, m или h).

Пример:

 
instance-id: limiter1storage-prefix: /leveestorage-addrs:  - "http://127.0.0.1:2379"listen-addr: "0.0.0.0:5454"gossip-addr: "1.2.3.4:7373"graphite-addr: "127.0.0.1:2003/udp"gc-max-keys: 10000gc-period: 1hgc-collect: 15sstandalone: falseverbose: false

Параметр observer-name — уникальное имя.

Пример:

 
instance-id: observer1observer-name: obs-1storage-prefix: /leveestorage-addrs:  - "http://127.0.0.1:2379"  - "http://127.0.0.2:2379"  - "http://127.0.0.3:2379"graphite-addr: "127.0.0.1:2003/tcp"verbose: true

Параметры client-proxy:

• listen-addr — адрес приема входящих запросов (ip:port).
• gc-max-keys — порог уникальных ключей для запуска сборки мусора. По умолчанию отключена.
• gc-period — период запуска сборщика ключей (s, m или h).

Пример:

 
instance-id: client1storage-prefix: /leveestorage-addrs:  - "http://127.0.0.1:2379"listen-addr: "0.0.0.0:5454"graphite-addr: "127.0.0.1:2003"gc-max-keys: 500gc-period: 30mverbose: false

Компоненты limiter или observer можно остановить и запустить без влияния на кластер — если сохраняется достаточное количество активных экземпляров. Компоненты обрабатывают SIGINT или SIGTERM, выполняют корректное завершение и уведомляют участников кластера об отключении. client-proxy переводит трафик на другие экземпляры, затем компоненты завершают активные задачи, и процесс останавливается.

Минимальное количество экземпляров в кластере:

• limiter — не меньше максимального значения размера группы limiter;
• observer — не меньше одного экземпляра.

Отказы обнаруживаются участниками кластера на уровне gossip-оверлея. Время сходимости (от подозрения узла до отметки его неактивным всеми участниками) зависит от размера кластера. На кластерах из 10–15 узлов — около 5 секунд.

• Отказ limiter: client-proxy пересчитывают маршрутизацию (по данным от observer) и переводят трафик на другой экземпляр. Возможно кратковременное превышение трафика на величину, вычисляемую по формуле:

  $\frac{\text{burst}}{\text{DF}}$

  Здесь:

  • burst — допустимая пульсация, запросов;
  • DF — размер группы limiter.

• Отказ observer: подключенный к нему client-proxy переподключается к другому observer. Клиентские запросы обрабатываются без прерывания. При успешном переподключении client-proxy синхронизирует представление топологии кластера и продолжает работу. При неудаче — завершается с ошибкой.

Чтобы добавить limiter, запустите новый экземпляр с локальной конфигурацией (подробнее — в разделе Конфигурация компонентов). Процесс подключится к кластеру, client-proxy начнут маршрутизировать на него трафик.

Чтобы добавить observer:

1. Задайте уникальное имя экземпляра.
2. Добавьте в etcd информацию о нем — адреса service и gossip (подробнее — в разделе Конфигурация observer).
3. Запустите процесс observer с новым именем.

Через 5 секунд новый процесс стабилизирует представление топологии кластера и начнет принимать запросы.

Чтобы остановить экземпляр limiter или observer, отправьте процессу SIGINT или SIGTERM.

Алгоритм лимитирования в Levee — вариант Leaky Bucket под названием Generic Cell Rate Algorithm (GCRA). Алгоритм согласовывает входящий поток с параметрами rate (интенсивность) и burst (пульсация).

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

Описание алгоритма — в рекомендации I.371-200403 (virtual scheduling algorithm).

Levee масштабируется линейно за счет распределения запросов по всем доступным limiter. При неравномерной нагрузке один ресурс может обрабатываться несколькими узлами — это требует синхронизации между ними в реальном времени. Возникает компромисс: точность лимитирования против задержки (consistency или availability).

Решение: исходный поток представляется суммой подпотоков равной интенсивности, каждый обрабатывается отдельным узлом независимо. Квоты уменьшаются пропорционально количеству подпотоков. Синхронизация между limiter не требуется.

Корректность подхода подтверждается на модели стационарного пуассоновского потока. Разделение потока интенсивностью µ на k подпотоков выполняется просеиванием: из исходного потока выбирается каждая k-я заявка. Полученный процесс — эрланговский k-го порядка с уменьшенной дисперсией интервалов и интенсивностью v, вычисляемой по формуле:

$v = \frac{\mu}{k}$

Здесь:

• µ — интенсивность потока;
• k — количество подпотоков.

Каждый подпоток после GCRA имеет интенсивность, значение которой вычисляется по формуле:

$\min\left(\frac{\text{limit}}{k}, v\right)$

Здесь:

• v — интенсивность подпотока;
• k — количество подпотоков.

Суммарная интенсивность k подпотоков не превышает limit (без учета пульсации).

Просеивание потоков выполняет client-proxy через round-robin маршрутизацию на группу limiter. Размер группы limiter определяет, сколько экземпляров limiter обрабатывает один ключ. Выбор узлов в группе зависит от ключа ресурса и определяется алгоритмом HRW (Rendezvous Hashing). Это обеспечивает равномерную загрузку узлов и отказоустойчивость кластера.

limiter и observer используют для внутренней коммуникации оверлейную сеть на базе gossip.

Gossip распространяет информацию в одноранговой сети: агенты обмениваются сообщениями со случайно выбранными соседями. Свойства gossip:

• надежная коммуникация;

• простая реализация;

• простое подключение и отключение узлов;

• стабильность при меняющейся топологии;

• нагрузка на узел не зависит от размера оверлея;

• трафик и время распространения растут не быстрее значения, вычисляемого по формуле:

  $O(\log N)$

  Здесь N — количество узлов в оверлее.

Gossip-модуль в компонентах Levee выполняет функции:

• topology discovery — обнаружение подключений и отключений узлов;
• failure detection — обнаружение отказов узлов;
• event dissemination — распространение событий в реальном времени.

В Levee используется реализация gossip на базе протокола SWIM (Scalable Weakly-consistent Infection-style Process Group Membership Protocol).

Компоненты Levee собирают метрики через клиентскую библиотеку Prometheus. Метрики накапливаются в памяти процесса и забираются внешним сборщиком (pull-модель).

В инфраструктуре без поддержки Prometheus используется Graphite (push-модель). Для совместимости каждый компонент содержит Graphite Bridge — модуль, который опрашивает коллектор Prometheus, преобразует имена метрик в формат Graphite, метки — в теги и отправляет метрики по TCP или UDP в сборщик Graphite (подробнее — в разделе Конфигурация компонентов).

Для перехода на Prometheus отключите Graphite Bridge и задайте локальный эндпоинт HTTP для сбора метрик (подробнее — в разделе Метрики).