일관성 해싱(Consistent Hashing)은 서버(노드)가 늘거나 줄어도 키의 재배치를 최소화하도록 설계된 분산 배치 기법입니다. 키와 노드를 같은 해시 공간의 원(링) 위에 올려두고, 각 키를 시계 방향으로 만나는 첫 번째 노드에 맡깁니다. 노드 하나가 빠져도 그 노드가 담당하던 키만 옆으로 넘어갈 뿐, 전체가 흔들리지 않습니다.
이걸 처음 제대로 이해하게 된 건 캐시 서버를 한 대 늘렸다가 사고를 친 뒤였습니다. 트래픽이 몰려서 memcached 노드를 3대에서 4대로 늘렸을 뿐인데, 캐시 적중률이 순간 20%대로 곤두박질쳤죠. 원인은 단순한 hash(key) % N 방식이었습니다.
왜 나머지 연산(modulo)이 문제인가
가장 흔한 분산 방식은 키 해시를 노드 수로 나눈 나머지를 쓰는 겁니다. 노드가 고정이면 완벽하게 균등하고 빠릅니다. 문제는 N이 바뀌는 순간입니다. N이 3에서 4로 바뀌면 거의 모든 키의 나머지가 달라져, 사실상 캐시 전체가 무효화됩니다.
# 노드 3대일 때
hash("user:42") % 3 = 1 → node1
# 노드 4대로 늘리면
hash("user:42") % 4 = 2 → node2 (자리가 통째로 바뀜)캐시라면 대량 미스가 뒤따르는 캐시 스탬피드로 이어지고, 샤딩된 저장소라면 데이터 대이동이 벌어집니다. 노드 한 대 추가에 전체의 3/4가 이사를 가는 셈이니, 실무에선 감당하기 어렵습니다.
링 위에 올린다는 발상
일관성 해싱은 관점을 바꿉니다. 0부터 2^32-1까지의 해시 값을 원형으로 이어붙인 해시 링을 상상하세요. 노드도 키도 같은 해시 함수로 이 링 위의 한 점에 배치합니다. 키가 담길 노드는 그 키의 위치에서 시계 방향으로 가장 먼저 만나는 노드입니다.
이 구조의 핵심은, 노드 하나가 죽거나 새로 들어와도 영향받는 키가 링에서 그 노드 주변 구간으로 국한된다는 점입니다. 평균적으로 K/N개의 키(K는 전체 키, N은 노드 수)만 재배치됩니다. modulo 방식이 거의 전부를 흔드는 것과 대비됩니다.
| 항목 | hash % N | 일관성 해싱 |
|---|---|---|
| 노드 추가 시 이동량 | 거의 전부 | 약 K/N |
| 분포 균등성 | 매우 좋음 | 가상 노드 필요 |
| 조회 비용 | O(1) | O(log N) |
가상 노드로 쏠림을 없앤다
순진하게 노드 하나당 링 위에 점 하나만 찍으면 분포가 들쭉날쭉해집니다. 운 나쁘게 두 노드가 링에서 가까이 붙으면, 그 사이 좁은 구간을 맡는 노드는 놀고 넓은 구간을 맡는 노드는 과부하가 걸리죠. 그래서 실무에선 가상 노드(virtual node)를 씁니다. 물리 노드 하나를 node1#0, node1#1… 처럼 수백 개의 가상 점으로 링에 흩뿌리는 겁니다.
import hashlib, bisect
class HashRing:
def __init__(self, nodes, vnodes=150):
self.ring = {} # 해시값 -> 노드
self.keys = [] # 정렬된 해시값
for n in nodes:
for i in range(vnodes):
h = self._hash(f"{n}#{i}")
self.ring[h] = n
bisect.insort(self.keys, h)
def _hash(self, s):
return int(hashlib.md5(s.encode()).hexdigest(), 16)
def get(self, key):
h = self._hash(key)
idx = bisect.bisect(self.keys, h) % len(self.keys)
return self.ring[self.keys[idx]]가상 노드 수를 150~200개쯤 주면 물리 노드 간 부하 편차가 통계적으로 크게 줄어듭니다. Redis Cluster, Cassandra, DynamoDB, 그리고 상당수의 로드밸런서가 이 아이디어의 변형을 씁니다. 참고로 구글이 2014년에 낸 점프 일관성 해싱(Jump Consistent Hash)은 메모리 없이 짧은 함수만으로 같은 성질을 내는 변형인데, 노드에 임의 이름을 붙이거나 중간 노드를 빼는 시나리오엔 안 맞아서 케이스를 봐야 합니다.
실전에서 데는 지점
- 가상 노드를 너무 적게 잡으면 균등성이 무너집니다. 반대로 수천 개씩 잡으면 메모리와 조회 비용이 커집니다. 150 근처에서 시작해 측정하세요.
- 해시 함수의 분포가 나쁘면 링 자체가 쏠립니다. MD5/무르무르해시(MurmurHash)처럼 분포 좋은 함수를 쓰되, 보안 목적이 아니면 굳이 SHA-256까지 갈 필요는 없습니다.
- 가중치(weight)가 다른 노드가 섞이면, 스펙 좋은 노드에 가상 노드를 더 많이 배정해 용량에 비례시키는 게 좋습니다.
자주 묻는 질문
일관성 해싱은 캐시에만 쓰나요?
아니요. 분산 캐시가 대표 사례지만, 샤딩된 데이터베이스의 파티션 배치, 로드밸런서의 세션 고정(sticky session), P2P 시스템의 키 라우팅 등 "키를 노드에 안정적으로 매핑"하는 모든 곳에 쓰입니다.
가상 노드는 몇 개가 적당한가요?
물리 노드당 100~200개가 흔한 시작점입니다. 노드 수가 적을수록(예: 3~5대) 편차가 크게 나타나니 가상 노드를 넉넉히 주는 편이 안전합니다. 실제 부하 분포를 측정해 조정하세요.
노드가 죽으면 그 데이터는 사라지나요?
일관성 해싱 자체는 배치 규칙일 뿐 복제를 보장하지 않습니다. 그래서 보통 링에서 다음 N개 노드에 복제본을 두는 방식과 함께 씁니다. Cassandra의 복제 계수(replication factor)가 이 조합의 예입니다.
Jump Consistent Hash가 항상 더 낫나요?
메모리를 거의 안 쓰고 분포도 좋지만, 노드가 순차적 정수 인덱스라는 전제가 있습니다. 노드에 임의 문자열 이름을 붙이거나, 중간 노드만 콕 집어 제거하는 유연함이 필요하면 전통적인 링 방식이 더 편합니다.
댓글 0