2.7 대기 행렬 이론

개요 및 동기

대기 행렬 이론은 대기 줄에 대한 수학적 연구다. 전달 파이프라인이 실제로 얼마나 많이 대기열인지 알아채기 전까지는 소프트웨어 엔지니어링 메트릭에 관한 책에 이상하게 어울리지 않는 것처럼 들린다: 리뷰어를 기다리는 풀 리퀘스트, CI 러너를 기다리는 커밋, 접수되기를 기다리는 티켓, 응답을 기다리는 고객 지원 메시지. 주제 2.4는 이미 플로우 로드와 플로우 타임을 소개하고 가치 흐름에 과부하를 주는 것이 전달을 급격하게 느리게 만든다는 것을 보여 주었으며, 주제 2.5와 주제 2.6은 대부분의 전달 시간이 작업 시간이 아니라 대기 시간이라는 것을 보여 주었다. 대기 행렬 이론은 단지 관측된 패턴이 아니라 그 모든 것이 왜 참인지 설명하는 근본적인 수학이다.

가장 유용한 단일 결과는 운영 연구자 John Little이 1961년에 증명한 정리인 리틀의 법칙이다: 안정적인 시스템에서 평균 아이템 수는 아이템이 도착하는 평균 비율에 각 아이템이 시스템에서 보내는 평균 시간을 곱한 것과 같다. 주제 2.4는 이미 이 결과를 플로우 프레임워크 자체의 이름 아래 사용했다, 플로우 로드는 도착률 곱하기 플로우 타임과 같다. 이 책의 더 넓은 어휘에서 그것은 또한 진행 중 작업(주제 2.5)은 새로운 작업의 도착률 곱하기 사이클 타임(주제 2.6)과 같다고도 읽힌다. 이것은 경험 법칙이나 일부 연구에서 관측된 상관관계가 아니다. 그것은 대기열이 무엇을 처리하고 있든, 혹은 다음에 무엇을 작업할지 어떻게 결정하든 어떤 안정적인 대기열에 대해서도 성립하는 증명이다.

대규모 팀에게 그 일반성이 핵심이다. 리틀의 법칙은 대기열이 칸반 보드든, 메시지 브로커든, 공유된 CI 파이프라인이든 동일하게 작동하는 온전성 검사를 제공한다. 측정된 진행 중 작업, 도착률, 사이클 타임이 대략 그 방정식을 만족하지 않는다면, 당신의 세 수치 중 하나가 틀린 것이며, 보통 “진행 중”이나 “도착”으로 집계되는 것에 대한 일관성 없는 정의 때문이다. 엔터프라이즈와 정부 조직은 한 번에 이러한 대기열을 수십 개 운영한다, 공유 코드 리뷰 풀, 공유 테스트 환경, 공유 승인 위원회 등이며, 리틀의 법칙은 잘못된 인력 배치나 프로세스 결정을 이끌기 전에 나쁜 메트릭 정의를 잡아내기 위해 이용 가능한 가장 저렴한 도구다.

핵심 원칙

리틀의 법칙은 경험칙이 아니라 증명이다. 진행 중 작업은 어떤 안정적인 대기열에 대해서도 도착률 곱하기 사이클 타임과 같으며, 이는 당신의 전달 메트릭이 내부적으로 일관성이 있는지에 대한 빠른 확인이다.
가동률은 대기 시간과 선형으로 확장되지 않는다. 공유 자원이 완전한 가동률에 접근함에 따라, 대기열 지연은 점진적으로가 아니라 급격하게 자란다. 95% 바쁘게 실행되는 자원은 흔히 80%로 실행되는 자원보다 단지 “약간 더 나쁜” 것이 아니라 여러 배 더 오래 기다린다.
대기열의 평균은 그 최악의 경우를 숨긴다. 평균 대기 시간만 보고하는 것은 용량 근처의 길고 고통스러운 꼬리를 감추며, 이는 정확히 주제 1.6이 평균 대신 백분위수를 사용하는 것에 대해 경고하는 것이다.
대기열이 정의되는 방식은 다른 어떤 메트릭만큼이나 쉽게 게임당할 수 있다. 무언가가 “도착했다”, “진행 중이다”, 혹은 “처리되었다”로 집계되는지는 하나의 선택이며, 작업에 실제로 일어나는 일을 바꾸지 않으면서 대시보드를 치장하도록 조정될 수 있다.
파이프라인은 보통 대기열의 대기열이다. 전달 파이프라인은 여러 단계를 함께 연결하며, 가장 느린 단계가 다른 것들이 얼마나 빠르게 실행되는지와 무관하게 전체 체인의 속도를 결정한다.

권장 사항

우리 자신의 수치를 신뢰하기 전에 리틀의 법칙을 사용해 확인하라

당신 팀의 측정된 평균 진행 중 작업, 주당 평균 새 아이템 도착률, 그리고 평균 사이클 타임을 가져와, 진행 중 작업이 대략 도착률 곱하기 사이클 타임과 같은지 확인하라. 그렇지 않을 때, 이론이 틀렸다고 가정하지 마라. 실제 원인을 찾아보라: 일관성 없이 집계된 단계 경계, “차단됨” 상태로 앉아 있지만 여전히 진행 중으로 집계되는 작업, 혹은 사이클 타임과 다른 창에 걸쳐 측정된 도착률. 이 단일한 확인은 대부분의 팀이 다른 어떤 방법으로도 발견하지 못하는 더 많은 잘못된 계측을 잡아낸다.

용량이 제약된 모든 공유 자원에 대해 가동률을 직접 추적하라

당신의 전달 파이프라인이 많은 팀에 걸쳐 공유하는 자원, 즉 코드 리뷰 풀, CI 클러스터, 스테이징 환경을 식별하고, 그것을 한계 근처에서 실행할 계획을 세우기 전에 각각이 이용 가능한 용량의 비율로 얼마나 바쁘게 실행되는지 측정하라. 완전한 용량 근처에서 실행되는 공유 리뷰어 그룹은 그것을 야기한 수요의 온건한 증가보다 훨씬 더 빠르게 자라는 리뷰 대기열 대기 시간을 만들어 내며, 이는 정확히 주제 2.9가 첫 리뷰까지의 시간을 선행 지표로 지켜보라는 조언 뒤에 있는 역학이다.

도착률, 성공률, 실패율, 생략율을 분리하라

대기열을 떠나는 모든 것을 단일한 “처리량”이나 “서비스율” 수치로 무너뜨리려는 유혹을 물리쳐라. 네 가지를 별도로 추적하라: 작업이 얼마나 빠르게 도착하는지, 그중 얼마나 많은 것이 성공적으로 끝나는지, 얼마나 많은 것이 실패해 재작업이 필요한지, 그리고 얼마나 많은 것이 누군가 끝내기 전에 포기되거나 조용히 버려지는지. 생략율이 조용히 오른 것 때문에 빨라 보이는 파이프라인은 실제로 더 많이 전달하고 있는 것이 아니며, 이 네 가지 비율을 별도로 추적하는 것만이 당신에게 그것을 보여 줄 것이다.

다단계 파이프라인을 대기열의 대기열로 모델링하라

전달 파이프라인, 혹은 어떤 다단계 프로세스, 즉 인시던트 생애주기, 채용 파이프라인이든, 그것을 “시간”의 미분화된 하나의 덩어리가 아니라 대기열의 체인으로 취급하라. 전체 도착률은 첫 번째 단계에 의해 설정되고, 전체 완료율은 마지막 단계에 의해, 그리고 파이프라인의 총 오류 및 생략 개수는 모든 단계 자체의 합이다. 이 프레이밍은 어느 단계에 투자할 가치가 있는지 즉시 알려준다: 계측하기 가장 쉬운 단계가 아니라, 높은 가동률과 높은 실패나 생략율의 최악의 조합을 가진 단계다.

처리량뿐 아니라 가동률을 염두에 두고 인력 배치와 WIP 제한을 설정하라

팀에게 몇 명의 리뷰어나 CI 러너가 필요한지 결정할 때, 평균 도착률에 정확히 맞춰 용량을 산정하지 마라. 평균적으로 100% 가동률로 실행되는 대기열은 실제로는 사실상 무한한 대기 시간을 가지는데, 실제 도착은 완벽하게 매끄러운 것이 아니라 고르지 않기 때문이다. 의도적으로 여유 공간을 계획하고, “우리의 리뷰어들은 거의 항상 바쁘다”를 효율적인 자원 배분의 증거가 아니라 다가올 대기 시간에 대한 경고 신호로 취급하라.

트레이드오프: 장단점

접근법	장점	단점
공식적인 대기열 모델 없음, 직감에 의한 인력 배치	시작하기 빠름; 팀을 위한 새로운 어휘 없음	완전한 용량 근처에서 대기 시간이 어떻게 폭발하는지 일관되게 과소평가함
기존 메트릭에 대한 온전성 확인으로서의 리틀의 법칙	저렴하고, 새로운 도구가 필요 없으며, 잘못된 정의를 빠르게 잡아냄	일관성만 확인할 뿐 그 자체로 원인을 진단하지는 않음
완전한 대기열 시뮬레이션 (도착 분포, 다중 서버)	부하 아래서 대기 시간 행동에 대한 가장 정확한 예측	대부분의 팀이 유지하지 못할 진정한 통계적 기술과 유지 보수가 필요함
더 깊은 모델링 없이 공유 자원에 대한 가동률 추적	단순하고, 실행 가능하며, 폭주하는 대기 시간의 단일한 가장 큰 원인을 잡아냄	왜 가동률이 높은지나 근본 원인에 대해 무엇을 해야 할지에 대해서는 아무것도 말해 주지 않음

핵심 긴장은 엄격함 대 채택이다. 완전한 대기열 시뮬레이션은 가장 정확한 답을 주지만, 거의 어떤 엔지니어링 팀도 그것을 구축하고 유지하지 않을 것이며, 아무도 신뢰하거나 갱신하지 않는 모델은 모델이 없는 것보다 더 나쁘다. 리틀의 법칙과 기본적인 가동률 추적은 약간의 정밀함을 포기하지만 전문화된 통계 기술이 필요 없으며 주제 2.4부터 주제 2.6까지를 위해 팀이 이미 수집하는 메트릭에 직접 들어맞는다. 그 저렴하고 채택 가능한 확인을 기본으로 삼고, 완전한 시뮬레이션은 단일한 공유 자원, 즉 대형 CI 플릿이나 전문화된 리뷰 풀이 그 투자를 정당화할 만큼 충분히 비싼 드문 경우를 위해 남겨 두라.

팀과 논의할 질문

우리가 측정한 진행 중 작업, 도착률, 사이클 타임은 실제로 리틀의 법칙을 만족하는가, 그렇지 않다면 왜인가? 이것은 잘못된 메트릭 정의에 대해 이용 가능한 단일한 가장 빠른 진단이다. 실제 수치를 함께 살펴보고, 그 방정식이 대략 성립하지 않는다면, 확인을 무시하는 대신 그 불일치를 특정한 정의상의 불일치로 추적하라.
우리의 전달 파이프라인에서 어떤 공유 자원이 완전한 가동률에 가깝게 실행되고 있으며, 우리는 실제로 그것들의 가동률 수치를 알고 있는가? 대부분의 팀은 “항상 바쁘게 느껴지는” 자원의 이름을 댈 수 있지만 그 가동률을 직접 측정한 적이 없다. 가장 제약된 두세 개의 공유 자원을 식별하고 각각에 대한 실제 수치를 얻어라.
우리는 성공, 실패, 생략을 하나의 처리량 수치로 섞고 있는가, 그리고 그것들을 분리한다면 우리는 무엇을 볼 것인가? 품질이 떨어지거나 작업이 조용히 포기되는 동안에도 단일한 “완료된 아이템” 개수는 오를 수 있다. 최근 기간의 처리량을 세 개의 별도 수치로 다시 계산하고 그 분할이 섞인 수치가 숨겼던 무엇을 드러내는지 논의하라.
우리 파이프라인에서 진짜 병목, 즉 하류의 모든 것의 속도를 결정하는 가장 느린 단계는 어디인가? 팀은 흔히 실제로 총 처리량을 제약하는 단계가 아니라 개선하기 가장 쉬운 단계에 투자한다. 높은 가동률과 높은 실패나 생략율의 최악의 조합을 가진 단계를 식별하라.
만약 우리가 가장 제약된 공유 자원에 용량을 추가한다면, 대기 시간이 실제로 개선될까, 아니면 수요가 단순히 그것을 채우기 위해 확장될까? 이 질문은 진정한 용량 부족을 수요 문제로부터 분리하며, 그 답은 올바른 해결책이 더 많은 인력인지, WIP 제한인지, 혹은 작업이 대기열에 들어가기 전에 우선순위가 매겨지는 방식의 변화인지를 바꾼다.
작업에 실제로 일어나는 일을 바꾸지 않으면서 대시보드를 더 좋아 보이게 만드는 방식으로 “진행 중”이나 “도착”으로 집계되는 것을 재정의한 적이 있는가? 이것은 가상의 우려로 취급하는 대신 지난 1년의 실제 사례로 정직하고 구체적으로 물어볼 가치가 있다.

분야별 관점

스타트업. 소수의 엔지니어만으로는 대부분의 대기열이 공식적인 대기열 분석이 과할 만큼 충분히 짧다. 유용한 습관은 더 작다: 한 사람, 흔히 가장 고참 엔지니어가 다른 모든 것이 기다리는 사실상의 공유 자원이 되었을 때를 알아채고, 그 뒤에 어떤 공식적인 모델도 없더라도 그것을 이름 붙일 가치가 있는 가동률 문제로 취급하라.

중소기업. 소규모 비즈니스 팀은 진정으로 공유되는 하나나 두 개의 자원, 흔히 단일한 리뷰어나 단일한 배포 파이프라인에 대한 가동률을 추적하고 “보통 이용 가능함”이 조용히 “보통 병목”이 되는 지점을 지켜보는 것보다 더 정교한 것이 거의 필요하지 않다. 스프레드시트면 충분하다. 이 규모에서는 전용 도구가 필요하지 않다.

엔터프라이즈. 공유 자원은 엔터프라이즈 규모에서 빠르게 증식한다: 중앙 플랫폼 팀, 공유 보안 리뷰 위원회, 수십 개의 제품 팀에 서비스하는 공유 CI 플릿. 이것들은 정확히 가동률 추적이 제 몫을 하는 자원인데, 단일한 과부하된 공유 자원이 그것에 의존하는 모든 팀의 전달 시간을 조용히 저하시킬 수 있고, 어떤 개별 팀 자체의 메트릭도 그들 자신의 파이프라인 바깥에 있는 원인을 드러내지 않을 것이기 때문이다.

정부. 다중 기관, 다중 공급업체 전달 프로그램은 흔히 어떤 단일 팀도 통제하거나 스스로 크기를 조정할 수 없는 공유 승인 위원회, 공유 보안 인증 프로세스, 공유 테스트 환경을 통해 작업을 라우팅한다. 이러한 공유 게이트, 즉 도착률, 용량, 가동률에 대한 대기열 분석은 용량을 추가하거나 작업이 게이트에 도달하기 전에 어떻게 일괄 처리되는지를 바꾸는 것에 대한 비즈니스 사례를 위해 흔히 이용 가능한 가장 명확한 증거다.

사례

엔터프라이즈. 한 클라우드 인프라 제공업체의 내부 플랫폼 팀은 어떤 개별 팀도 작업 방식을 바꾸지 않았음에도 그것의 공유 CI 플릿에 의존하는 모든 제품 팀에 걸쳐 변경에 대한 리드 타임(주제 2.10)이 기어올랐다는 것을 알아챘다. 가동률 분석은 핵심 시간 동안 그 플릿이 90% 이상 바쁘게 실행되고 있다는 것을 발견했으며, 이는 대기 행렬 이론이 대기 시간이 점진적으로가 아니라 급격하게 자란다고 예측하는 지점을 훨씬 넘어선 것이었다. 플랫폼 팀은 CI 용량을 추가하고 어떤 단일 팀의 활동 폭증도 대기열을 독점할 수 없도록 공정 분배 스케줄링 정책을 도입했다. 중앙값 CI 대기 시간은 한 달 안에 절반 넘게 떨어졌으며, 이는 병목이 줄곧 공유되고 보이지 않는 대기열이었다는 증거였다.

정부. 한 국가 허가 기관의 디지털 서비스 팀은 2년 동안 신청 처리를 단일한 “주당 종결된 사례” 처리량 수치로 추적했으며, 그 수치는 안정적으로 보였다. 그 수치를 승인된 사례, 거부된 사례, 그리고 오랜 지연 후 신청자에 의해 포기된 사례로 나눈 더 자세한 분석은 승인이 정체된 채로 유지되는 동안 같은 기간 동안 포기율이 거의 세 배가 되었다는 것을 발견했다. 사례 담당자 대기열에 적용된 리틀의 법칙은 진행 중 작업이 팀이 명시한 평균 처리 시간이 시사하는 것보다 훨씬 더 많이 자랐다는 것을 보여 주었으며, 이는 사례들이 “대기 중”으로 집계되지 않는 상태로 조용히 쌓이고 있었다는 것을 의미했다. 그 기관은 모든 열린 사례를 정직하게 집계하도록 사례 추적 정의를 재구성했고 가동률을 85% 미만으로 유지하기 위한 크기의 사례 담당자 역량을 추가했으며, 이는 이제 처리량 수치와 함께 상시적인 운영 목표로 추적된다.

비즈니스 사례: 동기, ROI, TCO

기본적인 대기 행렬 분석을 적용하는 것의 수익은 “파이프라인이 느리게 느껴진다”를 실제 원인을 놓치는 “더 빠르게 일하라”는 막연한 압박이 아니라 구체적이고 방어 가능한 결정, 즉 이 공유 자원에 여유 공간을 추가하라, 이 섞인 메트릭을 그 실제 구성 요소로 나누라로 바꾸는 것이다. 위의 클라우드 인프라 사례, 즉 개별 팀의 행동에 대한 어떤 변화도 없이 용량 및 스케줄링 수정으로 대기 시간을 절반으로 줄인 것은 이 분석이 신뢰성 있게 만들어 내는 패턴이다: 해결책은 그들이 볼 수 없는 병목 주위에서 모든 하류 팀에게 더 빠르게 움직이라고 요청하는 것보다 거의 항상 더 저렴하다.

도입의 총비용은 진정으로 낮다. 리틀의 법칙과 가동률 추적은 주제 2.4부터 주제 2.6까지가 이미 당신에게 수집하도록 요구하는 것, 즉 도착률, 진행 중 작업, 사이클 타임 이상의 어떤 새로운 도구도 필요로 하지 않는다. 투자는 대체로 분석적 규율이다: 수치를 서로 확인하고 공유 자원이 조직의 다음 설명되지 않는 리드 타임 퇴보가 되기 전에 그 가동률을 주기적으로 검토하는 것.

안티패턴과 함정

공유 자원의 용량을 그 평균 도착률에 정확히 맞춰 산정하기: 수요가 잠깐이라도 고르지 않을 때마다 높은 가동률과 폭주하는 대기 시간을 보장한다.
평균 대기 시간만 보고하고 결코 백분위수를 보고하지 않기: 그 안에서 기다리는 사람들에게 가장 중요한 긴 꼬리를 숨긴다.
성공, 실패, 생략을 하나의 처리량 수치로 섞기: 이 주제의 핵심에 있는 게임 벡터다. 압박을 받는 팀은 포기된 티켓, 조용히 버려진 요청, 결코 실패로 집계되지 않는 작업 등 생략율이 조용히 오르게 둠으로써 처리량을 건강해 보이게 만들 수 있다. 가드레일은 도착, 성공, 실패, 생략율을 네 개의 별도이고 눈에 보이는 수치로 추적하는 것이며, 이는 이 책의 모든 메트릭에 대해 주제 1.2가 요구하는 것과 동일한 규율이다. 그래야 상승하는 생략율이 평평한 처리량 차트 뒤에 숨을 수 없다.
“우리 사람들은 항상 바쁘다”를 칭찬으로 취급하기: 그것은 길고 예측 불가능한 대기 시간의 주된 원인인 높은 가동률의 증상이다.
“진행 중”을 재정의해 조용히 진행 중 작업을 줄이기: 완료하는 데 걸리는 시간을 바꾸지 않으면서 작업을 “차단됨”, “보류 중” 같은 집계되지 않는 상태로 옮기며, 그렇지 않았다면 그것을 잡아냈을 리틀의 법칙 확인을 무너뜨린다.
대기열 모델이 일단 구축되면 유지 보수가 필요 없다고 가정하기: 도착 패턴과 용량은 끊임없이 바뀌며, 낡은 모델은 자신 있지만 틀린 예측을 만들어 낸다.

성숙도 모델

1단계, 시작: 어떤 대기열도 명시적으로 측정되지 않는다. 대기 시간은 “일이 느리게 느껴진다”고 일화적으로 논의된다.
2단계, 개발: 도착률, 진행 중 작업, 사이클 타임이 적어도 하나의 파이프라인에 대해 추적되지만, 리틀의 법칙이나 공유 자원의 가동률에 비추어 결코 확인되지 않는다.
3단계, 표준화: 리틀의 법칙은 전달 파이프라인 전반의 일상적인 일관성 확인이며, 가장 중요한 공유 자원에 대해 가동률이 명시적으로 추적된다.
4단계, 관리: 성공, 실패, 생략율이 모든 중요한 대기열에 대해 별도로 추적되며, 용량 결정은 단지 평균 수요가 아니라 가동률 목표를 사용한다.
5단계, 조율: 조직은 그 주요 파이프라인을 대기열의 대기열로 모델링하고, 체계적으로 진짜 병목을 식별하며, 대기 행렬 분석 때문에 만들어진 구체적인 용량이나 프로세스 변경을 그것을 위한 측정된 대기 시간 개선과 함께 제시할 수 있다.

논의를 위한 아이디어

우리의 전달 파이프라인 중 하나를 골라 그 수치가 오늘 리틀의 법칙을 만족하는지 확인하라.
대부분의 사람들이 “항상 바쁘다”는 데 동의할 조직 내 단일한 공유 자원의 이름을 대고 그 실제 가동률 수치를 찾아보라.
지난 분기의 성공, 실패, 생략율로 나눈다면 우리의 처리량 차트는 어떻게 보일까?
올해 정확히 하나의 공유 자원에 용량을 추가해야 한다면, 어느 것이며, 어떤 증거가 그것을 정당화할까?

핵심 요약

리틀의 법칙, 진행 중 작업은 도착률 곱하기 사이클 타임과 같다는 것은 경험칙이 아니라 증명이며, 당신의 전달 메트릭이 내부적으로 일관성이 있는지에 대해 이용 가능한 가장 저렴한 확인이다.
가동률이 완전한 용량에 접근함에 따라 대기 시간은 점진적으로가 아니라 급격하게 자란다. “항상 바쁘다”를 칭찬이 아니라 경고 신호로 취급하라.
도착률, 성공률, 실패율, 생략율을 별도로 추적하라. 그것들을 하나의 처리량 수치로 섞는 것이 이 주제의 핵심 게임 벡터다.
다단계 파이프라인을 대기열의 대기열로 모델링하고, 개선하기 가장 쉬운 단계가 아니라 높은 가동률과 높은 실패나 생략율의 최악의 조합을 가진 단계에 투자하라.
대부분의 팀이 유지하지 못할 완전한 대기열 시뮬레이션보다 저렴하고 채택 가능한 확인인 리틀의 법칙과 가동률 추적을 선호하라.

참고 문헌 및 추가 자료

Little, John D. C. “A Proof for the Queuing Formula: L = λW.” Operations Research, 1961.
Kleinrock, Leonard. Queueing Systems, Volume 1: Theory. Wiley-Interscience, 1975.
Wescott, Bob. The Every Computer Performance Book: How to Avoid and Solve Performance Problems on the Computer Systems You Work With. CreateSpace Independent Publishing Platform, 2013.
Reinertsen, Donald G. The Principles of Product Development Flow: Second Generation Lean Product Development. Celeritas Publishing, 2009.
Vacanti, Daniel S. Actionable Agile Metrics for Predictability. Actionable Agile Press, 2015.