일관된 해싱 — 노드가 들고날 때 데이터를 통째로 옮기지 않는 법

hash % N의 저주

키를 여러 서버에 나눠 담는 가장 단순한 방법은 서버 = hash(key) % N 입니다. N개 서버에 고르게 퍼지고 조회도 O(1)이죠. 문제는 N이 바뀌는 순간 터집니다. 서버를 4대에서 5대로 늘리면 나누는 수가 바뀌어, 거의 모든 키의 귀속 서버가 재계산됩니다. 분산 캐시라면 캐시 거의 전체가 한순간에 미스가 되어(캐시 스탬피드) 백엔드가 폭주하고, 분산 DB라면 데이터 대부분이 노드 사이를 이사 다닙니다.

스케일 아웃·장애 복구가 일상인 분산 시스템에서 이건 치명적입니다. 일관된 해싱(consistent hashing) 은 “노드 1대가 늘거나 줄 때, 이동하는 키를 전체의 약 1/N로 최소화한다”는 목표로 이 저주를 풉니다.

해시 링 — 키와 노드를 같은 원 위에 놓는다

아이디어는 우아합니다. 키도 노드도 같은 해시 공간(예: 0 ~ 2³²)에 올린 뒤, 그 공간을 원(ring) 으로 잇습니다. 각 키는 자기 위치에서 시계 방향으로 처음 만나는 노드에 귀속됩니다. 노드를 하나 제거하면, 그 노드가 갖던 키들만 다음 노드로 넘어가고 — 나머지 키들은 전혀 움직이지 않습니다.

이게 전부입니다. 조회는 “키 해시 ≥ 노드 해시인 첫 노드”를 찾는 것이라, 노드 위치를 정렬해두면 이진 탐색으로 O(log N) 에 끝납니다.

import bisect, hashlib

class HashRing:
    def __init__(self, nodes, vnodes=150):
        self.ring = {}              # 해시 → 노드
        self.sorted_keys = []
        for n in nodes:
            for v in range(vnodes): # 가상 노드로 균등 분산
                h = self._hash(f"{n}#{v}")
                self.ring[h] = n
                bisect.insort(self.sorted_keys, h)

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get(self, key):
        h = self._hash(key)
        i = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[i]]   # 시계방향 첫 노드

모듈로 vs 일관된 해싱 — 노드가 하나 바뀔 때

차이는 노드가 변할 때 몇 개의 키가 이사하는가입니다. 아래에서 직접 비교해 보세요. 위쪽 hash % N은 N이 4→5로 바뀌자 거의 모든 칸의 색(귀속 노드)이 바뀌고, 아래쪽 일관된 해싱은 일부만 바뀝니다.

평균적으로 일관된 해싱은 노드 변동 시 K/N개의 키(K=전체 키, N=노드 수)만 이동시킵니다. 4→5로 갈 때 약 20%만 움직이고 80%는 그대로 — 캐시 적중률이 보존됩니다.

가상 노드 — 균등 분산과 부드러운 부하 이전

순진하게 노드를 링에 1점씩만 올리면 두 가지 문제가 생깁니다. (1) 노드들이 링에 불균등하게 떨어져 어떤 노드가 훨씬 큰 구간을 떠맡습니다. (2) 노드가 죽으면 그 부하가 다음 한 노드에 통째로 쏠립니다.

해결책은 각 물리 노드를 여러 개의 가상 노드(virtual node) 로 링에 흩뿌리는 것입니다(노드 A를 A#0, A#1, … A#149처럼). 그러면 부하가 고르게 펴지고, 한 노드가 빠질 때 그 부하가 여러 노드로 분산되어 이전됩니다. 가상 노드 수가 많을수록 표준편차는 $\frac{1}{\sqrt{vnodes}}$로 줄어듭니다.

flowchart TD
    P["물리 노드 A"] --> V1["A#0"]
    P --> V2["A#1"]
    P --> V3["A#…"]
    V1 --> R["해시 링 곳곳에 분산 배치"]
    V2 --> R
    V3 --> R
    R --> B["부하 균등 + 장애 시 여러 노드로 분산 이전"]

랑데부(HRW) 해싱 — 링 없이 같은 목표를

같은 문제를 푸는 또 다른 방법이 랑데부 해싱(Rendezvous / HRW, Highest Random Weight) 입니다. 링을 만들지 않고, 키마다 모든 노드와의 hash(key, node) 점수를 계산해 최댓값인 노드를 고릅니다. 노드가 빠지면 그 노드를 1등으로 뽑았던 키들만 차순위로 옮겨가, 일관된 해싱과 같은 최소 이동성을 얻습니다. 구현이 간결하고 가중치 부여가 자연스러워, 노드 수가 적당할 때 즐겨 쓰입니다(조회는 O(N)).

방식	조회 비용	균등성	특징
hash % N	O(1)	좋음	N 변하면 거의 전부 이동 ✗
일관된 해싱 + vnode	O(log N)	vnode로 우수	표준, 부하 이전 부드러움
랑데부(HRW)	O(N)	우수	링 불필요, 가중치 용이

어디에 쓰이나 — DynamoDB부터 CDN까지

일관된 해싱은 분산 시스템의 기본 골격입니다. Amazon DynamoDB·Cassandra가 파티션을 노드에 배치하는 방식, memcached 클라이언트(Ketama) 의 키 분배, CDN/로드밸런서가 같은 사용자를 같은 엣지/오리진에 붙이는 sticky 라우팅이 모두 이 계열입니다. 노드가 수시로 들고나는(오토스케일·장애) 환경에서 데이터 이동을 최소화한다는 한 가지 성질이 이 모든 곳에서 결정적이기 때문입니다.

프로덕션 함정

함정	증상	해법
가상 노드 없음/과소	노드 간 부하 불균등(핫노드)	vnode 100~200개 이상
핫키 편중	인기 키 하나가 한 노드를 폭주	핫키만 별도 복제/분할, 요청 코얼레싱
노드 추가 시 스탬피드	이전 구간 키가 일시에 미스	점진적 데이터 워밍, 백엔드 요청 병합
해시 비균등	특정 구간 쏠림	MD5/Murmur 등 균등 해시
복제 시 같은 노드 중복	복제본이 물리적으로 한 노드에	링에서 서로 다른 물리 노드로 N개 선택

면접/리뷰 단골 질문

• Q. hash % N의 문제와 일관된 해싱의 해결? → N이 바뀌면 거의 전 키 재배치(캐시 전멸). 일관된 해싱은 노드 변동 시 약 1/N만 이동.
• Q. 가상 노드는 왜 필요한가? → 링 상 균등 분산과, 노드 장애 시 부하를 여러 노드로 분산 이전하기 위해. 표준편차를 1/√vnode로 감소.
• Q. 조회 복잡도? → 노드 해시를 정렬해두고 이진 탐색 → O(log(노드·vnode 수)). 랑데부는 O(N).
• Q. 랑데부 해싱과의 차이? → 둘 다 최소 이동. 랑데부는 링 없이 키-노드 점수 최대값 선택, 가중치/구현이 간결하나 조회 O(N).
• Q. 복제는 어떻게? → 시계방향으로 만나는 서로 다른 물리 노드 N개에 사본을 둔다(vnode가 같은 물리 노드면 건너뜀).

정리

• hash % N은 노드 수가 변하면 거의 전부 재배치 — 분산 캐시·DB에서 치명적.
• 일관된 해싱은 키·노드를 같은 해시 링에 올려 “시계방향 첫 노드”에 귀속시켜, 노드 변동 시 약 1/N만 이동.
• 가상 노드로 부하를 균등화하고 장애 시 부하를 여러 노드로 분산 이전한다.
• 랑데부 해싱은 링 없이 같은 최소 이동성을 얻는 대안. DynamoDB·Cassandra·Ketama·CDN의 공통 골격.

같은 해시 함수가 자료구조 안에서는 충돌 회피에, 분산 시스템에서는 데이터 배치에 쓰입니다. 노드들이 데이터뿐 아니라 상태에 대한 합의까지 맞춰야 할 때, 다음 글 합의 알고리즘으로 이어집니다.

</content>