복잡도

일관된 해시의 비용은 세 가지로 나눠 봐야 합니다. 키 하나를 찾는 조회 비용, 링을 들고 있는 메모리, 그리고 노드가 바뀔 때 옮겨야 하는 키의 양입니다. 마지막 항목이 이 알고리즘의 존재 이유이므로 가장 중요합니다. 아래에서 N은 물리 노드 수, V는 노드당 가상 노드 수, K는 전체 키 수입니다.

해시 링의 시간과 공간

링에는 점이 N·V개 있습니다.

조회가 이진 탐색 한 번이므로 노드 100대에 가상 노드 200개, 곧 점 2만 개라도 비교는 15번 정도입니다. 실제로는 키 해시를 계산하는 시간이 탐색보다 큰 경우가 많습니다. 배열에 insort로 하나씩 넣는 방식은 넣을 때마다 뒤쪽 원소를 옮기므로 노드 변경이 잦다면 정렬 트리나 "모두 모아 한 번에 정렬"이 낫습니다. 노드 변경은 드물고 조회가 압도적으로 많다면 메모리 배치가 연속적인 정렬 배열이 오히려 빠릅니다.

import bisect

def build(points_with_owner):
    # O(M log M) once, instead of M separate insort calls
    items = sorted(points_with_owner)
    points = [p for p, _ in items]
    owner = dict(items)
    return points, owner

points, owner = build([(80, "C"), (10, "A"), (45, "B")])
print(points, owner[points[bisect.bisect_left(points, 50) % len(points)]])  # [10, 45, 80] C

옮겨지는 키의 양

해시가 고르게 퍼진다는 가정에서 기대값은 다음과 같습니다.

K/(N+1)은 새 노드가 공평한 몫을 가지려면 반드시 옮겨야 하는 양이므로 이보다 적게 옮기는 방법은 없습니다. 이 의미에서 일관된 해시는 최소 이동을 달성합니다. 다만 이것은 기대값이며, 가상 노드가 적으면 실제 이동량은 새 노드가 우연히 차지한 구간 크기에 따라 크게 흔들립니다.

부하 균형

노드마다 점이 하나뿐이면 N개의 무작위 점이 원을 나누는 간격 중 가장 큰 것은 평균의 약 ln N배입니다. 노드 100대라면 가장 바쁜 노드가 평균의 5배 안팎을 맡을 수 있습니다. 가상 노드 V개를 두면 한 노드의 몫은 V개 구간의 합이 되어 편차가 대략 1/sqrt(V)에 비례해 줄어듭니다. 그래서 실무에서는 노드당 수십에서 수백 개를 흔히 씁니다. V를 늘리면 메모리와 노드 변경 비용이 늘어나므로 균형과 비용 사이의 절충입니다.

import math

for v in (1, 10, 100, 1000):
    print(v, f"relative spread about {1 / math.sqrt(v):.0%}")
# 1 100%, 10 32%, 100 10%, 1000 3%

이 수치는 대략적인 크기만 보여 줍니다. 실제 키 분포가 고르지 않거나 특정 키가 유난히 뜨거우면(핫 키) 가상 노드로는 해결되지 않으며, 복제나 별도 캐시가 필요합니다.

다른 방법과 비교

랑데부 해시는 조회가 노드 수에 비례하지만 노드가 수십 대 이하라면 충분히 빠르고 코드가 가장 짧습니다. 점프 해시는 메모리가 필요 없고 균형도 매우 좋지만 노드에 이름이 아니라 0부터 N-1까지의 번호만 붙일 수 있고, 중간 번호를 빼는 것은 지원하지 않습니다. 그래서 장애로 임의의 서버가 빠지는 캐시보다는 샤드 번호가 순서대로 늘어나는 저장소에 어울립니다.

def jump_hash(key: int, num_buckets: int) -> int:
    # Lamping & Veach (2014): O(log n) time, no memory
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF
        j = int((b + 1) * ((1 << 31) / ((key >> 33) + 1)))
    return b

print(jump_hash(123456789, 10), jump_hash(123456789, 11))

버킷을 10개에서 11개로 늘리면 약 1/11의 키만 바뀌고, 바뀐 키는 모두 새 버킷 10번으로 갑니다.

정리

• 링 조회는 O(log(N·V)), 메모리는 O(N·V)입니다.
• 노드 추가 시 옮기는 키는 기대값 약 K/(N+1)로, 피할 수 없는 최소량입니다.
• 가상 노드는 편차를 대략 1/sqrt(V)로 줄이지만 메모리와 변경 비용을 늘립니다.
• 노드가 적으면 랑데부, 번호형 샤드면 점프 해시, 범용으로는 가상 노드 링이 무난합니다.