로드밸런서 알고리즘이라고 하면 라운드 로빈(Round Robin), 최소 연결(Least Connection), 가중 라운드 로빈(Weighted Round Robin)이 먼저 떠오른다. 표준 교과서 3종이다. 그런데 Envoy, AWS ALB(Application Load Balancer) 같은 최신 로드밸런서가 핵심 옵션으로 들고 오고 Finagle 같은 RPC(Remote Procedure Call) 스택이 기본값으로 두는 알고리즘은 셋 다 아니다 — Least Outstanding Requests, 그리고 그 실용 구현인 Power of Two Choices다.

이 전환은 단순히 “더 빠른 알고리즘이 나왔다"가 아니다. 클라우드 환경이 RR과 LC의 가정을 깼다. 요청 처리 시간 분산이 크고, autoscale로 backend가 계속 바뀌고, HTTP/2 multiplexing에서 오래 유지되는 connection이 흔해졌다. 그래서 분배 결정의 단위가 connection에서 request로 세분화됐다.

분배 문제

로드밸런서가 도착한 요청을 backend pool의 어느 인스턴스로 보낼지 결정하는 것이 분배다. 결정에는 두 가지가 필요하다. 어느 backend가 더 한가한지 알려주는 부하 신호, 그리고 매 요청마다 N개 backend를 비교할 여유가 있는지 따지는 결정 비용이다.

분배의 단위는 계층에 따라 다르다. L4 로드밸런서는 TCP connection 단위로 분배한다. 한 connection이 열리면 그 connection의 모든 패킷이 같은 backend로 간다. L7 로드밸런서는 HTTP request 단위로 분배할 수 있다. 같은 connection의 두 요청도 서로 다른 backend로 갈 수 있다. 이 차이가 알고리즘 선택의 범위를 결정한다. connection 단위 신호는 L4/L7 둘 다 쓸 수 있지만, request 단위 신호는 L7에서만 가능하다.

sequenceDiagram
    participant C as 클라이언트
    participant LB as 로드밸런서
    participant A as backend A
    participant B as backend B

    Note over C,B: L4 — 같은 connection은 항상 같은 backend
    C->>LB: TCP conn 1 (req 1)
    LB->>A: req 1
    C->>LB: TCP conn 1 (req 2)
    LB->>A: req 2

    Note over C,B: L7 — 같은 connection 위 다른 요청 가능
    C->>LB: HTTP req 1 (stream 1)
    LB->>A: req 1
    C->>LB: HTTP req 2 (stream 3)
    LB->>B: req 2

Round Robin

가장 단순한 분배 알고리즘이다. backend pool을 순환하며 차례대로 할당한다. 첫 요청은 A, 두 번째는 B, 세 번째는 C, 네 번째는 다시 A.

backend가 동등하다면 RR로 충분하다. 모든 backend에 같은 수의 요청이 가고, 시간이 지나면 부하가 평준화된다. 구현이 가볍고 로드밸런서가 backend 상태를 추적할 필요가 없다.

backend가 동등하지 않을 때도 있다. 더 큰 인스턴스가 섞여 있거나 일부 backend가 더 빠른 머신에서 실행된다면 Weighted Round Robin으로 확장한다. backend마다 가중치를 부여하고 가중치에 비례해서 순환한다. 가중치 3:1:1이면 A를 3번 보낸 뒤 B와 C에 한 번씩.

RR의 가정은 두 가지다. backend가 동등하다 (WRR이 이걸 일부 푼다). 요청 처리 시간이 균일하다. 두 번째 가정이 클라우드 환경에서 잘 깨진다.

캐시 미스가 잦은 요청과 적중하는 요청은 처리 시간이 10배 이상 차이 날 수 있다. RR이 모든 backend에 균등하게 요청을 보내도, 우연히 무거운 요청을 연속으로 받은 backend는 큐가 쌓인다. 다음 RR 순환에서도 그 backend는 동일하게 새 요청을 받는다. RR은 backend의 현재 상태를 신호로 쓰지 않기 때문이다.

autoscale로 새 backend가 추가되는 순간도 RR의 약점이다. 새 backend는 캐시가 비어 있고 JIT warming도 안 되어 있어서 처음 몇 분간 응답이 느리다. RR은 이를 모른 채 동등하게 요청을 보낸다.

Least Connection

RR은 backend 상태를 신호로 쓰지 못한다. LC는 이 한계를 보완한다. 로드밸런서가 각 backend의 현재 활성 connection 수를 추적하고, 새 요청이 오면 connection 수가 가장 적은 backend를 선택한다.

부하가 큰 backend는 connection 수가 늘어나고, 한가한 backend는 connection이 닫히면서 수가 줄어든다. LC는 이 차이를 즉시 반영한다. 응답이 느린 backend는 자연스럽게 더 적은 새 요청을 받는다.

LC가 잘 동작하는 전제는 connection 수가 부하의 신호라는 것이다. HTTP/1.1 환경에서는 대체로 맞다. 한 connection이 한 번에 한 요청을 처리하기 때문에 connection 수 ≈ 동시 처리 중인 요청 수다.

이 전제가 깨지는 환경이 등장했다. HTTP/2의 multiplexing이다. 하나의 connection에서 수십 개의 stream이 동시에 동작한다. gRPC는 오래 유지되는 connection으로 수많은 RPC를 처리한다. 이 환경에서 connection 수는 부하의 신호가 아니다.

graph TB
    subgraph view["LC의 시선 — connection 수만 본다"]
        LCa["backend A: 1 connection"]
        LCb["backend B: 1 connection"]
    end
    subgraph reality["HTTP/2의 실제 부하"]
        Ra["backend A — 1 conn / 50 streams"]
        Rb["backend B — 1 conn / 3 streams"]
    end
    view -->|결론| same["두 backend 동등하게 보임"]
    reality -->|실제| diff["A가 약 16배 바쁨"]

    style same fill:#FFCDD2
    style diff fill:#C8E6C9

LC에는 또 하나의 함정이 있다. 헬스체크가 부정확하면 장애 backend의 connection 수가 0으로 보인다. 그러면 LC는 그 backend를 “가장 한가한” 후보로 선택해서 새 요청을 계속 보낸다. 클라우드 환경에서는 인스턴스 종료, 네트워크 partition, OOM 같은 이유로 backend가 빠르게 장애 상태에 들어가는데, 헬스체크 주기가 길면 LC가 잘못 선택할 시간이 길어진다.

Least Outstanding Requests

LC의 두 한계를 모두 푼다. 분배 신호의 단위를 connection에서 outstanding request로 세분화한다. 현재 응답을 기다리고 있는 요청을 가리킨다.

LOR은 backend별로 현재 처리 중인 request 수를 추적한다. 새 요청이 오면 outstanding이 가장 적은 backend를 선택한다. HTTP/2 multiplexing 환경에서도 정확한 부하 신호가 된다. connection 수가 1이어도 outstanding이 50이면 그 backend는 바쁘다. 장애 backend는 outstanding이 누적되거나 (응답이 안 오니까), 회로 차단기가 켜져서 outstanding으로 잡히지 않는다.

부하 신호 자체는 LC보다 한 단계 정확해진다. 그런데 LOR에는 비용 문제가 있다. 매 요청마다 N개 backend의 outstanding 값을 비교해야 한다. backend가 100개라면 매 결정마다 100개를 훑어야 한다. backend pool이 클수록 결정 비용이 선형으로 증가한다.

backend 수가 작은 환경에서는 무시할 만한 비용이지만, 마이크로서비스 환경에서 한 서비스의 backend가 수십에서 수백 개에 달하면 무시할 수 없다.

Power of Two Choices

LOR의 정확도를 거의 보존하면서 결정 비용을 O(1)로 떨어뜨리는 변형이다. 알고리즘은 짧다. backend pool에서 랜덤하게 2개를 뽑고, 둘 중 outstanding이 더 적은 쪽을 선택한다.

flowchart TD
    Start["새 요청 도착"] --> Pick["backend pool에서 랜덤 2개 선택"]
    Pool["backend pool (N개)"] -.->|2개만 본다| Pick
    Pick --> Compare["둘 중 outstanding이 더 적은 쪽"]
    Compare --> Done["요청 전달"]

    style Pick fill:#FFF3E0
    style Compare fill:#C8E6C9

직관적으로는 “전체에서 최소를 찾지 않으면 부정확하지 않은가” 싶지만, Mitzenmacher의 분석 (2001) 이 이를 반박한다. 무작위 분배의 최악 부하(worst-case load)는 backend 중 가장 큰 값이 약 log N으로 자라는데, 매 결정에 2개만 비교해도 그 최악값이 log log N으로 줄어든다. 즉 1개 랜덤 선택 대비 2개 비교는 지수적 개선이고, 2개에서 N개로 늘려도 추가 개선은 미미하다.

이 분석이 P2C를 LOR의 “충분히 좋은 근사"로 만들었다. 비교 비용은 backend 수와 무관하게 항상 2 — backend가 100개든 1000개든 결정 비용이 같다. Envoy의 LEAST_REQUEST 정책은 정확히 P2C로 구현되어 있고 (랜덤 추출 host 수의 기본값이 2), AWS ALB의 least_outstanding_requests 옵션, gRPC의 weighted_round_robin 정책, Finagle의 기본값도 같은 P2C 계열이다.

부하 신호의 단위

분배 알고리즘의 진화는 부하 신호의 단위가 점점 작아지는 과정이다. RR은 단위가 없다. backend 상태를 보지 않는다. LC는 단위가 connection이다. LOR은 단위가 request다. P2C는 같은 단위 (request) 를 유지하면서 결정 비용을 떨어뜨린다.

최신 로드밸런서가 P2C를 핵심 옵션으로 들고 온 것은 더 빠른 알고리즘이 나왔기 때문이 아니다. HTTP/2 multiplexing, autoscale, 부정확한 헬스체크, 큰 요청 처리 시간 분산 같은 클라우드 환경이 connection을 부하 신호로 쓰지 못하게 만들었기 때문이다. 단위가 connection에서 request로 세분화돼야 했고, P2C가 그 단위 전환을 실용화했다.