큐잉 이론

큐잉 이론은 줄을 서서 기다리는 데 얼마나 걸릴지를 미리 따져 보는 분야입니다. 일이 들어오는 속도와 처리하는 속도가 이 계산의 입력입니다. 평균 몇 건이 밀려 있는지와 한 건이 얼마나 기다리는지가 답으로 나옵니다. 서버를 몇 대 둘지, 어느 선까지 밀어 넣어도 되는지를 이 계산으로 정합니다.

쉽고 빠른 이해

큐잉 이론은 기다리는 줄의 길이와 기다리는 시간을 계산으로 미리 아는 방법입니다. 초당 들어오는 요청 수와 한 건에 걸리는 처리 시간만 있으면 평균 대기가 나옵니다.

이게 없으면 서버 대수나 스레드 수를 감으로 정하게 됩니다. 어디까지 밀어 넣어도 되는지를 한 번 터뜨려 본 뒤에야 알게 됩니다.

도는 모양은 셋입니다.

1. 들어오는 속도와 처리하는 속도를 잽니다
2. 둘을 나눠 얼마나 바쁜지를 구합니다
3. 바쁜 정도가 한계에 가까울수록 대기가 급하게 늘어난다는 관계로 대기 시간을 읽습니다

대가가 있습니다. 이 계산은 요청이 서로 상관없이 도착하고 부하가 한동안 일정하다는 전제 위에 섭니다. 전제가 깨진 순간의 계산값은 실제 대기보다 짧게 나옵니다. 실패한 요청이 한꺼번에 다시 몰리는 순간이 그렇습니다.

상세

마트 계산대 앞에 줄이 생기는 것을 떠올려 봅니다. 손님은 고른 간격으로 오지 않고, 계산에 걸리는 시간도 사람마다 다릅니다. 계산원이 하루 동안 놀지 않을 만큼만 손님이 와도 어떤 순간에는 줄이 생깁니다.

줄이 얼마나 길어질지를 미리 모르면 서버를 몇 대 둘지, 동시에 몇 건까지 처리하게 할지를 한 번 터뜨려 본 뒤에 정하게 됩니다. 큐잉 이론은 이 줄을 감이 아니라 숫자로 다룹니다.

서버는 한꺼번에 못 처리할 만큼 일이 몰리면 그 일들을 큐에 세워 두고 하나씩 꺼내 씁니다. 큐잉 이론은 이 줄 하나를 모형으로 놓고 평균 몇 건이 기다리는지와 한 건이 얼마나 기다리는지를 구합니다.

줄이 생기는 까닭

줄은 처리 능력이 모자랄 때만 생기는 것이 아닙니다. 들어오는 시각과 한 건의 처리 시간이 들쭉날쭉하기만 해도 생깁니다.

요청이 꼭 1초 간격으로 오고 처리도 꼭 1초씩 걸린다면 줄은 서지 않습니다. 앞 건이 끝나는 순간에 다음 건이 오기 때문입니다. 현실의 요청은 이렇게 오지 않습니다.

두 건이 같은 순간에 몰리면 한 건은 기다립니다. 기다리는 동안 다음 건이 또 오면 줄이 이어집니다. 평균만 보면 여유가 있어 보여도 이런 순간이 쌓여 대기가 생깁니다.

flowchart TD
    subgraph even["고른 간격으로 올 때 · 3초에 3건"]
        A1["1초 · 1건 들어옴 · 1건 처리 · 남은 줄 0건"]
        A2["2초 · 1건 들어옴 · 1건 처리 · 남은 줄 0건"]
        A3["3초 · 1건 들어옴 · 1건 처리 · 남은 줄 0건"]
        A1 --> A2 --> A3
    end
    subgraph burst["몰려서 올 때 · 3초에 3건"]
        B1["1초 · 3건 들어옴 · 1건 처리 · 남은 줄 2건"]
        B2["2초 · 0건 들어옴 · 1건 처리 · 남은 줄 1건"]
        B3["3초 · 0건 들어옴 · 1건 처리 · 남은 줄 0건"]
        B1 --> B2 --> B3
    end

두 경우 다 3초 동안 3건을 받고 창구는 1초에 한 건씩 처리합니다. 받은 양도 처리 속도도 같은데 아래쪽만 줄이 섭니다.

그래서 큐잉 이론은 평균값 하나가 아니라 들쭉날쭉한 정도까지 넣어 계산합니다. 같은 평균이라도 들쭉날쭉한 정도가 클수록 줄이 길어집니다.

계산에 넣는 세 숫자

계산은 숫자 셋 위에 섭니다. 앞의 둘은 재는 값이고 셋째는 그 둘을 나눈 값입니다. 아래에서 "창구"는 앞에서 말한 계산원을 가리키고, 실제 시스템에서는 서버 한 대나 스레드 하나입니다.

이 셋은 그리스 글자 λ(람다) · μ(뮤) · ρ(로)로 적는 것이 관례입니다. 논문과 교재에서 이 글자를 만나면 각각 도착률 · 서비스율 · 사용률입니다.

세 숫자가 줄 모형의 어디에 붙는 값인지는 이렇습니다.

flowchart TD
    IN["들어옴 · 도착률 λ"] --> Q
    subgraph sys["시스템"]
        Q["큐 · 기다리는 건수"] --> S["창구 · 서비스율 μ"]
    end
    S --> OUT["나감"]

큐에서 창구를 기다린 시간이 대기 시간이고, 들어와서 나갈 때까지 시스템 안에 머문 시간이 체류 시간입니다. 체류 시간은 대기 시간에 한 건의 처리 시간을 더한 값입니다.

사용률은 0 과 1 사이 값입니다. 0.5 면 창구가 절반의 시간만 일한다는 뜻입니다. 나머지 절반은 비어 있습니다. 1 이면 쉴 틈 없이 일한다는 뜻입니다.

1 을 넘으면 처리하는 것보다 들어오는 것이 많아 밀린 일이 시간이 갈수록 쌓이기만 합니다. 이렇게 쌓이기만 하는 상태를 포화라고 부릅니다. 줄의 길이가 한 값에 머물지 않으므로 평균 대기를 구할 수 없습니다.

사용률이 올라갈 때

대기 시간은 사용률을 따라 나란히 늘지 않습니다.

창구가 하나이고 요청이 서로 상관없이 도착하는 가장 단순한 모형에서, 평균 대기 시간은 한 건을 처리하는 시간의 ρ/(1−ρ) 배입니다. 분모의 1−ρ 가 0 에 가까워지면 이 값이 급하게 커집니다.

xychart-beta
    title "사용률에 따른 평균 대기 시간"
    x-axis "사용률" ["0.5", "0.6", "0.7", "0.8", "0.9", "0.95"]
    y-axis "한 건 처리 시간의 몇 배" 0 --> 20
    line [1, 1.5, 2.3, 4, 9, 19]

가로축은 사용률이고 세로축은 한 건을 처리하는 시간의 몇 배를 기다리는지입니다. 이 그림에서 볼 것은 곡선이 꺾이는 대목입니다. 사용률을 0.5 에서 0.8 로 올리는 동안 대기는 네 배가 됩니다. 0.8 에서 0.9 로 한 걸음 더 올리면 다시 두 배가 넘게 늡니다.

들어오는 양을 늘려 사용률을 한계 가까이 끌어올리면 처리량은 조금 얻고 응답 시간은 많이 내줍니다. 그래서 남은 여유를 얼마나 둘지가 성능 설계의 손잡이입니다.

이 모양은 꼬리 지연이 튀는 까닭이기도 합니다. 평균 응답 시간이 견딜 만해 보여도, 요청이 몰린 순간에 들어온 몇 건은 그보다 훨씬 오래 기다린 뒤에 답을 받습니다.

줄 길이와 기다리는 시간을 잇는 법칙

리틀의 법칙은 줄에 들어 있는 건수와 한 건이 머무는 시간을 잇는 관계입니다. 앞에서 본 도착률(λ)에 한 건이 머무는 시간(W)을 곱하면 안에 들어 있는 평균 건수(L)가 나옵니다 — L = λ × W 입니다.

여기 W 는 앞에서 본 체류 시간입니다. 대기 시간은 줄에서 기다린 시간만이고, W 는 거기에 한 건의 처리 시간까지 더한 값입니다.

이 관계는 요청이 고르게 오든 몰려서 오든 성립합니다. 재는 구간 동안 줄이 계속 길어지지도, 계속 짧아지지도 않으면 됩니다. 언제 몰릴지 모르는 실제 서비스에도 그대로 댈 수 있습니다.

초당 200건을 받고 한 건이 0.05초 머무른다면 시스템 안에는 평균 열 건이 있습니다. 거꾸로 동시에 열 건까지만 처리하도록 묶어 두었다면 그 열이 곧 커넥션 풀이나 스레드 풀의 크기입니다.

풀 크기를 정할 때 이 식을 씁니다. 목표 처리량에 한 건의 체류 시간을 곱하면 동시에 처리하고 있어야 할 건수가 나옵니다.

창구를 늘리는 것과 줄을 합치는 것

기다림을 줄이는 손잡이는 둘입니다. 한 건 처리를 짧게 만들거나 창구를 늘리는 것입니다.

창구가 여럿이면 줄을 어떻게 세우는지가 한 번 더 갈립니다. 창구마다 줄을 따로 세우는 것과 한 줄로 세워 빈 창구로 보내는 것은 창구 수가 같아도 대기가 다릅니다.

flowchart TD
    subgraph 줄을 따로 세운다
        A1["줄 1"] --> S1["창구 1"]
        A2["줄 2"] --> S2["창구 2"]
    end
    subgraph 한 줄로 세운다
        Q["공용 줄"] --> T1["창구 1"]
        Q --> T2["창구 2"]
    end

따로 세우면 한 줄은 비었는데 옆 줄은 밀려 있는 순간이 생깁니다. 한 줄로 세우면 빈 창구가 있는 한 아무도 기다리지 않아 같은 창구 수로 대기가 줄어듭니다.

로드 밸런서 뒤에 같은 서버를 여럿 두는 구성이 이 차이를 다룹니다. 어느 서버로 보낼지를 받는 쪽이 정하면 공용 줄에 가까워집니다. 보내는 쪽이 미리 나눠 버리면 따로 세운 줄에 가까워집니다.

모형에 붙은 이름

지금까지 본 모형에는 이름이 붙어 있습니다. 창구가 하나면 M/M/1, 창구가 여럿이면 M/M/c 라고 부릅니다. 논문과 교재에서 이 표기를 만나면 칸마다 뜻이 정해져 있습니다.

block-beta
    columns 3
    a["M"] b["M"] c["1"]
    d["도착 간격"] e["한 건의 처리 시간"] f["창구 수"]

M 은 기억이 없다는 뜻입니다. 방금 한 건이 들어왔든 한참 조용했든 다음 건이 언제 올지는 달라지지 않는다는 말입니다. 처리 시간도 같습니다.

이 계산이 서 있는 전제

식이 주는 숫자는 전제 위에 섭니다. 전제를 적어 두어야 그 숫자를 어디까지 믿을지 정할 수 있습니다.

전제가 깨지면 계산은 실제보다 짧은 대기를 내놓습니다. 그래서 이론이 준 숫자는 넘지 않을 상한이 아니라 어디가 위험한지를 가리키는 밑그림으로 씁니다.

오토스케일링처럼 창구 수를 도중에 바꾸는 구성도 이 모형 밖입니다. 창구가 늘어나기를 기다리는 동안은 사용률이 1을 넘긴 구간을 지납니다. 그 구간에 쌓인 줄은 창구가 늘어난 뒤에도 한동안 남습니다.

flowchart TD
    P1["부하가 급증한다 · 사용률이 1을 넘는다"] --> P2["창구가 늘기를 기다린다 · 줄이 쌓인다"]
    P2 --> P3["창구가 늘었다 · 쌓인 줄을 빼는 동안 대기가 남는다"]

증설이 끝나는 순간에 대기가 제자리로 돌아오지 않습니다. 그 전에 쌓인 줄을 다 빼고 나서야 돌아옵니다.

관련 항목

큐잉 이론이 모형으로 삼는 구성 요소

큐 · 큐 길이 · 큐 대기 · 대기 시간 · 체류 시간 · 작업 단위

큐잉 이론이 재는 지표

도착률 · 서비스율 · 사용률 · 처리량 · 응답 시간 · 동시 처리 수 · 꼬리 지연

큐잉 이론이 기대는 법칙과 확률 분포

리틀의 법칙 · 포아송 분포 · 지수 분포 · 확률 분포 · 정상 상태 · 평균

줄이 길어질 때 나는 장애

병목 · 포화 · 연쇄 장애 · 타임아웃 · 재시도 폭풍 · 큐 적체

줄 길이를 조절하는 수단

백프레셔 · 부하 차단 · 속도 제한 · 우선순위 큐 · 커넥션 풀 · 스레드 풀 · 오토스케일링 · 로드 밸런서

이 계산에 넣을 값을 재는 작업

부하 테스트 · 성능 테스트 · 용량 계획 · 벤치마크 · 프로파일링