Queueing Theory란? 요청이 조금만 늘어도 서버 대기 시간이 급격히 길어지는 이유 쉽게 이해하기

웹서비스는 요청이 들어오면 바로 처리되는 것처럼 보이지만, 서버가 동시에 처리할 수 있는 수에는 한계가 있습니다. 처리 자리가 가득하면 새 요청은 줄을 섭니다. 이렇게 처리할 수 있는 자원보다 요청이 많을 때 줄을 서서 기다리는 현상을 분석하는 분야가 Queueing Theory(큐잉 이론, 대기행렬 이론)입니다.

요청이 얼마나 자주 들어오고
얼마나 빨리 처리되며
→ 얼마나 많은 요청이 줄을 서고
얼마나 오래 기다리는지 분석

은행 창구 비유

직원 한 명이 고객 한 명을 5분에 처리하는데 고객이 10분마다 오면 줄이 거의 없습니다. 고객이 4분마다 오면 도착이 처리보다 빨라 대기열이 계속 길어질 수 있습니다. 서버도 같습니다.

Arrival Rate · Service Rate · Utilization

Arrival Rate(λ)는 들어오는 속도, Service Rate(μ)는 처리 속도입니다. 들어오기보다 처리가 빨라야 안정적입니다. Worker가 여러 개면 전체 Capacity가 늘 수 있지만, DB 등 공유 병목 때문에 정확히 배수는 아닐 수 있습니다.

Utilization(이용률)은 Capacity 중 얼마나 쓰는지입니다. 50%와 90%의 대기가 비례로 늘지 않습니다. 한계에 가까워질수록 대기 시간이 비선형적으로 급증할 수 있습니다. 처리·도착 시간에 편차가 있고, 순간적으로 요청이 몰리기 때문입니다. 고속도로 95% 사용률처럼 작은 변화에도 정체가 납니다.

Headroom과 「평균만 맞추면」 함정

Arrival ≈ Service이면 기존 Queue가 거의 줄지 않고, 조금만 더 들어오면 매초 쌓입니다. 평균이 같아도 변동만으로 Queue가 생길 수 있어 Adaptive Concurrency에서 말한 Headroom이 필요합니다. 100% Utilization은 효율이 아니라 「대기열을 만들 준비가 된 상태」일 수 있습니다.

Little's Law

L ≈ λ × W
시스템 안 평균 작업 수
= 유입 속도 × 평균 체류 시간

초당 100요청·체류 0.2초면 약 20개, 체류 2초면 약 200개입니다. 유입이 같아도 응답이 느려지면 Active Request·Connection·메모리가 늘고 더 느려지는 악순환이 됩니다.

Waiting Time vs Service Time

전체 응답 ≈ Waiting Time(Queue·Connection 대기) + Service Time(실제 처리). 코드는 100ms인데 사용자는 2초를 기다릴 수 있습니다. 반대로 Queue는 0인데 DB Query가 5초일 수도 있습니다. End-to-End Latency와 분산 추적으로 「처리가 느린가, 기다리는가」를 나눕니다.

Queue Depth · Age · Throughput

Queue Depth는 대기 개수, Queue Age는 가장 오래된 작업의 대기 시간입니다. Depth가 일정해도 Age가 길면 사용자는 계속 느립니다. Throughput은 완료 수입니다. Concurrency를 늘리면 처음엔 Throughput이 오르다 포화되면 거의 안 늘고 Latency만 급증합니다 — Adaptive Concurrency가 Latency를 보고 Limit를 줄이는 배경입니다.

Buffer · Bounded Queue · 보호 패턴

적당한 Queue는 Burst를 흡수하는 Buffer입니다. 계속 Arrival > Service면 Queue만 키우는 것은 장애를 늦출 뿐입니다. 무한 Queue는 「버리지 않음」 대신 수 분 대기를 만들 수 있어 Bounded Queue와 Deadline 기준 거절이 필요합니다. 이는 Admission Control·Load Shedding·Waiting Room과 연결됩니다.

Queue의 연쇄와 Bottleneck Shift

요청은 LB·Application·DB Connection·DB·외부 API 등 여러 Queue를 지날 수 있습니다. Worker만 늘리면 App Queue는 줄고 DB Queue가 늘 수 있습니다(병목 이동). Connection Pool도 Queueing System입니다. Pool을 키우면 대기는 줄어도 DB 자체 처리 시간이 늘 수 있습니다. 로드밸런싱이 불균형하면 전체 Capacity가 남아도 한 서버 Queue만 길어집니다.

변동성 · Short/Long Queue · Priority

평균 Service Time이 같아도 일부 요청이 매우 길면 Queue가 불안정해집니다. 긴 작업이 앞을 막으면 짧은 작업도 오래 기다리는데, 이를 Head-of-Line Blocking으로 설명할 수 있습니다. Short/Long Queue 분리와 Priority는 Bulkhead와 맞닿고, Priority만 높이면 Starvation에 주의해야 합니다.

Burst · Waiting Room · 운영 관점

평균 500/s여도 이벤트 순간 5,000/s일 수 있습니다. Queue가 잠시 올랐다 내려가면 Buffer 역할이고, 계속 늘면 Capacity 증가·요청 감소·Admission·Load Shedding·최적화가 필요합니다. AI·GPU처럼 Worker가 적으면 Queue가 더 눈에 띕니다. 모니터링·SLO에서는 Queue 대기가 Service Time을 가려 SLO를 깨뜨릴 수 있어 시간을 분리해 봅니다. SEO 전용 이론은 아니며, 포화로 인한 지연·가용성 영향 맥락에서만 연결됩니다. 오토스케일은 Service Capacity를 늘리는 축입니다.

자주 묻는 질문

정리

Queueing Theory = 들어오는 속도와 처리 속도의 차이로 생기는 대기열·대기 시간을 이해하는 이론입니다. Arrival < Service면 Queue가 잘 줄고, Arrival > Service면 계속 늘어납니다. Utilization이 올라갈수록 Waiting Time·Latency가 급증할 수 있어 Admission·Load Shedding·Adaptive Concurrency가 필요합니다. Queue Depth·Age·Waiting/Service Time·Throughput을 함께 봅니다. 그런데 Queue에서 또 자주 생기는 문제가 있습니다. 앞의 작업 A가 30초, 뒤의 B·C가 100ms여도 한 Worker가 순서대로 처리하면 B·C는 A 때문에 오래 기다립니다. 이처럼 Queue 앞쪽의 느린 작업 때문에 뒤쪽의 빠른 작업까지 지연되는 현상을 Head-of-Line Blocking(HOL Blocking)이라고 합니다.