golang 비동기. 대기행렬이론과 이벤트루프 안전성
이번에는 golang에 대한 주제보다 일반적으로 큐를 사용하는 시스템에 대한 분석을 진행해보겠습니다. 흔히 큐를 다루는 이론은 queuing theory(대기행렬이론)이라 부르는 수리적 이론에서 다루고 있습니다. 해당 이론에서 다루는 주요 방정식을 가볍게 살펴보고 이론을 기반으로 큐를 사용하는 시스템에서 안정적으로 큐를 쓰기 위한 몇 방법을 학습해봅시다.
대기행렬이론
대기행렬이론은 고객이 서비스를 받기 위해 기다리는 상황을 분석하는 이론입니다. 이 이론에서 서비스 시스템은 고객이 도착하여 대기하고 서비스를 받고 나가는 과정을 모델링합니다. 고객이 대기하는 시스템은 프로그래밍에서 흔히 큐라는 자료구조로 구현되고 활용됩니다. 이벤트루프에서 고객은 이벤트로 간주할 수 있습니다. 따라서 해당 이론에서 다루는 부분을 이전에 설계한 이벤트루프에 상황을 대입해볼 수 있습니다.
대기행렬이론에서 다루는 큐에 대한 모델은 크게 다음 변수를 이용하여 구분하고 kendall’s notation이라는 규칙으로 표현합니다. 일반적으로 A/B/C으로 표현합니다.
- A: 도착 프로세스의 확률 분포: 도착하는 고객(이벤트) 시간의 분포
- B: 서비스 프로세스의 확률 분포: 각 고객(이벤트)이 서비스를 받는(처리되는) 시간의 분포
- C: 서버의 수(디스패처 수)
흔히 분포는 다음을 이용합니다.
- M(markovian, memoryless): 가장 많이 분석된 분포로 확률 분포가 지수 분포를 나타냅니다.
- D(degenerate distribution): 고정 상수 확률 분포를 갖는 분포입니다.
- G(general): 어떤 분포 상태를 가정하지 않는 일반 분포입니다.
보통 가장 많이 다루는 분포는 지수 분포인 M입니다. 이는 지수 분포가 메모리리스 특성을 가지고 있기 때문입니다. 한편 지수 분포가 아닌 일반적인 하나의 서버에 대한 확률 분포는 G/G/1 큐로 나타낼 수 있습니다. 이때 G/G/1 큐에 대하여 Lindley’s equation을 이용하여 n번째 고객의 대기 시간 W_n을 다음과 같이 귀납적으로 표현할 수 있습니다.
\[W_{n+1} = \max{(0, W_{n}+S_{n} - T_{n})}\]여기서 S_n은 n번째 고객의 서비스 시간, T_n은 n번째 고객과 (n+1)번째 고객 사이의 도착 시간 간격을 의미합니다. 만약 이벤트루프에서 이벤트가 큐를 통하여 처리되는 시스템의 경우 S_n은 이벤트가 디스패처에서 처리되는 속도에 관계되는 값이고 T_n은 이벤트가 얼마나 빠르게 유입되는지 관련된 값입니다. 위의 수식은 이산적인 경우만 분석하여 그리 중요하지 않겠지만 이론에서 다루는 내용은 큐에서 대기하는 시간은 이벤트 유입에 관계된 시간과 처리에 관계된 시간의 연산으로 표현된다는 점입니다. 따라서 일반적으로 큐의 데이터가 어떠한 분포를 따르는 것은 큐의 특성을 이해하는 데 중요한 성질이 됩니다. 특히 이 분포에 따라 분포의 모수로 큐의 특성을 결정할 수 있습니다.
- 이벤트루프의 이벤트 디스패칭에 대한 처리 시간 분포
- 이벤트 발행량에 대한 분포
만약 이벤트 발행과 처리의 분포가 메모리리스한 특성을 가진다면 분포는 지수 분포를 따르게 되고 이는 M/M/1 큐로 분석할 수 있습니다.
이벤트 발행/처리 시간에 대한 분포와 서비스 안전성의 관계
앞서 설명한 바에 따르면 이벤트 발행과 처리를 어떤 특정한 확률 분포로 묘사할 수 있으면 해당 이벤트루프 모델을 기존에 분석된 큐 모델을 가져와서 대입할 수 있다는 것을 알았습니다. 가장 기본적으로 이벤트 발행/처리에 대하여 지수 분포를 가정한 경우 큐의 특성에 대한 분석을 쉽게 진행할 수 있습니다. 그런데 왜 지수 분포를 가정하는 게 가장 편할까요? 그 이유는 지수 분포는 메모리리스 특성을 가지고 있기 때문입니다. 메모리리스 특성을 간단하게 설명하면 다음과 같습니다.
메모리리스 특성은 임의의 시간 t가 지나더라도 그 시점에 대하여 앞으로 이벤트가 발생할 확률이 처음 분포 상태와 동일함을 의미합니다. 이를 수식으로 표현하면
\[P(X>s+t|X>s)=P(X>t)\]인 특성을 갖음을 의미합니다. s는 지금까지 기다린 시간, t는 추가로 기다릴 시간을 의미한다고 할 때 해당 수식의 좌변은 X>s인 상황에서 X>s+t일 확률을 의미하고 우변은 전체 분포에서 X>t일 확률을 의미합니다.
위 특성을 만족하는 연속확률분포는 지수 분포이며, 그 확률 밀도 함수는 다음과 같습니다.
\[f(x;\lambda)= \lambda e^{-\lambda x} (x \ge0)\]지수 분포의 평균은 1/λ로 나타납니다.
여기서 만약 이벤트루프에 유입되는 이벤트가 평균적으로 단위 시간 1에 2번 들어오고 지수분포를 따르고 있다고 하면 λ=1/2가 되겠습니다. 따라서 평균의 단위는 시간이므로 λ는 시간의 역인 단위 시간당 발생 회수, 발생률을 나타냅니다. 따라서 유입되는 트래픽의 양의 평균을 알고 있고 해당 트래픽이 메모리리스 특성을 가진다면 M/M/1 특성으로 분석할 수 있습니다. M/M/1인 경우 도착률 λ과 처리율 μ로 큐의 특성을 분석할 수 있습니다.
일반적으로 유입되는 트래픽은 지수 분포를 따릅니다. 왜냐하면 고객이 서로가 서로에게 영향을 미치지 않고 고객이 유입될 확률은 현재와 현재에서 시간이 지났을 때와 다르지 않기 때문입니다. 물론 고객 유입이 시간에 대한 변동성이 크다면, 예를 들어 피크 형식으로 발생하는 부하인 경우 분포를 따르지 않겠지만 일반적으로 완만한 부하에 대하여 지수분포를 따른다고 가정할 수 있겠습니다.
이벤트루프의 경우를 살펴봅시다. 이벤트루프에 발행되는 이벤트 유입에 대한 분포는 지수 분포를 가정할 수 있습니다. 그러나 이벤트 처리는 지수 분포를 가정하기 어려울 수 있습니다. 어렵게 만드는 요인은 다음이 있습니다.
- 만약 디스패칭 시 블로킹 로직이 호출되어 시스템이 제어할 수 없는 상태에 빠지는 경우
- 디스패처끼리 임계 영역에 대하여 경쟁 상태를 가지는 경우
- 디스패칭 시 데드락이 발생하여 디스패처가 동작하지 않는 경우
따라서 큐를 예측하기 위한 상태로 만들기 위해 락과 블로킹을 최소화할 수 있습니다. 그러나 락과 블로킹과 같은 작업이 꼭 필요한 경우도 존재합니다. 이런 경우 안전하게 큐를 동작시킬 다른 방법을 생각해야 하는데 바로 디스패처가 실행되는 시간의 상한을 지정하는 것입니다. 따라서 작업이 일정 시간 이상 실행된 경우 작업을 취소하고 실패에 대한 처리를 하거나 이미 처리가 힘들 것으로 예측되면 아예 이벤트를 바로 취소할 수 있습니다. 물론 이런 설계가 지수 분포로 만들어주진 않지만, 평균을 무조건 상한 시간 이내로 만들 수 있습니다. 이런 안전성 패턴을 golang에서는 context 패키지를 이용하여 쉽게 구현할 수 있습니다. 예를 들어, context를 이용한 타임아웃 패턴의 경우 다음 코드처럼 쉽게 구현이 가능합니다.
func doSomething(timeout time.Duration) {
ctx, cancelFunc := context.WithTimeout(context.Background(), timeout)
defer cancelFunc()
// ...
ch, err := callOtherService()
if err != nil {
// ...
}
select {
case event, ok := <-ch:
// ...
case <-ctx.Done():
// timeout or 외부에서 취소 주입에 대한 처리
}
}
마찬가지로 이벤트를 발행하는 측도 이런 처리를 포함하여 이벤트루프에 이벤트를 발행하는 데 오래 걸리는 경우 취소 처리를 추가하여 서비스를 더 안전하게 구현할 수 있습니다.
주요 요약입니다.
- 대기행렬이론을 이용하여 이벤트루프를 분석할 수 있는데 이때 이벤트 발행과 처리에 대한 시간 분포가 중요합니다.
- 특히 메모리리스 특성을 따르는 지수분포를 이용하면 큐의 특성을 쉽게 이해할 수 있습니다.
- 이 특성을 방해하는 요소로 블로킹, 락 로직을 최소화해야 합니다. 만약 이런 방법이 어렵다면 golang의 context를 이용하여 안전성 패턴을 활용할 수 있습니다.
다음은 context에 대하여 알아보겠습니다.
참고자료
Leave a comment