연습 문제

아래 문제는 모두 구현 장의 hash64와 HashRing(정렬된 points, 위치에서 노드로 가는 owner)을 그대로 쓴다고 가정합니다. 먼저 스스로 풀어 보고 풀이와 비교해 보세요.

문제 1. 노드별 몫 계산하기

링이 주어졌을 때 각 노드가 링 전체(2^64) 중 몇 비율을 맡는지 계산하세요. 가상 노드 수를 1, 10, 100, 1000으로 바꿔 가며 가장 큰 몫과 가장 작은 몫이 평균과 얼마나 차이 나는지 확인합니다.

접근: 각 점은 바로 앞 점 다음부터 자기 위치까지를 맡습니다. 정렬된 점을 돌며 (p - 앞 점) mod 2^64를 그 점 주인의 몫에 더하면 됩니다. 인덱스 0의 앞 점은 마지막 점이며, Python의 pts[-1]이 이 감싸기를 자연스럽게 처리합니다. 점이 하나뿐이면 차가 0이 되므로 따로 처리합니다.

RING_SIZE = 1 << 64

def ownership(ring: HashRing) -> dict[str, float]:
    pts = ring.points
    if len(pts) == 1:
        return {ring.owner[pts[0]]: 1.0}
    share: dict[str, int] = {}
    for i, p in enumerate(pts):
        arc = (p - pts[i - 1]) % RING_SIZE   # i == 0 wraps to the last point
        node = ring.owner[p]
        share[node] = share.get(node, 0) + arc
    return {node: s / RING_SIZE for node, s in share.items()}

for v in (1, 10, 100, 1000):
    r = HashRing(vnodes=v)
    for n in range(10):
        r.add(f"node-{n}")
    s = ownership(r)
    print(v, round(max(s.values()) * 10, 2), round(min(s.values()) * 10, 2))

몫에 노드 수 10을 곱해 평균을 1로 맞췄습니다. 가상 노드가 늘수록 최댓값과 최솟값이 1에 가까워지는 것을 볼 수 있습니다.

문제 2. 가용 영역이 겹치지 않는 복제본

노드마다 속한 가용 영역(zone)이 있습니다. 키의 복제본 R개를 고르되, 서로 다른 물리 노드이면서 영역도 모두 달라야 합니다. 조건을 만족하는 노드가 부족하면 찾은 만큼만 돌려줍니다.

접근: 키 위치에서 시계 방향으로 점을 하나씩 걸으며, 이미 고른 노드이거나 이미 쓴 영역이면 건너뜁니다. 링을 한 바퀴 돌면 멈춥니다.

import bisect

def zone_replicas(ring: HashRing, zone_of: dict[str, str], key: str, n: int) -> list[str]:
    pts = ring.points
    start = bisect.bisect_left(pts, hash64(key))
    chosen: list[str] = []
    zones: set[str] = set()
    for step in range(len(pts)):
        node = ring.owner[pts[(start + step) % len(pts)]]
        if node in chosen or zone_of[node] in zones:
            continue
        chosen.append(node)
        zones.add(zone_of[node])
        if len(chosen) == n:
            break
    return chosen

zone_of = {"a1": "az-1", "a2": "az-1", "b1": "az-2", "b2": "az-2", "c1": "az-3"}
ring = HashRing(vnodes=50)
for node in zone_of:
    ring.add(node)
print(zone_replicas(ring, zone_of, "order:1001", 3))  # one node from each zone

문제 3. 노드 추가 시 이전 계획 세우기

새 노드를 추가하기 전에, 어떤 해시 구간을 어느 기존 노드에서 가져와야 하는지 목록으로 뽑으세요. 결과는 (시작, 끝, 원래 주인) 튜플이며 구간은 시작 초과, 끝 이하입니다.

접근: 새 노드를 넣은 링에서 새 노드의 각 점 p에 대해, 바로 앞 점부터 p까지가 넘어오는 구간입니다. 원래 주인은 "추가 전 링에서 p를 조회한 결과"입니다. 새 노드의 점이 연달아 있어도 이 규칙은 그대로 맞습니다.

def migration_plan(ring: HashRing, new_node: str) -> list[tuple[int, int, str]]:
    old_points = list(ring.points)
    old_owner = dict(ring.owner)
    ring.add(new_node)
    pts = ring.points
    plan = []
    for i, p in enumerate(pts):
        if ring.owner[p] != new_node:
            continue
        j = bisect.bisect_left(old_points, p) % len(old_points)
        plan.append((pts[i - 1], p, old_owner[old_points[j]]))
    return plan

def in_range(h: int, start: int, end: int) -> bool:
    if start < end:
        return start < h <= end
    return h > start or h <= end   # the range wraps past 0

검증은 키 수천 개를 추가 전후로 조회해, 주인이 바뀐 키가 정확히 계획의 구간 안에 있고 원래 주인도 일치하는지 확인하면 됩니다.

문제 4. 가중치 랑데부 해시

노드마다 용량 가중치가 있습니다. 키가 가중치에 비례해 배정되고, 노드 하나를 빼면 그 노드의 키만 움직이는 랑데부 해시를 만드세요.

접근: 노드마다 키와 섞은 해시로 0과 1 사이의 균등한 수 u를 만들고 점수 -w / ln(u)가 가장 큰 노드를 고릅니다. 이 점수는 가중치 w에 비례하는 확률로 1등이 됩니다. u가 정확히 0이나 1이 되지 않도록 상위 53비트에 0.5를 더해 나눕니다.

import math
from collections import Counter

def hrw(key: str, weights: dict[str, float]) -> str:
    best, best_score = "", -math.inf
    for node, w in weights.items():
        u = ((hash64(f"{node}:{key}") >> 11) + 0.5) / (1 << 53)   # 0 < u < 1
        score = -w / math.log(u)
        if score > best_score:
            best, best_score = node, score
    return best

weights = {"small": 1.0, "medium": 2.0, "large": 4.0}
keys = [f"obj:{i}" for i in range(70_000)]
first = {k: hrw(k, weights) for k in keys}
print(Counter(first.values()))   # roughly 10000 / 20000 / 40000
del weights["medium"]
moved = [k for k in keys if hrw(k, weights) != first[k]]
print(all(first[k] == "medium" for k in moved))  # True

정리

• 몫 계산은 정렬된 점 사이 간격을 주인별로 더하는 것입니다.
• 복제본 선택은 시계 방향으로 걸으며 조건에 맞지 않는 점을 건너뜁니다.
• 이전 계획은 새 점 앞 구간과 추가 전 주인을 짝지으면 됩니다.
• 가중치 랑데부 해시는 -w / ln(u) 점수로 비례 배정과 최소 이동을 함께 얻습니다.