Problem Statement / Feature Objective
The current rate-limiter applies a single flat token bucket per meter, which cannot express hierarchical capacity sharing: e.g., a regional substation has 100 MW total capacity, shared among 10 feeders each with individual 15 MW limits, and each feeder serves 100 meters with 200 kW limits. Overdraft at one level should debit from the parent bucket, but the sum of children must never exceed the parent's capacity. A hierarchical token bucket (HTB) scheduler must be implemented that models the grid topology as a tree of rate-limited buckets, enforces both hard per-node ceilings and burst allowances, and integrates with the tariff evaluation engine to reject or delay requests that exceed available hierarchical capacity.
Technical Invariants & Bounds
- Tree depth: max 5 levels (root → region → substation → feeder → meter). Total nodes in tree: up to 1,048,576 (2^20).
- Token refill: each leaf (meter) configured with
rate (tokens/second) and burst (max tokens). Internal nodes configured with rate (sum of children rates enforced) and ceil (absolute max rate, possibly > rate for borrowing).
- Token unit: scaled micro-watt-hours (µWh), stored as u64; one token = 1 µWh = 10^-6 Wh.
- Borrowing: a child can burst above its
rate up to its parent's ceil, borrowing from the parent's idle capacity. Debt is repaid from the child's future refill at a configurable interest rate (default 10% APR).
- Enforcement granularity: every tariff evaluation call (10–100 ms per meter) checks HTB conformance. Non-conforming requests are either queued (with a max queue depth of 100) or rejected with a
429 Too Many Requests-equivalent gRPC error.
- Locking: full tree traversal must complete in ≤ 5 µs to avoid adding latency to the tariff path; implemented as a lock-free tree using atomic counters where possible, with per-node
RwLock as fallback.
Codebase Navigation Guide
src/ratelimit/htb.rs — new module: HierarchicalTokenBucket tree structure, refill, and conformance check.src/ratelimit/topology.rs — new module: grid topology loader from a protobuf topology definition file.src/ratelimit/lib.rs — re-export HTB types; create global HTBTree singleton initialized at startup.src/tariff/evaluator.rs — before applying tariff, call htb.conform(meter_id, requested_tokens); if false, return TariffError::CapacityExceeded.src/rpc/proto/topology.proto — protobuf for defining hierarchical grid topology: message Node { uint32 id, optional uint32 parent_id, uint64 rate_tokens_per_s, uint64 burst_tokens, uint64 ceil_tokens_per_s }.src/admin/routes.rs — add GET/PUT endpoints for querying and updating HTB configuration in real-time.Cargo.toml — add dashmap = "5.5" for concurrent node map.tests/ratelimit/htb_test.rs — property-based tests validating hierarchical fairness, borrowing, and debt repayment.
Implementation Blueprint
- In
htb.rs, define struct HtbNode { id: u32, parent: AtomicU32, rate: AtomicU64, ceil: AtomicU64, burst: AtomicU64, tokens: AtomicI64, last_refill_ns: AtomicI64, children: DashSet<u32>, debt: AtomicI64 }. Tokens can go negative (borrowing), bounded by -burst.
- Implement
HtbTree { nodes: DashMap<u32, Arc<HtbNode>>, root: Option<u32> }. fn refill(&self) iterates all nodes (or lazily on access): compute elapsed time since last_refill_ns, add rate * elapsed_ns / 1e9 to tokens, cap at burst, update last_refill_ns. This is O(n) but occurs only once per tick (configurable: default 100 ms).
- Implement
fn conform(&self, meter_id: u32, requested: u64) -> bool: walk from meter node to root, atomically deducting requested from each node's tokens (using fetch_sub with AcqRel). If any node's tokens would go below -burst, fail and roll back by adding back the deducted amount along the path. Rollback uses the same atomic operations in reverse order (leaf to root) to avoid deadlocks.
- Implement borrowing: when a child's tokens are insufficient but the parent has idle capacity (parent.tokens > 0 after deducting the child's portion), allow overshoot up to
child.ceil - child.rate. Record debt in child.debt. Debt is repaid by deducting from the child's future refill at an interest rate.
- In
topology.rs, implement a parser that reads a protobuf Topology message and builds the HTB tree. Validate that no cycles exist (topological sort) and that sum of children rates <= parent ceil.
- In
evaluator.rs, before computing the tariff amount, call htb.conform(meter_id, scaled_reading). If false, either queue the request for retry (with exponential backoff, base 100 ms, max 5 retries) or fail fast with a CapacityExceeded error depending on the tariff's priority class.
- Write property-based tests using
proptest to generate random tree topologies with varying rates, simulate Poisson-distributed traffic, and verify that: (a) no meter ever exceeds its ceil rate over a 1-minute sliding window; (b) the sum of all leaf throughput does not exceed the root ceil; (c) borrowing and debt repayment converge such that debt is always zero within 10 minutes after a burst ends.
Problem Statement / Feature Objective
The current rate-limiter applies a single flat token bucket per meter, which cannot express hierarchical capacity sharing: e.g., a regional substation has 100 MW total capacity, shared among 10 feeders each with individual 15 MW limits, and each feeder serves 100 meters with 200 kW limits. Overdraft at one level should debit from the parent bucket, but the sum of children must never exceed the parent's capacity. A hierarchical token bucket (HTB) scheduler must be implemented that models the grid topology as a tree of rate-limited buckets, enforces both hard per-node ceilings and burst allowances, and integrates with the tariff evaluation engine to reject or delay requests that exceed available hierarchical capacity.
Technical Invariants & Bounds
rate(tokens/second) andburst(max tokens). Internal nodes configured withrate(sum of children rates enforced) andceil(absolute max rate, possibly > rate for borrowing).rateup to its parent'sceil, borrowing from the parent's idle capacity. Debt is repaid from the child's future refill at a configurable interest rate (default 10% APR).429 Too Many Requests-equivalent gRPC error.RwLockas fallback.Codebase Navigation Guide
src/ratelimit/htb.rs— new module:HierarchicalTokenBuckettree structure, refill, and conformance check.src/ratelimit/topology.rs— new module: grid topology loader from a protobuf topology definition file.src/ratelimit/lib.rs— re-export HTB types; create globalHTBTreesingleton initialized at startup.src/tariff/evaluator.rs— before applying tariff, callhtb.conform(meter_id, requested_tokens); if false, returnTariffError::CapacityExceeded.src/rpc/proto/topology.proto— protobuf for defining hierarchical grid topology:message Node { uint32 id, optional uint32 parent_id, uint64 rate_tokens_per_s, uint64 burst_tokens, uint64 ceil_tokens_per_s }.src/admin/routes.rs— add GET/PUT endpoints for querying and updating HTB configuration in real-time.Cargo.toml— adddashmap = "5.5"for concurrent node map.tests/ratelimit/htb_test.rs— property-based tests validating hierarchical fairness, borrowing, and debt repayment.Implementation Blueprint
htb.rs, definestruct HtbNode { id: u32, parent: AtomicU32, rate: AtomicU64, ceil: AtomicU64, burst: AtomicU64, tokens: AtomicI64, last_refill_ns: AtomicI64, children: DashSet<u32>, debt: AtomicI64 }. Tokens can go negative (borrowing), bounded by-burst.HtbTree { nodes: DashMap<u32, Arc<HtbNode>>, root: Option<u32> }.fn refill(&self)iterates all nodes (or lazily on access): compute elapsed time sincelast_refill_ns, addrate * elapsed_ns / 1e9totokens, cap atburst, updatelast_refill_ns. This is O(n) but occurs only once per tick (configurable: default 100 ms).fn conform(&self, meter_id: u32, requested: u64) -> bool: walk from meter node to root, atomically deductingrequestedfrom each node's tokens (usingfetch_subwithAcqRel). If any node's tokens would go below-burst, fail and roll back by adding back the deducted amount along the path. Rollback uses the same atomic operations in reverse order (leaf to root) to avoid deadlocks.child.ceil - child.rate. Record debt inchild.debt. Debt is repaid by deducting from the child's future refill at an interest rate.topology.rs, implement a parser that reads a protobufTopologymessage and builds the HTB tree. Validate that no cycles exist (topological sort) and that sum of children rates <= parent ceil.evaluator.rs, before computing the tariff amount, callhtb.conform(meter_id, scaled_reading). If false, either queue the request for retry (with exponential backoff, base 100 ms, max 5 retries) or fail fast with aCapacityExceedederror depending on the tariff's priority class.proptestto generate random tree topologies with varying rates, simulate Poisson-distributed traffic, and verify that: (a) no meter ever exceeds its ceil rate over a 1-minute sliding window; (b) the sum of all leaf throughput does not exceed the root ceil; (c) borrowing and debt repayment converge such that debt is always zero within 10 minutes after a burst ends.