아마 여러분들이 서버나 어떤 외부에서 트래픽을 받는 무언가를 운영해 보았다면 해당 레플리카 풀을 확장하거나 축소할 때 Connection Reset이 우수수 발생하면서 엄청난 수의 에러 로그와 함께 그라파나가 붉은 색으로 피가 터져나오며 슬랙 알럿 채널에서 헬리콥터 이륙하는 소리를 들어본 경험이 있을지도 모른다. 없었다면 축하드린다. 나는 있었다.

이런 문제는 많은 원인으로 인해 발생할 수 있으나, 그 중 하나의 이유는 Consistent Hashing의 한계에 있다. 해시 링을 사용하는 로드밸런싱의 경우 서버에 노드가 추가 혹은 제거될 때마다 해시 링의 재구성이 필요하고, 이 과정에서 키 재배치 비용이 시스템의 가용성을 위협하게 된다.

이 글에서 다뤄볼 Maglev LB는 이 Consistent Hashing을 기반으로 한 로드 밸런싱 알고리즘의 문제들을 상당히 개선하기 위해 노력한 기법이라고 생각하면 될 것 같다. 일단 Maglev는 구글에서 개발한 고성능 분산 트래픽 처리 기법이다. 이게 뭔가 슬라브 계열 사람 이름인 줄 알았는데 그냥 Magnetic Levitation, 즉 자기부상 열차라고 한다. 솔직히 그렇게 기깔나고 쌈@뽕한 이름이라고 생각하진 않는다. 아무튼 이 이름은 자기부상 열차처럼 안정적이면서 빠르게 원하는 지점에 트래픽을 배치할 수 있게 한다는 이름이라고 한다. Maglev의 핵심은 위에서 설명한 노드의 추가 및 변동이 잦은 환경에서 발생하는 불균형과 Consistent Hashing이 가진 단점들을 개선하고자 등장했다. 아무튼 이 친구는 구글이라는 압도적인 초대형 트래픽 환경에서 기인하여 재배치 비용을 최소화 하면서도 균등 분산을 극대화 하는 방향으로 설계되었다.

사실 기존에도 훌륭한 로드 밸런싱 기법들은 많이 있었다. 워낙 네트워크 소프트웨어 분야에서 SDN 만큼 코어가 되는 분야기도 하고, L4나 L7 수준에서 트래픽을 분산하는 접근은 이미 아주 많이, 그리고 널리 사용되고 있다. 이 글을 읽는 독자라면 아마 다뤄보지 않은 사람이 단 한 명도 없지 않을까 싶다. 그리고 이런 발전에서 가장 많이 사용되고 계속 비교할 Consistent Hashing이 가장 오랫동안 채택되어온 기법이다.

허나 최근에는 오토스케일링과 글로벌 리전 운영이 일상화 되고 있다.
이게 뭐가 중요하냐면,

  • 서버가 수시로 늘고 줄며,
  • 트래픽이 특정 시간대에 몰리고,
  • 일부 노드는 메모리나 CPU가 빨리 차서 빨리 내려가야 하는 상황

이 자주 발생할 수 있다는 것이다. 이때 Consistent Hashing은 다음과 같은 문제들이 슬슬 거슬리기 시작한다.

  1. 서버가 추가/제거 될 때마다 생각보다 많은 데이터가 재분배 된다
  2. 노드별로 트래픽이 균등 분산되지 않고 핫스팟이 잘 발생한다
  3. 트래픽 폭주나 장애가 발생할 경우 동적 라우팅이 불가능하다

Maglev는 이런 기존의 문제들을 제어하기 위한 목적으로 태어났으며, 노드가 변동되는 상황에서도 보다 매끄럽게 트래픽을 분산하는 것이 설계 목표이다.
대충 보면 Consistent Hashing과 매우 유사하긴 한데, 몇 가지 독자적인 데이터 구조와 알고리즘을 통해서 키 분포를 균등하면서도 동적이고 유연하게 관리하는 방식을 채택한다.

그리고 그냥 갑자기 하고 싶은 이야기인데, 우리는 어차피 클라우드 단에서는 ELB나 NLB를 쓰고, 쿠버네티스에서는 Service 기반의 Managed LB를 사용하고, 굳이 필요하다면 Istio 수준에서 로드밸런싱 알고리즘을 지정하는 정도인데 왜 이런 이름도 생소한 알고리즘의 구현까지 살펴봐야 하나라는 생각이 들 수 있다. 사실 첫 번째는 그냥 재미있어서고, 두 번째로 억지로 이유를 만들어보자면 Maglev에서 제시하는 로우 레이턴시 하이 쓰로풋 서비스를 다루는 방식은 충분히 살펴볼 만한 가치가 있는 것 같다.

로드 밸런싱

로드 밸런싱, 로드 밸런서, 암튼 그 비스무리한 무언가들. 당연히 못 들어봤을 리 없다.
어떻게 보면 이 로드 밸런서라는 이름 자체가 트래픽을 “알작딱따구리” 잘 분산시켜서 서버가 무너지지 않도록 하는 도구로 직관적으로 정의해볼 수 있다.
허나 로드 밸런싱이라는 주제를 자세히 들여다보면 OSI 계층으로부터 시작하여 각 계층별로 나뉘는 다양한 트래픽 분산 기법을 살펴볼 수 있게 된다.
그래서 일단은 L4와 L7 LB부터 한 번 짚어보고 넘어가고 싶다. 물론 이 두 가지를 모르는 사람은 없겠지만, 그래도 빌드업을 위해 한 번 정리해보자.

L4 vs L7

Layer 4

  • 이름 그대로 L4에서 동작하는 로드 밸런싱이다.
  • L4의 특징을 간단히 생각해보면 포트가 핵심 단어로 떠오를 수 있다.
  • 누군가 “L4가 뭐냐”라고 물어보면, “서로 다른 프로세스가 통신할 수 있는 채널을 제공하는 계층”이라고 부르는 게 좋겠다.
  • 여기서 서로 다른 프로세스가 서로를 식별하는 방식은 포트로 수행된다.

그래서 L4 LB는 이 포트 수준에서 라우팅을 결정하기에 상대적으로 단순하고 빠르다.
L7에서 다루는 정보인 HTTP Header나 Cookie들을 싸그리 무시하므로 자원 사용량이나 레이턴시가 비교적 적다.
물론 이게 장점이자 단점이다. 상위 계층 정보를 활용할 수 없으므로 더 유연하고 정교한 로드 밸런싱은 불가능하다.

결국 L4 로드 밸런서는 일종의 초기 단계 분배기 역할에 최적화되어 있다.
서버 풀에 들어오는 연결들을 적절히 나눠주는데 특화되었지만, 패킷 안쪽까지 파고들어 애플리케이션 레벨 로직에 대한 통제는 거의 할 수 없다.

Layer 7

  • 이름 그대로 L7에서 동작하는 로드 밸런싱이다.
  • L7에서 동작하니 HTTP Header나 URL, Cookie, SSL 등, 우리가 일상적으로 다루는 모든 데이터는 까서 제어할 수 있다는 압도적인 장점을 가진다.
  • 즉, L4에 비해서 훨씬 더 정교한 로드 밸런싱과 라우팅이 가능하지만, 당연히 성능이 L4에 비해 제한된다.

사실 말이 L7 LB지, 현재 L7 LB는 거의 HTTP LB라고 봐도 무방하다.
그래서 HTTP의 특성을 적극적으로 활용하는데, URL이나 쿠키, User-Agent까지도 분석해서 아주 유연하게 라우팅을 제어한다.

Consistent Hashing

사실 처음에는 로드 밸런서가 모든 트래픽을 알잘딱 재분배하면 되는 거 아니냐? 정도로 간단하게 생각할 수 있는데, 트래픽이나 노드가 많아지고 그 가운데 특정 노드로 계속해서 같은 타입의 요청을 보내야 하는 시나리오가 등장하면서부터 문제가 복잡해질 수 있다.

가장 대표적으로는 Sticky Session을 예로 들 수 있다.
특정 사용자의 세션 정보를 특정 서버에 모두 모아두어야 하면, 임의로 요청을 다른 서버로 보내면 세션 데이터를 다시 만들거나 캐시 미스가 발생하기 때문에 성능 저하가 발생할 수 있다.

이럴 때 Consistent Hashing은 노드가 늘거나 줄어도 전체 키 중 최소한의 키만 적절히 새 노드로 분배하고, 기존 노드는 그대로 사용하도록 하여 재배치 비용을 줄이자는 목표를 가지고 등장한 놈이다.

상당히 오랜 기간, 그리고 아직까지도 메이저로 자리 잡고 있는 놈이라 장점이 명확하다.
설명한 것과 같이 노드가 증감 시 키의 이동이 최소화된다. 전통적인 해싱 기법은 노드 수가 변하면 전체 키를 다시 해시해야 할 수도 있으나, Consistent Hashing은 해시 링 상에서 노드와 데이터를 순서대로 배치하여 새 노드가 추가되면 그 위치에 해당하는 일부 키만 새 노드로 옮기면 끝이다. 제거도 마찬가지로 최소 키만 다른 노드로 넘긴다.
이런 이유로 인해 노드가 수백 개가 넘어가더라도 해당 노드가 차지하는 링의 구간만 재분배가 되기에 대규모 환경에서도 확장과 축소에 대한 부담이 상당히 줄어든다.

허나 이 필살기처럼 등장했던 녀석도 단점이 있는데, 우선 데이터 불균형 문제이다.
랜덤 분포를 가정한 해싱이기에 실제로는 노드마다 데이터가 고르지 않게 분포되거나 특정 노드에 트래픽이 몰리는 핫스팟이 자주 발생한다. 이를 보완하기 위해 실제 구현에서는 Virtual Node 기법을 사용하긴 하는데,

  • Virtual Node가 너무 적으면 분산 효과가 미미하고,
  • 너무 많으면 연산량 및 메모리 사용량이 급증해서,

Consistent Hashing을 “쓰는 등 마는 둥”한 부담이 생긴다.

또 다른 단점은 데이터 로컬리티가 고려된 알고리즘이 아니라는 것이다.
Consistent Hashing에서 데이터의 위치와 노드의 위치는 네트워크 상의 토폴로지가 고려되지 않았다. 그래서 노드 간 거리나 네트워크 상태가 성능에 영향을 줄 수 있다.

동적 트래픽 분배도 어렵다.
해시 링 구조상 특정 노드가 과부하 상태니 “여기 오는 트래픽을 임의로 좀 빼서 다른 노드로 넘기자!” 같은 생각은 해시 함수를 재조정하지 않는 이상 쉽지 않다.

이 문제들이 실제 운영 환경으로 넘어가면 다양한 문제를 일으킬 수 있다.
현대 서비스 환경은 대부분 아주 유연한 로드 밸런싱을 채택한다. 그렇기 때문에 노드의 추가 및 제거가 매우 빈번하다.
Consistent Hashing의 링을 구성해 두었더라도 계속해서 노드 풀이 커지고 작아지는 동안에 키 분포를 재조정하고, 갑자기 대량으로 풀의 수량이 바뀌는 경우가 있는데, 이럴 때 Connection Reset이라는 끔찍한 일이 발생할 수 있다.
이것 말고도 뭐… 최악의 케이스를 고려해보자면 나올 수 있는 것은 많으니 한 번 상상해보시면 좋겠다.

핵심 아이디어

Maglev의 핵심 아이디어는 상당히 단순하다.
단순한 결정론적 매핑과 최소 재배치를 지향한다는 것에 있다.

Maglev 알고리즘에는 가장 중요한 두 가지 기둥이 있는데,

  1. Entry Table 기반의 구조
  2. 균형 재조정 알고리즘

이 두 가지를 기반으로 어떻게 Consistent Hashing을 이겨내었는지 살펴보자.

Entry Table

로드 밸런싱이 풀고자 하는 문제를 일반화하면 심플하다.
클라이언트의 요청을 특정 서버로 연결하는 매핑을 만드는 문제다.
Consistent Hashing에서는 이 매핑을 위해 해시 링을 만들고, 그 위에 노드와 데이터를 배치해서 “가장 가까운 노드”를 찾는 방식으로 매핑을 만든다.
허나 Maglev는 Entry Table이라는 고정된 크기의 테이블을 사용한다.

  • 이 Entry Table은 일정 크기의 배열로 이루어진 자료구조이다.
  • 다른 이름으로는 Lookup Table이라고도 부른다.
  • 길이가 $M$인 테이블이 있을 때, 인덱스 $0$부터 $M-1$까지 각각 특정 서버들을 매핑해 놓고, 해시 결과값이 해당 테이블의 인덱스를 가리키도록 만든다.

그리고 이제 서버 노드가 $N$개 있다고 가정해보자.
각 서버에 대해서 서로 다른 해시 기반 순열을 생성한다. 예를 들어 서버 A, B, C가 있다면,

  • 서버 A의 순열,
  • 서버 B의 순열,
  • 서버 C의 순열

이렇게 각각 어떠한 순서로 테이블 $M$의 칸을 채울지를 계산하고, 각 서버가 자신의 고유 슬롯을 가지도록 한다.

이제 실제로 슬롯을 채울 때 중요한 점은 충돌을 피해야 한다는 것이다.
서버 A의 순열에서 나오는 인덱스를 순서대로 보면서 비어있는 슬롯이 있다면 그 자리에 서버 A를 매핑한다.
만약 이미 다른 서버가 차지하고 있는 슬롯이라면 건너뛰고 다음 인덱스로 이동한다.
이 과정을 모든 서버에 대해 수행하면, 결정론적이면서도 랜덤성이 포함된 테이블이 완성된다.

그리고 이제 이 Entry Table(또는 Lookup Table)을 사용하면, 키를 해싱한 결과가 테이블의 특정 인덱스를 가리키기만 하면, 어떤 서버로 트래픽을 분산해야 할지 상수 시간($O(1)$)에 알 수 있다.

특히 이 Entry Table은 고정 크기를 가진다고 했다.
고정 크기를 가지기 때문에 노드 증가나 트래픽 증감에 대해 조회 비용이 크게 영향을 받지 않는 장점이 있다.

정리해보면,
Maglev는 테이블을 한 번 구성해두면 해시 링을 순회하거나 다른 복잡한 연산을 하지 않고도,
매우 빠른 속도로(사실상 상수 시간 내에) 서버를 결정할 수 있다.
무엇보다 이 테이블이 전체 서버 풀을 균등하게 반영하도록 만들어졌기 때문에, 서버 부하가 더 평준화될 수 있도록 유도된다.

Minimal Disruption

Entry Table이 가장 핵심적인 요소인데, 테이블과 함께 또 중요한 특징은 서버가 추가되거나 제거될 때 발생하는 재배치 비용이 최소화된다는 것이다.
Consistent Hashing도 마찬가지로 적은 재배치가 일어나는 것을 목표로 하고 있긴 하지만, Maglev는 테이블 기반이라는 점을 활용해서 조금은 다른 방식으로 접근한다.

노드 추가 시

  • 새 서버 노드가 추가되면 그 노드에 대한 새로운 순열을 생성한다.
  • 그리고 기존 테이블에 빈 슬롯이 남아있으면 그 위치를 그대로 채운다.
  • 만약 충돌이 발생한다면 일부 슬롯만 재배치한다.
  • 이때 가능한 한 기존 노드가 담당하던 슬롯을 크게 바꾸지 않는 것이 중요하다.
    • 현재 트래픽이 어느 정도 안정적으로 분산되어 있다면, 그 상태를 최대한 유지하면서만 테이블에 변화를 주자는 것이다.

노드 제거 시

  • 노드에 장애가 발생하거나 노드의 수가 줄어서 노드가 없어진다면, 그 노드가 차지하던 슬롯들을 비우거나 다른 노드들이 대신 차지하도록 한다.
  • 가능한 한 전체 테이블을 크게 흔들지 않도록 하여, 기존에 매핑되어 있던 많은 요청 키들이 그대로 유지되도록 한다.

최소 재배치

결국 최대한 많은 키의 매핑이 그대로 유지되게 하는 것이 핵심이다.
그래야 캐시 로컬리티나 세션 데이터를 유지하는 데도 유리하고,
클러스터가 확장/축소되는 환경에서 일어날 수 있는 대규모 캐시 미스나 세션 재생성 문제를 어느 정도 완화할 수 있다.

물론 Maglev도 Consistent Hashing과 마찬가지로 재조정 로직을 아예 제거할 수는 없다.
그래도 꼭 필요한 부분만 최소한으로 변동시키자라는 전략을 취한다.
이는 Consistent Hashing의 목표와 유사하지만, 테이블 기반 구조로 인해 좀 더 결정론적이고 균등한 분산을 구현하기가 수월하다는 차이가 있다.

해시 함수는 복잡할 필요가 없다

Maglev에 관련된 구글 문서를 보면,
해시 함수는 굳이 암호학적으로 강력할 필요가 없고 오히려 가볍고 빠른 해시를 쓰라고 자주 언급한다.
이유는 다음과 같다.

  1. 충돌 방지가 절대적인 목표가 아님
    • SHA나 DEC 같은 암호학적 해시들은 충돌 확률이 극단적으로 낮다.
    • 그러나 연산량과 속도면에서 부담이 크다.
    • Maglev에서는 완벽한 충돌 회피가 목적이 아니라, “테이블 인덱스를 적절히 분배해주는 정도”면 충분하다.
  2. 테이블 재배치 로직이 결정론적으로 충돌 완화
    • 해시 충돌이 발생해도 순열을 통해 슬롯을 채우는 과정에서 자연스럽게 충돌을 우회한다.
    • 즉, 충돌이 치명적인 버그로 이어지지 않는 구조가 이미 설계되어 있다.
  3. 속도가 중요함
    • 구글 인프라처럼 수백만 RPS를 감당하는 환경에서 복잡한 해시 함수의 지연은 치명적이다.
    • 누적된 미묘한 몇 ms 차이도 극단적으로 커지기 때문에, 가벼운 해시(Jenkins Hash나 CRC 등)를 사용해 $O(1)$에 가까운 Lookup을 만드는 것이 더 낫다.

Maglev의 한계

Maglev는 기본적으로 구글이라는 거대한 인프라에서 대규모 트래픽을 효율적으로 밸런싱하기 위해 설계된 구조다.
당연히 이놈도 만능은 아니고, 고유한 단점을 가지고 있으며 운영 환경에 따라 고려해야 할 이슈들이 있다.
대표적으로는 두 가지 문제가 있다.

  1. 고정된 테이블 크기로 인한 확장성 제약
  2. 멀티테넌트 환경에서의 격리 필요성

이 두 가지를 살펴보겠다.

고정된 테이블 크기로 인한 확장성 제약

Maglev는 고정된 엔트리 테이블을 가짐을 통해 룩업 속도와 관리를 편하게 할 수 있게 되었다.
허나 이 특징이 이제는 단점으로 다가온다.
예를 들어 $M$이라는 크기의 배열을 쓰기로 결정했다면, 실제 서버 노드가 늘어나거나 줄어들 때에도 해당 배열의 크기는 그대로 유지된다.
서버 수가 적당히 많은 수준에서 운영될 때는 빠른 해시 룩업과 안정적인 트래픽 분산이라는 큰 이점을 가져다주지만,
극단적으로 노드가 많아지거나 너무 적어지는 상황에서는 다음과 같은 문제가 발생할 수 있다.

슬롯 부족

  • 노드가 매우 많아지면, 고정된 테이블 $M$에 비해 노드의 수 $N$이 훨씬 커지는 상황이 온다.
  • 이때는 각 노드에 할당되는 슬롯이 극단적으로 줄어들거나, 일부 노드는 아예 슬롯을 배정받지 못할 수도 있다.

테이블 재구성 부담

  • 테이블 크기를 애초에 너무 크게 잡으면 메모리 사용량이 급증하고, 빌드 시간도 길어진다.
  • 당연히 성능도 떨어진다.
  • 반대로 작게 잡으면 위에서 말한 슬롯 부족 이슈가 발생한다.
  • 결국 적절한 균형을 찾기가 쉽지 않다.

멀티테넌트 환경에서의 격리

Maglev는 기본적으로 Single Tenant 환경에서 설계된 구조에 가깝다.
구글 내부에서는 여러 서비스를 동시에 운영하더라도 각 로드 밸런싱 레이어를 별도의 풀이나 클러스터로 분리해서 관리하는 경우가 많아,
굳이 멀티테넌트를 한 곳에 몰아넣는 방식이 아닌 경우가 대부분이라는 것이다.

하지만 현대 서비스 환경에서는 여러 테넌트가 하나의 인프라 위에서 공존하는 경우가 흔하다.
그래서 멀티테넌트 환경에서도 잘 동작해야 하는데, 여기서 몇 가지 단점이 드러난다.

각 테넌트별 부하 편차

  • 특정 테넌트가 갑자기 트래픽이 폭발하면, 동일 테이블에 매핑된 다른 테넌트에 영향이 갈 수 있다.
  • 슬롯 충돌이 쉽게 발생할 수 있고, 테이블의 특정 부분(슬롯)이 특정 테넌트로 몰리면서 균등 분산이 깨질 우려가 있다.