Backpressure and Queueing Theory — Capacity Planning with Little's Law TODO
Concept
Queueing theory models arrival and service processes probabilistically to predict queue length and latency. Little's law states that in steady state, L = λW — the average number of items in the system equals the average arrival rate times the average time spent in the system — and its power is that it holds without any assumption about the distributions involved. As utilization ρ approaches 1, waiting time grows roughly proportional to 1/(1-ρ) and blows up sharply, so a system should be run with some slack, not at 100% utilization. Backpressure is a technique that pushes back on inflow the consumer can't keep up with, toward the producer, so the queue doesn't grow without bound — implemented via bounded queues, blocking, credit-based flow control, or load shedding. An unbounded queue doesn't solve overload — it just turns the failure into runaway latency and memory exhaustion instead.
When load spikes and a service collapses, the path is usually the queue growing without bound, latency crossing timeouts, and retries exploding — and this is exactly the point that capacity math can head off in advance.
Code & Formula
# 백프레셔와 큐 이론 — Little's law(L = λW)를 이용률(ρ)이 오를 때 대기시간이 급격히 커지는 걸로 확인하고,
# 유계 큐 + 거절(load shedding)로 무한정 큐잉을 막는 백프레셔를 시뮬레이션한다.
import random
random.seed(7)
def simulate(arrival_rate, service_rate, queue_capacity, num_events=20_000):
"""이산 시간 슬롯 시뮬레이션: 매 슬롯마다 arrival_rate 확률로 도착, service_rate 확률로 서비스 완료."""
queue_len = 0
total_in_system_time = 0.0
completed = 0
rejected = 0
wait_started = [] # 각 대기 항목이 큐에 들어간 시각(슬롯 인덱스)을 기록
for t in range(num_events):
if random.random() < arrival_rate:
if queue_len < queue_capacity: # 유계 큐: 꽉 차면 즉시 거절(load shedding)
queue_len += 1
wait_started.append(t)
else:
rejected += 1
if queue_len > 0 and random.random() < service_rate:
queue_len -= 1
started = wait_started.pop(0)
total_in_system_time += (t - started + 1)
completed += 1
avg_wait = total_in_system_time / completed if completed else 0.0
avg_queue_len = (arrival_rate * avg_wait) # Little's law: L = λ * W (도착률은 실제 수락된 요청 기준으로 근사)
return completed, rejected, avg_wait, avg_queue_len
service_rate = 0.5
print(f"{'utilization(rho)':>18} {'completed':>10} {'rejected':>9} {'avg_wait':>10} {'L=lambda*W':>12}")
for rho in (0.5, 0.8, 0.95):
arrival_rate = rho * service_rate
completed, rejected, avg_wait, avg_L = simulate(arrival_rate, service_rate, queue_capacity=15)
print(f"{rho:>18.2f} {completed:>10} {rejected:>9} {avg_wait:>10.2f} {avg_L:>12.2f}")
print("\n관찰: rho 가 1에 가까워질수록 avg_wait 이 완만하지 않고 급격히 커진다 (~1/(1-rho) 형태).")
print("유계 큐 덕분에 rho=0.95 에서도 무한정 쌓이지 않고 일부는 거절(reject)되어 시스템이 보호된다.")
docs/code/algorithms/algorithms-43.py
Exercise
Put a bounded queue in front of a worker pool, raise the arrival rate to 50%, 80%, and 95% of the service rate, measure p50/p99 latency and queue length, and check whether the numbers match what Little's law predicts.
Practical Connection
In a pipeline like Verex, where order intake is fast but on-chain settlement is slow, tied to block time, without a bounded queue and load shedding up front, back-end latency directly turns into user timeouts and a storm of resubmissions.
Where it lands in Jayverse
- Rabbit: put a bounded queue and load-shedding in front of the ERC-4337 bundler/relayer path. It has the same fast-intake-slow-settlement shape as Verex; size the queue with Little's Law instead of letting a spike become unbounded retries.
- OFA: measure p50/p99 latency and queue length at 50/80/95% of service rate before trusting the solver auction under load. The intake-to-settlement gap in the auction needs the same capacity math the exercise runs.
- gitboard: surface queue depth and utilization ρ per service. A service approaching ρ→1 should be visible on the dashboard before latency blows up, not discovered after timeouts start.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| push back on | ~에 저항하다, 밀어내다 · 감당 못 하는 입력 흐름을 역으로 제한할 때. "pushes back on inflow the consumer can't keep up with" |
| bounded queue | 크기가 제한된 큐 · 무한정 쌓이지 않도록 상한을 둔 대기열을 가리킬 때. "implemented via bounded queues, blocking, credit-based flow control" |
| load shedding | 부하 차단(일부 요청을 의도적으로 버림) · 과부하 시 시스템을 지키기 위한 기법. "credit-based flow control, or load shedding" |
| run with some slack | 여유를 두고 운영하다 · 시스템을 100% 가동하지 않고 여지를 남길 때. "a system should be run with some slack" |
| blow up | 급격히 치솟다, 폭증하다 · 지연 시간 등이 걷잡을 수 없이 커질 때. "and blows up sharply" |
| runaway latency | 걷잡을 수 없이 늘어나는 지연 시간 · 큐가 무한정 쌓여 생기는 실패 양상을 가리킬 때. "turns the failure into runaway latency and memory exhaustion" |
| a storm of | ~이 폭주하다, 쏟아지다 · 재시도 요청 등이 한꺼번에 몰릴 때. "user timeouts and a storm of resubmissions" |
| Little's Law | 리틀의 법칙(L = λW) · 대기 시스템의 평균 항목 수, 도착률, 체류시간의 관계를 나타내는 정리, 분포 가정 없이 성립. "Little's law states that in steady state, L = λW" |
| credit-based flow control | 크레딧 기반 흐름 제어 · 수신 측이 처리 가능한 만큼만 허용량을 주는 방식의 배압 기법. "implemented via bounded queues, blocking, credit-based flow control, or load shedding" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.