[System] 논문 리뷰: The Tail at Scale

도입

이 글에서 다루는 논문은 "The Tail at Scale"이라는 제목을 가진 논문으로 Google의 Jeffrey Dean과 Luiz André Barroso가 2013년에 발표한 논문이다. 논문의 제목에 나와 있는 것처럼 이 논문은 대규모 시스템에서의 Tail latency에 대해 다룬다.

다음 링크를 통해 논문 정보를 확인할 수 있다.

https://dl.acm.org/doi/10.1145/2408776.2408794

 

Tail latency가 뭘까? Tail latency를 직역하면 꼬리 지연이다. 지연 시간에 왜 꼬리라는 말이 붙었을까?

지연 시간은 항상 동일하지 않다. 상황과 환경에 따라 지연 시간은 매번 달라진다. 그렇다면 지연 시간의 분포를 자연스럽게 생각할 수 있다.

이 분포의 오른쪽 끝부분을 보자. 이 부분은 전체 지연 시간 분포에서 상위 분위수에 해당한다. 이러한 상위 분위수에 해당하는 지연 시간을 tail latency라고 한다. 이 부분이 분포의 꼬리에 있기 때문에 tail이라는 말이 붙었다.

Tail latency와 관련해 p95, p99, p99.9 latency라는 용어도 있다. 지연 시간 분포에서 상위 95%, 99%, 99.9%에 해당하는 지연 시간을 뜻하는 용어이다.

 

어느 정도 규모의 시스템까지는 tail latency가 크게 문제가 되지 않는다. 하지만 대규모 시스템에서는 tail latency 값이 높다면 문제가 된다.

왜 대규모 시스템에서는 높은 tail latency 값이 왜 문제일까?

Tail latency의 정의를 보면 tail latency에 해당하는 지연 시간이 발생할 확률은 낮다. 예를 들어 어느 단일 서버의 p50 latency가 1ms이고 p99 latency가 5ms, p99 latency가 10ms라 하자. 이는 50%의 확률로 지연 시간이 1ms 이하이고, 5% 확률로 지연 시간이 5ms 이상, 1% 확률로 지연 시간이 10ms 이상이라는 의미이다. 5%의 경우를 제외하면 전부 5ms 이하로 동작하고, 지연 시간이 10ms 이상인 경우는 1%이다.

 

이렇게 간헐적으로 발생하는 긴 지연은 무시해도 괜찮지 않을까? 어차피 긴 지연이 발생할 확률이 낮고, 대부분의 경우에는 빠르게 동작하지 않는가? 왜 tail latency가 문제일까?

 

대규모 온라인 서비스에서는 지연 시간을 줄이기 위해 일반적으로 여러 다른 서버에 하위 작업을 병렬화한다. 지연 시간을 줄이기 위해 흔히 사용하는 기술이다. 루트 서버에 요청이 들어오면 이를 작은 요청으로 나누고 여러 서버에 이 작은 요청들을 보낸다. 하나의 서버에서 커다란 요청을 전부 처리하는 것보다, 요청을 작은 요청으로 쪼개고 여러 서버에서 병렬 처리하는 것이 더 효율적이기 때문이다. 그래서 Google과 같은 글로벌 서비스에서는 수천 대의 서버를 사용한다. 하지만 역설적이게도 지연 시간을 줄이기 위해 작업을 쪼개고 여러 서버로 병렬 처리하는 기술 때문에 tail latency는 문제가 된다.

 

단일 인스턴스에서는 10ms 이상의 지연시간이 발생할 확률이 1%라고 하더라도, 이러한 인스턴스를 수백, 수천 개씩 하나의 요청을 처리할 때 쓰게 된다면 10ms 이상의 지연시간이 발생할 확률이 더욱 올라간다. 요청에 대한 응답을 사용자한테 제공하기 위해서는 모든 인스턴스에서 응답이 와야 한다. 하지만 하나의 요청을 처리하기 위해 사용해야 하는 인스턴스가 늘어날수록 지연 시간이 긴 인스턴스가 생길 확률이 올라간다. 하나의 요청을 처리하기 위해 사용한 수많은 서버 중 딱 하나의 서버에서만 긴 지연이 발생해도 요청에 대한 응답도 지연된다. 다른 서버에서 아무리 빠르게 작업을 처리했더라도 모든 서버의 작업이 끝날 때까지는 응답이 지연된다. 이를 논문에서는 구성 요소 수준 변동성의 규모에 따른 증폭(Component-Level variability amplified By Scale)이라고 표현한다.

 

다음 표는 실제 Google 서비스의 측정 결과를 나타낸다. 루트 서버가 중간 서버를 통해 매우 많은 수의 리프 서버로 요청을 분산하는 경우와 논리적으로 유사한 사례라고 한다. 실제로 tail latency가 대규모 시스템에 어떤 영향을 미치는지 볼 수 있다.

 

단일 랜덤 리프 서버의 p50 latency는 1ms, p95 latency는 5ms, p99 latency는 10ms 이다. 이는 사실 무시할만하다고 볼 수도 있다. 99%의 경우에서도 10ms 이하의 지연이 발생하기 때문이다. 10ms 정도면 충분히 빠르다고 생각할 수도 있다. 하지만 이러한 서버를 여러 대 사용하면 tail latency가 문제가 됨을 수치로 확인할 수 있다.

 

표에 나와 있는 사례의 경우, 전체 리프 서버 중 가장 느린 5%의 서버에서 발생한 지연이 전체 지연 시간에 절반 이상을 차지한다는 것을 확인할 수 있다. 하나의 요청에 대한 모든 리프 서버의 응답이 돌아오기까지 p50 latency는 40ms, p95 latency는 87ms, p99 latency는 140ms 이다. 한편 하나의 요청에 대한 95%의 리프 서버 응답이 돌아오기까지 p50 latency는 12ms, p95 latency는 32ms, p99 latency는 140ms 이다.

 

즉, 리프 서버 95%의 응답이 돌아오기까지의 지연 시간과 리프 서버 100%의 응답이 돌아오기까지의 지연 시간을 비교해 보면 p50 latency는 약 3.3배, p95 latency는 약 2.7배, p99 latency는 2배 상승했다. 조금 비틀어서 생각해 보면, 이러한 느린 일부 아웃라이어들의 성능을 개선하는 작업은 전체 서비스 성능에 대한 극적인 개선을 가져올 수 있고 유추할 수 있다. 이 글에서 다루는 논문 "The tail at scale"에서는 이러한 tail latency로 인한 성능 저하를 개선하는 방법을 다룬다.

지연 시간의 변동(Variability)은 왜 존재할까?

Tail latency를 개선하기 전에, 높은 tail latency를 발생시키는 지연 시간의 변동성(Variability)이 생기는 이유에 대해 알아보자.

 

논문에서는 공유 자원(shared resources), 데몬(daemons), 글로벌 리소스 공유(global resource sharing), 유지보수 활동(maintenace activities), 큐잉(queueing), 전력 제한(power limits), 가비지 컬렉션(garbage collection), 에너지 관리(energy menagement)를 지연 시간 변동이 생기는 이유로 들고 있다. 각각 간단히 살펴보자.

• 공유 자원(shared resources): 다양한 애플리케이션이 공유 자원(e.g. CPU 코어, 프로세서 캐시, 메모리 대역폭, 네트워크 대역폭 등)을 놓고 경쟁할 수 있으며, 동일한 애플리케이션 내에서도 다양한 요청이 자원을 놓고 경쟁할 수 있다.
• 데몬(daemons): 백그라운드 데몬은 평균적으로 제한된 자원을 사용하지만, 스케줄링될 경우 다중 밀리초(multi-millisecond) 수준의 일시적인 지연을 유발할 수 있다.
• 글로벌 리소스 공유(global resource sharing): 서로 다른 머신에서 실행되는 애플리케이션은 글로벌 리소스(e.g. 네트워크 스위치 및 공유 파일 시스템)를 놓고 경쟁할 수 있다.
• 유지보수 활동(maintenace activities): 백그라운드 작업(e.g. 분산 파일 시스템에서의 데이터 재구성, BigTable과 같은 저장 시스템에서의 주기적 로그 압축, 가비지 컬렉션 언어에서의 주기적 가비지 컬렉션)은 지연 시간의 주기적 급증을 유발할 수 있다.
• 큐잉(queueing): 중간 서버와 네트워크 스위치에 존재하는 다중 큐잉 계층은 지연 시간 변동을 증폭시킨다.
• 전력 제한(power limits): 현대 CPU는 평균 전력 범위 이상으로 일시적으로 작동하도록 설계되었으며, 이 활동이 장기간 지속될 경우 열을 낮추기 위해 속도를 조절한다.
• 가비지 컬렉션(garbage collection): SSD는 매우 빠른 랜덤 읽기 접근을 제공하지만, 많은 데이터 블록에 대해 주기적으로 가비지 컬렉션(garbage collection)을 수행해야 할 필요 때문에, 쓰기 활동이 조금만 있어도 읽기 지연 시간이 최대 100배까지 증가할 수 있다.
• 에너지 관리(energy menagement): 많은 유형의 장치에서 전력 절약 모드는 상당한 에너지를 절약하지만, 비활성 모드에서 활성 모드로 전환할 때 추가 지연 시간을 발생시킨다.

이러한 요소들 때문에 높은 tail latency가 발생한다. 위 요소들을 잘 처리하면 tail latency를 낮출 수 있다. 일반적으로 자원 과다 할당(overprovisioning of resources), 소프트웨어의 세심한 실시간 엔지니어링(careful real-time engineering of software), 신뢰성 개선(improved reliability)을 통해 모든 수준과 구성 요소에서 변동성의 근본 원인을 줄일 수 있다.

구성요소의 변동성 줄이기 (Reducing Component Variability)

앞서 설명했던 것처럼 대규모 시스템에서는 높은 tail latency가 문제인데, 지연 시간 또는 응답 시간 변동성 때문에 높은 tail latency가 발생한다. 그렇다면 높은 tail latency를 줄이기 위해서는 일단 응답 시간 변동성 자체를 줄이면 되지 않을까? 논문에서 다룬 방법은 다음과 같다.

서비스 클래스 구분과 상위 수준 큐잉(queuing)

모든 요청이 동일하게 중요할까? 대부분의 경우 그렇지 않다. 사용자가 빠른 상호작용을 기대하고 있는 요청은 매우 중요하다. 하지만 백그라운드에서 돌아가는 배치 처리나 로그 압축 등의 작업은 상대적으로 중요하지 않다. 즉, 어떤 요청은 빠르게 처리되어야 하고 다른 요청은 굳이 빠르게 처리될 필요가 없다. 논문에서 구분된 서비스 클래스(differentiated service classes)라고 표현하는 개념이 이러한 것을 의미한다.

 

중요도에 따라 요청을 구분하면 요청을 더욱 효율적으로 처리할 수 있다. 지연에 민감한 요청을 더욱 빠르게 처리해 그러한 요청의 지연 시간을 줄일 수 있다. 지연에 민감하지 않은 요청은 조금 느리게 처리되어도 상관없기 때문에 괜찮다.

 

Google의 스토리지 서버는 중요도에 따라 요청을 구분한다. 그리고 운영체제 단의 큐에 요청을 바로 쌓는 것이 아니라, 상위 수준의 큐를 만들어 요청을 관리한다. 운영체제의 큐에 들어간 요청의 처리 순서를 바꾸기 힘들다. 하지만 애플리케이션 수준에서 큐를 만들어 요청을 관리하면 중요도에 따라 처리 순서를 바꿀 수 있다. 일종의 우선순위 큐라고 볼 수 있다. 지연에 민감하지 않은 요청이 먼저 큐에 들어와 있더라도 지연에 민감한 요청이 큐에 들어오게 되면 지연에 민감한 요청을 먼저 큐에서 꺼낼 수 있다. 운영체제 레벨의 큐는 애플리케이션이 이런 식으로 요청의 순서를 바꾸기 힘들기 때문에 상위 레벨의 큐를 사용한다. 운영체제의 큐는 항상 짧게 유지한다. 이렇게 하면 지연에 민감한 요청에 빠르게 응답할 수 있다.

HOL 블로킹(Head Of Line Blocking) 줄이기

요청마다 처리하는 비용이 다르다. 어떤 요청은 적은 비용으로 처리할 수 있지만, 또 어떤 요청은 매우 많은 비용을 들여야 처리할 수 있다.

 

그렇다면 HOL 블로킹은 무엇일까? 예시를 통해 알아보자. 처리 비용이 매우 큰 요청 하나와 처리 비용이 낮은 요청 10개가 있다고 해보자. 요청은 하나씩 순서대로 처리된다. 만약 비용이 매우 큰 요청이 먼저 처리되기 시작하면, 처리 비용이 낮은 요청은 빨리 처리될 수 있음에도 계속 기다려야 한다. 아직 앞에 있는 요청이 처리되지 않았기 때문이다. 이러한 현상을 HOL 블로킹(Head Of Line Blocking)이라 한다. 말 그대로 Line의 Head에 의해 Blocking이 발생했다고 볼 수 있다. 이러한 현상을 해결하려면 어떻게 해야 할까?

 

논문에서는 처리 비용이 큰 요청을 처리 비용이 낮은 여러 요청으로 쪼개는 방식을 언급한다. 쪼개진 작은 요청들을 다른 요청 사이에 끼워 넣으면 HOL 블로킹을 줄일 수 있다. Google의 웹 검색 시스템은 이러한 방식을 사용한다고 한다. Google의 웹 검색 시스템에는 다양한 쿼리가 들어올 것이다. 계산 비용이 매우 큰 소수의 쿼리가 들어오면 Google의 웹 검색 시스템은 쿼리를 time-slicing 방식으로 쪼갠다. 그리고 저비용 쿼리들 사이사이에 쪼개진 쿼리를 배치하여 실행한다. 이렇게 하면 계산 비용이 매우 큰 소수의 쿼리가 다수의 저비용 쿼리들의 지연 시간을 크게 늘리지 않도록 할 수 있다.

백그라운드 작업과 동기화된 방해(synchronized disruption) 관리

서버에는 서비스를 위한 애플리케이션 외에도 다양한 백그라운드 작업이 실행된다. 백그라운드 작업은 CPU, 디스크, 네트워크 부하를 크게 유발할 수 있다. 예를 들어, 로그 지향 스토리지 시스템(log-orientied storage system)에서의 로그 압축(compaction)과 가비지 컬렉션 언어에서의 가비지 컬렉터 활동 등이 있다. 스로틀링(throttling), 무거운 작업을 더 작은 작업으로 분할, 전체 부하가 낮은 시점에 그러한 작업을 트리거하는 방법 등을 조합하면 백그라운드 작업이 지연 시간에 민감한 대화형 요청의 지연 시간에 미치는 영향을 줄일 수 있다. 여기서 스로틀링은 시스템이 과부하되지 않도록 의도적으로 처리 속도를 제한하는 기법을 말한다.

 

또한 대규모 팬아웃(fan-out) 서비스를 위해서는 시스템이 여러 서버 전반에서 백그라운드 작업을 동기화하는 것이 유용할 때가 있다. 여기서 팬아웃 서비스는 하나의 상위 요청이 동시에 여러 개의 하위 요청으로 나눠지고, 그 결과를 모아 최종 응답을 만드는 구조를 말한다. 백그라운드 작업을 동기화하면 각 서버에서 짧은 시간 동안 동시에 활동이 몰리도록 강제할 수 있다. 그러면 그 짧은 시간에 처리 중인 대화형 요청만 느려진다. 반대로 동기화가 없다면 항상 일부 서버에서 백그라운드 작업이 수행되고 있기 때문에 모든 요청의 tail latency가 올라가게 된다.

캐싱(caching)은 어디에?

흔히 지연 시간을 줄이기 위해 캐싱 기법을 자주 사용한다. 자주 들어오는 요청에 대한 응답이나 자주 사용되는 데이터는 캐시에 넣어두고 사용하면 빠르게 응답할 수 있다. 그렇지만 캐싱은 tail latency를 직접적으로 해결할 수 없다. 효과적인 캐싱 계층은 유용할 수 있고, 어떤 시스템에서는 필수적이기까지 하다. 그렇지만 애플리케이션의 모든 데이터가 캐시에 전부 상주함이 보장되는 것과 같은 경우를 제외하면, 캐싱은 tail latency 문제를 직접적으로 해결할 수 없다. 일부 요청에서는 캐시 미스가 발생할 수 있기 때문이다. 캐시 미스가 발생하면 캐시가 없는 것과 동일한 지연이 발생한다. 그렇기 때문에 tail latency는 캐시가 없는 것과 크게 다르지 않을 것이고 tail latency 문제가 직접적으로 해결되지 않는다.

지연 시간 변동성은 완전하게 제거할 수 없다

지금까지 지연 시간 변동성을 낮추기 위한 다양한 엔지니어링 기법들을 살펴보았다. 이러한 기법들은 고성능 대화형 서비스(high-performance interactive service)를 구축하는 데 필수적이다. 하지만 현대 웹 서비스의 커다란 규모와 복잡성 때문에 모든 지연 시간 변동성을 완전히 제거하는 것은 사실상 불가능하다. 그래서 Google은 지연 시간 변동성을 전면적으로 제거하려고 하기보다는, 일시적인 지연 이상(latency pathologies)을 가리거나(mask) 우회(work around)할 수 있는 꼬리 내성(tail-tolerant) 기법을 개발하는 것이 더 유리하다는 점을 발견했다.

 

이러한 꼬리 내성 기법은 크게 둘로 나눌 수 있다.

1. 요청 내부의 즉각 대응(within-request immediate-response) 기법: 더 장기적인 기법이 반응할 틈이 생기기 전에 수십 밀리초 단위의 시간 규모에서 작동하는 기법
2. 요청 간의 장기 적응(cross-request long-term adaptations) 기법: 수십 초에서 수 분에 이르는 시간 규모에서 동작하며 장기적인 현상의 영향을 완화하기 위한 기법

각 기법에 대해 알아보자.

요청 내 단기적 조정(Within Request Short-Term Adaptations)

웹 서비스에서는 흔히 레플리카(replica, 복제본)를 사용한다. 레플리카는 같은 데이터를 여러 서버에 복제해 둔 것을 말한다. 레플리카를 사용하면 읽기 트래픽을 분산시켜 더 많은 요청을 처리할 수 있고, 하나의 서버가 죽더라도 다른 레플리카가 서비스를 지속할 수 있기 때문의 시스템의 고가용성을 달성할 수 있다. 특히 읽기 전용 요청이면서 느슨하게 일관된 데이터셋(loosely consistent datasets)을 대상으로 할 때 특히 효과적이다. 예를 들어, 모델이 하루에 한 번 업데이트되지만 초당 수천 개의 교정 요청을 처리하는 철자 교정 서비스에 레플리카가 유용하게 사용될 수 있다.

 

이제 단일 상위 레벨 요청(single higher-level request) 내에서 지연 시간 변동성을 줄이기 위해 레플리카를 활용하는 테크닉들을 살펴보자. 단일 상위 레벨 요청의 정의가 논문에 나와 있지는 않지만, 사용자가 체감하는 하나의 작업 단위라고 이해하면 좋을 것 같다.

 

단, 여러 레플리카로 동일한 요청을 중복 전송해 가장 먼저 끝난 결과만 사용하는 기법은 지연을 유발하는 현상이 레플리카들 간에 동시에 일어나지 않을 때 잘 작동한다. 만약 지연 원인이 여러 레플리카에 동시에 영향을 미치면 복제 요청을 보내도 전부 느려져서 효과가 거의 없다. 그렇지만 대규모 시스템에서는 이러한 비상관(uncorrelated)의 지연 원인이 흔하기 때문에 이제 소개할 기법들이 유용하다.

헤지 요청(Hedged Request)

지연 시간 변동성을 줄이는 간단한 방법은 동일한 요청을 여러 레플리카에 보내고, 가장 먼저 응답하는 레플리카의 결과를 사용하는 것이다. 이를 헤지 요청(hedged request)라고 부른다. 헤지 요청을 사용하면 동일한 읽기 요청을 레플리카 A에 먼저 보내고, 짧은 지연 시간 동안 응답이 없으면 다른 레플리카로 보조 요청을 보낸다. 먼저 도착한 응답을 채택하고, 나머지 요청들은 즉시 취소한다. 보조 요청을 추가로 보냄으로 지연 시간 변동성을 억제하기 때문에 헤지(hedge)라는 이름이 붙었다.

 

헤지 요청 기법을 단순하게 구현하면 허용하기 어려운 추가 부하가 생기기 쉽다. 하지만, 부하 증가는 소폭으로 억제하면서도 지연 시간 단축 효과의 대부분을 얻을 수 있는 다양한 기법이 존재한다. 그중 하나는 첫 번째 요청이 p95 latency를 초과하여 대기 중일 때까지 보조 요청 전송을 미루는 방식이다. 이 접근법은 추가 부하를 대략 5% 수준으로 제한하면서도 지연 시간의 꼬리를 크게 단축할 수 있다. 이 기법이 효과적인 이유는 지연의 원인이 종종 해당 요청 자체에 내재되어 있기보다는 다른 형태의 간섭에 기인하기 때문이다.

 

예를 들어, 100대의 서로 다른 서버에 분산된 BigTable의 테이블에 저장된 1,000개의 키 값을 읽는 Google 벤치마크에서, 10ms 지연 후 헤지 요청을 보내면 1,000개 값을 모두 가져오는 작업의 p99.9 지연 시간이 1,800ms에서 74ms로 감소했으며, 추가로 전송된 요청은 2%에 불과했다. 또한 헤지 요청을 기본 요청보다 낮은 우선순위로 태깅하면 헤지 요청의 오버헤드를 더 줄일 수 있다.

묶인 요청(Tied Request)

앞에서 헤지 요청 방식의 부하를 줄이기 위해 p95 latency를 초과할 때까지 대기했다가 보조 요청을 전송하는 방식에 대해 살펴보았다. 이 방식은 헤지 요청 방식의 부하를 줄일 수 있지만 헤지 요청 방식의 이점이 전체 요청 중 극히 일부에만 한정되는 한계가 있다. 약 95%의 요청에서는 보조 요청을 보내지 않기 때문이다. 보다 공격적으로 헤지 요청을 사용할 필요가 있다. 그렇지만 자원 소모 역시 적정 수준으로 유지할 필요가 있다. 그러기 위해서는 더 빠른 요청 취소가 필요하다.

 

많은 서비스에서 지연 시간 변동성의 흔한 원인은 요청이 실제 실행되기 전 서버에서의 대기열(큐) 지연이다. 다수의 서비스에서는 일단 요청이 스케줄 되어 실행을 시작하면, 완료 시간의 변동성은 상당히 줄어든다.

 

Mitzenmacher라는 사람은 서버의 큐 길이를 기준으로 요청을 큐에 넣는 시점(enqueue time)에 두 서버 중 하나를 선택할 수 있게 하면 균일 무작위 방식에 비해 부하 분산 성능이 지수적으로 개선된다고 주장했다. Google은 서버를 선택하는 것이 아니라 동일 요청의 사본을 여러 서버에 동시에 넣고 서버들끼리 해당 사본들의 상태를 서로에게 갱신해 주도록 할 것을 권장한다. 서버들이 교차 상태 업데이트를 수행하는 요청을 묶인 요청(tied request)라고 부른다.

 

가장 단순한 형태의 연결된 요청은 클라이언트가 동일한 요청을 서로 다른 두 서버에 전송하되 각 요청에 상대 서버의 식별자를 태깅하는 방식이다. 어느 한쪽에서 요청이 실행되기 시작하면, 그 요청은 상대 서버로 취소 메시지를 보낸다. 상대편 요청이 아직 다른 서버의 큐에 대기 중이라면 즉시 중단되거나 우선순위가 크게 낮아질 수 있다. 양 서버가 모두 요청 실행을 시작하는 짧은 구간이 존재하는데, 이는 양방향 취소 메시지가 상대 서버로 전송 중일 때의 평균 네트워크 메시지 지연 시간만큼의 구간이다. 이러한 상황이 발생하기 쉬운 일반적인 사례는, 두 서버의 대기열이 모두 완전히 비어 있는 경우이다. 따라서 클라이언트가 첫 번째 요청을 보낸 뒤 두 번째 요청을 보내기까지 평균 네트워크 메시지 지연의 두 배에 해당하는 작은 지연을 도입하는 것이 유용하다. 이 지연 시간은 현대 데이터 센터 네트워크에서는 1ms 이하이다.

 

Google에서는 이러한 기법을 구현해 클러스터 수준 분산 파일 시스템(cluster-level distributed file system)에서의 지연 시간의 중앙값과 꼬리 지연(tail latency) 모두를 효과적으로 줄였다고 한다.

 

다음 표는 메모리에 캐시되지 않아 하부 파일 시스템에서 읽어 와야 하는 BigTable의 작은 읽기 요청을 처리하는 데 걸리는 시간을 나열하고 있다. 각 파일 청크는 서로 다른 세 대의 서버에 복제된다.

 

표에는 두 가지 시나리오에서, 묶인 요청(tied request) 사용 여부에 따른 읽기 지연이 포함되어 있다. 첫 번째는 벤치마크가 고립된 상태로 실행되는 클러스터로, 지연 가변성은 주로 자체 간섭(self-interference)과 정규 클러스터 관리 활동으로부터 발생한다. 이 경우, 1ms 후 다른 파일 시스템 레플리카로 교차 서버 취소(cross-server cancellation)를 동반한 연결된 요청을 보내면 중앙값 지연이 16% 감소하고, 지연 분포의 꼬리로 갈수록 효과가 커져 p99.9 latency는 거의 40% 감소된다.

 

두 번째 시나리오는 첫 번째와 유사하지만, 동일한 공유 파일 시스템의 디스크 자원을 두고 경쟁하는 대규모 동시 정렬 작업이 클러스터에서 함께 실행되는 경우(with concurrent terasort)이다. 전체 지연은 더 높은 자원 사용률 때문에 다소 증가하지만, 앞서 다룬 묶인 요청(tied request) 기법으로 유사한 지연 시간 개선을 얻을 수 있다. 연결된 요청을 사용할 때 대규모 정렬 작업을 동시에 수행한 지연 시간은, 묶인 요청을 사용하지 않은 거의 유휴 클러스터(mostly idle cluster)의 지연 시간과 거의 동일하다. 연결된 요청은 작업 부하를 단일 클러스터로 통합할 수 있게 해주기 때문에 컴퓨팅 비용을 극적으로 절감한다.

 

위 두 시나리오 모두에서, 디스크 사용률 측면의 묶인 요청 오버헤드는 1% 미만으로, 취소 전략이 중복 읽기를 효과적으로 제거함을 보여준다.

 

묶인 요청과 헤지 요청의 대안으로는, 먼저 원격 큐를 탐색(probe)한 뒤 가장 덜 부하된 서버에 요청을 보내는 방식이 있다. 이는 유익할 수 있지만 다음 세 가지 이유로 두 큐에 동시에 작업을 제출하는 방식보다 덜 효과적이다.

1. 탐색 시점과 실제 요청 제출 시점 사이에 부하 수준이 변할 수 있다.
2. 하위 시스템 및 하드웨어 가변성 때문에 요청 서비스 시간을 추정하기 어려울 수 있다. 가장 덜 부하된 서버를 고르려면 요청의 서비스 시간을 추정해야 한다. 하지만 이를 추정하기 어렵다면 가장 덜 부하된 서버를 정확하게 고르기 힘들다.
3. 클라이언트들이 모두 동일한(가장 덜 부하된) 서버를 동시에 선택함으로써 일시적인 핫스팟을 만들어낼 수 있다.

요청 간 장기적 적응(Cross-Request Long-Term Adaptations)

앞에서는 작은 규모의 지연 시간 변동성을 줄이는 데 적용할 수 있는 기법들을 살펴보았다. 이제 서비스 시간 변동성이나 부하 불균형과 같은 더 큰 규모의 현상으로 인해 발생하는 지연 시간의 변동성을 줄이는 데 적용할 수 있는 기법들을 살펴보자. 

 

많은 시스템이 데이터 조각(partition)들의 비용이 동일해지도록 데이터를 분할하려고 노력한다. 하지만 두 가지 이유로 인해 각 서버에 단일 데이터 조각을 정적으로 할당하는 방식은 실제로는 거의 충분하지 않다.

1. 기반 하드웨어의 성능은 시간에 따라 균일하지도, 일정하지도 않다. 같은 데이터 조각이라도 어떤 시점에는 해당 데이터 조각을 맡은 서버가 느려져 지연 시간이 튀고 처리량이 줄어 불균형이 생길 수 있다.
2. 데이터 자체에서 쏠림(핫스팟)이 생긴다. 초기엔 모두 비슷해 보였던 데이터 조각 비용이, 운영 중 여러 이유들 때문에 크게 달라진다. 특정 데이터가 인기를 끌어 해당 데이터 조각의 부하가 증가하는 경우 등이 있다.

설계 시점에 균등했던 데이터 조각 비용이 운영 시점에는 깨질 수 있다. 그리고 데이터 조각을 정적으로 할당하는 방식은 이를 재조정하기 어렵다.

 

이를 해결하기 위해 논문에서 제시하는 기법들을 살펴보자.

마이크로 파티션(Micro-partitions)

마이크로 파티션이라는 이름에서 알 수 있는 것처럼 데이터를 더욱 잘게 쪼개는 방법이다. 기존에는 서버 1개에 데이터 파티션 1개가 할당되었다. 마이크로 파티션 방식은 데이터를 잘게 쪼개서 서버 1개에 여러 개의 파티션을 할당하는 방식이다.

 

서버에 있는 데이터는 갑자기 인기가 많아질 수 있다. 그리고 서버의 속도는 매 순간 변한다. 그래서 처음의 공평한 분할이 운영 중엔 깨지기 쉽다. 만약 공평한 분할이 깨질 경우 빠르게 재조정해야 한다. 마이크로 파티션 방식은 작은 데이터 파티션을 여러 개 가지고 있기 때문에 어느 서버에 부하가 몰릴 경우 데이터 파티션 몇 개를 다른 서버로 옮겨서 빠르고 가볍게 부하를 분산시킬 수 있다. 서버 당 평균 20개의 파티션이 있다면, 시스템은 대략 5% 단위로 부하를 덜어낼 수 있다. 서버 1개에 데이터 파티션 1개를 할당하는 방식과 비교하면 약 1/20의 시간에 이를 수행할 수 있다.

선별적 복제(Selective Replication)

선별적 복제 기법은 마이크로 파티셔닝 방식의 확장이다. 부하 불균형을 유발할 가능성이 있는 특정 항목들을 탐지 또는 예측하여 그 항목들의 추가 복제본을 만드는 방식이다. 선별적 복제 기법을 사용하면 로드 밸런싱 시스템은 이 추가 복제본을 활용하여 인기가 많은 마이크로 파티션의 부하를 실제로 마이크로 파티션을 이동시키지 않고도 여러 서버에 분산시킬 수 있다. Google의 주요 웹 검색 시스템은 이 기법을 사용하여, 인기 있고 중요한 문서들의 추가 복사본을 여러 마이크로 파티션에 생성한다고 한다.

지연 유발 프로베이션(Latency-induced Probation)

지연 유발 프로베이션은 느려진 서버를 잠시 라우팅 대상에서 빼서, 전체 지연 시간을 낮추는 기법이다. 라우팅 대상에서는 빠졌지만, 백그라운드에서 계속 상태 체크 요청(Shadow request)을 보내서 서버가 정상화되면 다시 라우팅 대상에 투입한다. 느림의 원인은 흔히 관련 없는 네트워크 트래픽 간섭이나 해당 서버에서 다른 작업의 CPU 사용량 급증과 같은 일시적인 현상이기 때문에 이러한 기법이 효과적이다.

 

높은 부하 기간 동안 실시간 시스템에서 제공 용량의 일부를 제거하는 것이 오히려 지연 시간을 개선한다는 사실이 이 기법의 흥미로운 포인트이다.

대규모 정보 검색 시스템(Large information Retrieval Systems)

Google에서 발표한 논문 답게 정보 검색 관련 테크닉도 함께 소개하고 있다.

 

대규모 정보 검색 시스템에서 속도는 단순한 성능 지표를 넘어 핵심 품질 지표(key quality metric)라고 한다. 최상의 결과를 느리게 반환하는 것보다 양호한 결과를 빠르게 반환하는 편이 더 낫기 때문이다. 이러한 정보 검색 시스템과 본질적으로 비슷한, 불완전한 결과를 다루는 다른 시스템에도 적용되는 기법 2가지를 살펴보자.

Good enough

대규모 정보 검색 시스템에서는 전체 리프 서버(leaf server) 중 충분한 비율이 응답하면, 약간 불완전하지만 충분히 좋은(good enough) 결과를 제공하여 엔드 투 엔드 지연 시간(end-to-end latency)을 개선하는 편이 사용자에게 더 유리할 수 있다.

 

특정 리프 서버가 해당 쿼리에 대해 최고의 결과를 보유할 확률은 1,000건 중 1건보다 낮다고 한다. 또한 코퍼스(corpus, 자연어를 연구하거나 컴퓨터에서 처리하기 위해 특정 목적을 가지고 모아 놓은 언어 표본의 집합)의 가장 중요한 문서를 여러 리프 서버에 복제해 두기 때문에 그 확률은 더 낮아진다고 한다.

 

매우 느린 서버를 기다리면 서비스 지연이 수용 불가능한 수준으로 늘어날 수 있으므로 Google의 정보 검색 시스템은 전체 코퍼스 중 허용 가능한 비율이 검색되었을 때 가끔 충분히 좋은(good enough) 결과로 응답하도록 튜닝되어 있으며, 그러한 상황이 드물게만 발생하도록 주의한다. 일반적으로 "충분히 좋음(good enough)" 방식은 비필수 하위 시스템을 건너뛰어 응답성을 높이는 데에도 사용된다. 예를 들어, 웹 검색에서 광고나 철자 교정 시스템의 결과가 제때 응답하지 않으면 쉽게 생략될 수 있다.

카나리 요청(Canary requests)

매우 큰 팬아웃(fan-out)을 갖는 시스템에서는 특정 요청이 검증되지 않은 코드 경로를 밟아 수천 대의 서버에서 동시에 크래시(crash)나 극단적 지연을 유발할 수 있다.

 

이러한 시나리오를 방지하기 위해 Googld의 일부 정보 검색 시스템은 카나리 요청 기법을 사용한다. 즉, 루트 서버가 처음부터 수천 대의 리프 서버에 요청을 전송하는 대신, 먼저 한두 대의 리프 서버에만 보낸다. 루트 서버가 카나리로부터 합리적인 시간 내 성공 응답을 받으면 그때 나머지 서버들에 질의를 보낸다. 카나리 요청이 진행되는 동안 대상 서버가 크래시하거나 행(hang) 상태가 되면, 시스템은 그 요청을 잠재적으로 위험하다고 표시하고, 나머지 리프 서버로 전송하지 않음으로써 추가 실행을 차단한다.

 

카나리 요청은 예측하기 어려운 프로그래밍 오류나 악의적 서비스 거부 공격에 직면했을 때 백엔드의 강건성(robustness)을 높여준다. 카나리 요청 단계는 단일 서버의 응답만 기다리면 되므로 전체 지연 시간에 소량만을 더하며, 대규모 팬아웃 요청에서 모든 서버의 응답을 기다리는 경우보다 변동성이 훨씬 적다. 위에 소개한 Table 1의 첫 번째 행과 마지막 행을 비교하면 알 수 있다. 이러한 미세한 지연 증가에도 불구하고, 카나리 요청이 제공하는 추가 안전성 때문에 Google의 대규모 팬아웃 검색 시스템에서는 사실상 모든 요청에 카나리 요청이 사용되는 경향이 있다고 한다.

변경(Mutation)을 수행하는 연산은 더 수월하다

지금까지 살펴본 기법들은 시스템 상태에 대한 중요한 변경(mutation)을 수행하지 않는 연산에 가장 잘 적용되며, 이는 다양한 데이터 집약적 서비스에 폭넓게 해당한다. 한편, 상태를 변경하는 연산에서 지연 시간 변동성을 감내하는 일은 몇 가지 이유로 상대적으로 더 수월하다.

1. 지연에 민감한 수정의 규모는 대체로 작다. 대부분의 중요한 쓰기 작업은 레코드 몇 개, 플래그 하나 업데이트처럼 작은 변경이다.
2. 사용자에게 응답한 이후, 업데이트를 임계 경로(critical path) 밖에서 수행하는 경우가 많다. 임계 경로는 사용자 응답 지연에 직접 영향을 주는 처리 경로를 말한다. 사용자에게 필수 최소 정보만 동기 처리하고, 나머지 부가 업데이트는 응답 이후 큐/잡으로 밀어낼 수 있다. 예를 들어, "주문 접수 완료" 정보는 바로 응답하고, 영수증 이메일 발송과 알림 푸시는 SQS/Kafka와 Lambda 등의 워커로 뒤에서 처리할 수 있다.
3. 많은 서비스에서는 약한 일관성 허용이 가능하다. 쓰기 결과가 즉시 모든 곳에 반영되지 않아도 사용자 경험에 큰 문제가 없는 경우가 많다. 예를 들어, 좋아요/조회수 카운트가 몇 초 늦게 늘어도 사용자는 크게 불편하지 않다.
4. 강한 일관성이 필요해도 쿼럼(quorum)은 tail-tolerant 하다. 쿼럼 기반 합의는 전체 레플리카 중 일부의 동의를 얻으면 커밋을 인정하는 방식을 말한다. 결제나 재고처럼 정합성이 꼭 필요한 경우에는 Paxos/Raft 같은 쿼럼 합의를 사용한다. 쿼럼은 일정 비율 이상의 레플리카에만 커밋을 완료하면 되므로 본질적으로는 tail latency에 내성이 있다.

읽고 느낀 점

• p99 latency 값이 중요하다고 생각해본 적이 없다. 근데 이 논문을 읽으면서 이러한 극단적인 지연 시간도 대규모 시스템에서는 문제가 된다는 사실이 신기했다.
• 지연 시간 변동성이 큰 단일 인스턴스들을 모아서 tail latency에 내성을 갖는 시스템을 만드는 기법들이 신기했다. 불완전한 요소들을 최대한 활용해서 완전한 시스템을 구축하기 위한 노력들이 인상적이었다.
• Google과 같은 글로벌 서비스의 서버는 어떻게 구축되어 있는지 항상 궁금했었다. 이 논문을 읽으면서 Google의 서버 구성에 대해 맛이라도 본 것 같아서 좋다.
• 좋게 말하면 테크닉이고, 나쁘게 말하면 꼼수라고 볼 수 있는 기법들이 인상적이었다. 단일 인스턴스의 지연 시간 변동성 그 자체를 줄이기보다는, 적절히 변동성을 가리거나 우회해서 단일 인스턴스의 지연 시간 변동성은 그대로여도 시스템의 지연 시간 변동성을 낮추는 것이 신기했다.
• 나중에 내 프로젝트에도 몇 가지 기법들을 적용해보고 실험해보면 참 유익하겠다는 생각이 들었다.