[대규모 시스템 설계 기초] 5장 안정 해시 설계

[meloncha]

• 수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요
• 균등하게 나누기 위해 보편적으로 사용하는 기술

해시 키 재배치(rehash) 문제

• N개의 캐시 서버의 부하를 균등하게 나누는 보편적 방법
• serverIndex = hash(key) % N
• 서버 풀(server pool)의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작한다
• 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다
• 서버 하나가 장애를 일으켜 동작을 중단하면 서버 풀의 갯수가 하나 줄어든다
• 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 달라지고, 장애가 발생한 서버에 보관된 키 뿐만 아니라 대부분의 키가 재분배된다
• 그 결과 대규모 캐시 미스(cache miss)가 발생하게 된다

안정 해시

• 위의 대규모 캐시 미스를 효과적으로 해결하는 기술
• 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술
• k는 키의 개수, n은 슬롯(slot)의 개수
• 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다

해시 공간과 해시 링

• 해시 함수 f는 SHA-1 사용 (해시 공간은 0 ~ 2^160-1)
• 함수의 출력 값 범위는 x0, x1, ... xn
• x0는 0, xn은 2^160-1
• 이 해시 공간의 양쪽을 구부려 접으면 해시 링(hash ring)이 만들어진다

해시 서버

• 해시 함수 f를 사용하여 서버 IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있다

해시 키

• 해시 함수는 나머지 연산은 사용하지 않는다
• 캐시할 키 또한 해시 링 위의 어느 지점에 배치할 수 있다

서버 조회

• 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해가면서 만나는 첫번째 서버

서버 추가

• 서버가 하나 추가되면 key 하나만 재배치 된다
• 하나의 키가 시계 방향으로 링을 탐색하면서 처음으로 만나는 서버가 추가된 서버로 변경되고 나머지 키들은 영향이 없다 -> 탐색 시간은 N번 걸릴 것 같다

서버 제거

• 하나의 서버가 제거되면 키 가운데 일부만 재배치된다
• 각 키마다 시계 방향으로 탐색하고 하나의 키만 재배치 된다

기본 구현법의 두 가지 문제

안정 해시 알고리즘

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다

문제점

• 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다
  • 파티션은 인접한 서버 사이의 해시 공간 -> 파티션이 커지면 무슨 문제가 생길 수 있을까?
• 키의 균등 분포를 달성하기 어렵다
• 한 서버에 쏠림 현상이 있을 수 있다
• 이 문제를 해결하기 위해 가상 노드(virtual node) 또는 복제(replica) 기법이 제안되었다

가상 노드

• 가상 노드 : 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다
• 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다
• 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다
• 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다
• 가상 노드의 개수를 늘리면 가상 노드 데이터를 저장할 공간이 더 많이 필요해진다
• 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야 한다

-> 시스템 요구사항에 맞추는 의미? best practice는 무엇일까?

재배치할 키 결정

• 서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다
• 서버가 추가되면 새 서버의 모든 가상 노드부터 그 반시계 방향에 있는 첫번째 가상 노드 서버까지이다
• 그 사이의 키들을 새 서버의 가상 노드로 재배치해야 한다
• 서버가 제거되면 그 서버의 모든 가상 노드부터 그 반시계 방향에 있는 최초 가상 노드 서버 사이의 키들이 제거되는 가상 노드 다음 가상 노드 서버로 재배치 되어야 한다

안정 해시의 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다
• 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다 (유명인 문제)

[meloncha]

고민 Point

안정 해시가 최고의 해답일까?

https://dgryski.medium.com/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8

• Jump Hash

• Multi-Probe Consistent Hashing

• Rendezvous Hashing

• Maglev Hashing

• 알고리즘 별로 걸리는 시간

• CHash(Consistent Hashing) 의 경우 시간 복잡도 O(logN) 이다

https://itnext.io/introducing-consistent-hashing-9a289769052e

Rendezvous Hashing

type RendezVous struct {
    nodes []Node
}

type Node struct {
    id string
}

func (r *RendezVous) Get(key string) (*Node, error) {
    length := uint32(len(r.nodes))
    var maxHashValue = hash(key, r.nodes[0].id, length)
    result := 0

    for index, node := range r.nodes[1:] {
        currentHashValue := hash(key, node.id, length)
        if currentHashValue > maxHashValue {
            maxHashValue = currentHashValue
            result = index
        }
    }
    return &r.nodes[result], nil
}

• 각 노드들을 순회하면서 노드와 키를 기반으로 해시 값을 만들어 가장 큰 값에 해당하는 노드를 반환한다
• 가장 높은 무작위 가중치 해시
• 단점 : 시간복잡도 O(N) (N : 노드의 수)
• 제한된 수의 노드를 사용할 경우 안정해시보다 효율적이다 (가상 노드를 사용하지 않아서 메모리 절약)

Jump Consistent Hashing

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { 
  int64_t b = ­1, j = 0;
  while (j < num_buckets) { 
    b=j;
    key = key * 2862933555777941757ULL + 1; // Did you say magic number?
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

• Bucket size는 목적지까지의 거리. Key는 말
• 특수 제작된 주사위를 던져서 말을 앞으로 전진시켜 몇 번만에 목적지를 뛰어 넘는지를 계산
• 멀리 뛸 확률은 점점 줄어든다
• 이 확률이 1/N(거리) 로 맞추면 공정한 게임판이 된다
• 목적지까지의 거리(버킷 크기)가 4이면 1, 1/2, 1/3, 1/4 의 확률을 가진다
• 솔직히 이해 안됨..

장점

• 메모리 오버해드 없이 노드간의 워크로드 분산을 개선
• 가상 노드 개념이 더 이상 필요없다
• 반환되는 값이 0 ~ N-1 사이의 정수이며 임의의 노드 이름을 지원하지 않는다
• 서버 이름이 아닌 샤드 번호를 제공하는 것이 유용하다
• 임의의 노드를 추가하고 삭제할 때는 사이의 노드가 아닌 끝만 가능하므로 임의의 노드를 삭제할 수 없다
• 샤딩 컨텍스트에서는 유용하지만 로드 밸런싱에는 유용하지 않다