무작위로 딱 둘만 비교해도 왜 쏠림이 크게 줄어들까

‘두 선택의 힘’은 대상 전체를 훑는 대신 무작위로 뽑은 둘만 견주어 덜 바쁜 쪽을 고르는 규칙이다. 이 한 번의 비교만으로 가장 붐비는 곳의 쏠림이 크게 줄고, 후보를 셋, 넷으로 늘려도 더 나아지는 폭은 거의 없다.

고속도로 요금소에 부스가 여럿 열려 있을 때, 우리는 모든 차선의 줄을 일일이 세어 보지 않는다. 그저 가까운 두어 줄만 눈대중으로 견주고, 짧아 보이는 쪽으로 붙을 뿐이다.

밀려드는 요청을 여러 서버에 나눠 맡기는 로드밸런서도 실은 이 눈대중과 똑같은 판단을 한다. 서버가 수천 대라면 전부 재 보는 값이 너무 크니, 몇 대만 슬쩍 견주고 덜 바쁜 쪽에 맡긴다. 그런데 이 가벼운 비교 한 번이 만드는 차이는 놀랄 만큼 크다. 그 차이가 어디서 오는지는, 문제를 공과 통으로 바꿔 놓으면 가장 또렷하게 드러난다.

밝은 크림 배경의 플랫 벡터 인포그래픽. 왼쪽 카드는 운전자가 요금소 부스 한 곳을 무작위로 골라 그 뒤로 차량이 길게 늘어선 장면에 '최대 9배 쏠림' 배지가, 오른쪽 카드는 가까운 두 부스의 줄을 견주어 짧은 쪽으로 붙어 차량이 고르게 짧은 장면에 '최대 4로 뚝' 배지가 붙어 있다.

공 백만 개를 통에 던지면

공 던지기는 이 문제의 뼈대만 남긴 축소 모형이다. 공 100만 개를, 개수가 똑같은 통 100만 개에 하나씩 나눠 던진다고 하자. 공이 완벽하게 고르게 퍼진다면 통마다 한 개꼴로 돌아가니, 이 세계의 평균은 통마다 딱 한 개다.

이제 규칙을 정한다. 공 하나를 던질 때마다 통을 아무렇게나 하나 골라 그 안에 떨어뜨린다. 이 동작을 100만 번 되풀이한 뒤, 가장 붐비는 통을 열어 본다. 평균이 한 개인 세계인데, 그 통에는 공이 아홉 개나 쌓여 있다. 운 나쁘게 공이 몰린 단 하나의 통에 평균의 아홉 배가 담긴 것이다.

규칙을 딱 한 군데만 바꿔 보자. 공을 놓을 때마다 통을 하나가 아니라 두 개 무작위로 뽑고, 그중 지금 덜 찬 쪽에 넣는다. 통의 개수는 그대로고, 여전히 전체를 훑지도 않는다. 바뀐 것은 후보를 하나에서 둘로 늘려 한 번 견준 것뿐이다. 그런데 이번에 가장 붐비는 통을 열면, 공은 네 개밖에 없다.

아홉과 넷. 부스 두 곳을 눈대중으로 견주던 그 사소한 습관이, 붐비는 통의 높이를 절반 넘게 깎아낸 것이다.

그림 1은 같은 실험을 통 900개 규모로 줄여 한눈에 담은 그림이다. 왼쪽은 통을 하나만 골랐을 때, 오른쪽은 둘을 뽑아 덜 찬 쪽에 넣었을 때다. 같은 시드로 같은 공을 던졌는데도 왼쪽에는 유독 밝게 뭉친 칸이 몇 개 튀고, 오른쪽은 결이 고르다. 두 그림이 같은 컬러바를 나눠 쓴다는 점이 중요하다. 붐비는 정도를 같은 자로 재야 아홉과 넷을 정직하게 견줄 수 있기 때문이다. 축소판이라 최댓값은 왼쪽 여섯·오른쪽 셋으로 낮아지지만, 튀고 고른 대비만큼은 그대로다.

같은 시드로 공을 던진 뒤 통별 적재량을 색으로 나타낸 두 격자 패널. 왼쪽 d=1은 몇몇 칸이 유독 밝게 튀고, 오른쪽 d=2는 결이 고르다. — **그림 1.** 같은 900개 공을 같은 시드로 던진 결과. 왼쪽(후보 한 개)은 붐비는 칸이 튀어 최댓값이 높고, 오른쪽(후보 두 개)은 낮게 멈춘다. 두 패널은 같은 컬러바를 공유한다.

규칙의 이름은 ‘두 선택의 힘’

두 격자를 갈라놓은 규칙을 한 줄로 적으면 이렇다. 공 하나를 놓을 자리로 통 두 개를 무작위로 뽑고, 그중 지금 덜 찬 쪽에 넣는다. 이 방법을 흔히 두 선택의 힘(power of two choices)이라 부르고, 짧게는 d=2로 쓴다. 여기서 d는 공 하나를 놓을 때 견주는 후보 통의 수다. 후보를 하나만 보면 d=1, 둘을 보면 d=2인 식이다.

오해하기 쉬운 지점이 둘 있다. 첫째, 이 규칙은 어느 통이 앞으로 빌지 내다보는 영리한 예측이 아니다. 뒤에 무슨 공이 올지는 전혀 모른 채, 지금 이 순간 눈앞의 두 후보만 견줄 뿐이다. 앞을 내다보는 전략이라기보다, 확률과 조합이 저절로 빚어내는 현상에 가깝다.

둘째, 후보를 둘로 늘려도 통 하나가 받는 공의 평균은 꿈쩍하지 않는다. 공의 총량도 통의 개수도 그대로니, 통마다 한 개꼴이라는 평균은 d와 상관없이 늘 1이다. 달라지는 것은 평균이 아니라 꼬리다. 운 나쁘게 공이 몰리는 극단, 그 최댓값만 납작하게 눌린다.

규칙이 한 줄이라는 말은 코드도 한 줄이라는 말과 같다. 후보 둘을 뽑아 덜 찬 쪽으로 갈아타는 부분만 떼어 보면, 정말 아래 몇 줄이 전부다.

import random

def max_load(n, d, seed=7):
    rng = random.Random(seed)
    bins = [0] * n
    for _ in range(n):             # 공 n개를 하나씩 던진다
        i = rng.randrange(n)       # 후보 통 1
        for _ in range(d - 1):     # d=2면 후보를 하나 더 뽑아
            j = rng.randrange(n)
            if bins[j] < bins[i]:  # 덜 찬 쪽으로 갈아탄다
                i = j
        bins[i] += 1
    return max(bins)

n = 100_000
print("d=1 최대 부하:", max_load(n, d=1))
print("d=2 최대 부하:", max_load(n, d=2))

d=1 최대 부하: 8
d=2 최대 부하: 3

통 10만 개를 놓고 돌리면 후보 하나만 보는 d=1은 여덟 개까지 쌓인다. 그런데 여기서 후보 하나만 더 보태면 d=2는 세 개에서 멈춘다. 갈아타는 조건 딱 한 줄이 최댓값을 절반 아래로 끌어내린 것이다. 평균은 그대로 둔 채 오직 극단만 눌렀다.

‘지수적’이라는 말의 진짜 뜻

‘지수적으로 줄었다’는 표현은, 통 100만 개에서 본 아홉과 넷만 놓고 보면 조금 과해 보인다. 고작 두 배 남짓 차이이니 말이다. 이 말이 정직해지려면 n을 하나에 고정하지 말아야 한다. 통 개수를 점점 키우면서, 가장 붐비는 통이 어떤 속도로 자라는지를 봐야 한다.

공 n개를 통 n개에 던질 때 가장 붐비는 통의 최대 부하는, 후보를 몇 개 보느냐에 따라 자라나는 급 자체가 다르다.

(1) $$ L_{d=1} \sim \frac{\ln n}{\ln\ln n}, \qquad L_{d\ge 2} \sim \frac{\ln\ln n}{\ln d} $$

식 1의 왼쪽은 로그를 로그로 나눈 값이다. n이 커지면 천천히, 그래도 멈추지 않고 계속 자란다. 오른쪽은 로그의 로그다. $\ln\ln n$은 n이 아무리 폭발적으로 커져도 좀처럼 움직이지 않는다. 로그와 이중로그 사이의 이 간격이 바로 ‘지수적 개선’의 진짜 뜻이다. 값이 9에서 4로 준다는 이야기가 아니라, 자라나는 급이 통째로 한 단 내려앉는다는 이야기다.

그림 2는 이 식을 말이 아니라 실측으로 확인한 것이다. 통 개수 n을 10³에서 10⁷까지 열 배씩 키우며 d=1·d=2·d=3의 최대 부하를 그대로 재 봤다. d=1은 n이 열 배 될 때마다 최대 부하가 1씩 꾸준히 올라간다. 반면 d=2는 3에서 4로 딱 한 번 오른 뒤 눕고, d=3은 초반에 3에 닿은 뒤로 더는 움직이지 않는다. 그림이 잡아내는 것은 절댓값의 높낮이가 아니라 자라나는 속도의 갈림이다.

가로축이 로그 스케일인 통 개수 n에 대해 d=1·d=2·d=3의 최대 부하를 그린 선그래프. d=1은 계속 올라가고 d=2·d=3은 거의 평평하다. — **그림 2.** n을 10³에서 10⁷까지 늘리며 실측한 최대 부하. d=1은 열 배마다 +1로 계속 자라고, d=2는 4에서·d=3은 3에서 멈춘다. 옅은 점선은 d=1 이론 점근선.

한 가지는 미리 짚어야 한다. 이 점근식을 유한한 n에 대한 예언으로 읽으면 곤란하다.

그래서 그림 2에서도 d=1의 이론 점근선은 실측 곡선보다 한참 아래로 처져 있다. 그래도 두 곡선이 갈라지는 방향만큼은 또렷하다.

그런데 왜 셋은 안 쓸까

이제 제목이 던진 질문으로 돌아갈 차례다. 두 개면 충분하다면, 셋은 왜 필요 없을까. 답은 식 1의 오른쪽 식에 이미 들어 있다. 그 식에서 d는 딱 한 자리, 분모의 $\ln d$에만 나타난다.

d를 1에서 2로 올릴 때는 식의 모양 자체가 통째로 갈아탄다. $\ln n / \ln\ln n$이던 것이 이중로그로 내려앉는 도약이다. 그런데 d를 2에서 3으로 올리면, 분자는 그대로인 채 분모의 로그 밑만 2에서 3으로 커진다. 최대 부하가 대략 0.63배로 살짝 줄 뿐, 자라나는 급은 조금도 변하지 않는다.

이 비대칭은 통 하나하나의 붐빔을 늘어놓아 보면 눈으로 잡힌다. 그림 3는 n=10⁶ 실험에서 공이 0개, 1개, 2개… 든 통이 각각 몇 개인지를 d=1과 d=2로 겹쳐 그린 것이다. 세로축은 로그라, 아주 드문 통까지 보인다. d=1은 꼬리가 두툼하게 오른쪽으로 뻗어 공 아홉 개짜리 통까지 닿는다. d=2는 네 개 언저리에서 꼬리가 뚝 끊긴다. 눌리는 것은 가장 붐비는 한 점이 아니라, 붐비는 쪽 꼬리 전체다.

n=10⁶ 공-통 실험의 통 점유 분포를 d=1과 d=2로 겹쳐 그린 히스토그램. 세로축은 로그. d=1은 꼬리가 9까지 뻗고 d=2는 4에서 끊긴다. — **그림 3.** 통에 공이 몇 개 들었는지의 분포(n=10⁶, 세로축 로그). d=1은 꼬리가 두툼하게 9까지 이어지고, d=2는 4에서 절벽처럼 끊긴다.

그렇다면 d=3은 이 꼬리를 얼마나 더 깎을까. 다음 절에서 다룰 흐르는 줄 모델의 숫자를 미리 빌려 오면 답이 분명해진다. 창구가 처리 능력의 99%까지 밀리는 λ=0.99에서, 손님이 시스템에 머무는 평균 시간은 d=1일 때 100이다. 여벌로 후보 하나를 더 보태는 d=2에서 이 값은 5.43으로 내려앉는다. 한 번에 94.6이 줄어든 것이다.

그런데 셋째 선택은 5.43을 3.86으로, 겨우 1.57밖에 못 깎는다. 넷째 선택도 3.24에서 멈춘다. 첫 여벌 선택 하나가 가져가는 몫과, 그 뒤가 가져가는 몫의 크기 차이가 이만큼이다.

논문은 이 비대칭을 한 문장으로 못 박는다.

Having d = 2 choices leads to exponential improvements in the expected time a customer spends in the system over d = 1, whereas having d = 3 choices is only a constant factor better than d = 2.

출처: Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing”, IEEE TPDS, 2001

셋을 안 쓰는 이유가 여기 있다. 이득의 거의 전부는 첫 여벌 선택에 실리고, 셋째부터는 덤이다.

멈춘 통에서 흐르는 줄로

공 던지기 실험은 공을 다 던지고 나면 멈추는 정적인 그림이었다. 하지만 진짜 계산대는 그렇게 멈춰 있지 않다. 손님은 쉬지 않고 새로 들어오고, 계산을 마친 사람은 줄에서 빠져나간다. 손님이 끊임없이 드나드는 이 줄에서도 두 선택의 힘이 살아남는지가 다음 질문이다.

흐르는 버전을 슈퍼마켓 모델(supermarket model)이라 부른다. 마트 계산대 비유가 아예 모델의 이름이 된 셈이다. 손님은 도착률 λ로 들어와, 무작위로 뽑은 d개 창구 가운데 가장 짧은 줄에 선다. 각 창구는 손님을 한 명씩 처리해 내보낸다. 시스템이 정상 상태에 이르면, 손님이 i명 이상 밀려 있는 창구의 비율이 하나의 값으로 수렴한다. 이 값을 $s_i$라 쓴다.

(2) $$ s_i = \lambda^{\frac{d^{\,i}-1}{d-1}} \ \ (d \ge 2), \qquad s_i = \lambda^{\,i} \ \ (d = 1) $$

식 2에서 눈여겨볼 곳은 분모의 $d-1$이다. d=2면 지수가 $2^i-1$이다. d=3이면 $(3^i-1)/2$로, 후보가 하나 늘 때마다 지수의 밑이 통째로 커진다. 붐비는 창구의 비율이 이렇게 가파르게 줄어드니, 꼬리가 절벽처럼 꺾이는 것이다. 이 비율을 전부 더하면 손님 한 명이 시스템에 머무는 평균 시간이 나오는데, 여기엔 대기행렬 이론의 오래된 다리 하나가 놓인다.

리틀의 법칙: 안정된 시스템에서 줄에 서 있는 평균 인원은 도착률 × 평균 체류시간과 같다. 줄의 길이와 기다리는 시간을 도착률 하나로 이어 주는 다리다.

(3) $$ T = \frac{1}{\lambda}\sum_{i \ge 1} s_i $$

식 2의 $s_i$를 식 3에 그대로 넣으면 평균 체류시간 T가 나온다. d=1이면 이 합은 익숙한 $1/(1-\lambda)$, 곧 창구 하나짜리 기본 대기행렬(M/M/1)의 그 공식이 된다. λ를 0.1에서 0.99까지 밀어 보면 그림 4처럼 두 세계가 갈라진다. d=1 곡선은 λ가 1에 다가갈수록 하늘로 치솟고, d=2 곡선은 바닥에 낮게 눕는다.

가로축 도착률 λ, 세로축(로그)이 평균 체류시간인 그래프. d=1·d=2 이론 곡선에 시뮬레이션 실측 마커가 거의 포개진다. — **그림 4.** 도착률 λ에 따른 평균 체류시간. 선은 고정점 이론, 마커는 시뮬레이션 실측. λ=0.95에서 d=1은 20, d=2는 3.5.

숫자로 보면 이렇다. λ=0.95, 곧 창구가 처리 능력의 95%까지 밀린 상황에서 d=1의 평균 체류시간은 20이다. 여기서도 후보 하나만 더 보면 d=2는 3.5로 내려간다. 같은 혼잡도에서 손님이 약 5.8배 빨리 빠져나가는 셈이다. 선으로 그린 이론과 점으로 찍은 실측이 거의 포개진다는 점도 눈여겨볼 만하다.

정적인 통 던지기에서 봤던 그 비대칭이, 시간이 흐르는 줄에서도 고스란히 살아 있다.

요금소에서 로드밸런서까지

이 한 줄짜리 규칙이 닿는 자리는 생각보다 넓다. Nginx와 HAProxy는 요청을 여러 서버에 흩뿌릴 때, 전부를 재 보는 대신 무작위 두 대의 부하만 견주는 방식을 즐겨 쓴다. 흔히 P2C(power of two choices)라 부르는 그 선택이다. 분산 스케줄러가 쓰는 JSQ(2)(join-the-shortest-of-2-queues)도 이름만 다를 뿐 같은 규칙이다. 해시 테이블의 충돌을 다루는 cuckoo hashing도 같은 핏줄이다. 열쇠 하나에 후보 버킷 두 개를 주고, 자리가 없으면 먼저 든 열쇠를 다른 후보 자리로 밀어내는 규칙을 더해, 최악의 탐색 횟수를 상수 번으로 묶는다.

서버를 수천 대씩 굴리면서도 실무가 d=3, d=4로 올라가지 않는 데는 이유가 있다. 후보를 하나 더 보려면 그 서버의 부하를 한 번 더 조회해야 하는데, 조회 비용은 후보 수만큼 그대로 늘어난다. 반면 얻는 이득은 식 1의 $\ln d$만큼뿐이라 금세 밋밋해진다. d=2는 비용과 이득이 균형을 이루는 딱 그 자리에 서 있다.

다만 이 그림은 각 후보의 줄 길이를 곧바로 정확히 볼 수 있다는 전제 위에 서 있다. 부하 정보가 지연되거나, 여럿이 같은 캐시된 상태를 동시에 들여다보면 이야기가 달라진다. 모두가 ‘지금 제일 한가해 보이는’ 같은 서버로 우르르 몰려가는 군집 쏠림(herd behavior)이 생기기 때문이다. 이때는 후보를 늘릴수록 쏠림이 오히려 커져, 두 선택의 힘이 역효과로 뒤집힌다.

요금소에서 짧은 줄을 고르는 눈대중이, 서버 수천 대의 부하 분산과 해시 테이블의 최악 탐색과 캐시 배치를 한 줄로 꿰뚫는다. 그리고 그 한 줄이 통하는 조건과 무너지는 조건을, 똑같은 분모 $\ln d$가 함께 일러 준다. 무작위로 둘만 견주는 마법은, 각 후보의 상태를 제때 정확히 볼 수 있는 동안에만 제 힘을 낸다.

더 읽기

Mitzenmacher, "The Power of Two Choices in Randomized Load Balancing", IEEE TPDS 12(10), 2001 — supermarket model과 고정점 공식의 원전.
Azar, Broder, Karlin, Upfal, "Balanced Allocations", SIAM J. Comput., 1999 — $\ln\ln n / \ln d$ 최대 부하 결과의 출처.
Mitzenmacher, Richa, Sitaraman, "The Power of Two Random Choices: A Survey of Techniques and Results", 2001 — 기법 전반을 훑는 서베이.
Owen Garrett, "NGINX and the ‘Power of Two Choices’ Load-Balancing Algorithm", NGINX Blog, 2018 — P2C의 실무 채택 사례.