NGINX 로드 밸런싱 알고리즘 작동 원리

새로운 사용 사례에서는 NGINX 로드 밸런싱 새로운 부하 분산 알고리즘이 필요할 수 있습니다. NGINX Plus R16 및 NGINX Open Source 1.15.1부터 분산형 로드 밸런서에 특히 적합한 새로운 로드 밸런싱 방법을 추가했습니다.

목차

1. NGINX 로드 밸런싱에 새로운 부하 분산 알고리즘이 필요한 이유
2. “Power of Two Choices는 어떻게 작동합니까?
2-1. 라운드로빈 로드 밸런싱
2-2. 최소 연결 로드 밸런싱
2-3. 최소 시간 로드 밸런싱
2-4. 여러 가이드로 모든 것이 무너집니다.
2-5. “Power of Two Choices” 로드 밸런싱 알고리즘
3. NGINX 로드 밸런에 “Power of Two Choices 사용
4. NGINX 로드 밸런싱 결론

1. NGINX 로드 밸런싱 에 새로운 부하 분산 알고리즘이 필요한 이유

최소 연결(Least Connections)과 같은 클래식한 로드 밸런싱 방법은 로드 밸런싱 노드의 상태를 완전히 보유하는 단일 활성 로드 밸런서에서는 매우 잘 작동합니다. 그러나 “Power of Two Choices” 접근 방식은 단일 로드 밸런서에서는 효과적이지 않지만 독립적인 로드 밸런서의 수가 많아질 때 발생할 수 있는 쏠림 현을 능숙하게 회피합니다.

이러한 시나리오는 고성능 환경에서 Scale-out 하는 경우뿐만 아니라, 여러 프록시가 동일한 서비스 인스턴스 집합으로 트래픽을 로드 밸런싱하는 컨테이너화된 환경에서도 관찰됩니다.

분산 로드 밸런서를 사용하는 클러스터 토폴로지

분산 로드 밸런서를 사용한 클러스터 토폴로지

이러한 시나리오의 일반적인 예는 Kubernetes에 대한 NGINX Ingress Controller를 사용할 때, 각 Kubernetes 노드당 하나의 로드 밸런싱 인스턴스를 사용하는 경우입니다.

이 알고리즘은 Michael Mitzenmacher의 1996 논문 “The Power of Two Choices in Randomized Load Balancing“에서 처음으로 설명되어 “power of two choices”로 불립니다. NGINX와 NGINX Plus에서는 Random 로드 밸런싱 알고리즘의 변형으로 구현되므로 Random with Two Choices로도 참조됩니다.

2. “Power of Two Choices는 어떻게 작동합니까?

익숙한 상황에서 예를 들어보겠습니다. 긴 국제 여행을 마치고 막 도착했고, 400명 이상의 다른 여행자들과 함께 붐비는 도착 로비에 들어왔습니다.

사진: Caroline M.A Otleno

사진: Caroline M.A Otleno

많은 공항에서는 도착 로비에 가이드를 고용합니다. 그들의 임무는 각 여행자가 각 출입국 관리 데스크의 여러 대기열 중 하나에 합류하도록 지시하는 것입니다. 가이드를 로드 밸런서로 생각하면:

  • 당신과 동료 여행자들은 요청(requests)입니다. 각각은 최대한 빨리 처리되길 바라고 있습니다.
  • 출입국 관리 데스크는 (backend) 서버로 각각 백로그 요청을 처리합니다.
  • 가이드는 각 요청에 대해 최상의 서버를 선택하여 효율성을 극대화합니다.
  • 가이드가 사용할 수 있는 서버 선택 방법은 로드 밸런싱 알고리즘(load-balancing algorithms)과 대응됩니다.

도착 로비와 같은 분산 로드 밸런싱 시나리오에서 가능한 알고리즘 중 몇 가지가 얼마나 잘 작동하는지 살펴보겠습니다.

2-1. 라운드 로빈(Round Robin) 로드 밸런싱

라운드 로빈(Round Robin)은 로드 밸런싱에 대한 단순한 접근법입니다. 이 접근법에서 가이드는 각 대기열을 순서대로 선택합니다. 첫 번째 여행자는 대기열 A로 안내되고, 다음 여행자는 대기열 B로 안내되는 식입니다. 마지막 대기열로 안내된 여행자가 있으면 프로세스는 대기열 A에서 다시 시작합니다. 라운드 로빈(Round Robin)은 NGINX에서 사용되는 기본(Default) 로드 밸런싱 알고리즘입니다.

라운드 로빈 NGINX 로드 밸런싱

이 접근법은 대기열 중 하나에 지연이 발생할 때까지는 충분히 작동합니다. 아마도 한 명의 여행자가 서류를 잘못 놓거나 이민국 담당자의 의심을 사는 경우가 그렇습니다. 이러한 경우에는 해당 대기열의 처리 시간이 길어지기 때문에 그 대기열에 할당된 서버는 다른 서버보다 더 많은 요청을 처리할 수 없게 됩니다. 이는 전체 시스템의 성능 저하를 유발할 수 있습니다.

증

대기열이 멈추면서 대기열에 여행자를 계속 할당하는 상황이 발생하게 됩니다. 이렇게 되면 백로그(backlog)가 더욱 길어지고, 불만스러운 여행자들에게는 더 큰 문제가 발생할 수 있습니다. 이는 가이드가 모든 대기열을 균등하게 처리하려는 라운드 로빈(Round Robin) 알고리즘의 한계로 볼 수 있습니다.

2-2. 최소 연결(Least Connection) 로드 밸런싱

그 대신, 가이드는 각 대기열을 지켜보며 각각의 여행자가 도착할 때마다 가장 짧은 대기열로 보내는 방법이 있습니다. 이 방법은 NGINX에서 최소 연결(Least Connection) 로드 밸런싱 방법과 유사하며, 각 새 요청을 처리할 서버는 가장 많은 대기 중인 요청이 있는 서버에 할당됩니다. 이를 통해 대기열이 각각 균등하게 분산되지 않고, 항상 가장 적은 수의 요청이 있는 서버에 대해 처리를 요청하므로, 대기 시간이 크게 감소될 수 있습니다.

최소 연결 NGINX 로드 밸런싱

최소 연결(Least Connections) 로드 밸런싱은 처리 시간이 다른 여행자들을 효과적으로 처리할 수 있습니다. 이는 대기열의 길이를 균형있게 조정하고, 멈춘 대기열에 더 많은 요청을 추가하지 않도록 노력합니다. 따라서 가장 적은 요청이 있는 서버에 새 요청을 배치하여 대기 시간을 최소화하고 처리 효율성을 높일 수 있습니다.

2-3. 최소 시간(Least Time) 로드 밸런싱

우리는 서로 다른 여행객들이 다른 시간이 소요되는 것을 보았습니다. 또한 일부 대기열은 다른 것보다 더 빠르거나 느릴 수 있습니다. 예를 들어, 한 명의 이민국 공무원은 컴퓨터 문제로 인해 여행객을 더 느리게 처리할 수 있습니다. 또 다른 공무원은 여행객을 매우 자세히 심문하는 세심한 사람일 수 있습니다. 다른 공무원들은 매우 숙련되어 있어 여행객을 더 빠르게 처리할 수 있습니다.

예를 들어, 각 이민 심사 창구 위에는 최근 10분간 처리된 여행객 수를 나타내는 카운터가 있다면 어떨까요? 그러면 가이드는 큐의 길이와 얼마나 빨리 처리되고 있는지를 기반으로 여행객을 해당 큐로 안내할 수 있습니다. 이것은 더욱 효과적인 부하 분산 방법이며, 이것이 NGINX Plus의 최소 시간(Least Time) 로드 밸런 알고리즘입니다.

최소 시간 NGINX 로드 밸런싱

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

2-4. 여러 가이드로 모든 것이 무너집니다.

지금까지 도착 로비에서 대기열 응답 시간을 전체적으로 볼 수 있는 하나의 가이드(로드 밸런서)가 있었습니다. 그 가이드는 알고 있는 정보에 기초하여 각 여행객에 대한 최선의 선택을 시도합니다.

이번에는 여러 가이드가 각각 독립적으로 여행자를 지시하는 경우를 생각해 봅시다. 가이드들은 각각의 대기열 길이와 대기 시간에 대한 독립적인 시각을 가지고 있으며, 각각의 대기열에 지시하는 여행자만 고려합니다.

이 경우에는 모든 가이드가 일시적으로 더 짧고 빠른 대기열 인지하고 모든 여행자를 해당 대기열로 보내는 불필요한 행동이 발생할 수 있습니다. 시뮬레이션 결과 이러한 “쏠림”은 여행자를 균형과 공정성에 어긋나게 분배하게 됩니다. 마찬가지로, 여러 개의 독립적인 로드 밸런서는 어떤 “최상의 선택” 알고리즘을 사용하더라도 일부 Upstream 서버를 과부하로 만들 수 있습니다.

2-5. “Power of Two Choices” 로드 밸런싱 알고리즘

해결책은 “Power of Two Choices” 로드 밸런싱 알고리즘에 있습니다. “Power of Two Choices” 알고리즘은 불완전한 데이터를 사용하여 절대적으로 최상의 선택을하는 대신, 무작위로 두 개의 대기열을 선택하고 두 개 중에서 더 나은 선택을 하여 더 나쁜 선택을 피합니다.

“Power of two choices”는 구현이 효율적입니다. 매번 최선의 선택을 하기 위해 모든 큐를 비교할 필요가 없으며 대신 두 개의 큐를 비교하기만 하면 됩니다. 그리고 아마 직관적이지는 않지만 최선의 선택 알고리즘보다 대규모로 더 잘 작동합니다. 무작위성을 조금 더하여 최악의 대기열을 피하고 트래픽을 분산함으로써 원하지 않는 군집 동작을 방지합니다.

3. NGINX 로드 밸런싱 에 “Power of Two Choices” 사용

NGINX와 NGINX Plus에서 “Power of Two Choices” 로드 밸런싱 방법은 Random 알고리즘의 변형으로 구현되어 있으므로 Random with Two Choices로 부릅니다.

NGINX Open Souce에서 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 매개변수도 지원합니다. 해당 알고리즘과 마찬가지로 다음 중 하나를 고려하여 추가로 선택합니다.

  • 응답 헤더를 받는 데 걸리는 시간 (least_time=header)
  • 전체 스니펫과 같이 전체 응답을 수신하는 시간(least_time=last_byte)입니다. 최소 시간 기준은 각 Upstream 서버에 대한 대기 시간이 다를 수 있는 상황에 이상적입니다.
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
}

4. NGINX 로드 밸런싱 결론

NGINX 및 NGINX Plus는 다양한 로드 밸런싱 방법을 지원합니다. 이 기사에서는 결정론적 Hash 및 IP Hash 방법을 고려하지 않았습니다.

최고 연결(및 NGINX Plus의 경우 최소 시간) 방법은 로드 밸런서가 각 노드에 할당된 워크로드와 과거 성능을 전체적으로 볼 수 있을 때 로드 밸런싱에 매우 효과적입니다. 여러 로드 밸런서가 요청을 할당하고 각각 워크로드 및 성능에 대한 불완전한 보기가 있는 경우에는 덜 효과적입니다.

“Power of Two Choices은 편향된 무작위 알고리즘(randomized algorithm)을 사용하며 각 로드 밸런서가 불완전하거나 지연된 보기를 가질 때 로드 밸런싱에 효과적인 것으로 입증되었습니다. 모든 요청에 대해 최선의 결정을 내리려는 다른 알고리즘에서 나타나는 “쏠림”을 방지합니다. 고성능 환경과 분산 로드 밸런싱 시나리오를 위한 NGINX의 “Power of Two Choices” 구현인 Random with Two Choices를 고려하십시오. Kubernetes에서 여러 Ingress Controller 를 사용할 때 좋은 사용 사례가 발생합니다.

NGINX 또는 NGINX Plus 를 사용해 보시려면 지금 30일 무료 평가판을 시작하거나 당사에 연락하여 사용 사례에 대해 논의하십시오.

NGINX에 대해 최신 소식을 빠르게 전달받고 싶으시면 아래 뉴스레터를 구독하세요.