07-EFT.WP.Core.Threads v1.0 | Chapter 7 — Flow Control and Rate Limiting

Home ／ Docs-Technical WhitePaper ／ 07-EFT.WP.Core.Threads v1.0

Chapter 7 — Flow Control and Rate Limiting

I. Scope and Objectives

• Provide a unified model for rate limiting and traffic shaping that covers rate_limiter, leaky_bucket, closed-loop backpressure, and hierarchical quotas, ensuring rho < 1 approx stability while meeting SLOs.
• Define postulates P77-, minimal equations S77-, and the operational flow Mx-6, in coordination with I70-6, I70-3, I70-5, I70-8.
• Maintain causal consistency (hb) and predictability in the presence of retries and jitter, preventing request storms and cascading degradation.

II. Terms and Variables

• Limiter: rps (tokens/sec), burst (max instantaneous tokens), tokens_req (tokens per request, default 1), tau_mono (monotonic clock).
• Queues and rates: lambda (arrival rate), mu (service rate), rho = lambda / mu, q_len, W_q, cap.
• Backpressure: bp ∈ [0,1], bp = f(q_len, cap, W_q); K_thr (concurrency cap).
• Windows and jitter: SLA_window, J (jitter), Delta_t (observation window).
• Hierarchy and scope: lim_dom(tenant|service|endpoint|chan), gid, thr, prio.

III. Postulates P77 (Limiting and Closed Loop)

• P77-1 (Shaping-first): prefer admission shaping at the ingress over “after-the-fact” dropping; only reject strategically when rho destabilizes or deadline is imminent.
• P77-2 (Monotone timing): limiters and queue metrics must use tau_mono; audit in ts.
• P77-3 (Hierarchical conservation): enforce sum(child.rps) <= parent.rps and sum(child.burst) <= parent.burst.
• P77-4 (HB-safe loop): publish and consume bp under hb; forbid racy concurrent updates on the same chan.
• P77-5 (Stability guardrail): within the control loop keep lambda_hat <= mu * (1 - headroom), with headroom ∈ (0,0.3].
• P77-6 (Bounded retries): cap retry budgets by rate_budget to prevent p_retry amplifying into storms; compose with Chapter 5 retry policies.
• P77-7 (No priority inversion): low-prio traffic must not bypass high-prio reserved bandwidth via oversized burst.
• P77-8 (Observe-before-switch): any threshold or parameter change ships in shadow (read-only) first; switch only after confirming P99 and ErrRate do not regress.

IV. Minimal Equations S77 (Tokens and Stability)

• S77-1 (Token bucket envelope): for any interval [t1,t2] the admitted count N_admit satisfies
  N_admit <= rps * ( t2 - t1 ) + burst.
• S77-2 (Instant borrowing): a request admits iff tokens >= tokens_req; otherwise the wait lower bound is
  T_wait >= ( tokens_req - tokens ) / rps.
• S77-3 (Post-shaped arrival rate): lambda_hat <= rps; with batching batch_size = b,
  lambda_hat_eff <= min( rps, K_thr / E[S] ), where E[S] is mean service time.
• S77-4 (Steady-state wait approximation): W_q approx rho / ( mu - lambda_hat ) (for rho < 1), for coarse capacity sizing.
• S77-5 (Backpressure mapping): with thresholds q_lo < q_hi,
  bp = clamp( ( q_len - q_lo ) / ( q_hi - q_lo ), 0, 1 ); sender shaping uses rps_new = rps_base * ( 1 - bp )。
• S77-6 (Hierarchical conservation): in window Delta_t, parent admits A_parent and children sum to A_children with
  A_children <= A_parent + epsilon_window (sampling drift epsilon_window from clock/aggregation error).

V. Policy Families and Applicability

1. Token Bucket
   • Use when controlled bursts are acceptable; cap peaks without hard smoothing.
   • Parameters: rps sets long-term throughput; burst caps instantaneous spikes. Typical burst ∈ [rps, 2*rps].
2. Leaky Bucket
   • Use for strong smoothing (A/V, strict downstream rates).
   • Approximation: token bucket with small burst; as burst -> 0, behavior approaches constant-rate sending.
3. AIMD (Additive-Increase, Multiplicative-Decrease)
   Use when no explicit downstream metrics exist; probe usable bandwidth; tie multiplicative decrease to bp.
4. PI control (Proportional–Integral)
   Use to target q_len* or W_q*; adjust rps via error e(t)=q_len - q_len*; bound integral and add hysteresis to avoid oscillation.

VI. Topology and Placement

• Ingress limiting: lim_dom(tenant), lim_dom(service) to prevent cross-tenant contention.
• Channel limiting: lim_dom(chan) to tame local hot spots (align with Chapter 3 cap).
• Egress shaping: if downstream mu < upstream, enforce rps <= mu * (1 - headroom).
• Distributed aggregation: for replicas, distribute budgets as rps_i = rps_total * w_i / ∑ w, with w_i from health or historical throughput.

VII. Implementation Notes (I70-6 / I70-3)

1. Limiter API
   • rate_limiter(name:str, rps:float, burst:int) -> LimiterRef
   • limit_acquire(lim:LimiterRef, tokens:int=1, timeout:float|None=None) -> bool
2. Monotonic replenishment: token accrual must be driven by tau_mono—never by ts.
3. Fairness: when multiple producers share a LimiterRef, use proportional fairness share_i = weight_i / ∑ weight.
4. Batching: for tokens_req = b, ensure b <= burst and recommend b <= min( burst/2, cap/4 ).
5. Timeout semantics: on limit_acquire(..., timeout=t) failure return False; callers degrade or queue. Compose upper bound with Chapter 5:
   W_retry <= timeout * ( retries + 1 ) + J_total.

VIII. Backpressure Closed Loop and De-oscillation

• Signals: q_len, W_q, throttle_ms, P99.
• Hysteresis: use q_hi/q_lo—adjust rps and K_thr only upon boundary crossings.
• Adjustment order
  Reduce rps (shape ingress) → reduce K_thr (concurrency) → increase inter-batch or shrink batch_size → drop low-prio or return soft 429.
• Target binding: with target W_q* or P99*, PI update
  rps_{t+1} = clamp( rps_t - k_p * e_t - k_i * ∑ e , rps_min, rps_max ).

IX. Distribution and Consistency

1. Budgeting
   • Static quotas: pre-distribute rps_i, burst_i; reclaim when a replica fails.
   • Leases: replicas periodically lease tokens to avoid a central bottleneck.
2. Approximate consistency: tolerate epsilon_window drift; converge to S77-6 within SLA_window.
3. Causality: record an eid before broadcasting new budgets; stamp the activation with tau_mono to avoid overlapping writes.

X. SLO Binding and Observability (I70-7 / I70-8)

1. SLIs: QPS_admit, QPS_drop, W_q, P99_latency, 429_rate, bp_level.
2. Budget model: decompose P99_total <= P99_queue + P99_service; shaping targets P99_queue.
3. Alert thresholds
   • Alert if rho > 1 - headroom for ≥ SLA_window/10.
   • If 429_rate > 1% and bp_level > 0.5, tighten limits and initiate root-cause drill.

XI. Contract Assertions and Test Examples

1. Contract items (samples)
   • {"type":"rate_envelope","rps":1000,"burst":2000}
   • {"type":"queue_bound","q_len_le":cap*0.8}
   • {"type":"stability","rho_le":1-headroom}
   • {"type":"fair_share","weights":{"A":2,"B":1},"share_tol":0.1}
   • {"type":"retry_budget","max_retries":2,"window_sec":60}
2. Expected outputs: pass/fail, worst-window N_admit, 429_rate, P99 deltas, and bp time series.

XII. Parameter Guidelines (Empirical Ranges)

• Online APIs: headroom ∈ [0.1, 0.2], burst ∈ [rps, 2*rps], q_hi = 0.8*cap, q_lo = 0.5*cap.
• Event streams: set rps to 0.7~0.85 * mu_downstream; b ∈ [100, 1000] bounded by W_q.
• Batch: primarily control with K_thr; use rps only at ingress; burst ≈ 0.5*cap.

XIII. Operational Flow Mx-6 (Rollout and Tuning)

• Sample mu and E[S]; estimate baseline rps_base = mu * ( 1 - headroom ); set burst and q_lo/q_hi.
• Create LimiterRef in a canary/shadow path; observe P99 and q_len.
• Enable limit_acquire; route failures to graceful degradation or soft 429; begin bp reporting.
• Observe for one SLA_window; tune rps/K_thr via S77-5; switch to AIMD or PI if needed.
• Freeze configs and write contract tests; execute assert_thread_contract and record a regression baseline.
• Continuously watch rho, 429_rate, bp_level; if oscillation appears, widen hysteresis or shrink burst.

XIV. Interface Bindings and Examples (I70-6 / I70-3)

• Configure
  lim = rate_limiter(name="ingress.api", rps=1200.0, burst=1800)
• Acquire & backpressure
  Sender loop: ok = limit_acquire(lim, tokens=1, timeout=5e-3); if !ok, sleep(jitter) or degrade.
  Consumer publishes bp = f(q_len, cap, W_q); sender updates rps_new = rps_base * (1 - bp).
• Hierarchy
  Check tenant.lim, service.lim, endpoint.lim in order—any failure rejects.

XV. Coordination with Neighboring Chapters

• With Chapter 3: definitions of q_len/cap/bp and overflow policies are consistent.
• With Chapter 5: compose upper bounds via W_retry <= timeout * ( retries + 1 ) + J_total.
• With Chapter 6: when rho_* approaches limits, degrade in the order “revoke burst → lower K_thr → rate limit.”

XVI. Deliverables and Acceptance

• Parameter set for limiting and backpressure (rps, burst, q_lo/q_hi, headroom, K_thr).
• Shadow-period observations (P99, W_q, rho, 429_rate, bp).
• Contract assertion results and replay scripts.
• Audit of hierarchical conservation and epsilon_window drift analysis.