대기행렬이론으로 설계하는 시스템 혼잡과 용량 계획
대기행렬이론의 도착률·서비스율·이용률을 바탕으로 시스템 병목, SLA, 오토스케일링과 큐 제어를 설계하는 방법을 정리합니다.
2026-08-14 · 최초 발행 2024-04-29
혼잡은 요청 수가 아니라 도착률과 처리율의 관계에서 시작된다
대기행렬이론(Queuing Theory)은 서비스 지연과 병목을 정량적으로 예측하고 제어하는 수리적 프레임워크다. IT 시스템과 네트워크뿐 아니라 제조, 콜센터처럼 요청 또는 작업이 도착하고 처리되는 환경에서 용량 계획, SLA 설계, 자원 최적화의 근거로 사용된다.
시스템은 도착 과정의 도착률 λ, 서비스 과정의 서비스율 μ, 서버 수 c, 대기열 용량 K, 고객 집단 크기 N으로 표현할 수 있다. 대기 규율도 결과를 바꾼다. FCFS, Priority, Shortest Processing Time 같은 규율에 따라 같은 부하에서도 대기시간 분포가 달라진다.
관측할 성능 지표에는 이용률 ρ, 시스템 평균 체류수 L, 평균 대기열 길이 Lq, 평균 체류시간 W, 평균 대기시간 Wq, 차단·포기 확률 Pblock/Prng가 있다.
Kendall 표기법은 이 조건을 A/S/c/K/N/D 형태로 기록한다. A는 도착분포, S는 서비스분포, c는 서버 수, K는 시스템 용량, N은 고객 집단, D는 규율을 뜻한다. 포아송 도착·지수 서비스·단일 서버를 가정한 M/M/1, 다중 서버의 M/M/c, 서비스 시간이 일반분포인 M/G/1, 더 일반적인 G/G/1이 대표적이다.
M/M/1은 이용률 ρ=λ/μ < 1일 때 안정적이다. 이 조건이 무너지면 대기열은 지속적으로 누적된다. 대표 공식은 다음과 같다.
W = 1/(μ−λ)Wq = ρ/(μ−λ)L = λWLq = λWq
분포 가정을 단순하게 둘수록 계산과 해석은 쉬워진다. 반면 실제 트래픽의 변동성을 얼마나 반영할 수 있는지는 낮아질 수 있다.
이용률이 높아질 때 지연이 급격해지는 이유
포아송 도착과 지수 서비스 가정의 M/M/· 모델은 수학적으로 다루기 쉽다. 다만 Heavy-tail 또는 버스트 트래픽이 두드러지는 경우에는 G/G/· 모델이나 시뮬레이션을 함께 써야 한다. Kendall 표기법은 이런 모델 공간을 체계화하고, 파라미터 추정과 감도 분석의 기준을 제공한다.
이용률 ρ가 1에 가까워지면 대기시간은 지수적으로 폭증한다. SLA 한계에 닿기 전 완충 구간으로 ρ≤0.7~0.8을 확보하는 접근이 권장된다. Balking(차단), Reneging(이탈), Retry(재시도)를 모델에 포함하면 실제 사용자 경험에 더 가까운 분석이 가능하다.
큐 규율 역시 운영 정책이다. FCFS와 Priority, WRR은 서로 다른 지연 분포를 만든다. 우선순위 큐는 임계 요청을 보호하고 Tail latency를 제어하는 수단이 될 수 있지만, 규율을 바꾸면 공정성·SLA·스루풋 사이의 트레이드오프도 함께 검토해야 한다.
토폴로지에서는 단일 큐-다중 서버 구성이 부하균형과 공정성 측면에서 유리하다. 다중 큐-다중 서버는 지역 혼잡 위험이 있다. 오버플로 큐, 버스트 버퍼, 배치 처리 믹스는 변동성을 흡수하는 데 활용할 수 있다.
서버 수 c를 늘리는 수평 확장과 서비스율 μ를 높이는 수직 확장은 비용과 효과를 비교해 선택한다. Autoscaling과 Rate limiting을 결합하고, 백프레셔와 큐 길이 기반 제어 루프를 구성하면 지연 폭증을 억제할 수 있다.
서비스 유형별로 보는 큐 제어
마이크로서비스와 메시지 큐에서는 요청 도착률 λ, 컨슈머 처리율 μ, 파티션·컨슈머 그룹 수 c가 입력이 된다. 단일 큐-다중 컨슈머 패턴으로 Head-of-line blocking을 완화하고 Backpressure를 적용한다. 목표 Wq를 제한하며, 큐 길이 임계치를 스케일 아웃 트리거로 설계한다.
API 게이트웨이에서는 초당 요청량 RPS, 허용 버스트, 토큰 버킷 파라미터를 본다. 토큰 버킷 또는 리키 버킷으로 유효 λ를 제어하고, 429 비율을 Pblock의 관측값으로 삼는다. 이 방식은 다운스트림을 보호하면서 지연을 안정화하고 SLA 준수율을 높이는 데 쓰인다.
클라우드 자동 확장에서는 큐 길이, 소비 지연, ρ 추정치가 기준이다. 목표 이용률 ρ*에 따라 c를 산정하고 워밍업·쿨다운 윈도우를 설정하면 과확장과 소확장을 피하면서 비용 대비 지연 최적점을 운영할 수 있다.
제조·물류 라인은 공정별 λ/μ와 버퍼 용량 K를 놓고 병렬 스테이션 증설과 병목 공정의 μ 향상을 비교한다. 로트 배치 최적화까지 연결하면 WIP 감소와 택타임·리드타임 단축을 검토할 수 있다.
콜센터·병원 트리아지에서는 콜 또는 환자 λ, 상담 또는 진료 μ, 우선순위 규칙을 사용한다. Erlang C로 상담원 c를 산정하고 Priority Queue로 긴급 케이스를 보호한다. 응답지연·이탈률을 낮추고 인력 스케줄 효율화를 지원한다.
관측값에서 운영 정책까지 연결하기
먼저 도착 간격, 서비스 시간, 큐 길이, 이탈·재시도 이벤트를 수집한다. 포아송·지수 가정이 맞는지 검증하고, 필요하면 일반분포 G를 채택한다.
모델은 M/M/1, M/M/c, M/G/1, G/G/1 순으로 단순한 모델부터 적합화한다. ρ < 1 안정 조건을 확인하고 목표 여유율로 ρ≤0.7을 설정한다. 용량은 M/M/1 근사에서 μ ≥ λ + 1/W 목표식을 적용하며, 멀티서버 환경에서는 Erlang C와 시뮬레이션을 병행한다.
설계 산출물은 서버 수 c, 인스턴스 스펙 μ, 큐 용량 K, 규율 D, Rate limit이다. 부하시험으로 분포를 검증하고 L, W, ρ, Pblock을 모니터링해 피드백 제어 루프를 구성한다.
버스트가 허용 한계를 넘으면 일시적 대기를 허용할 범위를 정하고, 초과분을 차단하거나 디그레이드하는 정책이 필요하다. 이탈과 재시도는 재시도 지연·지수 백오프, 중복 처리 아이들포턴시로 제어한다.
모델마다 달라지는 해석 범위와 운영 부담
| 모델 | 성능(해석/예측) | 확장성 | 일관성(지연 분산) | 안정성(혼잡 내성) | 운영 편의 |
|---|---|---|---|---|---|
| M/M/1 | 폐형식 해, 즉시 계산 가능 | 제한적(수직 확장 위주) | 변동성 큼, Tail 취약 | ρ→1에서 급격한 폭증 | 파라미터 추정 용이 |
| M/M/c | Erlang C로 근사 가능 | 수평 확장 용이 | 단일 큐로 분산 안정 | 적정 c에서 완충 우수 | 중간 난이도 |
| M/G/1 | 평균·분산 반영, Pollaczek–Khinchine 사용 | 단일 서버 기준 | 서비스 분산 영향 반영 | 모멘트 추정 품질 의존 | 통계 추정 필요 |
| G/G/1 | 가장 일반적, 시뮬 필요 | 설계 유연 | 현실 근사 우수 | 제어 전략 중요 | 운영 복잡도 높음 |
지연 목표를 수치로 검토하는 방법
M/M/1 근사에서 λ=80 rps, μ=100 rps이면 ρ=0.8이다. 이때 W=1/(μ−λ)=1/20=0.05s(50ms), Wq=ρ/(μ−λ)=0.8/20=0.04s(40ms), Lq=λ·Wq=3.2건으로 계산된다.
목표가 W≤100ms라면 μ≥λ + 1/W = 80 + 10 = 90 rps 조건을 적용해 단일 인스턴스로 SLA를 달성할 가능성을 판단할 수 있다.
ρ 목표치로 최소 서버 수를 구하면 과잉 프로비저닝을 피하고 TCO를 절감할 수 있다. 우선순위 큐는 중요 트래픽의 95/99퍼센타일 지연을 현저히 줄일 수 있다. 백프레셔·Rate limit·오버플로 큐를 함께 적용하면 버스트 상황에서도 지연 폭증을 억제하고, 차단·이탈률 관리를 통해 사용자 경험과 매출 손실을 최소화할 수 있다.
대기행렬이론은 λ·μ·c·K·규율을 통해 혼잡을 계량화하고, 목표 SLA에 맞는 용량과 제어 정책을 설계하는 접근이다. 단순 모델에서 시작해 관측 데이터를 토대로 일반화 모델과 시뮬레이션을 병행하며 정밀도를 높인다. 단일 큐-다중 서버, 목표 이용률, Rate limiting·백프레셔·오토스케일 조합은 운영 환경에서 검토할 수 있는 표준 패턴이다.