NGINX와 ‘두 가지 선택의 힘’ 부하 분산 알고리즘

Owen Garrett제품 관리 부문 수석 이사

새로운 사용 사례에는 때때로 새로운 부하 분산 알고리즘이 필요합니다. 이에 NGINX Plus R16과 NGINX Open Source 1.15.1에는 분산형 부하 분산기에 특히 적합한 새로운 방식인 ‘두 가지 선택의 힘’ 알고리즘 구현을 추가했습니다.

새로운 부하 분산 알고리즘이 필요한 이유는 무엇일까요?

다음과 같은 기존의 부하 분산 방식은 최소 연결 부하 분산 대상 노드의 상태를 완벽하게 파악하는 단일 활성 부하 분산 장치를 운영할 때 매우 효과적입니다. ‘두 가지 선택의 힘’ 접근 방식은 단일 부하 분산 장치에서는 그다지 효과적이지 않지만, 여러 개의 독립적인 부하 분산 장치로 확장할 때 발생할 수 있는 최악의 ‘군집 행동’을 효과적으로 방지합니다.

이러한 현상은 고성능 환경에서 확장할 때만 나타나는 것이 아닙니다. 여러 프록시가 각각 동일한 서비스 인스턴스 집합으로 트래픽을 부하 분산하는 컨테이너 환경에서도 나타납니다.

이 시나리오의 일반적인 사례는 Kubernetes에서 NGINX Ingress Controller를 사용하면서 Kubernetes 노드마다 하나의 부하 분산 인스턴스를 배치하는 경우입니다.

이 알고리즘은 Michael Mitzenmacher의 1996년 박사 학위 논문인 무작위 부하 분산에서 두 선택지의 힘에서 처음 소개되었기 때문에 문헌에서는 ‘두 선택지의 힘(power of two choices)’이라고 합니다. NGINX와 NGINX Plus에서는 무작위 부하 분산 알고리즘의 변형으로 구현되므로 두 선택지를 사용한 무작위 방식(Random with Two Choices)이라고도 합니다.

“두 가지 선택의 힘”은 어떻게 작동할까요?

익숙하게 느껴질 법한 상황부터 살펴보겠습니다. 긴 국제선 비행을 마치고 막 착륙한 뒤, 다른 여행객 400명과 함께 붐비는 입국장으로 들어섰습니다.

많은 공항에서는 입국장에 안내 직원을 배치합니다. 이들의 역할은 각 여행객을 출입국 심사대별로 마련된 여러 대기 줄 중 하나로 안내하는 것입니다. 이 안내 직원을 로드 밸런서라고 생각해 보면 다음과 같습니다:

• 여러분과 다른 여행객들은 가능한 한 빨리 처리되기를 바라는 요청입니다.
• 출입국 심사대는 (백엔드) 서버이며, 각각 밀려 있는 요청을 처리합니다.
• 가이드는 각 요청에 가장 적합한 서버를 선택하여 효율성을 극대화합니다.
• 가이드가 최적의 서버를 선택하는 데 사용할 수 있는 방식은 부하 분산 알고리즘에 해당합니다.

입국장과 같은 분산 부하 분산 시나리오에서 몇 가지 가능한 알고리즘이 얼마나 효과적으로 작동하는지 살펴보겠습니다.

라운드 로빈 부하 분산

라운드 로빈은 단순한 부하 분산 방식입니다. 이 방식에서는 안내원이 각 대기열을 순서대로 선택합니다. 첫 번째 여행자는 대기열 A로, 다음 여행자는 대기열 B로 안내하는 식입니다. 여행자가 마지막 대기열로 안내되면 대기열 A부터 이 과정을 반복합니다. 라운드 로빈은 NGINX에서 사용하는 기본 부하 분산 알고리즘입니다:

이 방식은 어느 한 줄에서 지연이 발생하기 전까지는 무난하게 작동합니다. 예를 들어 어떤 여행객이 서류를 분실했거나 출입국 심사관의 의심을 살 수 있습니다:

대기열은 더 이상 움직이지 않는데도 안내자는 계속해서 여행객들을 그 대기열로 보냅니다. 밀린 줄은 점점 더 길어지고, 성급한 여행객들의 불만만 커질 뿐입니다!

최소 연결 수 로드 밸런싱

훨씬 더 나은 방법이 있습니다. 안내원이 각 대기열을 살펴보다가 여행자가 도착할 때마다 가장 짧은 대기열로 보냅니다. 이 방법은 NGINX의 최소 연결 부하 분산 방식과 유사하며, 새 요청이 들어올 때마다 처리 대기 중인 요청 수가 가장 적은 서버에 할당합니다:

최소 연결(Least Connections) 부하 분산은 처리 시간이 서로 다른 요청을 매우 효과적으로 처리합니다. 이 방식은 대기열의 길이를 균등하게 유지하고, 정체된 대기열에 요청이 더 추가되지 않도록 합니다.

최소 시간 부하 분산

앞서 살펴본 것처럼 승객마다 처리에 걸리는 시간이 다르며, 일부 대기열은 다른 대기열보다 처리 속도가 빠르거나 느릴 수 있습니다. 예를 들어, 어떤 출입국 심사관은 컴퓨터 문제로 여행객을 더 느리게 처리할 수 있고, 또 다른 심사관은 세부 사항을 꼼꼼히 따지는 성격이라 여행객에게 매우 자세히 질문할 수 있습니다. 반면 경험이 풍부해 여행객을 더 신속하게 처리하는 심사관도 있을 수 있습니다.

각 출입국 심사대 위에 최근 10분 동안 처리한 여행객 수를 표시하는 계수기가 있다면 어떨까요? 그러면 안내 담당자는 대기열의 길이와 처리 속도를 기준으로 여행객을 적절한 대기열로 안내할 수 있습니다. 이는 부하를 더 효과적으로 분산하는 방법이며, NGINX Plus의 최소 시간 부하 분산 알고리즘이 바로 이러한 방식으로 작동합니다:

이 알고리즘은 NGINX Plus의 확장 상태 메트릭을 통해 수집된 추가 데이터를 사용하므로 NGINX Plus에서만 사용할 수 있습니다. 특히 각 서버의 지연 시간이 예측할 수 없게 달라질 수 있는 클라우드 또는 가상 환경에서 효과적입니다. 이러한 환경에서는 대기열 길이만으로 지연을 추정하기에 충분하지 않습니다.

여러 가이드를 사용하면 모든 것이 무너집니다

지금까지는 입국장에서 대기열과 응답 시간을 모두 파악하고 있는 안내원(즉, 로드 밸런서)이 한 명뿐이었습니다. 이 안내원은 자신이 알고 있는 정보를 바탕으로 각 여행자에게 가장 적합한 선택을 하려고 합니다.

이제 여러 명의 안내원이 각자 독립적으로 여행객을 안내하면 어떤 일이 일어나는지 살펴보겠습니다. 안내원들은 대기열의 길이와 대기 시간을 각자 독립적으로 파악합니다. 즉, 자신이 각 대기열로 보낸 여행객만 고려합니다.

이 시나리오에서는 모든 안내자가 특정 대기열이 일시적으로 더 짧고 빠르다는 사실을 알아차리고 여행객을 모두 그 대기열로 보내는 바람직하지 않은 동작이 발생하기 쉽습니다. 시뮬레이션에 따르면 이러한 ‘군집 행동’으로 인해 여행객이 불균형하고 불공정하게 분산됩니다. 마찬가지로 어떤 ‘최선의 선택’ 알고리즘을 사용하더라도 여러 개의 독립적인 로드 밸런서가 일부 업스트림 서버에 과부하를 일으킬 수 있습니다.

‘두 가지 선택의 힘’ 부하 분산 알고리즘

해결책은 ‘두 가지 선택의 힘’ 부하 분산 알고리즘에 있습니다. 불완전한 데이터로 절대적인 최선의 선택을 하려는 대신, ‘두 가지 선택의 힘’에서는 두 개의 큐를 무작위로 고른 뒤 둘 중 더 나은 쪽을 선택하여 더 나쁜 선택을 피합니다.

“두 가지 선택의 힘”은 효율적으로 구현할 수 있습니다. 매번 최선의 옵션을 선택하기 위해 모든 큐를 비교할 필요 없이 두 개만 비교하면 됩니다. 다소 직관에 반할 수 있지만, 규모가 커질수록 최선의 선택 알고리즘보다 더 효과적으로 작동합니다. 최악의 큐를 피하고 트래픽을 어느 정도 무작위로 분산하는 간단한 방식으로 바람직하지 않은 군집 행동을 방지합니다.

NGINX 및 NGINX Plus에서 ‘두 가지 선택의 힘’ 사용하기

NGINX와 NGINX Plus에서 '2개 선택의 힘' 부하 분산 방식은 Random 알고리즘의 변형으로 구현되므로 이를 Random with Two Choices라고 합니다.

NGINX Open Source에서 Random with Two Choices는 무작위로 선택된 두 서버 중 현재 활성 연결 수가 더 적은 서버를 선택합니다. 이는 Least Connections 알고리즘에서 사용하는 것과 동일한 선택 기준입니다. (이는 NGINX Plus의 기본 알고리즘이기도 하며, least_conn 매개변수를 추가하여 명시적으로 구성할 수 있습니다.)

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two; 
}

NGINX Plus는 least_time 매개변수도 지원하며, 이 매개변수는 최소 시간(Least Time) 알고리즘과 동일한 선택 기준을 사용합니다. 해당 알고리즘과 마찬가지로 다음 중 하나를 고려하도록 선택할 수 있습니다:

• The time to receive the 응답 헤더를 수신하는 데 걸리는 시간(least_time=header)
• The time to receive the 전체 응답을 수신하는 데 걸리는 시간(least_time=last_byte). 다음 코드 조각과 같습니다. 최소 시간 기준은 각 업스트림 서버의 지연 시간이 달라질 수 있는 상황에 적합합니다.

upstream service1 {    zone service1 64k;
    server 192.168.1.11;
    server 192.168.1.12;
    server 192.168.1.13;
    random two least_time=last_byte; # use header or last_byte
}

결론

NGINX와 NGINX Plus는 다양한 부하 분산 방식을 지원합니다. 이 문서에서는 결정론적 방식인 해시 및 IP 해시 방식은 다루지 않았습니다.

최소 연결 방식(및 NGINX Plus의 경우 최소 시간 방식)은 로드 밸런서가 각 노드에 할당된 워크로드와 해당 노드의 과거 성능을 완전히 파악하고 있을 때 부하를 매우 효과적으로 분산합니다. 여러 로드 밸런서가 요청을 할당하면서 각 로드 밸런서가 워크로드와 성능을 불완전하게 파악하고 있는 경우에는 효과가 떨어집니다.

“2개 중 하나 선택(Power of Two Choices)”은 편향된 무작위 알고리즘을 사용하며, 각 로드 밸런서가 불완전하거나 지연된 정보를 가지고 있을 때도 부하를 효과적으로 분산하는 것으로 입증되었습니다. 또한 요청마다 최선의 결정을 내리려는 다른 알고리즘에서 나타나는 “군집 행동”을 방지합니다.

초고성능 환경과 분산 부하 분산 시나리오에서는 NGINX가 ‘두 가지 선택의 힘’을 구현한 Random with Two Choices를 고려해 보세요. Kubernetes에서 여러 Ingress 컨트롤러를 사용할 때 유용합니다.

작성자 소개

Owen Garrett제품 관리 부문 수석 이사

Owen Garrett의 다른 블로그 게시물