부하 밸런싱(컴퓨팅)

Load balancing (computing)
로드 밸런서에 의해 분산되는 Elastic Search 클러스터에 대한 사용자 요청을 나타내는 다이어그램입니다(Wikipedia의 예).

컴퓨팅에서 로드밸런싱은 일련의 작업을 일련의 자원(컴퓨팅 유닛)에 걸쳐 분산하는 프로세스를 말합니다.이 프로세스는 전체적인 처리를 보다 효율적으로 하기 위한 것입니다.로드 밸런싱을 통해 응답 시간을 최적화하고 일부 컴퓨팅 노드가 유휴 상태인 동안 일부 컴퓨팅 노드의 과부하를 균일하게 방지할 수 있습니다.

부하 분산은 병렬 컴퓨터 분야의 연구 주제입니다.두 가지 주요 접근법이 존재합니다.다른 기계들의 상태를 고려하지 않는 정적 알고리즘과 다른 컴퓨팅 유닛들 간의 정보 교환이 필요한 동적 알고리즘입니다.이 알고리즘은 일반적으로 더 일반적이고 효율적이지만 효율성이 저하될 위험이 있습니다.

문제의 개요

로드 밸런싱 알고리즘은 항상 특정 문제에 대한 응답을 시도합니다.무엇보다도 태스크의 특성, 알고리즘의 복잡성, 알고리즘이 실행되는 하드웨어 아키텍처 및 필요한 오류 허용치를 고려해야 합니다.따라서 애플리케이션 고유의 요건을 가장 잘 충족하기 위해 타협점을 찾아야 합니다.

태스크의 성질

로드 밸런싱 알고리즘의 효율성은 작업의 특성에 따라 결정적으로 달라집니다.따라서 의사결정 시 작업에 대한 정보를 더 많이 얻을 수 있을수록 최적화의 가능성은 높아집니다.

태스크의 크기

각 태스크의 실행 시간을 완벽하게 알면 최적의 부하 분산에 도달할 수 있습니다(프리픽스 [1]합계 알고리즘 참조).불행하게도, 이것은 사실 이상적인 경우입니다.각 작업의 정확한 실행 시간을 아는 것은 극히 드문 일입니다.

이 때문에, 다른 실행 시간을 파악할 수 있는 몇개의 테크닉이 있습니다.우선, 비교적 균일한 크기의 태스크를 갖는 행운의 시나리오에서는 각각의 태스크가 대략 평균 실행 시간을 필요로 하는 것을 고려할 수 있다.반면 실행 시간이 매우 불규칙한 경우에는 보다 정교한 기술을 사용해야 합니다.한 가지 방법은 각 작업에 메타데이터를 추가하는 것입니다.유사한 메타데이터의 이전 실행 시간에 따라 [2]통계를 기반으로 향후 작업에 대해 추론할 수 있습니다.

의존 관계

경우에 따라 작업이 서로 종속될 수 있습니다.이러한 상호의존성은 유도 비순환 그래프로 나타낼 수 있습니다.직관적으로 일부 작업은 완료될 때까지 시작할 수 없습니다.

각 작업에 필요한 시간을 미리 알고 있다고 가정할 때 최적의 실행 순서를 통해 총 실행 시간을 최소화해야 합니다.이것은 NP-hard 문제이기 때문에 정확하게 해결하기 어려울 수 있습니다.작업 스케줄러와 같이 메타 휴리스틱 방법을 사용하여 최적의 작업 분포를 계산하는 알고리즘이 있습니다.

태스크의 분리

로드 밸런싱 알고리즘 설계에 중요한 태스크의 또 다른 특징은 실행 중에 서브태스크로 분할할 수 있다는 것입니다.나중에 제시된 "트리 모양 계산" 알고리즘은 이 특수성을 크게 활용합니다.

정적 알고리즘 및 동적 알고리즘

스태틱

로드 밸런싱 알고리즘은 작업 분산에 시스템 상태를 고려하지 않을 경우 "정적"입니다.따라서 시스템 상태에는 특정 프로세서의 부하 수준(경우에 따라서는 과부하)과 같은 측정이 포함됩니다.대신, 들어오는 작업의 도착 시간 및 자원 요건과 같은 전체 시스템에 대한 가정이 사전에 이루어집니다.또, 프로세서의 수, 각각의 전력, 통신 속도도 알려져 있습니다.따라서 스태틱 로드밸런싱은 특정 퍼포먼스 기능을 최소화하기 위해 기존의 태스크세트와 사용 가능한 프로세서를 관련짓는 것을 목적으로 합니다.요령은 이 퍼포먼스 기능의 개념에 있습니다.

스태틱 로드밸런싱 기술은 일반적으로 라우터 또는 마스터를 중심으로 집중되어 부하를 분산하고 퍼포먼스 기능을 최적화합니다.이 최소화는 배포되는 태스크와 관련된 정보를 고려하여 예상 실행 시간을 도출할 수 있습니다.

스태틱 알고리즘의 장점은 셋업이 용이하고 상당히 통상적인 태스크(웹 사이트로부터의 HTTP 요구 처리 등)의 경우 매우 효율적이라는 것입니다.그러나 일부 컴퓨팅 유닛의 과부하를 초래할 수 있는 태스크 할당에는 여전히 통계적인 차이가 있습니다.

역학

정적 부하 분산 알고리즘과 달리 동적 알고리즘은 시스템 내 각 컴퓨팅 유닛(노드라고도 함)의 현재 부하를 고려합니다.이 방법에서는 작업을 과부하 노드에서 과부하 노드로 동적으로 이동하여 처리 속도를 높일 수 있습니다.이러한 알고리즘은 설계가 훨씬 복잡하지만, 특히 작업마다 실행 시간이 크게 다를 때 우수한 결과를 얻을 수 있습니다.

다이내믹 로드밸런싱 아키텍처는 특정 노드를 작업분산 전용으로 설정할 필요가 없기 때문에 모듈러성이 향상될 수 있습니다.태스크가 특정 순간의 상태에 따라 프로세서에 일의로 할당되는 경우, 이것은 일의 할당입니다.한편, 시스템 상태와 그 진화에 따라 태스크를 영구적으로 재배포할 수 있는 경우, 이를 동적 [3]할당이라고 합니다.확실히 부하 밸런싱 알고리즘은 그 결정에 도달하기 위해 너무 많은 통신을 필요로 하기 때문에 전체적인 문제 해결 속도가 느려질 위험이 있습니다.

하드웨어 아키텍처

이종 기기

병렬 컴퓨팅 인프라스트럭처는 부하분산을 고려해야 하는 컴퓨팅 파워가 다른 유닛으로 구성되어 있는 경우가 많습니다.

예를 들어, 저전력 유닛은 보다 적은 양의 계산이 필요한 요구를 수신할 수 있습니다.또, 동종 또는 불분명한 요구 사이즈의 경우는, 보다 큰 유닛보다 적은 요구를 수신할 수 있습니다.

공유 메모리 및 분산 메모리

병렬 컴퓨터는 대개 두 개의 큰 범주로 나뉩니다. 모든 프로세서가 병렬로 읽고 쓰는 단일 공통 메모리를 공유하는 것(PRAM 모델)과 각 컴퓨팅 유닛에 자체 메모리가 있는 것(분산 메모리 모델)과 메시지에 의해 정보가 교환되는 것.

공유 메모리 컴퓨터의 경우 쓰기 충돌을 관리하면 각 컴퓨팅 유닛의 개별 실행 속도가 크게 느려집니다.그러나 병렬로 완벽하게 잘 작동할 수 있습니다.반대로 메시지 교환의 경우 각 프로세서는 최대 속도로 동작할 수 있습니다.한편, 일괄적인 메시지 교환에 관해서는, 모든 프로세서는, 통신 국면이 개시될 때까지, 가장 느린 프로세서를 기다릴 필요가 있습니다.

실제로 정확히 어느 하나의 카테고리로 분류되는 시스템은 거의 없습니다.일반적으로 프로세서는 각각 다음 계산에 필요한 데이터를 저장하기 위한 내부 메모리를 가지고 있으며 연속되는 클러스터로 구성되어 있습니다.대부분의 경우 이러한 처리 요소는 분산 메모리와 메시지 전달을 통해 조정됩니다.따라서 로드 밸런싱 알고리즘은 병렬 아키텍처에 고유하게 적응해야 합니다.그렇지 않으면 병렬 문제 해결의 효율성이 크게 저하될 위험이 있습니다.

계층

위에서 설명한 하드웨어 구조에 따라 로드밸런싱 알고리즘에는 2가지 주요 카테고리가 있습니다.한편, 태스크는 "마스터"에 의해 할당되고 "작업자"에 의해 실행되며, 마스터는 작업 진행 상황을 마스터에게 계속 알려주고 동적 알고리즘의 경우 워크로드 할당 또는 재할당을 담당할 수 있습니다.문헌에서는 이것을 「마스터 워커」아키텍처라고 부릅니다.한편, 제어는 다른 노드간에 분산할 수 있다.그런 다음 로드 밸런싱 알고리즘이 각각 실행되어 태스크 할당(및 필요에 따라 재할당 및 분할)에 대한 책임이 공유됩니다.마지막 카테고리는 동적 로드밸런싱 알고리즘을 전제로 하고 있습니다.

각 로드 밸런싱 알고리즘의 설계는 고유하기 때문에 앞의 구별이 인정되어야 합니다.따라서 각 서브클러스터의 "마스터" 노드 등 글로벌 "마스터"의 대상이 되는 중간 전략을 가질 수도 있습니다.마스터 슬레이브 전략과 분산 제어 전략을 번갈아 사용하는 다단계 조직도 있습니다.후자의 전략은 빠르게 복잡해지고 거의 발생하지 않습니다.설계자는 제어하기 쉬운 알고리즘을 선호합니다.

대규모 아키텍처에 대한 적응(확장성)

매우 장기적인 알고리즘(서버, 클라우드 등)에서 컴퓨터 아키텍처는 시간이 지남에 따라 진화합니다.단, 매번 새로운 알고리즘을 설계할 필요는 없습니다.

따라서 로드밸런싱 알고리즘의 매우 중요한 파라미터는 확장 가능한 하드웨어 아키텍처에 적응할 수 있는 것입니다.이것을 알고리즘의 scalability라고 부릅니다.입력 파라미터의 퍼포먼스가 그 파라미터의 사이즈에 비교적 의존하지 않는 경우 알고리즘은 scalable이라고 불립니다.

알고리즘이 다양한 컴퓨팅 유닛 수에 적응할 수 있지만 실행 전에 컴퓨팅 유닛 수를 고정해야 하는 경우 이를 금형가능이라고 합니다.한편, 알고리즘이 실행중의 프로세서의 변동량에 대응할 수 있는 경우, 이 알고리즘은 가단성이 있다고 한다.대부분의 로드 밸런싱 알고리즘은 적어도 성형 가능합니다.[4]

폴트 톨러런스

특히 대규모 컴퓨팅 클러스터에서는 단일 컴포넌트의 장애를 견딜 수 없는 병렬 알고리즘을 실행할 수 없습니다.따라서 프로세서의 정지를 검출하고 계산을 회복할 수 있는 [5]폴트 톨러런스 알고리즘이 개발되고 있습니다.

접근

태스크에 대한 완전한 지식이 있는 정적 배포: 프리픽스 합계

태스크가 서로 독립적이고 각각의 실행 시간과 태스크를 세분화할 수 있다면 단순하고 최적의 알고리즘이 있습니다.

각 프로세서에 동일한 양의 연산을 부여하도록 태스크를 분할함으로써 이제 해야 할 일은 결과를 그룹화하는 것 뿐입니다.이 나눗셈은 프리픽스섬 알고리즘을 사용하여 프로세서 수에 대한 로그 시간으로 계산할 수 있습니다.

태스크의 분할 가능성에 따른 부하 밸런싱 알고리즘

그러나 과제를 세분화할 수 없는 경우(즉, 원자) 과제 할당을 최적화하는 것은 어려운 문제이지만, 각 노드의 크기가 [1]각 노드에 의해 수행되는 총 계산보다 훨씬 작다면 여전히 과제의 비교적 공정한 분배를 근사화할 수 있다.

대부분의 경우 작업 실행 시간은 알 수 없으며 대략적인 근사치만 사용할 수 있습니다.이 알고리즘은 특히 효율적이지만 이러한 시나리오에서는 실행할 수 없습니다.

사전 지식이 없는 정적 부하 분산

실행시간을 전혀 미리 알 수 없는 경우에도 항상 정적 부하분산이 가능하다.

라운드 로빈 스케줄링

라운드로빈 알고리즘에서는 첫 번째 요구가 첫 번째 서버에 전송되고 두 번째 요구가 두 번째 서버에 전송되며, 그 다음 요구가 마지막 서버까지 전송됩니다.그런 다음 다시 시작하여 다음 요청을 첫 번째 서버에 할당하는 방식으로 계속됩니다.

이 알고리즘은 가장 강력한 유닛이 가장 많은 수의 요구를 수신하고 가장 먼저 수신하도록 가중치를 부여할 수 있습니다.

랜덤화 스태틱

랜덤화된 스태틱로드 밸런싱은 단순히 태스크를 다른 서버에 랜덤하게 할당하는 것입니다.이 방법은 꽤 효과가 있다.한편, 작업 수를 미리 알고 있다면 랜덤 치환을 미리 계산하는 것이 훨씬 효율적입니다.이것에 의해, 각 과제의 통신 코스트를 회피할 수 있습니다.모든 프로세서가 배포 마스터에 할당된 태스크를 알고 있기 때문에 배포 마스터는 더 이상 필요하지 않습니다.작업 수를 알 수 없는 경우에도 모든 프로세서가 알고 있는 의사 랜덤 할당 생성과의 통신을 피할 수 있습니다.

이 전략의 성능(특정 고정 작업 세트에 대한 총 실행 시간으로 측정됨)은 작업의 최대 크기에 따라 감소합니다.

다른이들

물론 다른 할당 방법도 있습니다.

  • 작업량 감소:더 적은 작업을 수행하여 서버에 더 많은 작업을 할당합니다(메서드에 가중치를 부여할 수도 있습니다).
  • 해시: 해시 테이블에 따라 쿼리를 할당합니다.
  • 2가지 선택지의 힘: 2개의 서버를 랜덤으로 선택하여 2개의 옵션 [6][7]중 하나를 선택합니다.

마스터 워커 방식

마스터 워커 방식은 가장 단순한 다이내믹로드 밸런싱 알고리즘 중 하나입니다.마스터는 모든 작업자에게 워크로드를 분배합니다('슬레이브'라고도 함).처음에는 모든 워커가 아이돌 상태이며 마스터에게 보고합니다.마스터는 작업자 요청에 응답하여 작업을 배포합니다.그는 더 이상 할 일이 없을 때 직원들에게 일을 부탁하는 것을 그만두라고 알린다.

이 시스템의 장점은 부담을 매우 공평하게 분배할 수 있다는 것이다.실제로 할당에 필요한 시간을 고려하지 않으면 실행 시간은 위의 프레픽스 합계와 비슷합니다.

이 알고리즘의 문제는 필요한 통신량이 많기 때문에 많은 프로세서에 적응하기 어렵다는 것입니다.이러한 확장성 결여로 인해 대규모 서버 또는 대규모 병렬 컴퓨터에서는 빠르게 동작할 수 없게 됩니다.마스터가 병목현상으로 작용합니다.

마스터 워커와 병목 현상

그러나 마스터를 다른 프로세서에서 사용할 수 있는 태스크리스트로 대체함으로써 알고리즘의 품질을 크게 향상시킬 수 있습니다.이 알고리즘은 구현이 조금 더 어렵지만 매우 큰 컴퓨팅 센터에는 아직 충분하지 않지만 훨씬 더 나은 확장성을 약속합니다.

시스템에 대한 지식이 없는 비계층 아키텍처: 작업 도둑질

작업 완료에 필요한 시간을 알 수 없을 때 확장성 문제를 해결하는 또 다른 방법은 작업 도둑질입니다.

이 접근방식은 랜덤 또는 미리 정의된 방법으로 각 프로세서에 일정 수의 작업을 할당하고 비활성 프로세서가 액티브 또는 과부하된 프로세서에서 작업을 "스틸"할 수 있도록 하는 것으로 구성됩니다.태스크 분할 모델과 프로세서 간의 교환을 결정하는 규칙에 의해 정의되는 이 개념의 몇 가지 구현이 존재합니다.이 기술은 특히 효과적이지만, 문제를 해결하는 것이 아니라 통신이 프로세서의 주요 직업이 되지 않도록 보장하는 것이 필요하기 때문에 구현하기가 어렵습니다.

원자 태스크의 경우 부하가 낮은 프로세서가 부하가 가장 높은 프로세서에 컴퓨팅 능력을 제공하는 전략과 부하가 가장 높은 유닛이 할당된 워크로드를 경감하는 전략을 구분할 수 있습니다.네트워크의 부하가 높을 때는 부하가 적은 유닛이 가용성을 제공하는 것이 효율적이며 네트워크의 부하가 적을 때는 부하가 높은 프로세서가 부하가 높은 프로세서의 지원을 필요로 하는 것으로 나타났습니다[8].이 규칙은 교환되는 메시지의 수를 제한합니다.

원자 수준을 넘어 분할할 수 없는 하나의 큰 태스크에서 시작하는 경우, 상위 태스크가 워크 트리로 분산되는 매우 효율적인 알고리즘인 "트리 모양 계산"[9]이 있다.

원칙

처음에 많은 프로세서에는 빈 태스크가 있습니다.단, 이 태스크에서 순차적으로 동작하는 태스크는 제외됩니다.아이돌 상태의 프로세서는, 다른 프로세서에 랜덤으로 요구를 발행합니다(액티브할 필요는 없습니다).후자가 작업 중인 작업을 세분화할 수 있는 경우 작업의 일부를 요청을 하는 노드에 전송하여 세분화합니다.그렇지 않으면 빈 작업이 반환됩니다.이것은 나무 구조를 유도한다.그런 다음 하위 작업이 완료되면 부모 프로세서에 종료 신호를 전송하여 트리의 루트에 도달할 때까지 부모 프로세서에 메시지를 전송해야 합니다.첫 번째 프로세서(루트)가 완료되면 글로벌 종료 메시지를 브로드캐스트할 수 있습니다.결국 나무 위로 올라가 결과를 모아야 한다.

효율성.

이러한 알고리즘의 효율은 작업 컷팅과 통신 시간이 수행해야 할 작업에 비해 너무 높지 않은 경우 접두사 합계에 가깝습니다.너무 높은 통신 비용을 피하기 위해 공유 메모리에 작업 목록을 상상하는 것이 가능합니다.따라서 요구는 마스터 프로세서의 요구에 따라 이 공유 메모리 상의 특정 위치에서 읽기만 하면 됩니다.

사용 사례

부하 밸런싱 알고리즘은 병렬 연산을 통한 효율적인 문제 해결과 더불어 다수의 사용자가 있는 사이트가 초당 다수의 요청을 처리할 수 있어야 하는 HTTP 요청 관리에서 널리 사용됩니다.

인터넷 기반 서비스

로드 밸런싱에서 가장 일반적으로 사용되는 응용 프로그램 중 하나는 여러 서버에서 단일 인터넷 서비스(서버 팜이라고도 함)를 제공하는 것입니다.일반적으로 로드밸런싱된 시스템에는 일반적인 웹 사이트, 대규모 인터넷 릴레이 채팅네트워크, 고대역폭 File Transfer Protocol(FTP) 사이트, Network News Transfer Protocol(NNTP) 서버, Domain Name System(DNS) 서버 및 데이터베이스가 포함됩니다.

라운드 로빈 DNS

주요 기사: 라운드 로빈 DNS

라운드 로빈 DNS는 전용 소프트웨어 또는 하드웨어 노드가 필요 없는 로드밸런싱의 대체 방법입니다이 기술에서는, 복수의 IP 주소가 1 개의 도메인명에 관련지어져 클라이언트에 라운드 로빈 방식으로 IP 가 주어집니다.유효기간이 짧은 클라이언트에 IP가 할당되기 때문에 클라이언트는 다음에 요구되고 있는 인터넷서비스에 액세스 할 때 다른 IP를 사용할 가능성이 높아집니다.

DNS 위임

DNS를 사용한 로드밸런싱의 또 다른 효과적인 기술은www.example.org 는, 그 존이 Web 사이트를 서비스 하고 있는 같은 서버에 의해서 서비스 되는 서브 도메인입니다.이 기술은 특히 개별 서버가 인터넷상에 지리적으로 분산되어 있는 경우에 효과적입니다.예를 들어 다음과 같습니다.

one.example.org A 192.0.2.1 two.example.org A 203.0.124.2 www.example.org NS one.example.org NS two.example.org NS two.example.org

단, 각 서버의 www.example.org 존파일은 다르기 때문에 각 서버는 자신의 IP 주소를 [10]A레코드로 해결합니다.서버 1에서는 www.example.org 보고서용 존파일이 다음과 같이 표시됩니다.

192.0.2.1의 경우

서버 2 에서는, 같은 존파일에 다음이 포함됩니다.

@ in 203.0.1982.2

이렇게 하면 서버가 다운되면 DNS는 응답하지 않고 웹 서비스는 트래픽을 수신하지 않습니다.1대의 서버에의 회선이 congestion 하고 있는 경우는, DNS 의 신뢰성이 떨어지기 때문에, 그 서버에 도달하는 HTTP 트래픽이 적어집니다.또한 리졸바에 대한 가장 빠른 DNS 응답은 거의 항상 네트워크의 가장 가까운 서버로부터의 응답이기 때문에 지리적 영향을 받기[citation needed] 쉬운 로드밸런싱이 보증됩니다.A 레코드의 짧은 TTL을 사용하면 서버가 다운되었을 때 트래픽이 신속하게 전송되도록 할 수 있습니다.이 기술로 인해 세션 중에 개별 클라이언트가 개별 서버 간에 전환될 수 있다는 점을 고려해야 합니다.

클라이언트 측 랜덤 로드밸런싱

로드 밸런싱의 또 다른 접근방식은 서버 IP 목록을 클라이언트에 전달한 후 클라이언트가 각 [11][12]접속 목록에서 무작위로 IP를 선택하도록 하는 것입니다.이는 기본적으로 동일한 부하를 생성하는 모든 클라이언트와 대수의[12] 법칙에 의존하여 서버 간에 부하를 상당히 균일하게 분산시킵니다.클라이언트 측 랜덤 로드밸런싱은 라운드 로빈 DNS보다 부하 분산이 뛰어난 경향이 있다고 알려져 있습니다.이것은 라운드 로빈 DNS의 캐싱 문제에 기인하고 있습니다.대규모 DNS 캐싱 서버의 경우 클라이언트 측 랜덤 선택은 영향을 받지 않고 라운드 로빈 DNS에 대해 분산이 왜곡되는 경향이 있습니다.의 DNS [12]캐싱입니다.

이 어프로치에서는, IP 리스트를 클라이언트에 전달하는 방법이 다양해, DNS 리스트로서 실장할 수도 있습니다(라운드 로빈을 사용하지 않고 모든 클라이언트에 송신할 수도 있고, 리스트에 하드 코드 하는 것에 의해서 실장할 수도 있습니다.「스마트 클라이언트」를 사용하고, 랜덤으로 선택한 서버가 다운하고 있는 것을 검출해, 다시 랜덤으로 접속하는 경우, 폴트 톨러런스도 실현됩니다.

서버측 로드 밸런서

인터넷 서비스의 경우 서버 측 로드 밸런서는 일반적으로 외부 클라이언트가 서비스에 접속하는 포트에서 수신하는 소프트웨어 프로그램입니다.로드 밸런서는 요구를 "백엔드" 서버 중 하나로 전송합니다.백엔드 서버는 일반적으로 로드 밸런서에 응답합니다.이를 통해 로드 밸런서는 내부 기능 분리에 대해 클라이언트 모르게 클라이언트에 응답할 수 있습니다.또, 클라이언트가 백엔드 서버에 직접 접속하는 것을 방지합니다.이것에 의해, 내부 네트워크의 구조를 숨기고, 커널의 네트워크 스택이나 다른 포토로 실행되고 있는 관련 없는 서비스에 대한 공격을 방지할 수 있기 때문에, 시큐러티상의 메리트가 있습니다.

일부 로드 밸런서는 모든 백엔드 서버를 사용할 수 없는 경우에 특별한 작업을 수행하기 위한 메커니즘을 제공합니다.여기에는 백업 로드 밸런서로 전달하거나 중단에 대한 메시지를 표시하는 작업이 포함될 수 있습니다.

로드 밸런서 자체가 단일 장애 지점이 되지 않는 것도 중요합니다.일반적으로 로드 밸런서는 특정 애플리케이션에서 필요한 경우 세션 [13]지속성 데이터도 복제하는 고가용성 쌍으로 구현됩니다.특정 어플리케이션에서는 정의된 네트워크 이외의 차분 공유 플랫폼에서 로드밸런싱 포인트를 오프셋함으로써 이 문제에 대한 내성이 프로그램되어 있습니다.이러한 함수와 쌍을 이루는 순차 알고리즘은 특정 데이터베이스에 [14]고유한 유연한 매개 변수로 정의됩니다.

스케줄링 알고리즘

로드 밸런서에서는 요구를 송신하는 백엔드 서버를 결정하기 위해 로드밸런싱 방식이라고도 불리는 다양한 스케줄링 알고리즘을 사용합니다.단순한 알고리즘에는 랜덤 선택, 라운드 로빈 또는 최소 접속이 [15]포함됩니다.보다 고도의 로드밸런서에서는 서버의 보고된 부하, 최소 응답 시간, 업/다운 상태(일종의 모니터링 폴링에 의해 결정), 액티브한 접속 수, 지리적 위치, 기능, 최근 할당된 트래픽 양 등의 추가 요인을 고려할 수 있습니다.

고집

로드밸런싱 서비스를 운용할 때 중요한 문제는 사용자의 세션에서 여러 요구에 걸쳐 보관해야 하는 정보를 처리하는 방법입니다.이 정보가 하나의 백엔드 서버에 로컬로 저장되어 있는 경우 다른 백엔드 서버로 전송되는 후속 요구는 해당 정보를 찾을 수 없습니다.이는 재계산할 수 있는 캐시 정보일 수 있습니다.이 경우 다른 백엔드 서버에 대한 요구 로드밸런싱에 의해 퍼포먼스 [15]문제가 발생합니다.

클라이언트가 언제든지 백엔드 서버에 접속해도 사용자 환경에 영향을 주지 않도록 로드 밸런서의 배후에 있는 서버 클러스터는 세션을 인식하지 않는 것이 이상적입니다.이것은 보통 공유 데이터베이스 또는 메모리 내 세션 데이터베이스(Memcached 등)를 사용하여 이루어집니다.

세션 데이터 문제에 대한 기본적인 해결 방법 중 하나는 사용자 세션 내의 모든 요청을 동일한 백엔드 서버로 일관되게 전송하는 것입니다.이것은 "지속성" 또는 "붙임성"으로 알려져 있습니다.이 기술의 중요한 단점은 자동 페일오버가 없다는 것입니다.백엔드 서버가 다운되면 세션별 정보에 액세스할 수 없게 되고 이에 따라 세션이 손실됩니다.같은 문제는 보통 중앙 데이터베이스 서버와 관련되어 있습니다.웹 서버가 '스테이트리스'로 '스틱'이 아닌 경우에도 중앙 데이터베이스는 마찬가지입니다(아래 참조).

특정 서버에 대한 할당은 사용자 이름, 클라이언트 IP 주소 또는 랜덤에 기반할 수 있습니다.DHCP, 네트워크주소 변환 및 웹 프록시에 의해 클라이언트의 인식 주소가 변경되기 때문에 이 방법은 신뢰성이 떨어질 수 있습니다.랜덤 할당은 로드 밸런서에서 기억해야 하므로 스토리지에 부담이 생깁니다.로드 밸런서가 교체되거나 실패할 경우 이 정보가 손실될 수 있으며, 할당 테이블에 사용할 수 있는 공간을 초과하지 않도록 시간 초과 기간 후 또는 부하가 높은 기간 동안 할당을 삭제해야 할 수 있습니다.랜덤 할당 방법에서는 클라이언트가 일부 상태를 유지해야 하는데, 예를 들어 웹 브라우저가 쿠키 저장소를 사용하지 않도록 설정한 경우 문제가 될 수 있습니다.고도의 로드 밸런서는 여러 가지 지속성 기술을 사용하여 하나의 방법의 단점을 회피합니다.

또 다른 해결책은 세션별 데이터를 데이터베이스에 유지하는 것입니다.이는 일반적으로 데이터베이스에 대한 부하를 증가시키기 때문에 성능에 좋지 않습니다.데이터베이스는 세션별 데이터보다 일시적인 정보를 저장하는 데 가장 적합합니다.데이터베이스가 단일 장애 지점이 되는 것을 방지하고 확장성을 높이기 위해 데이터베이스는 여러 머신에 걸쳐 복제되며 로드 밸런싱은 이러한 복제본 간에 쿼리 로드를 분산하기 위해 사용됩니다.Microsoft의 ASP.net 스테이트 서버 테크놀로지는 세션 데이터베이스의 예입니다.웹 팜 내의 모든 서버는 세션 데이터를 상태 서버에 저장하고 팜 내의 모든 서버는 데이터를 가져올 수 있습니다.

클라이언트가 웹 브라우저인 매우 일반적인 경우 세션별 데이터를 브라우저 자체에 저장하는 방법이 간단하지만 효율적입니다.이를 실현하기 위한 한 가지 방법은 브라우저 쿠키를 사용하는 것입니다.이 쿠키에는 타임스탬프가 찍혀 암호화되어 있습니다.또 하나는 URL 개서입니다.일반적으로 클라이언트에 세션 데이터를 저장하는 것이 좋습니다.그러면 로드 밸런서는 요구를 처리할 백엔드 서버를 자유롭게 선택할 수 있습니다.단, 이 상태 데이터 처리 방식은 세션 상태 페이로드가 크고 서버 상의 모든 요구에 따라 이를 재계산할 수 없는 복잡한 비즈니스 로직 시나리오에는 적합하지 않습니다.최종 사용자가 송신된 URL을 쉽게 변경하여 세션스트림을 변경할 수 있기 때문에 URL 개서에는 중대한 보안 문제가 있습니다.

또 다른 영구 데이터 저장 솔루션은 각 데이터 블록에 이름을 관련짓고 분산 해시 테이블을 사용하여 사용 가능한 서버 중 하나에 해당 이름을 의사 랜덤으로 할당한 후 할당된 서버에 해당 데이터 블록을 저장하는 것입니다.

로드 밸런서 기능

하드웨어 및 소프트웨어 로드밸런서에는 다양한 특수 기능이 있습니다.로드 밸런서의 기본적인 기능은 스케줄링 알고리즘에 따라 클러스터 내의 여러 백엔드 서버에 착신 요구를 분산할 수 있는 것입니다.다음 기능의 대부분은 벤더 고유의 것입니다.

비대칭 부하
비율을 수동으로 할당하면 일부 백엔드 서버가 다른 서버보다 더 많은 워크로드를 할당할 수 있습니다.이것은, 일부의 서버가 다른 서버보다 용량이 큰 것을 대략적으로 설명하기 위해서 사용되는 경우가 있습니다.또, 항상 원하는 대로 동작하지 않는 경우도 있습니다.
우선 활성화
사용 가능한 서버의 수가 특정 수 이하로 떨어지거나 부하가 너무 높아지면 스탠바이 서버를 온라인으로 할 수 있습니다.
TLS 오프로드 및 액셀러레이션
TLS(또는 이전 SSL) 가속은 암호화 프로토콜 계산을 특수 하드웨어에 오프로드하는 기술입니다.워크로드에 따라서는 TLS 요청의 암호화 및 인증 요건의 처리가 웹 서버의 CPU에 대한 요구의 주요 부분이 될 수 있습니다.요구가 증가함에 따라 TLS 오버헤드가 웹 서버 간에 분산되기 때문에 사용자의 응답 시간이 느려집니다.웹 서버에서 이러한 요구를 제거하기 위해 밸런서는 TLS 연결을 종료하고 HTTPS 요청을 HTTP 요청으로 웹 서버에 전달할 수 있습니다.밸런서 자체가 과부하가 되지 않으면 최종 사용자가 인식하는 퍼포먼스가 현저하게 저하되지 않습니다.이 접근방식의 단점은 모든 TLS 처리가 단일 디바이스(밸런서)에 집중되어 새로운 보틀 넥이 될 수 있다는 것입니다.일부 로드 밸런서 장치에는 TLS를 처리하기 위한 특수 하드웨어가 포함되어 있습니다.상당히 비싼 전용 하드웨어인 로드 밸런서를 업그레이드하는 대신 TLS 오프로드 없이 웹 서버를 몇 대 추가하는 것이 더 저렴할 수 있습니다.또한 Oracle/Sun 등의 일부 서버 벤더는 현재 T2000 등의 CPU에 암호화 액셀러레이션 하드웨어를 탑재하고 있습니다.F5 Networks는 TLS 트래픽 암호화 및 복호화에 사용되는 전용 TLS 액셀러레이션하드웨어 카드를 Local Traffic Manager(LTM; 로컬트래픽 매니저)에 내장하고 있습니다.밸런서에서의 TLS 오프로드의 분명한 이점 중 하나는 HTTPS 요청의 데이터를 기반으로 균형 조정 또는 콘텐츠 전환을 수행할 수 있다는 것입니다.
분산 서비스 거부(DDoS) 공격 보호
로드 밸런서는 SYN cookie나 지연 바인딩(백엔드 서버는 TCP 핸드쉐이크가 완료될 때까지 클라이언트를 인식하지 않음) 등의 기능을 제공하여 SYN 플래드 공격을 완화하고 일반적으로 서버에서 보다 효율적인 플랫폼으로 작업을 오프로드할 수 있습니다.
HTTP 압축
HTTP 압축은 모든 최신 웹 브라우저에서 사용할 수 있는 gzip 압축을 사용하여 HTTP 개체에 대해 전송되는 데이터 양을 줄입니다.응답이 크고 클라이언트가 멀리 떨어져 있을수록 이 기능은 응답 시간을 단축할 수 있습니다.단점은 이 기능을 통해 로드 밸런서에 CPU 수요가 증가하며 대신 웹 서버가 이를 수행할 수 있다는 것입니다.
TCP 오프로드
벤더마다 다른 용어를 사용하고 있습니다만, 통상은 각 클라이언트로부터의 각 HTTP 요구는 다른 TCP 접속입니다.이 기능은 HTTP/1.1을 사용하여 여러 클라이언트로부터의 여러 HTTP 요구를 백엔드 서버에 대한 단일 TCP 소켓으로 통합합니다.
TCP 버퍼링
로드 밸런서는 서버로부터의 응답을 버퍼링하여 저속 클라이언트에 데이터를 스푼으로 전달할 수 있습니다.따라서 웹 서버는 클라이언트에 전체 요청을 직접 전송할 때보다 더 빠르게 스레드를 해방할 수 있습니다.
다이렉트 서버 반환
요구와 응답의 네트워크 경로가 다른 비대칭 부하 분산 옵션.
헬스 체크
밸런서는 애플리케이션 계층 상태를 위해 서버를 폴링하고 풀에서 장애가 발생한 서버를 제거합니다.
HTTP 캐시
밸런서는 정적 콘텐츠를 저장하므로 서버에 연결하지 않고도 일부 요청을 처리할 수 있습니다.
콘텐츠 필터링
일부 밸런서는 통과 중에 트래픽을 임의로 변경할 수 있습니다.
HTTP 보안
일부 밸런서는 HTTP 오류 페이지를 숨기고 HTTP 응답에서 서버 ID 헤더를 삭제하며 최종 사용자가 해당 헤더를 조작할 수 없도록 쿠키를 암호화할 수 있습니다.
priority 큐잉
레이트 쉐이핑이라고도 불리는 트래픽에 다른 priority를 부여하는 기능.
콘텐츠 인식 스위칭
대부분의 로드 밸런서는 요구가 암호화되지 않은 경우(HTTP) 또는 HTTPS 요구가 로드 밸런서로 종료(복호화)되는 경우(HTTP 경유)에 근거해, 요구되고 있는 URL 에 근거해 다른 서버에 요구를 송신할 수 있습니다.
클라이언트 인증
웹 사이트에 대한 액세스를 허용하기 전에 다양한 인증 소스에 대해 사용자를 인증합니다.
프로그래밍 방식의 트래픽 조작
하나 이상의 밸런서를 통해 스크립트 언어를 사용하여 사용자 지정 균형 조정 방법, 임의 트래픽 조작 등을 수행할 수 있습니다.
방화벽
방화벽은 네트워크 보안상의 이유로 백엔드 서버에 대한 직접 접속을 방해할 수 있습니다.
침입 방지 시스템
침입 방지 시스템은 방화벽 보안에 의해 제공되는 네트워크/트랜스포트 계층과 더불어 애플리케이션 계층 보안을 제공합니다.

전기 통신

로드 밸런싱은 다중 통신 링크가 있는 응용 프로그램에서 유용합니다.예를 들어, 한 회사에 여러 개의 인터넷 연결이 있어 연결 중 하나가 실패할 경우 네트워크 액세스를 보장할 수 있습니다.페일오버 배치란 1개의 링크가 통상의 사용을 위해 지정되어 있는 것을 의미하며, 2번째 링크는 프라이머리 링크에 장애가 발생했을 경우에만 사용됩니다.

로드 밸런싱을 사용하면 양쪽 링크를 항상 사용할 수 있습니다.디바이스 또는 프로그램은 모든 링크의 가용성을 감시하고 패킷 전송 경로를 선택합니다.여러 링크를 동시에 사용하면 사용 가능한 대역폭이 증가합니다.

최단 패스 브리징

TRIL(Transparent Interconnection of Lots of Links)을 사용하면 이더넷이 임의의 토폴로지를 가질 수 있으며 설정 및 사용자 개입 없이 Dijkstra 알고리즘을 통해 흐름 쌍별로 부하 분할이 가능합니다.TRIL의 촉매제는 2002년 [16][17]11월 13일 베스 이스라엘 디콘스 메디컬 센터에서 시작된 이벤트입니다.Rridges[18] [sic]의 개념은 2004년에 [19]전기전자공학연구소에 처음 제안되었으며, 2005년에[20] TRIL로 알려진 것을 거부하였고, 2006년부터 2012년까지[21] Shortest Path Bridging으로 알려진 호환되지 않는 변형을 고안하였다.

IEEE는 2012년 [22]5월에 Shortest Path Bridging(SPB)이라고도 불리는 IEEE 802.1aq 표준을 승인했습니다.SPB를 사용하면 모든 링크가 여러 등가 비용 경로를 통해 활성화되고 컨버전스 시간이 단축되어 다운타임을 줄일 수 있습니다.또한 네트워크의 [23][24]모든 경로에서 트래픽을 로드 쉐어링할 수 있기 때문에 메시 네트워크토폴로지(부분적으로 접속 또는 완전 접속)에서의 로드밸런싱 사용을 심플화할 수 있습니다.SPB는 설정 시 인위적인 오류를 실질적으로 배제하도록 설계되었으며 이더넷을 레이어 [25]2에서 사실상의 프로토콜로 확립한 플러그 앤 플레이 특성을 유지합니다.

라우팅 1

상세 정보:라우팅

많은 통신회사들이 자사 네트워크 또는 외부 네트워크에 대한 여러 경로를 보유하고 있습니다.고도의 로드밸런싱을 사용하여 특정 링크의 네트워크 congestion를 회피하고 때로는 외부 네트워크 간 전송 비용을 최소화하거나 네트워크의 신뢰성을 향상시킵니다.

로드 밸런싱을 사용하는 다른 방법은 네트워크모니터링 액티비티입니다로드 밸런서를 사용하면 대규모 데이터 플로우를 여러 서브플로우로 분할하고 여러 네트워크 분석기를 사용하여 각각 원래 데이터의 일부를 읽을 수 있습니다.이것은, 10 GbE 나 STM64 [26]와 같은 고속 네트워크를 감시하는 경우에 매우 편리합니다.이 경우 와이어 속도로 복잡한 데이터 처리가 불가능할 수 있습니다.

데이터센터 네트워크

로드 밸런싱은 데이터센터 네트워크에서 널리 사용되며, 임의의 2대의 [27]서버 간에 많은 기존 경로에 트래픽을 분산합니다.네트워크 대역폭을 보다 효율적으로 사용하고 프로비저닝 비용을 절감할 수 있습니다.일반적으로 데이터센터 네트워크의 로드밸런싱은 정적 또는 동적 중 하나로 분류할 수 있습니다.

스태틱 로드밸런싱에서는, 송신원주소와 행선지 주소, 및 트래픽흐름의 포토 번호의 해시를 계산해, 그것을 사용해 플로우가 기존의 패스 중 하나에 할당되는 방법을 결정합니다.다이내믹 로드밸런싱에서는 다른 경로에서의 대역폭 사용을 감시함으로써 트래픽플로우를 패스에 할당합니다.동적 할당은 사전 또는 사후 대응적일 수도 있습니다.전자의 경우 할당은 일단 이루어지면 고정되지만 후자의 경우 네트워크 로직은 사용 가능한 경로를 계속 감시하고 네트워크 사용률 변화에 따라 이들 사이를 흐르는 흐름을 전환합니다(새로운 흐름의 도착 또는 기존 흐름의 완료).데이터센터 네트워크의 로드밸런싱에 관한 포괄적인 개요를 이용할 [27]수 있게 되었습니다.

페일오버

로드 밸런싱은 페일오버(하나 이상의 컴포넌트에 장애가 발생한 후 서비스를 계속)를 구현하기 위해 자주 사용됩니다.컴포넌트는 지속적으로 감시됩니다(예를 들어 웹 서버는 기존의 페이지를 취득하여 감시할 수 있습니다).또, 1개의 컴포넌트가 응답하지 않게 되면 로드 밸런서에 통지되어 트래픽을 송신하지 않게 됩니다.구성 요소가 다시 온라인 상태가 되면 로드 밸런서가 해당 구성 요소에 대한 트래픽 재루팅을 시작합니다.이 기능이 작동하려면 서비스 용량(N+1 용장성)을 초과하는 컴포넌트가 하나 이상 있어야 합니다.이 방법은 장애 발생 시(듀얼 모듈러 이중화)를 인계하는 단일 백업 구성 요소와 모든 활성 구성 요소를 쌍으로 구성하는 페일오버 방식보다 훨씬 저렴하고 유연합니다.RAID 시스템에 따라서는, 핫 스페어를 사용해 같은 효과를 [28]얻을 수도 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (11 September 2019). Sequential and parallel algorithms and data structures : the basic toolbox. ISBN 978-3-030-25208-3.
  2. ^ Liu, Qi; Cai, Weidong; Jin, Dandan; Shen, Jian; Fu, Zhangjie; Liu, Xiaodong; Linge, Nigel (30 August 2016). "Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment". Sensors. 16 (9): 1386. Bibcode:2016Senso..16.1386L. doi:10.3390/s16091386. PMC 5038664. PMID 27589753. S2CID 391429.
  3. ^ Alakeel, Ali (November 2009). "A Guide to Dynamic Load Balancing in Distributed Computer Systems". International Journal of Computer Science and Network Security (IJCSNS). 10.
  4. ^ Asghar, Sajjad; Aubanel, Eric; Bremner, David (October 2013). "A Dynamic Moldable Job Scheduling Based Parallel SAT Solver". 2013 42nd International Conference on Parallel Processing: 110–119. doi:10.1109/ICPP.2013.20. ISBN 978-0-7695-5117-3. S2CID 15124201.
  5. ^ Punetha Sarmila, G.; Gnanambigai, N.; Dinadayalan, P. (2015). "Survey on fault tolerant — Load balancing algorithmsin cloud computing". 2nd International Conference on Electronics and Communication Systems (ICECS): 1715–1720. doi:10.1109/ECS.2015.7124879. ISBN 978-1-4799-7225-8. S2CID 30175022.
  6. ^ "NGINX and the "Power of Two Choices" Load-Balancing Algorithm". nginx.com. 2018-11-12. Archived from the original on 2019-12-12.
  7. ^ "Test Driving "Power of Two Random Choices" Load Balancing". haproxy.com. 2019-02-15. Archived from the original on 2019-02-15.
  8. ^ Eager, Derek L; Lazowska, Edward D; Zahorjan, John (1 March 1986). "A comparison of receiver-initiated and sender-initiated adaptive load sharing". Performance Evaluation. 6 (1): 53–68. doi:10.1016/0166-5316(86)90008-8. ISSN 0166-5316.
  9. ^ Sanders, Peter (1998). "Tree Shaped Computations as a Model for Parallel Applications". Workshop on Application Based Load Balancing (Alv '98), München, 25. - 26. März 1998 - Veranst. Vom Sonderforschungsbereich 342 "Werkzeuge und Methoden für die Nutzung Paralleler Rechnerarchitekturen". Ed.: A. Bode: 123. doi:10.5445/ir/1000074497.
  10. ^ IPv4 주소 레코드(A)
  11. ^ 패턴: 클라이언트 측 로드밸런싱
  12. ^ a b c MMOG 서버측 아키텍처프론트 엔드 서버 및 클라이언트 측 랜덤 로드밸런싱
  13. ^ "High Availability". linuxvirtualserver.org. Retrieved 2013-11-20.
  14. ^ Ranjan, R (2010). "Peer-to-peer cloud provisioning: Service discovery and load-balancing". Cloud Computing.
  15. ^ a b "Load Balancing 101: Nuts and Bolts". F5 Networks. 2017-12-05. Archived from the original on 2017-12-05. Retrieved 2018-03-23.
  16. ^ "All Systems Down" (PDF). cio.com. IDG Communications, Inc. Archived from the original (PDF) on 23 September 2020. Retrieved 9 January 2022.
  17. ^ "All Systems Down". cio.com. IDG Communications, Inc. Archived from the original on 9 January 2022. Retrieved 9 January 2022.
  18. ^ "Rbridges: Transparent Routing" (PDF). courses.cs.washington.edu. Radia Perlman, Sun Microsystems Laboratories. Archived from the original (PDF) on 9 January 2022. Retrieved 9 January 2022.
  19. ^ "Rbridges: Transparent Routing". researchgate.net. Radia Perlman, Sun Microsystems; Donald Eastlake 3rd, Motorola.
  20. ^ "TRILL Tutorial" (PDF). postel.org. Donald E. Eastlake 3rd, Huawei.
  21. ^ "IEEE 802.1: 802.1aq - Shortest Path Bridging". ieee802.org. Institute of Electrical and Electronics Engineers.
  22. ^ Shuang Yu (8 May 2012). "IEEE APPROVES NEW IEEE 802.1aq™ SHORTEST PATH BRIDGING STANDARD". IEEE. Retrieved 2 June 2012.
  23. ^ Peter Ashwood-Smith (24 Feb 2011). "Shortest Path Bridging IEEE 802.1aq Overview" (PDF). Huawei. Archived from the original (PDF) on 15 May 2013. Retrieved 11 May 2012.
  24. ^ Jim Duffy (11 May 2012). "Largest Illinois healthcare system uproots Cisco to build $40M private cloud". PC Advisor. Retrieved 11 May 2012. Shortest Path Bridging will replace Spanning Tree in the Ethernet fabric.
  25. ^ "IEEE Approves New IEEE 802.1aq Shortest Path Bridging Standard". Tech Power Up. 7 May 2012. Retrieved 11 May 2012.
  26. ^ 모하마드 누모함마드푸어, 카울리기 S.Raghavendra Inter-Datacenter Wide Area Networks를 통한 적응형 루팅을 사용한 흐름 완료 시간 최소화 IEEE INFOCOM 2018 포스터 세션, DOI: 10.1340/RG.2.36009.90720 2019년 1월 6일
  27. ^ a b M. Noormohammadpour, C. S. Raghavendra, "데이터센터 트래픽 제어: 테크닉과 트레이드오프의 이해」, IEEE 커뮤니케이션 조사 및 튜토리얼, vol. PP, No. 99, 페이지 1-1.
  28. ^ 페일오버 및 로드 밸런싱 IBM 2019년 1월 6일

외부 링크

Wikimedia Commons에는 부하 분산(컴퓨팅)과 관련된 미디어가 있습니다.