Maglev: Google의 로드밸런싱 알고리즘

Maglev는 Google에서 개발한 로드밸런싱 알고리즘으로, 백엔드 서버 간의 부하를 효율적으로 분산하는 역할을 합니다.

 

핵심 아이디어

Maglev의 핵심 아이디어는 다음과 같습니다:

1. 소수 M 크기의 해시 테이블(슬롯)을 만든다.
2. 각 백엔드에 대해 “슬롯에 들어갈 순서”를 (offset, skip)으로 계산
3. 해시 테이블에 차례로 백엔드를 배정해 나가며, 슬롯이 이미 차 있으면 다음 순서로 건너뛴다.

 

Maglev 동작 상세하게 살펴보기

초기 설정

 

lb에 달려있는 백엔드가 이렇게 3개있고 

 

이렇게 해시 테이블의 사이즈가 7일때 

 

해시 알고리즘 2개를 이용해서 해시 테이블을 구성합니다. 

 

오프셋 계산을 위한 해시 알고리즘

 

얼마만큼 건너뛸건지를 계산할 해시 알고리즘 

 

이렇게 해서 다음과 같이 먼저 각각의 백엔드 값을 이용해서 offset계산을 합니다.

백엔드로 들어가는 값은 [10.2.2.3:80/tcp,State:active] 이런 식으로 문자열을 만든 뒤 murmur3로 해싱하게 됩니다. 

 

동일하게 skip으로 사용할 값도 계산합니다.

이 정보들을 통해서 이제 테이블을 채워봅시다.

 

 

해시 테이블 채워 넣기

먼저 첫 시작인 2번째에 보라색 백엔드를 넣고

 

돌아가면서 한번씩 다 offset에 맞게 채워줍니다.

 

이제 다음부터는 기존의 값에서 skip의 만큼 위치를 옮겨서 채워줍니다.

기존 보라색이 2이고 skip인 3만큼 이동시키면 5인데 이미 빨간색으로 채워져있기때문에 충돌이 납니다.

 

그럼 이번엔 추가로 +3을 더하는데 그렇게 하면 테이블을 벗어나게 됩니다.

 

테이블 사이즈로 그럼 값을 나눠주어 해당 위치에 넣습니다.

하지만 그렇게 되면 값이 1이고 초록색과 충돌나게 됩니다.

 

한번 더 +3을 더해서 계한을 해보겠습니다.

하면 11인데 테이블 사이즈를 벗어나서 테이블 사이즈로 나누어 나머지를 계산 한 값인 4에 보라색을 넣어주게 됩니다. 

 

이런식으로 테이블을 전채를 채워주게 됩니다. 

이런식으로 채워진 테이블 정보를 갖고 백엔드 서버를 결정하기 때문에 계속해서 일관적인 백엔드를 선택할 수 있게 됩니다.

 

TMI).. cilium의 경우 가중치 계산도 더 들어가기 때문에 이거랑 완벽한 방식으로 테이블을 채우지는 않는것 같습니다. 

TMI2) cilium에서 사용하는 해시 알고리즘은 murmur3라고 하는듯하다..

 

cilium 코드로 조합해본 offset과 skip 계산하는 코드.. 

package main

import (
  "fmt"
  "encoding/base64"

  "github.com/cilium/cilium/pkg/murmur3"
)

func getOffsetAndSkip(addr []byte, m uint64, seed uint32) (uint64, uint64) {
	h1, h2 := murmur3.Hash128(addr, seed)
	offset := h1 % m
	skip := (h2 % (m - 1)) + 1
	return offset, skip
}

func main() {
  tablesize := 251
  seed := "JLfvgnHc2kaSUFaI" # cilium에서 쓰는 기본 seed
  hasString := "[10.2.2.3:80/tcp,State:active]"
  d, err := base64.StdEncoding.DecodeString(seed)
  if err != nil {
	fmt.Errorf("cannot decode base64 Maglev hash seed %q: %w", seed, err)
  }
  if len(d) != 12 {
	fmt.Errorf("decoded hash seed is %d bytes (not 12 bytes)", len(d))
  }

  seedMurmur := uint32(d[0])<<24 | uint32(d[1])<<16 | uint32(d[2])<<8 | uint32(d[3])

  offset, skip := getOffsetAndSkip([]byte(hasString), uint64(tablesize), seedMurmur)
  fmt.Println(offset)
  fmt.Println(skip)
}

 

뭐가 좋지?

 

기존 해싱 알고리즘을 사용하면, 백엔드 서버가 추가되거나 제거될 때 전체 해시 테이블을 재구성해야 하는 경우가 많습니다. 이 과정에서 기존 트래픽이 새로운 서버로 이동하면서 연결이 끊기거나 서비스의 일관성이 저하될 수 있습니다.

기존 방식의 한계

• 예를 들어, 모듈로 해싱(Modulo Hashing) 방식에서는 hash(client_ip) % N을 사용하여 백엔드를 선택합니다.
• 그러나, N(백엔드 개수)이 변하면 해시 테이블 전체를 재구성해야 하며, 이로 인해 많은 요청이 다른 백엔드로 이동합니다.

Maglev의 해결책

Maglev 알고리즘은 5-tuple(소스 IP, 소스 포트, 목적지 IP, 목적지 포트, 프로토콜)을 이용하여 해시 값을 계산합니다.

• 이를 통해 해시 테이블의 슬롯 인덱스를 결정
• 슬롯 인덱스는 백엔드 개수와 독립적으로 유지됨
• 백엔드가 추가/제거되더라도 기존 백엔드와 유사한 서버로 트래픽을 전달 가능

결과적으로, Maglev을 사용하면 트래픽 분배의 안정성이 높아지고, 연결 유지 및 서비스 일관성이 강화됩니다.