가상 서버 스케쥴링 알고리즘

원문: http://tunelinux.pe.kr/virtual/scheduling.html

Round-Robin Scheduling (라운드 로빈 스케쥴링)

말그대로 라운드-로빈 방식을 이용해 네트웍 연결을 서로 다른 서버에 연결하는 것을 말한다. 이경우 실제서버의 연결갯수나 반응시간등은 고려를 하지 않는다. 그렇지만 약간의 차이가 있다. 라운드 로빈 DNS는 단일한 도메인을 서로 다른 IP로 해석을 하지만, 스케쥴링의 기초는 호스트 기반이며 캐싱때문에 알고리즘을 효율적으로 사용하기 힘들다. 그래서 실제 서버사이에 동적인 부하 불균형이 심각해질 수 있다. 가상 서버의 스케쥴링 기초는 네트웍 기반이며 라운드 로빈 DNS 에 비해 훨씬 더 훌륭하다.

Weighted Round-Robin Scheduling (가중치기반 라운드 로빈 스케쥴링)

가중치기반 라운드 로빈 스케쥴링은 실제 서버에 서로 다른 처리 용량을 지정할 수 있다. 각 서버에 가중치를 부여할 수 있으며, 여기서 지정한 정수값을 통해 처리 용량을 정한다. 기본 가중치는 1이다. 예를 들어 실제 서버가 A,B,C 이고 각각의 가중치가 4,3,2 일 경우 스케쥴링 순서는 ABCABCABA 가 된다.

가중치가 있는 라운드 로빈 스케쥴링을 사용하면 실제 서버에서 네트웍 접속을 셀 필요가 없고 동적 스케쥴링 알고리즘보다 스케쥴링의 과부하가 적으므로 더 많은 실제 서버를 운영할 수 있다. 그러나 요청에 대한 부하가 매우 많을 경우 실제 서버사이에 동적인 부하 불균형 상태가 생길 수 있다.

라운드 로빈 스케쥴링은 가중치기반 라운드 로빈 스케쥴링의 특별한 한 종류이며 모든 가중치가 동일한 경우이다. 가상 서버의 규칙을 변경하고나서 스케쥴링 순서를 생성하는데는 거의 과부하가 걸리지 않으며 실제 스케쥴링에 어떠한 과부하도 추가하지 않는다. 그러므로 라운드 로빈 스케쥴링만 단독으로 실행하는 것은 불필요한 일이다.

Least-Connection Scheduling (최소 접속 스케쥴링)

최소 접속 스케쥴링은 가장 접속이 적은 서버로 요청을 직접 연결하는 방식을 말한다. 각 서버에서 동적으로 실제 접속한 숫자를 세어야 하므로 동적인 스케쥴링 알고리즘 중의 하나이다. 비슷한 성능의 서버로 구성된 가상 서버는 아주 큰 요구가 한 서버로만 집중되지 않기 때문에, 접속부하가 매우 큰 경우에도 아주 효과적으로 분산을 한다.

가장 빠른 서버에서 더 많은 네트웍 접속을 처리할 수 있다. 그러므로 다양한 처리 용랑을 지닌 서버로 구성했을 경우에도 훌륭하게 작동한다는 것을 한눈에 알 수 있을 것이다. 그렇지만 실제로는 TCP의 TIME_WAIT 상태때문에 아주 좋은 성능을 낼수는 없다. TCP의 TIME_WAIT는 보통 2분이다. 그런데 접속자가 아주 많은 웹 사이트는 2분 동안에 몇 천개의 접속을 처리해야 할 경우가 있다. 서버 A는 서버 B보다 처리용량이 두배일 경우 서버 A는 수천개의 요청을 처리하고 TCP의 TIME_WAIT 상황에 직면하게 된다. 그렇지만 서버 B는 몇천개의 요청이 처리되기만을 기다리게 된다. 그래서 최소 접속 스케쥴링을 이용할 경우 다양한 처리용량을 지난 서버로 구성되었을 경우 부하분산이 효율적으로 되지 못할 수 있는 것이다.

Weighted Least-Connection Scheduling (가중치 기반 최소 접속 스케쥴링)

가중치 기반 최소 접속 스케쥴링은 최소 접속 스케쥴링의 한 부분으로서 각각의 실제 서버에 성능 가중치를 부여할 수 있다. 언제라도 가중치가 높은 서버에서 더 많은 요청을 받을 수 있다. 가상 서버의 관리자는 각각의 실제 서버에 가중치를 부여할 수 있다. 가중치의 비율인 실제 접속자수에 따라 네트웍 접속이 할당된다. 기본 가중치는 1이다.

가중치가 있는 최소 접속 스케쥴링은 다음과 같이 작동한다:

n개의 실제 서버가 있는 경우 각 서버 i는 가중치 Wi (i = 1, ... , n)를 가진다고 가정하자. 서버 i의 활동 접속(active connection)은 Ci (i = 1, ... , n)이고 모든_접속 은 Ci (i = 1, ... , n)의 합이다. 서버 j로 가는 넷트웍 접속은 아래와 같다.

(Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1,..,n)

이 비교에서 ALL_CONNECTIONS는 상수이므로 Ci를 모든_접속 으로 나눠줄 필요가 없다. 그러면 다음과 갈이 최적화될 것이다.

Cj/Wj = min { Ci/Wi } (i=1,..,n)

가중치가 있는 최소 접속 스케쥴링 알고리즘은 최소 접속 스케쥴링 알고리즘에 비해 부가적인 배분작업이 필요하다. 서버들이 같은 처리 용량을 가졌을때는 작업 할당의 간접 비용을 최소화하기위해 최소 접속 스케쥴링과 가중치가 있는 최소 접속 스케쥴링 알고리즘 둘 다 사용할 수 있다.