Pyohwan/english-study

NGINX and the “Power of Two Choices” Load-Balancing Algorithm

Opened this issue · 0 comments

Pyohwan commented

https://www.nginx.com/blog/nginx-power-of-two-choices-load-balancing-algorithm/

NGINX 1.15.1 에서부터 "power of two choices" 알고리즘 구현이 추가 되었다.

Why Do We Need a New Load‑Balancing Algorithm?

Least Connections 과 같은 클래식 LB 방법은 노드의 상태를 완전히 볼 수 있는 싱글 액티브 로드밸런서에 유용하다.
"power of two choices" 접근 방식은 싱글 로드밸랜서에 효과적이진 않지만, 여러 독립적인 로드밸런서로 확장할때 발생하는 "herd behavior" 문제를 피할 수 있다.

이 시나리오는 고사양 환경 뿐만 아니라, 동일한 서비스 인스턴스 집합으로 된 컨테이터 환경에서도 관찰된다.


이 시나리오에서 일반적으로 인스턴스는 Kubernetes 노드 당 하나의 LB 인스턴스가 있고, Kubernetes 용 NGINX Ingress Controller 를 쓸때 발생한다.

이 알고리즘은 Michael Mitzenmacher의 1996 년 논문 인 Randomized Load Balancing 에서 처음 설명 되었고, 논문에서 "power of two choices" 라고 했음. NGINX와 NGINX Plus 에서는 약간 변형해서 Random with Two Choices 이라고 함.

How Does “Power of Two Choices” Work?

국제선 비행을 마치고 400 여명의 사람들과 함께 홀로 들어왔음


<Photo: Caroline M.A Otieno – Own work, CC BY 2.0>

많은 공항이 입국장에서 안내를 한다. 그들의 임무는 각 여행자를 각 출입국 관리 데스크의 여러 대기열(queues) 중에 집어 넣는것이다.

  • 당신과 동료 요청(requests)이고, 가능한 빨리 처리되길 원한다.
  • 이민국(backend) 는 서버이며 각 요청을 backlog 한다.
  • 가이드는 로드밸런서이고, 요청에 가장 적합한 서버를 선택한다.

가이드는 최상의 서버를 선택하기 위해 LB 알고리즘을 고민한다.

Round-Robin Load Balancing

Round robin 은 소박한 접근 방식이다. 가이드는 순환적으로 각 큐를 선택한다; 첫 번째 여향자는 큐 A로, 다음은 큐 B로 이렇게. 여행자가 마지막 큐로 갔다면 다음은 큐 A에서부터 다시 반복한다. Round robin은 NGINX 에서 사용하는 기본 알고리즘이다.

이 방법은 큐중에 하나가 지연 될때까지는 잘 동작한다. 아마도 한 여행자가 서류를 잘 못 놓았거나, 이민국 직원에게 의심을 받거나 해서

image
큐 이동이 멈췄지만 가이드는 여행자를 계속해서 그 큐에 할당한다. backlog 가 계속 길어진다 - 여행자는 불행함

Least Connections Load Balancing

좀더 나은 접근 방식이다. 가이드는 줄을 보고, 여행자가 도착하면 가장 짧은 큐로 보낸다. 이 방법은 NGINX의 Least Connections LB 와 유사하고, 대기중인 요청이 가장 작은 서버로 새 요청을 할당한다.

처리 시간이 다른 여행자들을 효과적으로 처리한다. 큐 길이의 균형을 유지하려하고, 정지된 큐에 더이상 요청을 추가하지 않는다.

Least Time Load Balancing

승객 마다 처리 시간이 다르다. 또한 큐 사이에도 처리 시간이 다르다. 예를 들어, 한 이민국 직원 컴퓨터가 문제가 생기면 다른 여행자들보다 처리가 느릴것이다. 다른 오피서는 여행자에게 매우 가깝게 질문할 수도 있고, 다른 오피서는 경험이 많아 더 빨리 처리할 수도 있다.

이민자 부스 위에 처리된 카운트가 있다. 예를 들어 지난 10분 동안 몇명의 여행자가 처리 되었나? 그러면 가이드는 길이와 처리 속도에 따라 여행자를 큐로 안내 가능하다. NGINX Plus 에서 Least Time load‑balancing algorithm 이다.

이 알고리즘은 NGINX Plus의 확장된 상태 케트릭에 의존하기 때문에 NGINX Plus 에서만 사용 가능하다. 하지만 각 서버에 대한 latency 가 예측 하기 힘든 클라우드 또는 가상 환경에서는 효과적이지만, 큐 길이로만 delay 를 추정하기에는 충분하지 않다.

It All Falls Apart with Multiple Guides

지금까지는 한명의 가이드만 있었는데, 가이드가 여려명이면 어떻게 할껀가? 가이드가 독립적으로 큐 길이와 큐 대기시간을 볼수 있다 - 이 가이드들은 각 큐에만 여행자를 보낼려고만 한다

이 시나리오는 바람직하지 않는 행동을 하기 쉽다. 하나의 큐가 순간적으로 빨라보여서 그 큐로 여행자를 몰아버린다. 시뮬레이션 결과에 다르면 "herd behavior" 는 불균형하고 불공평하게 여행자를 분산한다. 독립적인 LB는 "best choice" 알고리즘을 사용하든 말든, 일부 업스트림 서버에 과부하를 일으킬 수 있다.

The “Power of Two Choices” Load-Balancing Algorithm

불완전한 데이터를 사용하여 확실한 선택 대신에 "power of two choices" 을 사용하면, 두개의 큐를 무작위로 선택하고, 두가지 중에 더 나은 옵션을 선택하여, 나쁜 선택을 피하도록 한다.

"Power of two choices" 는 매번 최상의 옵션을 선택하기 위해 모든 큐를 비교할 필요 없다 : 대신 두가지를 비교한다. 또한 best‑choice 알고리즘보다 확장이 우수하다. 최악의 큐를 피하고 무작위 비율로 트래픽 분배라는 간단한 접근으로 무리지는 행동을 피한다.

Using “Power of Two Choices” with NGINX and NGINX Plus

NGINX, NGINX Plus 에서는 "power of two choices" 로드밸런싱 방법이 Random 알고리즘의 변형으로 구현되었고, Random with Two Choices 라고 부른다.

NGINX 오픈 소스에서 Random with Two Choices 는 현재 active 커넥션이 적은 서버를 기준으로 임의로 2개의 서버를 선택한다. Least Connections 알고리즘을 쓰는것과 동일하다.

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 algorithm 을 지원하는 least_time 파라미터를 지원한다.

  • 응답 헤더를 받은 시간 (least_time=header)
  • 전체 응답을 수신하는 시간(least_time=last_byte). Least Time 기준은 각 업스트림 서버에 대해 달라질 수 있는 상황에 적합하다.

Conclusion

Least Connections 방법은 로드 밸런서가 각 노드의 부하를 환벽하게 볼수 있을때 매우 효과적이다. 여러 로드 밸런서가 요청을 할당할때에는 효과가 떨어지고 각 부하와 성능에 불안전하게 바라본다.

"Power of two choices" 은 랜덤 알고리즘을 사용해서, 각 로드 밸랜서가 불완전하거나 지연된 뷰를 가질때에는 효과적인것이 입증되었다. "herd behavior" 를 피한다.

multiple Ingress controllers on Kubernetes 환경에서 좋은 사용사례가 있다.