프리퀄 | 마이크로 서비스 시대의 부하 분산 정책
당신의 눈 앞에 n 개의 공이 있다. 우리는 이를 n 개의 상자에 담으려고 한다. 만약 우리가 공을 하나씩 넣을 때 마다 상자를 균등한 확률 (uniformly at random)로 고르고 그 상자에 공을 넣는다고 하자. 그러면 높은 확률로 모든 상자에 들어간 공의 개수는 3 ln n / ln ln n 을 넘지 않는다.
그러면 이번에는 상자를 두 개씩 골라보자. 두 개의 상자를 비교한뒤 공의 개수가 더 적은 쪽으로 공을 넣는다. 무언가 절차가 추가되었지만 오버헤드가 그렇게 큰 것 같진 않다. 이러면 결과가 얼마나 좋아질까? 놀랍게도 높은 확률로 모든 상자는 공의 개수가 ln ln n / ln 2 + O(1)을 넘지 않는다[1]. 이 글[2]은 이를 직접 시뮬레이션한 분포를 보여준다.
100만개의 공을 1000개의 상자로 분배하려고 한다. 하나는 랜덤하게 분배하는 경우의 그래프를, 다른 하나는 상자를 두 개씩 고르고 더 작은 상자를 고른 그래프를 보여준다.
import numpy as np
import matplotlib.pyplot as plt
balls = np.random.randint(0, 1000, 1000000)
counts = np.bincount(balls, minlength=1000)
unique_counts = np.unique(counts, return_counts=True)
plt.figure(figsize=(10,6))
plt.bar(unique_counts[0], unique_counts[1], color='green')
plt.show()
new_counts = np.zeros(1000, dtype=int)
for _ in range(1_000_000):
box1, box2 = np.random.randint(0, 1000, 2)
if new_counts[box1] <= new_counts[box2]:
new_counts[box1] += 1
else:
new_counts[box2] += 1
unique_counts = np.unique(new_counts, return_counts=True)
plt.bar(unique_counts[0], unique_counts[1], color='green')
plt.show()
이 문제는 컴퓨터 과학에서 해시 테이블, 부하 분산 등에서 중요하게 다룬다. 이를 두 개씩 고르는 것의 능력(power of two choice)이라고 부르고 d개의 상자를 고르는 경우에는 PodC(power of d choice) 라고 부른다. PodC는 Nginx, Envoy Proxy 등 현업에서 많이 쓰이는 프록시 서비스들이 기본적으로 제공하는 부하 분산 전략이다[3].
이제 2개씩 고르면 부하 부산의 결과가 더 좋아진다는 것은 알았다. 이제 2가지 질문이 남는다. ① 서버 중에서 무엇을 기준으로 로드가 더 적다고 평가할 것인가? ② 샘플링은 어떻게 할 것인가? 오늘은 구글 리서치가 NSDI’24 에서 발표한 프리퀄(Prequal)[4] 정책에 대해 소개한다.
지금까지는 CPU 사용량 기준으로 요청을 분배했다면, 이 논문에서는 요청 수(requests-in-flight)와 예상 지연 시간(estimated latecny)을 기준으로 부하를 분산해야 한다고 주장한다.
INDEX
- CPU 기준 부하 분산 정책의 이면
- 꼬리 지연(Tail Latency)
- YouTube에 프리퀄을 적용한 결과
- 프리퀄 시스템 디자인
- 성능 평가
- 마무리
CPU 기준 부하 분산 정책의 이면
먼저 논문에서 표현하는 용어부터 정리하고 시작하자.
- Multi-tenant : 멀티 테넌트 서비스는 aws/gcp/azure 처럼 물리적 머신을 다른 사용자와 공유하는 환경이다. 쿠버네티스 환경도 서로 다른 성격의 Pod가 호스트 머신을 공유한다는 점에서 멀티 테넌트 환경이다.
- CPU Allocation : 모던 대규모 애플리케이션은 수 많은 서버가 RPC 통신을 통해 서로 상호작용하며 비즈니스 요구사항을 수행한다. 각 서비스를 담당하는 서버들의 규모는 워크로드에 따라 수십대에서 수백대 까지 존재한다. 각 서버는 가상 머신(VM)에서 실행되고 호스트 머신으로 부터 일정 부분의 CPU cycle을 할당받는다.
- CPU Utilization : 특정 시간 동안 각 서버가 사용한 CPU cycle과 할당받은 할당량의 관계를 CPU Utilization 이라고 한다. 이 값은 100%를 넘을수도 있고 넘지 않을 수도 있다. CPU Allocation은 최소로 보장해주는 값이다. 실제로는 호스트의 자원이 넉넉하면 할당량 이상의 자원을 쓸 수 있게 해준다. 하나의 서비스는 수 많은 서버를 복제해서 생성한다. 이렇게 복제된 서버의 CPU Utilization을 평균낸 값을 job utilization이라고 부른다. (여기서 복제란 표현은 쿠버네티스에서 replica 라고 부르는 것과 같다)
- Isolation : 서버는 다른 VM들과 호스트 자원을 공유한다. 서버 입장에서 호스트에 입주해있는 다른 사용자를 논문에서는 적대자(antagonist) 라고 부른다. 이 표현이 좀 어색해서, 이 글에서는 이웃이라고 부르겠다. 호스트는 이웃이 나를 방해하지 않도록 할 의무가 있다.
서버(replica)들의 CPU 사용율을 동일하게 하는 가진 부하 분산 정책은 얼핏 합리적이게 보이기도 하다. 위 그림은 하루를 기준으로 서버의 CPU 사용율을 샘플링한 결과로 위에 있는 그래프는 1분, 아래 그림은 1초로 샘플링한 결과를 보여준다. Y축에서 1.0에 그어진 빨간 선은 CPU limit을 의미한다. 짙은 빨간색에 가까울수록 서버가 많이 밀집해 있다는 의미이다.
1분을 기준으로 보면 거의 할당량 이하로 계산되는 것으로 보이지만, 1초를 기준으로 샘플링 해보면 피크 타임에는 항상 CPU할당량 이상을 요구한다. 호스트 머신은 높은 부하를 주는 VM의 행위를 제한해서 층간소음을 내지 않을 의무가 있다. 다시 말하면 호스트 머신이 여러 서비스들이 바쁘게 돌아가고 있다면 내 서비스가 임시로 빌릴 CPU 자원이 없다.
예를 들어 보자, 우리는 100대의 서버를 운영하고 있고 각 서버는 호스트의 40% 정도의 CPU를 할당받았고, 1번과 2번 노드에서 이웃의 CPU 이용율이 60%까지 올라온 상황이다. job utilization이 할당량의 1.1x 만큼 필요하다면 1번, 2번 노드를 제외한 나머지 98개의 머신은 4%의 자원을 추가로 사용할 수 있다.
이 예시는 환경에 따라 조금씩 다르게 적용될 수 있다. AWS에서 T타입 인스턴스는 크레딧을 기반으로 필요에 따라 CPU를 더 사용할 수 있는 Burstable-type인 반면, M타입 인스턴스는 Non-burstable type이다.
Non-burstable 인스턴스를 사용하는 멀티 테넌트 환경에서도 프리퀄 정책이 유효한지는 논문만 보고는 결론을 낼 수 없었다.
정리하자면 높은 꼬리 지연을 줄이기 위해서는 높은 부하를 받고 있는 서버를 실시간으로 식별해야 한다. 하지만 아래와 같은 문제가 있다.
- 시끄러운 이웃으로 부터 영향을 받는 상황이 있다.
- CPU 이용율은 가까운 과거에서 집계된 정보일 뿐, 실시간 부하를 반영하지 못한다.
- CPU 이용율만 고려하여 락 컨텐션, 메모리, 네트워크 대역폭 등 다른 지연 요소는 고려하지 않는다.
꼬리 지연(Tail Latency)
꼬리 지연(tail latency)이란 high-percentil latency라고도 부르며 드물게 높은 지연이 발생하는 현상을 말한다. p99에서 레이턴시가 10ms이면 100명중 99명은 10ms이하의 요청을 경험한다. p99.9에서 레이턴시가 100ms이면 1000명중 한 명은 100ms를 경험한다는 표현이다. 어떻게 보면 큰 문제가 아닌 것 처럼 보이기도 한다.
마이크로 서비스 시대에서 하나의 요청은 많은 서비스와 상호작용하면서 비즈니스 요구사항을 완수한다. Parallel Wait은 동시에 다수의 서비스에 요청을 보내고 모든 응답이 돌아올 때 까지 대기하는 패턴이다. Serial Chain은 한 서비스가 또 다른 연관 서비스에 의존하는 경우이며 Blocking Call 이기 때문에 의존하는 서비스의 길이가 길수록 지연이 커진다.
직관적으로 받아들이면 꼬리지연이 굉장히 흔하게 발생할 수 있고, 서비스 요구사항에 큰 영향을 준다는 것을 알 수 있다. 필자는 사내에서 공용 서비스를 만드는 조직에 있었고 현재는 게임 서버를 개발하고 있다. 공용 서비스를 만들다 보면 이런 꼬리 지연에 대한 영향을 낮게 평가하기 쉬운 것 같다.
AWS 엔지니어인 Marc Brooker는 자신의 블로그[5]에서 꼬리 지연의 영향을 시각적으로 잘 표현했다. 위 그림은 Parallel Wait 패턴에서 요청을 보내는 서비스 수에 따라 경험하는 레이턴시의 분포를 보여준다. 블로그에 방문하면 더 자세한 내용이 나와있다.
YouTube에 프리퀄을 적용한 결과
논문은 프리퀄(Prequal)에 대한 설명에 들어가기 앞서, YouTube 웹사이트의 부하 분산 정책을 가중 라운드 로빈(WRR:Weighted Round Robin)에서 프리퀄로 변경한 결과부터 보여주면서 쇼앤프루브 한다. 유튜브 서비스는 마이크로서비스 아키텍처로 구성되어 있기에 모든 연관 서비스와의 상호작용에서 부하 분산 정책이 일관되지 않을 수 있다. 논문에서는 홈페이지 서비스에만 적용된 결과를 보여준다.
08:00시 이전에는 라운드 로빈 정책이 적용되어 있다가 08:00부터는 프리퀄로 전환한 결과를 보여준다. 프리퀄은 모든 분야에서 높은 개선을 보여준다. 꼬리 지연은 2x나 감소했고, RIF는 5x-10x, CPU의 tail utilization은 2x, 메모리의 tail usage는 10~20% 감소했다.
위 그림은 p99.9(빨간색), p99(초록색), p50(파랑색)에서 지연에 에러가 발생한 비율(e.g. timeout)과 레이턴시를 보여준다. 그 이전까지는 분포가 산만하게 오두방정 떨다가 08:00시에 프리퀄이 적용되자 tail latency를 멱살잡고 평균 근처까지 끌어 내린 결과를 볼 수 있다. 그리고 error ratio는 거의 0에 가깝도록 감소했다.
구글 연구진들이 쇼앤프루브를 한 결과, 프리퀄은 현재 유튜브를 구성하는 다른 메이저 서비스는 물론, 구글의 다른 많은 서비스에 적용되어 있다고 한다.
프리퀄 시스템 디자인
클라이언트는 주어진 정보를 바탕으로 어떤 서버로 요청을 전송할 지 선택한다. 프리퀄은 전용 로드밸런서로 만들 수도 있고 gRPC 처럼 클라이언트 사이드에서 로드 밸런싱을 구현할수도 있다.
클라이언트 사이드 로드 밸런싱 (client side load balancing)
dedicated load balancer를 이용하지 않고, 클라이언트가 직접 어느 서버로 요청을 전송할지 결정하는 매커니즘이다. gRPC에는 dns lookup으로 도메인 뒤에 있는 서버 IP를 조회한 뒤 정책에 따라 부하 분산하는 매커니즘을 가지고 있다.프리퀄도 클라이언트-사이드 로드 밸런싱 매커니즘이다. 이 매커니즘을 프록시 서비스안에서 구현할 수 있기에 정책이 적용되는 부분이 어디에 있는가에 따라서 구분한다.
논문에서는 그림이 없고 말로만 때우고 있어서 독자의 상상력을 요구한다. 논문 내용을 바탕으로 위와같이 Prequal의 구조도를 그려보았다.
① 부하 신호 (Load signal)
Prequal은 서버-사이드 모듈의 도움을 받는다. 서버는 현재 처리중인 요청 수(requests-in-flight)와 예상 레이턴시(estimated latency)를 계산한다.
- RIF(requests-in-flight) : 요청 수는 RPC 프레임워크로부터 애플리케이션 로직에 요청이 진입했으나 아직 응답을 주지 않은 개수를 의미한다.
- 예상 레이턴시 (estimated latency) : 서버는 요청에 대해 응답을 주고나서 레이턴시 정보를 현재 RIF수와 함께 저장한다. 클라이언트가 서버에게 probe를 요청하면 서버는 현재 RIF수에 해당하는 latency의 평균값을 반환한다. 해당 값이 없다면 가장 가까운 RIF값을 기준으로 계산한다.
서버가 수행하는 쿼리마다 조금의 오버헤드가 추가되었다. 프리퀄은 무시해도 될 정도(negligible)의 오버헤드만 추가하는 것을 목표로 한다. 위 RIF 및 예상 레이턴시를 계산하기 위한 자료구조를 충분히 작게 유지해야 한다. 논문에서는 초당 요청 수가 충분히 많다면 마지막 O(1–10)ms에 발생한 정보만을 저장한다고 되어있다.
② Probing Rate
프로브(probe)는 클라이언트가 서버에 정기적으로 RIF와 예상 지연 정보를 요청하는 프로세스이다. probing rate는 단위 시간 동안 얼마나 자주 이 프로세스를 수행할지 결정하는 값으로, 클라이언트가 수행해야 하는 쿼리 수에 비례해서 증가한다. 값이 증가할수록 더 자주 서버에게 정보를 요구한다.
클라이언트는 단위 쿼리당 요구할 probe의 수인 r_probe 값을 결정한다. probing rate는 단위 시간당 처리하는 쿼리 수 * r_probe 값으로 결정된다.
클라이언트가 프로브를 수행할 때 접속할 수 있는 서버 중에서 하나를 랜덤으로 선정한다. 이는 thundering herd 현상을 방지하기 위함이다. 만약 서버와 통신하는 RPC Client가 2개 이상인데 모든 서버에 프로브를 수행한다면 다수의 클라이언트가 특정 하나의 서버를 최선의 선택이라고 판단해서 요청을 분배할 것이다.
③ Replica Selection (= Server Selection)
클라이언트는 프로브 프로세스를 통해 서버마다 RIF와 예상 지연 시간 정보를 알고있다. 나이브한 방법으로 예상 지연 시간이 가장 짧은 서버로 요청을 분배할 수 있다. 하지만, 실제로는 RIF와 예상 지연 시간 사이에 적절한 밸런스가 중요하다.
유튜브에서는 처리하고 있는 쿼리마다 일정량의 메모리를 요구한다. 아마 대부분의 서버가 비슷할 것 같은데 RIF값이 증가할수록 현재 점유하고 있는 메모리가 증가할 것이다. 그리고 RIF는 미래의 부하를 나타내는 선행지표이며 예상 레이턴시는 가장 최근에 수행된 쿼리를 기준으로 계산된 값이다. 둘 다 CPU utilization 보다는 최신성을 나타내는 지표이다.
프리퀄은 레이턴시와 RIF를 줄이기 위해 HCL(a hot cold lexicographic) 서버 선택 규칙을 사용한다. 클라이언트는 Q_RIF(quantile-RIF) 값을 사전에 결정하는데 이 값에 따라 서버의 상태가 hot인지 cold인지 결정된다. 만약 Q_RIF가 0.5이면 RIF의 중위값보다 큰 서버는 hot으로 결정하고 반대는 cold 상태로 결정한다. HCL 서버 선택 규칙은 cold 인 서버 중에서 예상 레이턴시가 가장 작은쪽으로 요청을 분배한다.
④ Probe pools
Probe pools는 클라이언트가 서버 프로브 정보를 저장하는 공간이다. pool의 엘리먼트(element)는 하나의 서버와 프로브를 응답한 시간 쌍으로 구성된다.
Probe pools은 staleness, depletion, degradation 이 세 가지 문제를 풀기 위한 추가적인 매커니즘을 가지고 있다. 논문은 긴 지면을 할애해서 설명하고 있는데 여기서는 내용을 생략해서 각 문제가 무엇인지, 그리고 어떻게 해결했는지만 서술한다.
- staleness : 풀에 저장된 load signal이 너무 오래되서 정확하지 않음
이 문제는 풀에 저장된 프로브에 타임아웃을 설정해서 해결한다. - depletion : 풀이 비어있는 상황
클라이언트가 서버 선택을 위해 프로브 정보를 이용할 때 마다 재사용 예산(reuse budge)이 1씩 증가하는데 이 값이 최댓값에 도달하면 해당 프로브는 풀에서 제거된다. 풀이 완전히 비어있는 상황을 방지하기 위해 재사용 예산을 설정하는 파라미터가 존재한다. - degradation : 특정 replica가 high-load 라는 편향을 가진 경우
풀에서 특정 서버가 도저히 선택될 수 없는 load signal을 가지고 있는 경우에 많은 수의 서버 선택 라운드를 거쳐도 풀에 지속적으로 남아있다. 이런 편향을 방지하기 위해 정기적으로 high load probe를 지운다.
⑤ Sinkholing
서버가 애플리케이션 로직을 타기 전에 에러 코드를 반환하는 경우 레이턴시에 대한 평가가 왜곡된다. 이런 현상을 싱크홀이라고 한다. 프리퀄은 휴리스틱한 방법으로 이를 해결했다고 하는데 자세한 내용은 없다.
Prequal includes some heuristics to avoid sinkholing, but since they are not central to our contribution, we have chosen to simplify our exposition by omitting details.
⑥ 동기 모드
비동기식 프로브는 정보를 저장하는 프로브 풀을 사용한다. 서버 선택 시, 프로브 풀에서 정보를 가져와 평가하여 서버를 선택한다. 동기식 프로브는 프로브 풀을 사용하지 않는다. 쿼리가 들어올 때마다 d개의 서버를 무작위로 선택하여 프로브 정보를 조회하고, 이 정보를 기반으로 서버를 한다.
유튜브에서는 실제 프리퀄 사용 시 동기식 프로브를 사용했다. 반면, 테스트베드 실험에서는 비동기식 프로브를 사용했다.
지금까지 프리퀄의 설계에 대해서 설명해 왔는데, 사실 필자도 아직까지 햇갈리는 부분도 있고 논문에서 명확하게 설명을 안해준 부분도 있다. 예를 들면 probing rate값이 100이면 10ms당 하나씩 요청을 보내는건가? 라는 추측만 할 뿐 논문에서는 디테일한 설명이 부족해 이해하는데 어려움이 있었다.
하지만 프리퀄의 내용은 잊더라도, 단 하나만 기억하면 된다. RIF와 Latency를 기준으로 부하 분산을 하는 목적을 가지고 있고 그것을 구현하는 방법이 프리퀄이다. 업계에 경험이 많아지면 분명 더 단순한 설계를 가진 방법론이 나올 것으로 기대한다.
성능 평가
성능 평가는 테스트-베드 환경에서 이루어진다. 테스트-베드 환경은 100개의 클라이언트와 100개의 서버로 구성되어 있으며 각 서버는 해시 연산을 하는 단순한 작업만 수행한다. 하나의 요청이 몇 번의 해시 연산을 하는지는 정규 분포를 따라 결정된다. 모든 서버와 클라이언트는 구글 데이터센터에 상주해있고 데이터 센터에 적용된 기본 Isolation 정책이 적용되어 있다.
각 서버는 10%의 CPU를 할당했으며, 프로브 풀의 최대값은 16, Q_RIF는 0.84로 선택했다. 그리고 probing rate를 결정하는 r_probe값은 3으로 결정한다. 필자가 제대로 이해한 게 맞다면 클라이언트는 쿼리를 수행한 뒤 비동기로 3개의 서버에 프로브를 요청한다.
① 시끄러운 이웃에 대한 저항성
각 서버의 CPU load는 할당량의 75%에서 시작해서 1.74x 까지 점진적으로 증가한다. 서버에 부하를 주기 위해 초당 5.6k의 쿼리부터 시작해서 초당 13k의 쿼리가 생성되도록 증가시켰다. 현재 많이 사용되는 부하 분산 알고리즘인 Weighted Round Robin(WRR) 알고리즘과 프리퀄을 비교했으며, 각 시간마다 처음 30분은 WRR을, 나머지 30분은 프리퀄을 적용했다.
우선 CPU load가 증가할 수록 WRR은 에러율과 꼬리지연이 크게 증가한다. 반면 프리퀄은 지연이 조금 증가하긴 하지만 WRR에 비해서는 귀여운 수준이며 에러율은 0에 근사하다. 여기서 에러율이란 클라이언트의 요청이 5초를 넘겨서 타임아웃이 발생하는 비율이다. 그래서 그래프(a)를 보면 Y축의 최댓값이 5초인 것을 알 수 있다.
여기서 가장 흥미로운 부분은 (c) CPU Utilization 분포이다. WRR 정책은 본인의 책무를 충실히 이행해서 서버의 CPU load가 균일하도록 잘 분포했다. 반면 프리퀄 정책은 애초에 CPU load와는 무관하기 때문에 분포가 고르게 퍼져있다. 이 결과는 연구자들이 논문 제목에서부터 주장하는 것 처럼 Load is not what you should balance 라는 것이며 가상머신의 시끄러운 이웃의 부하(antagonist load)가 내 서비스에 끼치는 영향이 크다는 것을 말해준다.
② Replica selection rule
데이터센터는 다양한 하드웨어 세대와 프로세서 아키텍처의 물리적 장비로 구성되어 있고, 우리가 프로비전 하는 서버는 다양한 하드웨어로 배포된다. 서비스마다 최적의 성능을 내는 하드웨어가 다를 수 있다. 예를 들면 유튜브는 A라는 장비에서 더 좋은 성능을 내고, 구글맵은 B라는 장비에서 더 좋은 성능을 낼 수 있다.
서버를 선택하는 규칙에서 이러한 점까지 고려하는 다양한 알고리즘들이 있다. 위에서 당신이 분산해야 하는 건 cpu load가 아니다 라고 주장했다면, 여기서는 프리퀄의 서버 선택 규칙인 HCL이 최선이었는가를 평가한다.
논문은 더 많은 지면을 할애해서 이를 설명하는데
이 포스팅에서는 생략하려고 한다.
한가지 눈여겨 볼만한 건 C3 알고리즘이 프리퀄과 비교할만한 성능을 보여주었는데 이것도 RIF를 기준으로 로드 밸런싱 하는 알고리즘이다. 다만 프리퀄보다는 조금 더 복잡하다.
마무리
프리퀄은 CPU load로 부하 분산 하는 건 VM에서 배포되는 모던한 마이크로 서비스 아키텍처에서는 좋은 선택이 아니며 RIF와 latency를 기준으로 요청을 분할해야 최적의 성능을 낸다고 주장한다.
유튜브에서는 요청 한 번에 상자 5개를 선택한다. 다시 말해 유저 요청 하나당 서버에 6번의 요청이 간다. 이게 직관적으로는 성능에 문제가 없나 라는 의문을 가지게 되는데, 구글 데이터 센터 내에서 주고 받는 probe 통신 지연이 1ms 이하라고 한다. RIF와 latency만 주고받으면 되기 때문에 기껏 해봐야 4 byte integer 2개 전송하는 거라서 납득은 된다. 그리고 논문에서는 tail latency를 줄여서 얻는 이익이 더 크다고 강조했다.
