Этот документ объясняет внутреннее устройство распределённого rate limiter'а в YDB — от публичного gRPC API до алгоритма раздачи квоты внутри таблетки Kesus. Все ссылки ведут на исходный код в этом репозитории.
- Общая идея
- Архитектура: три уровня
- Координационный узел = таблетка Kesus
- Иерархическое дерево ресурсов
- Алгоритм HDRR: как таблетка раздаёт квоту
- Клиентская сторона: TQuoterService и TKesusQuoterProxy
- Протокол между proxy и Kesus
- Локальный bucket и prefetch
- Публичный API: AcquireResource и семантика required/used
- Отказоустойчивость
- Учёт потребления и биллинг (metering)
- Пример использования через SDK
- Карта исходного кода
Задача: ограничить суммарную скорость потребления некоторого ресурса (запросов в секунду, request units, байт и т.п.) во всём кластере, а не на одном узле. Наивное решение — ходить за каждой «единицей» квоты в центральную точку — не масштабируется: каждая операция превращалась бы в сетевой round-trip.
YDB решает это так:
- Центральная точка учёта — координационный узел (таблетка Kesus), который хранит описание ресурсов и их лимиты (
max_units_per_secondи т.д.). - Локальные кэши квоты — на каждом узле кластера живёт сервис-квотер, который заранее (prefetch) запрашивает у Kesus «пачку» квоты в локальное ведро (bucket) и раздаёт её локальным потребителям без сетевых обращений.
- Kesus периодически (каждые 100 мс) пополняет ведра активных подписчиков, честно (round-robin) деля скорость ресурса между всеми узлами, которые сейчас потребляют.
То есть точность лимита глобальная, а latency получения квоты в нормальном режиме — локальная (наносекунды, обращение к актору на том же узле).
flowchart TB
subgraph node1 ["Узел кластера №1"]
APP1["Потребитель<br/>(gRPC AcquireResource, YMQ/SQS,<br/>внутренние сервисы)"]
QS1["TQuoterService<br/>(один актор на узел,<br/>ydb/core/quoter)"]
PROXY1["TKesusQuoterProxy<br/>(один актор на каждый<br/>координационный узел)"]
BUCKET1[("Локальный bucket<br/>ресурса")]
APP1 -- "TEvQuota::TEvRequest" --> QS1
QS1 -- "TEvClearance" --> APP1
QS1 <--> PROXY1
PROXY1 --- BUCKET1
end
subgraph node2 ["Узел кластера №2"]
APP2["Потребитель"]
QS2["TQuoterService"]
PROXY2["TKesusQuoterProxy"]
APP2 --> QS2
QS2 <--> PROXY2
end
subgraph kesus ["Таблетка Kesus (координационный узел)"]
TREE["TQuoterResourceTree<br/>иерархия ресурсов + HDRR"]
DB[("Локальная БД таблетки:<br/>таблица QuoterResources")]
TREE --- DB
end
PROXY1 <-- "TabletPipe:<br/>Subscribe / UpdateConsumptionState /<br/>ResourcesAllocated" --> TREE
PROXY2 <-- "TabletPipe" --> TREE
SS["SchemeShard<br/>(путь типа EPathTypeKesus)"] -.->|"резолв пути → TabletId<br/>через SchemeCache"| QS1
Три уровня:
| Уровень | Кто | Что делает |
|---|---|---|
| Сервер квоты | Таблетка Kesus (ydb/core/kesus/tablet/) | Хранит дерево ресурсов, считает и раздаёт квоту по алгоритму HDRR |
| Локальный квотер | TQuoterService (ydb/core/quoter/) |
Один актор на узел; принимает запросы потребителей, держит очереди, раздаёт квоту из локального ведра |
| Прокси к Kesus | TKesusQuoterProxy (kesus_quoter_proxy.cpp) |
Один актор на каждый используемый координационный узел; держит pipe к таблетке, подписки и локальные ведра |
«Координационный узел» (coordination node) — это публичное имя сущности; внутри это таблетка Kesus — реплицируемая state machine на базе tablet_flat:
- Класс таблетки:
TKesusTablet— tablet_impl.h:25. - В схеме SchemeShard путь имеет тип
EPathTypeKesus— schemeshard__operation_create_kesus.cpp:35. - Одна таблетка обслуживает две независимые функции: семафоры/сессии (distributed locks) и квотер (rate limiter). Этот документ — про вторую.
Что персистится в локальной БД таблетки (схема — schema.h):
- Таблица
QuoterResources(Id, ParentId, Props) — описания ресурсов и их настройки. При рестарте таблетки дерево восстанавливается из этой таблицы (tx_init.cpp:210-235). - Не персистится: текущее наполнение вёдер, активные подписки клиентов, история потребления. После рестарта таблетки клиенты просто переподписываются, и раздача начинается заново — кратковременная неточность лимита считается допустимой ценой за простоту и скорость.
Ресурсы внутри одного координационного узла образуют лес деревьев. Путь ресурса — строка с разделителем /, без ведущего слеша; первый элемент — корневой ресурс:
graph TD
ROOT["root<br/>max_units_per_second = 1000"]
A["root/write<br/>(наследует лимит)"]
B["root/read<br/>max_units_per_second = 200"]
A1["root/write/user1"]
A2["root/write/user2"]
ROOT --> A
ROOT --> B
A --> A1
A --> A2
style ROOT fill:#e8f0fe,stroke:#4285f4
style B fill:#fef7e0,stroke:#f9ab00
Правила (код: quoter_resource_tree.cpp, валидация и наследование — CalcParameters(), строки ~713–739):
- Корневой ресурс обязан иметь
max_units_per_second(kesus.proto:329-330). - Дочерний ресурс наследует
max_units_per_second,prefetch_coefficient,prefetch_watermarkот родителя, если не задал свои. - Лимит ребёнка не может превысить лимит родителя по факту раздачи: квота «протекает» сверху вниз, и родитель не отдаст детям больше своей скорости. Это позволяет строить схемы вида «суммарно 1000 RPS на всех, но не более 200 RPS на чтение».
- Потребители подписываются на листовые (вообще говоря — любые) ресурсы по полному пути, например
root/write/user1.
Хранение в памяти таблетки: TQuoterResources с индексами ResourcesById / ResourcesByPath (quoter_resource_tree.h:369-444).
HDRR = Hierarchical Deficit Round Robin. Единственная поддерживаемая на сегодня алгоритмическая схема (в proto она называется HierarchicalDrrSettings).
Ключевые механики (всё в quoter_resource_tree.cpp):
-
Тики. Время нарезано на тики по 100 мс:
TICKS_PER_SECOND = 10.0(quoter_resource_tree.cpp:32). Каждый ресурс на каждом тике получает квант:ResourceTickQuantum = MaxUnitsPerSecond / 10(строка 737). -
Round Robin по активным детям. Ресурс делит свой квант поровну между активными детьми (и активными сессиями клиентов) по кольцевому списку
TRoundRobinListItem(строки 106–136). «Deficit» означает: если ребёнку нужно меньше его доли — остаток возвращается в общий котёл и достаётся другим на этом же тике. -
Сессии. Подписка клиента (пары
{ActorId клиента, ResourceId}) — этоTHierarchicalDRRQuoterSession(строки 303–385). Сессия:- активна, пока клиент заявил потребление и его ведро не заполнено (
Activate(), строка 338); - деактивируется, когда запрошенное выдано и ведро полное (
Deactivate(), строка 352). Неактивные сессии не участвуют в round robin и не тратят CPU таблетки.
- активна, пока клиент заявил потребление и его ведро не заполнено (
-
Очередь тиков. Таблетка держит приоритетную очередь задач
TTickProcessorQueue(сортировка по времени и уровню в иерархии — родители обрабатываются раньше детей) и будит себяTEvWakeupтолько когда очередь непуста (quoter_runtime.cpp:263-308). Если никто ничего не потребляет — таблетка спит. -
Отправка квоты. Выданная на тике квота аккумулируется per-client в
TQuoterResourceSessionsAccumulatorи уходит одним батч-событиемTEvResourcesAllocated(quoter_runtime.cpp:46-105).
flowchart TD
WAKE["TEvWakeup (тик, раз в 100 мс<br/>пока есть активные сессии)"] --> POP["Взять задачи текущего тика из<br/>TTickProcessorQueue<br/>(родители раньше детей)"]
POP --> Q["Ресурс получает квант:<br/>MaxUnitsPerSecond / 10"]
Q --> RR["Round Robin: делим квант между<br/>активными детьми/сессиями;<br/>излишек — обратно в котёл"]
RR --> FULL{"Сессия получила всё,<br/>что просила?"}
FULL -- "да" --> DEACT["Deactivate() —<br/>выходит из round robin"]
FULL -- "нет" --> NEXT["Остаётся активной,<br/>планируем следующий тик"]
DEACT --> ACC
NEXT --> ACC["Аккумулятор: батчим выдачу<br/>per client"]
ACC --> SEND["TEvResourcesAllocated → клиентам"]
SEND --> SCHED["ScheduleQuoterTick(): если очередь<br/>непуста — Schedule(TEvWakeup)"]
- Регистрируется при старте узла под фиксированным
TActorIdMakeQuoterServiceID()("quotersvs") — quoter.cpp:5-8, инициализация в kikimr_services_initializers.cpp. - Принимает
TEvQuota::TEvRequest(quoter.h:79-89): векторTResourceLeaf(путь квотера, имя ресурса, количество, флагIsUsedAmount) + дедлайн. - Отвечает
TEvQuota::TEvClearanceс результатомSuccess / UnknownResource / Deadline / GenericError. - Внутри держит очереди ожидающих запросов per-resource (связные списки
QueueHead/QueueTail, учётQueueSize/QueueWeight) и колесо дедлайнов.
Когда приходит запрос на ещё не известный путь (например /Root/MyCoordinationNode):
TQuoterServiceшлётTEvTxProxySchemeCache::TEvNavigateKeySetв SchemeCache (quoter_service.cpp:571-577).- Если в ответе
Kind == KindKesus— извлекаетKesusTabletIdи создаётTKesusQuoterProxy— отдельный актор на этот координационный узел (quoter_service.cpp:1238-1273).
Прокси (kesus_quoter_proxy.cpp):
- открывает TabletPipe к таблетке Kesus;
- подписывается на ресурсы (
TEvSubscribeOnResources) по мере появления первых запросов к ним; - ведёт локальное ведро каждого ресурса (
TResourceState:Available,QueueWeight, размеры ведра); - сообщает сервису о состоянии ресурса (
TEvProxySession, затемTEvProxyUpdateс порциями квоты); - получает от сервиса статистику потребления (
TEvProxyStats) и транслирует её в Kesus.
События определены в events.h:444-575, обработчики — в quoter_runtime.cpp.
sequenceDiagram
autonumber
participant C as Потребитель<br/>(актор на узле)
participant QS as TQuoterService<br/>(локальный)
participant P as TKesusQuoterProxy<br/>(локальный)
participant K as Таблетка Kesus
C->>QS: TEvQuota::TEvRequest("MyNode", "root/write", 5)
Note over QS: путь неизвестен → резолв через SchemeCache,<br/>создание proxy
QS->>P: ProxyRequestState (нужен ресурс root/write)
P->>K: TEvSubscribeOnResources(ResourcePath="root/write")
K-->>P: TEvSubscribeOnResourcesResult(ResourceId, EffectiveProps, InitialAvailable)
P->>QS: TEvProxySession(ResId, props)
loop пока локальной квоты не хватает
P->>K: TEvUpdateConsumptionState(ResId, consume=true, Amount)
Note over K: сессия активна → участвует<br/>в round robin на тиках (100 мс)
K-->>P: TEvResourcesAllocated(ResId, Amount)
P-->>K: TEvResourcesAllocatedAck
P->>QS: TEvProxyUpdate(квота в локальное ведро)
end
QS-->>C: TEvQuota::TEvClearance(Success)
Note over QS,P: периодически
QS->>P: TEvProxyStats(Consumed, QueueWeight, History)
P->>K: TEvAccountResources(история потребления) — для биллинга
K-->>P: TEvAccountResourcesAck(AcceptedUs)
Note over P,K: когда ведро заполнено
P->>K: TEvUpdateConsumptionState(consume=false)
Note over K: сессия деактивируется,<br/>тики для неё не тратятся
Сводка событий:
| Событие | Направление | Назначение |
|---|---|---|
TEvSubscribeOnResources / ...Result |
proxy → Kesus | Создать сессию на ресурс(ы) по пути; в ответ — ResourceId и эффективные настройки |
TEvUpdateConsumptionState / ...Ack |
proxy → Kesus | Включить/выключить потребление, сообщить сколько нужно |
TEvResourcesAllocated / ...Ack |
Kesus → proxy | Push выданной квоты (батч по всем ресурсам клиента за тик) |
TEvAccountResources / ...Ack |
proxy → Kesus | Отчёт об истории фактического потребления (для metering/биллинга) |
TEvReportResources, TEvSyncResources |
оба | Протокол replicated bucket (экспериментальный leaf_behavior: replicated_bucket) |
Самая важная для производительности часть: потребители почти никогда не ждут сети, потому что proxy заранее держит запас квоты.
Настройки (proto: ydb_rate_limiter.proto:92-132, дефолты: quoter_constants.h):
prefetch_coefficient(дефолт 0.2) — размер локального ведра:ResourceBucketMaxSize = max_units_per_second × 0.2, т.е. запас на ~200 мс потребления.prefetch_watermark(дефолт 0.75) — порог дозаказа:ResourceBucketMinSize = MaxSize × 0.75.max_burst_size_coefficient(дефолт 1) — допустимый burst на стороне Kesus.immediately_fill_up_to(отрицательное) — насколько глубоко ведро может уйти «в минус» (актуально для отчётовused, см. ниже).
Логика активации сессии в proxy (CheckState, kesus_quoter_proxy.cpp:1118-1124):
flowchart TD
EV["Изменилось Available или QueueWeight<br/>(пришла квота / потребитель израсходовал)"] --> CHK{"Сессия активна?"}
CHK -- "да" --> FULLQ{"Available ≥ MaxSize + QueueWeight ?"}
FULLQ -- "да" --> STOP["UpdateConsumptionState(consume=false)<br/>— хватит, перестаём просить"]
FULLQ -- "нет" --> WAIT["Ждём следующих TEvResourcesAllocated"]
CHK -- "нет" --> LOWQ{"Available < MinSize (watermark)<br/>+ QueueWeight ?"}
LOWQ -- "да" --> START["UpdateConsumptionState(consume=true)<br/>— дозаказываем квоту"]
LOWQ -- "нет" --> IDLE["Квоты достаточно, сидим тихо"]
Итого жизненный цикл квоты: Kesus капает квоту порциями раз в 100 мс → proxy складывает в ведро → TQuoterService мгновенно отдаёт её локальным потребителям из ведра → когда уровень падает ниже watermark, proxy снова включает потребление. При стабильной нагрузке это даёт плавный поток без всплесков latency.
Ydb.RateLimiter.V1.RateLimiterService (ydb_rate_limiter_v1.proto) — 6 методов:
| Метод | Тип | Куда идёт на сервере |
|---|---|---|
CreateResource, AlterResource, DropResource, ListResources, DescribeResource |
Control plane | Резолв пути → TabletPipe → напрямую в таблетку Kesus (TEvAddQuoterResource и т.д.) |
AcquireResource |
Data plane | В локальный TQuoterService (TEvQuota::TEvRequest) — без обращения к схеме |
Ресурсы создаются внутри координационного узла: coordination_node_path (например /Root/MyNode, создаётся через CoordinationService.CreateNode) + resource_path (например root/write).
AcquireResourceRequest.units — это oneof (ydb_rate_limiter.proto:271-292), обработчик — TAcquireRateLimiterResourceRPC (rpc_rate_limiter_api.cpp:438-546):
sequenceDiagram
participant A as gRPC-клиент
participant R as TAcquireRateLimiterResourceRPC
participant QS as TQuoterService
rect rgb(232, 240, 254)
Note over A,QS: required = N — «дай мне N единиц, я подожду»
A->>R: AcquireResource(required: 5)
R->>QS: TEvRequest(leaf, IsUsedAmount=false, deadline)
Note over QS: блокируется в очереди,<br/>пока в ведре не наберётся 5 единиц<br/>или не истечёт дедлайн
QS-->>R: TEvClearance(Success | Deadline)
R-->>A: SUCCESS | TIMEOUT/CANCELLED
end
rect rgb(254, 247, 224)
Note over A,QS: used = N — «я уже потратил N единиц, учти»
A->>R: AcquireResource(used: 5)
R->>QS: TEvRequest(leaf, IsUsedAmount=true)
Note over QS: ведро уходит в минус (до immediately_fill_up_to),<br/>не блокирует, отвечает сразу
QS-->>R: TEvClearance(Success)
R-->>A: SUCCESS
end
required— классический «возьми токены перед операцией»: запрос ждёт в очереди квотера.operation_timeout/cancel_afterопределяют, вернётсяTIMEOUTилиCANCELLEDпри нехватке квоты.used— отчёт постфактум: операция уже выполнена, мы лишь списываем потраченное. Ведро может уйти в отрицательное значение — тогда последующиеrequired-запросы будут ждать, пока долг не погасится притоком квоты. Это удобно, когда стоимость операции известна только после её выполнения.
TEvQuota::TEvRequest шлют не только gRPC-хендлеры:
- YMQ/SQS (ydb/core/ymq/actor/queue_schema.cpp) — лимиты на операции с очередями;
- rate limiter в Federated Query (ydb/core/fq/libs/rate_limiter/);
- любой актор в кластере может использовать квотер напрямую через
MakeQuoterServiceID()(есть и системный квотер со «статическими» ресурсами без Kesus — фиксированная локальная ставка, закодированная в ResourceId).
stateDiagram-v2
[*] --> Online: pipe к Kesus установлен
Online --> Reconnecting: TEvClientDestroyed /<br/>ошибка pipe
Reconnecting --> Online: переподключился,<br/>повторная подписка на все ресурсы
Reconnecting --> Broken: KesusReconnectCount ><br/>KesusReconnectLimit (5)
Online --> Offline_alloc: связь потеряна,<br/>но есть история потребления
Offline_alloc --> Online: связь восстановлена
Broken --> [*]: TEvProxyUpdate(Broken) —<br/>сервис фейлит очереди и пересоздаёт квотер
note right of Offline_alloc
Proxy продолжает «выдавать» квоту
по последней наблюдаемой ставке,
затухая с коэффициентом
FADING_ALLOCATION_COEFFICIENT = 0.999
end note
- Разрыв pipe: proxy переподключается (до 5 попыток —
KesusReconnectLimit, kesus_quoter_proxy.cpp:48) и заново шлётTEvSubscribeOnResourcesна все известные ресурсы. - Offline-режим: пока связи нет, proxy планирует «виртуальные» пополнения ведра по исторической ставке с экспоненциальным затуханием (
FADING_ALLOCATION_COEFFICIENT = 0.999, quoter_constants.h:7) — потребители не встают колом мгновенно, но и не получают квоту вечно. - Рестарт таблетки Kesus: описания ресурсов поднимаются из локальной БД, а сессии и вёдра — нет; клиенты переподписываются через pipe-reconnect. Возможен кратковременный overshoot/undershoot лимита.
- Ресурс не найден (
NOT_FOUNDна подписку): сервис отвечает потребителюTEvClearance::UnknownResource. - Дедлайны: у каждого запроса в очереди квотера есть дедлайн; по его истечении —
TEvClearance::Deadline.
Опциональная подсистема для serverless-биллинга (MeteringConfig в ydb_rate_limiter.proto:23-83, реализация — rate_accounting.h):
flowchart LR
P["TKesusQuoterProxy<br/>история потребления<br/>(каждые report_period_ms = 5с)"] -- "TEvAccountResources" --> RA["TRateAccounting<br/>(в таблетке Kesus,<br/>per resource)"]
RA -- "классификация" --> M1["provisioned<br/>(до provisioned_units_per_second)"]
RA --> M2["on_demand<br/>(сверх provisioned)"]
RA --> M3["overshoot<br/>(сверх допустимого burst)"]
M1 & M2 & M3 -- "billing records<br/>(billing_period_sec = 60с)" --> BILL["Metering actor →<br/>биллинговая система"]
- Proxy копит фактическое потребление по интервалам и периодически шлёт
TEvAccountResources; таблетка дедуплицирует по(clientId, resourceId)и времени. - Потребление раскладывается на три метрики: provisioned (оплаченная ставка), on_demand (сверх неё), overshoot (превышение burst, обычно для алертов/контроля). Каждая метрика отдельно включается и снабжается labels/полями для биллинговой записи.
C++ SDK (rate_limiter.h):
NYdb::NCoordination::TClient coordination(driver);
NYdb::NRateLimiter::TRateLimiterClient rl(driver);
// 1. Координационный узел
coordination.CreateNode("/Root/MyNode").GetValueSync();
// 2. Дерево ресурсов: 1000 у.е./с суммарно, из них чтение — не более 200
rl.CreateResource("/Root/MyNode", "root",
NYdb::NRateLimiter::TCreateResourceSettings()
.MaxUnitsPerSecond(1000)).GetValueSync();
rl.CreateResource("/Root/MyNode", "root/read",
NYdb::NRateLimiter::TCreateResourceSettings()
.MaxUnitsPerSecond(200)).GetValueSync();
rl.CreateResource("/Root/MyNode", "root/write",
NYdb::NRateLimiter::TCreateResourceSettings()).GetValueSync(); // наследует 1000
// 3a. Взять 5 единиц перед операцией (заблокируется при нехватке)
auto st = rl.AcquireResource("/Root/MyNode", "root/write",
NYdb::NRateLimiter::TAcquireResourceSettings()
.Amount(5)
.OperationTimeout(TDuration::Seconds(1))).GetValueSync();
// 3b. Отчитаться о 7 уже потраченных единицах (не блокирует)
rl.AcquireResource("/Root/MyNode", "root/write",
NYdb::NRateLimiter::TAcquireResourceSettings()
.Amount(7)
.IsUsedAmount(true)).GetValueSync();Тесты с живыми примерами всех методов: rate_limiter_ut.cpp.
Rate limiter в YDB — это двухуровневый token bucket: глобальное иерархическое дерево вёдер живёт в таблетке Kesus (координационном узле) и пополняется со скоростью max_units_per_second, а на каждом узле кластера прокси-актор держит маленькое локальное ведро (~20% секундной ставки) и пополняет его пачками раз в 100 мс по алгоритму Hierarchical DRR — поэтому потребители получают квоту локально и мгновенно, а суммарный лимит соблюдается на уровне всего кластера.