일관된 해시의 개념

데이터나 요청을 여러 서버에 나눠 담을 때 가장 먼저 떠오르는 방법은 hash(key) % N입니다. 키를 해시하고 서버 수 N으로 나눈 나머지를 서버 번호로 쓰는 방식입니다. 계산이 빠르고 분포도 고르지만, 서버 수가 바뀌는 순간 거의 모든 키의 자리가 바뀐다는 큰 약점이 있습니다. 일관된 해시(consistent hashing)는 이 문제를 풀기 위해 1997년 Karger 등이 웹 캐시 분산을 위해 제안한 방법으로, 서버가 추가되거나 빠질 때 꼭 옮겨야 하는 만큼의 키만 옮기도록 설계되어 있습니다.

mod-N 샤딩의 문제

키 10,000개를 서버 4대에 나눠 둔 캐시를 생각해 봅시다. 서버를 1대 늘려 N이 4에서 5가 되면 h % 4와 h % 5가 같은 키만 제자리에 남습니다. 해시값이 고르게 퍼져 있다면 그런 키의 비율은 약 1/(N+1)이므로, 나머지 약 N/(N+1), 곧 80%의 키가 다른 서버로 옮겨 갑니다. 서버가 10대에서 11대가 되면 약 91%가 움직입니다.

import hashlib

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

keys = [h(f"user:{i}") for i in range(100_000)]
for n in (4, 10):
    moved = sum(k % n != k % (n + 1) for k in keys)
    print(n, "->", n + 1, f"{moved / len(keys):.0%}")
# 4 -> 5 80%
# 10 -> 11 91%

캐시라면 이것은 곧 캐시 적중률이 순간적으로 거의 0이 되고 모든 요청이 원본 데이터베이스로 몰린다는 뜻입니다. 저장소라면 전체 데이터를 다시 옮겨야 합니다. 서버 한 대가 고장 나 빠질 때도 똑같은 일이 벌어집니다.

이상적인 목표

서버가 N대에서 N+1대가 될 때 새 서버가 공평한 몫을 가지려면 전체 키의 1/(N+1)은 반드시 새 서버로 가야 합니다. 일관된 해시의 목표는 바로 이만큼만, 그리고 새 서버로만 옮기는 것입니다. 기존 서버끼리 키를 주고받는 일은 없어야 합니다. 서버가 빠질 때도 그 서버가 갖고 있던 키만 나머지 서버로 흩어지면 됩니다.

해시 링

일관된 해시의 가장 널리 알려진 형태는 해시 링입니다. 해시 값의 범위(예: 0부터 2^64 - 1까지)를 원처럼 끝과 처음이 이어진 고리로 봅니다.

• 서버마다 이름을 해시해 링 위의 한 점(토큰, 위치)에 놓습니다.
• 키도 같은 해시 함수로 링 위의 한 점에 놓습니다.
• 키에서 시계 방향으로 가다가 처음 만나는 서버가 그 키의 주인입니다.
• 가장 큰 위치를 지나면 0으로 돌아가 다시 찾습니다(감싸기, wrap-around).

이렇게 하면 서버 하나가 추가될 때 새 서버의 위치와 그 앞(반시계 방향) 서버 사이 구간의 키만 새 서버로 넘어옵니다. 링의 나머지 부분은 전혀 영향을 받지 않습니다.

0 ---- A(10) ---- B(45) ---- C(80) ---- 99, 다시 0으로
키 7  -> 시계 방향 첫 노드 A
키 33 -> B
키 52 -> C
키 91 -> 끝을 지나 처음으로 감싸서 A

가상 노드

서버마다 점을 하나만 두면 점 사이 간격이 우연에 크게 좌우됩니다. 서버 10대에 점 하나씩이면 어떤 서버는 평균의 두세 배를 맡고 어떤 서버는 거의 놀게 됩니다. 그래서 서버 하나를 A#0, A#1, ... 처럼 여러 이름으로 해시해 링 위에 여러 점을 둡니다. 이 점들을 가상 노드(virtual node, vnode)라고 부릅니다. 점이 많을수록 각 서버가 맡는 구간의 합이 평균에 가까워지고, 서버가 빠질 때 그 부하가 한 이웃이 아니라 여러 서버로 고르게 흩어집니다. 성능이 좋은 서버에 가상 노드를 더 많이 주면 가중치도 표현할 수 있습니다.

node = "cache-a"
names = [f"{node}#{i}" for i in range(4)]
print(names)  # ['cache-a#0', 'cache-a#1', 'cache-a#2', 'cache-a#3']
# each name is hashed separately: 4 points on the ring for one server

다른 방식들

링만 있는 것은 아닙니다.

• 랑데부 해시(rendezvous hashing, HRW): 키마다 모든 서버에 대해 hash(서버, 키) 점수를 매기고 가장 높은 서버를 고릅니다. 링이 필요 없고 구현이 매우 짧지만 조회마다 서버 수만큼 계산합니다.
• 점프 일관된 해시(jump consistent hash): 2014년 Google의 Lamping과 Veach가 발표한 방법으로, 메모리 없이 키를 0부터 N-1 사이 버킷 번호로 보냅니다. 버킷은 끝에서만 늘리거나 줄일 수 있습니다.
• 고정 슬롯 방식: Redis Cluster는 링을 쓰지 않고 16,384개의 해시 슬롯(CRC16(key) mod 16384)을 두고 슬롯을 노드에 명시적으로 배정합니다. 일관된 해시와 목표는 비슷하지만 다른 설계입니다.

좋은 분산 방법의 조건

Karger 등의 논문은 좋은 분산 방법이 갖춰야 할 성질을 다음과 같이 정리합니다.

• 균형(balance): 키가 노드에 고르게 나뉩니다.
• 단조성(monotonicity): 노드가 추가될 때 키는 기존 노드에서 새 노드로만 옮겨 가고, 기존 노드끼리는 주고받지 않습니다.
• 퍼짐(spread)과 부하(load): 클라이언트마다 알고 있는 노드 목록이 조금씩 달라도 한 키가 너무 많은 노드에 흩어지지 않고, 한 노드에 너무 많은 키가 몰리지 않습니다.

용어 정리

언제 쓰나

노드 수가 운영 중에 바뀌고, 키를 옮기는 비용(캐시 미스, 데이터 복사)이 큰 곳에서 씁니다. 분산 캐시 클라이언트, Dynamo 계열 키-값 저장소, 세션을 같은 서버로 보내야 하는 로드 밸런서가 대표적입니다. 반대로 노드 수가 고정이거나 키를 옮기는 비용이 거의 없다면 단순한 % N으로도 충분합니다.

정리

• hash % N은 노드 수가 바뀌면 약 N/(N+1)의 키를 옮깁니다.
• 일관된 해시는 꼭 필요한 약 1/(N+1)만 옮기는 것을 목표로 합니다.
• 해시 링에서는 키에서 시계 방향으로 처음 만나는 노드가 주인입니다.
• 가상 노드는 부하 편차를 줄이고 가중치를 표현합니다.
• 랑데부 해시, 점프 해시, 고정 슬롯 방식도 같은 문제를 다르게 풉니다.