동작 원리

이 장에서는 작은 링을 손으로 따라가며 키 조회, 노드 추가와 제거, 가상 노드, 복제본 선택이 어떻게 이루어지는지 살펴봅니다. 이해를 돕기 위해 해시 값 공간을 0부터 99까지인 작은 원으로 가정합니다. 실제 구현에서는 0부터 2^64 - 1 같은 큰 공간을 씁니다.

1단계: 노드를 링에 놓기

노드 A, B, C의 이름을 해시했더니 다음 위치가 나왔다고 합시다.

위치를 정렬해 두면 각 노드가 맡는 구간이 정해집니다. 규칙은 "키 위치 이상인 첫 노드"이며, 노드는 바로 앞 노드 위치 다음부터 자기 위치까지를 맡습니다.

2단계: 키 조회

키 위치가 정렬된 배열에서 어디에 들어갈지 이진 탐색으로 찾습니다. 끝을 지나면 0번 칸으로 감쌉니다.

import bisect

points = [10, 45, 80]
owner = {10: "A", 45: "B", 80: "C"}

def lookup(h: int) -> str:
    i = bisect.bisect_left(points, h)   # first point >= h
    if i == len(points):
        i = 0                           # wrap around
    return owner[points[i]]

print([lookup(h) for h in (7, 33, 52, 91, 45)])  # ['A', 'B', 'C', 'A', 'B']

3단계: 노드 추가

새 노드 D가 위치 60에 놓였습니다. 바뀌는 것은 D 바로 앞 노드 B(45)와 D(60) 사이, 곧 46~60 구간뿐입니다. 이 구간은 원래 C가 맡던 곳이므로 C의 키 일부만 D로 옮겨 갑니다. A와 B의 키는 하나도 움직이지 않습니다.

한 키라도 옮기는 쪽은 언제나 "새 노드의 시계 방향 다음 노드"이고 받는 쪽은 새 노드뿐입니다. 이것이 기존 노드끼리 키를 주고받지 않는다는 성질입니다.

4단계: 노드 제거

이번에는 B가 고장 나 빠졌다고 합시다. B가 맡던 11~45 구간은 시계 방향 다음 노드에게 넘어갑니다. 다른 구간은 그대로입니다. 문제는 넘겨받는 쪽이 이웃 한 노드뿐이라는 점입니다. 그 노드의 부하가 갑자기 두 배 가까이 늘어날 수 있습니다.

5단계: 가상 노드로 부하 펴기

노드마다 점을 여러 개 두면 위 문제가 줄어듭니다. 노드 A를 A#0, A#1, A#2처럼 이름을 바꿔 가며 해시해 세 점을 만들고, B와 C도 똑같이 합니다.

이제 B가 빠지면 B의 세 구간이 각각 다음 점의 주인인 A, A, C에게 나뉘어 갑니다. 점이 많을수록 몫이 여러 노드에 고르게 흩어집니다. 아래 코드로 서버 10대를 실험해 보면 노드당 점이 1개일 때는 가장 바쁜 노드가 평균의 3배 넘게 맡고 거의 일이 없는 노드도 생기지만, 100개일 때는 평균의 약 0.86~1.17배, 1,000개일 때는 약 0.93~1.05배로 좁혀집니다(한 번 돌린 결과이며 해시 함수와 노드 이름에 따라 달라집니다).

import bisect, hashlib

def h(s: str) -> int:
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

RING = 1 << 64
for v in (1, 10, 100, 1000):
    pts = sorted((h(f"node{n}#{i}"), n) for n in range(10) for i in range(v))
    share = [0] * 10
    for j, (p, n) in enumerate(pts):
        share[n] += (p - pts[j - 1][0]) % RING   # arc owned by this point
    ratios = [s / RING * 10 for s in share]
    print(v, round(max(ratios), 2), round(min(ratios), 2))

6단계: 복제본 고르기

Dynamo 계열 저장소는 키를 한 노드에만 두지 않고 시계 방향으로 이어지는 여러 노드에 복제합니다. 가상 노드가 있으면 이어지는 점들이 같은 물리 노드일 수 있으므로, 이미 고른 물리 노드는 건너뛰고 서로 다른 노드 R개를 모읍니다. 위 표에서 위치 30인 키의 복제본 2개를 고르면 41(B), 55(A) 순으로 B, A가 됩니다.

def replicas(points, owner, h, r):
    start = bisect.bisect_left(points, h)
    chosen = []
    for step in range(len(points)):
        node = owner[points[(start + step) % len(points)]]
        if node not in chosen:
            chosen.append(node)
            if len(chosen) == r:
                break
    return chosen

랑데부 해시로 같은 일 하기

랑데부 해시는 링 없이 같은 성질을 얻습니다. 키마다 모든 노드의 점수 hash(노드:키)를 계산하고 가장 높은 노드를 고릅니다. 노드가 빠지면 그 노드가 1등이던 키만 2등 노드로 옮겨 가고, 노드가 추가되면 새 노드가 1등이 되는 키만 옮겨 옵니다. 복제본은 점수 상위 R개를 고르면 됩니다.

def rendezvous(key: str, nodes: list[str]) -> str:
    return max(nodes, key=lambda node: h(f"{node}:{key}"))

정리

• 정렬된 위치 배열과 이진 탐색, 끝에서 처음으로 감싸기가 조회의 전부입니다.
• 노드 추가 시 새 노드 앞 구간만, 제거 시 빠진 노드의 구간만 바뀝니다.
• 가상 노드는 구간 크기의 편차를 줄이고, 빠진 노드의 부하를 여러 노드로 나눕니다.
• 복제본은 시계 방향으로 걸으며 서로 다른 물리 노드를 고릅니다.