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

새로운 사용 사례에는 때때로 새로운 부하 분산 알고리즘이 필요하며, NGINX Plus R16 및 NGINX Open Source 1.15.1 에서는 분산 부하 분산 장치에 특히 적합한 새로운 방법인 "두 가지 선택의 힘" 알고리즘 구현을 추가했습니다.

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

단일 활성 로드 밸런서를 작동시켜 로드 밸런싱된 노드의 상태를 완전히 볼 수 있는 경우 최소 연결 과 같은 기존 로드 밸런싱 방법이 매우 효과적입니다. "두 가지 선택의 힘" 접근 방식은 단일 로드 밸런서에서는 효과적이지 않지만 여러 개의 독립 로드 밸런서로 확장할 때 발생할 수 있는 나쁜 경우 "군중 행동"을 교묘히 방지합니다.

이 시나리오는 고성능 환경에서 확장할 때만 관찰되는 것이 아니라 여러 프록시가 각각 동일한 서비스 인스턴스 세트에 트래픽을 로드 밸런싱하는 컨테이너화된 환경에서도 관찰됩니다.

이 시나리오의 일반적인 사례는 Kubernetes 노드당 하나의 부하 분산 인스턴스가 있는 Kubernetes용 NGINX Ingress Controller를 사용할 때 발생합니다.

이 알고리즘은 문헌에서 "두 가지 선택의 거듭제곱"으로 언급되는데, 이는 Michael Mitzenmacher의 1996년 논문 "무작위 부하 분산에서 두 가지 선택의 거듭제곱" 에서 처음 기술되었기 때문입니다. NGINX 및 NGINX Plus에서는 Random 부하 분산 알고리즘의 변형으로 구현되므로 Random with Two Choices 라고도 합니다.

"두 가지 선택의 힘"은 어떻게 작동합니까?

익숙할 법한 상황부터 시작해 보겠습니다. 긴 국제선 비행을 마치고 방금 착륙했고, 400명의 다른 여행객과 함께 분주한 도착장에 들어섰습니다.

많은 공항은 도착장에 가이드를 고용합니다. 그들의 임무는 각 여행객을 각 출입국 심사대 대기줄 중 하나에 들어가도록 안내하는 것입니다. 가이드를 로드 밸런서로 생각한다면:

• 당신과 당신의 동료 여행자들은 요청 대상이며, 각자 가능한 한 빨리 처리되기를 바라고 있습니다.
• 이민국 데스크는 (백엔드) 서버 로, 각각 백로그된 요청을 처리합니다.
• 가이드는 각 요청에 가장 적합한 서버를 선택하여 효율성을 극대화합니다.
• 가이드에서 최상의 서버를 선택하기 위해 사용할 수 있는 방법은 부하 분산 알고리즘에 해당합니다.

도착장과 같은 분산 부하 분산 시나리오에서 일부 가능한 알고리즘이 얼마나 잘 작동하는지 고려해 보겠습니다.

라운드 로빈 로드 밸런싱

라운드 로빈은 로드 밸런싱에 대한 순진한 접근 방식입니다. 이 방법에서는 가이드가 차례로 각 대기열을 선택합니다. 첫 번째 여행자는 대기열 A로 안내되고, 다음 여행자는 대기열 B로 안내되는 식입니다. 여행자가 마지막 대기열로 이동하면 프로세스는 대기열 A에서 반복됩니다. 라운드 로빈은 NGINX에서 사용하는 기본 부하 분산 알고리즘입니다.

이 접근 방식은 대기열 중 하나에 지연이 발생할 때까지는 제대로 작동합니다. 어쩌면 한 여행자가 자신의 서류를 분실했거나 이민 관리관의 의심을 받았을 수도 있습니다.

대기열은 더 이상 움직이지 않지만 가이드는 계속해서 여행객을 대기열에 배정합니다. 대기 행렬은 점점 더 길어지고 있습니다. 그러면 참을성 없는 여행객들은 더 이상 행복해질 수 없습니다!

최소 연결 로드 밸런싱

훨씬 더 나은 접근 방식이 있습니다. 가이드는 각 줄을 지켜보다가 여행자가 도착할 때마다 그 여행자를 가장 짧은 줄로 안내합니다. 이 방법은 NGINX의 최소 연결 부하 분산 방법과 유사합니다. 이 방법은 각 새 요청을 대기 중인(대기 중인) 요청이 가장 적은 서버에 할당합니다.

최소 연결 로드 밸런싱은 처리하는 데 걸리는 시간이 다른 여행자를 매우 효과적으로 처리합니다. 이는 대기열의 길이를 균형 있게 조절하고, 중단된 대기열에 더 많은 요청이 추가되는 것을 방지합니다.

최소 시간 로드 밸런싱

우리는 승객마다 처리하는 데 걸리는 시간이 다르다는 것을 보았습니다. 게다가, 어떤 대기열은 다른 대기열보다 처리가 더 빠르거나 더 느립니다. 예를 들어, 한 이민국 직원은 컴퓨터 문제가 있어 여행객을 처리하는 속도가 느릴 수 있고, 다른 직원은 세부 사항에 꼼꼼하여 여행객에게 매우 면밀하게 질문할 수도 있습니다. 다른 직원들은 매우 경험이 많아서 여행객을 더 빨리 처리할 수도 있습니다.

각 출입국 심사대 위에 카운터를 설치해서, 예를 들어 지난 10분 동안 얼마나 많은 여행객이 처리되었는지 표시하면 어떨까요? 그러면 가이드는 대기줄의 길이와 처리 속도에 따라 여행객을 대기열로 안내할 수 있습니다. 이는 부하를 분산하는 더 효과적인 방법이며 NGINX Plus의 최소 시간 부하 분산 알고리즘이 수행하는 작업입니다.

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

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

지금까지 우리는 도착 홀의 대기열과 응답 시간을 완벽하게 볼 수 있는 가이드(즉, 로드 밸런서)를 한 명만 두었습니다. 그 가이드는 자신이 알고 있는 정보를 토대로 각 여행자마다 가장 좋은 선택을 하려고 노력합니다.

이제 여러 명의 가이드가 있어서 각자가 독립적으로 여행객을 안내한다면 어떻게 될지 생각해 보세요. 가이드는 대기줄 길이와 대기 시간에 대한 독립적인 견해를 가지고 있으며, 각 대기줄에 보낸 여행객만 고려합니다.

이런 시나리오에서는 바람직하지 않은 동작이 발생하기 쉽습니다. 즉, 모든 가이드가 한 대기열이 일시적으로 더 짧고 빠르다는 것을 알아차리고, 모든 여행객을 그 대기열로 보내는 것입니다. 시뮬레이션 결과, 이런 "군중 행동"으로 인해 여행객이 불균형하고 불공평하게 분포된다는 사실이 드러났습니다. 마찬가지로, 어떤 "최상의 선택" 알고리즘을 사용하든 여러 개의 독립적인 로드 밸런서는 일부 업스트림 서버를 과부하시킬 수 있습니다.

“두 가지 선택의 힘” 부하 분산 알고리즘

해결책은 "두 가지 선택의 힘" 부하 분산 알고리즘에 있습니다. 불완전한 데이터를 이용해 절대적으로 가장 좋은 선택을 하는 대신, "2의 거듭제곱 선택"을 사용하면 무작위로 두 개의 대기열을 선택하고 둘 중 더 나은 옵션을 선택하여 더 나쁜 선택은 피할 수 있습니다 .

"두 가지 선택의 힘"은 구현하기 효율적입니다. 매번 가장 좋은 옵션을 선택하기 위해 모든 대기열을 비교할 필요는 없습니다. 대신 두 대기열만 비교하면 됩니다. 그리고 직관적이지 않을 수도 있지만, 이는 최상의 선택 알고리즘보다 규모에 따라 더 잘 작동합니다. 최악의 대기열을 피하고 어느 정도 무작위적으로 교통을 분산시키는 간단한 접근 방식을 통해 바람직하지 않은 무리 행동을 방지합니다.

NGINX 및 NGINX Plus를 사용하여 "Power of Two Choices" 사용

NGINX 및 NGINX Plus에서 "두 가지 선택의 거듭제곱" 부하 분산 방식은 Random 알고리즘의 변형으로 구현되므로 Two Choices가 있는 Random이라고 합니다.

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

업스트림 서비스1 { 존 서비스1 64k; 서버 192.168.1.11; 서버 192.168.1.12; 서버 192.168.1.13; 무작위 두 개 ; }

NGINX Plus는 최소 시간 알고리즘과 동일한 선택 기준을 사용하는 least_time 매개변수도 지원합니다. 해당 알고리즘과 마찬가지로 다음 중 하나를 추가로 고려합니다.

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

업스트림 서비스1 { 존 서비스1 64k; 서버 192.168.1.11; 서버 192.168.1.12; 서버 192.168.1.13; 무작위 두 개 least_time=last_byte ; # 헤더나 last_byte 사용 }

결론

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

최소 연결(NGINX Plus의 경우 최소 시간) 방식은 부하 분산 장치가 각 노드에 할당된 작업 부하와 과거 성능을 완전히 파악할 수 있을 때 부하 분산에 매우 효과적입니다. 여러 개의 로드 밸런서가 요청을 할당하고 각 로드 밸런서가 작업 부하와 성능을 불완전하게 보는 경우에는 효율성이 떨어집니다.

"두 가지 선택의 거듭제곱"은 편향된 무작위 알고리즘을 사용하며 각 로드 밸런서에 불완전하거나 지연된 뷰가 있는 경우 로드를 분산하는 데 효과적인 것으로 입증되었습니다. 이는 모든 요청에 대해 최상의 결정을 내리려는 다른 알고리즘이 보이는 "군중 행동"을 방지합니다.

매우 고성능 환경과 분산 부하 분산 시나리오를 위한 NGINX의 "2가지 선택의 거듭제곱" 구현인 Random with Two Choices를 고려해 보십시오. Kubernetes에서 여러 Ingress 컨트롤러를 사용하면 좋은 사용 사례가 발생합니다.