노드를 하나 늘렸을 뿐인데 캐시가 거의 다 miss나는 이유 — 일관된 해싱과 가상 노드
1. 노드 하나 추가했을 뿐인데 히트율이 바닥을 쳤다
샤딩 키를 hash(key) % N으로 나누던 캐시 클러스터에 서버를 한 대 늘렸더니 히트율이 순식간에 바닥을 친 적이 있다. "노드 하나 추가했을 뿐인데 왜 거의 전부 재배치되나"가 이해가 안 됐다. 막연히 "일관된 해싱(consistent hashing)은 키를 균등하게 분배한다"고 알고는 있었지만, 정작 가상 노드가 왜 필요한지는 설명하지 못했다.
이 글은 그 두 질문에 답한다. (1) 노드가 하나 바뀔 때 왜 modulo는 거의 전부를, 일관된 해싱은 전체의 약 1/N만 옮기는가. (2) 그런데 왜 일관된 해싱만으로는 부족하고 가상 노드가 필요한가.
2. modulo 해싱이 무너지는 지점
slot = hash(key) % N은 N이 고정일 때만 안정적이다. N이 N+1로 바뀌면 나머지 연산의 주기가 통째로 어긋나 거의 모든 키의 slot이 변한다. x % 4와 x % 5가 같은 값을 주는 x는 드물다는 걸 떠올리면 직관적이다. 캐시라면 대량 miss, 샤드라면 대량 데이터 이동이 된다.
핵심 원인은 키의 목적지가 N에 직접 의존한다는 것이다. 일관된 해싱은 바로 이 의존을 끊는다.
3. 해시 링 — 목적지를 상대 위치로 정한다
일관된 해싱은 해시 함수의 출력 공간(예: [0, 2^32))을 끝과 시작이 이어진 원으로 본다.
- 각 노드를
hash(node_id)로 원 위 한 점에 놓는다. - 각 키도
hash(key)로 원 위 한 점에 놓는다. - 키의 소유자 = 키 위치에서 시계방향으로 처음 만나는 노드(successor).
0 / 2^32
│
keyX → ● ● Node A (hash=40)
┌──┘ │ keyX(hash=10) → 시계방향 첫 노드 = A
Node C ● │
(280) │ ● keyY(hash=120)
└──● Node B (150) → keyY의 소유자 = B노드 A를 제거하면 A가 갖던 키들은 시계방향 다음 노드(B)로만 넘어간다. B~C, C~A 구간의 키는 전혀 건드리지 않는다. 노드 추가도 대칭이다 — 새 노드는 자기 앞 구간의 키만 이전 successor에게서 넘겨받는다.
왜 이동량이 K/N인가
노드 N개가 원을 대략 균등하게 N개 호(arc)로 나눈다고 보면, 각 노드는 평균적으로 전체 키 K개 중 K/N개를 담당한다. 노드 하나를 추가/제거하면 영향받는 호는 그에 인접한 하나뿐이므로, 이동하는 키의 기댓값도 K/N이다.
Karger et al.(STOC 1997) §4는 이 성질을 네 속성으로 정리한다. 그중 monotonicity(단조성) — 버킷이 추가돼도 이미 배치된 항목은 새 버킷으로만 이동하고 기존 버킷들 사이에서 재배치되지 않는다 — 가 K/N 이동의 근거다. modulo 해싱은 바로 이 monotonicity를 만족하지 못한다. N이 바뀌면 항목이 기존 버킷들 사이에서 마구 재배치되기 때문이다.
| 속성 | 의미 |
|---|---|
| Balance | 항목이 버킷들에 고르게 분산 (가상 노드가 담당) |
| Monotonicity | 버킷 추가 시 항목은 새 버킷으로만 이동 |
| Spread | 뷰가 달라도 한 항목이 소수 버킷에만 사상 |
| Load | 한 버킷이 떠안는 항목 수의 상한 |
4. 조회는 정렬된 맵의 ceiling 두 줄이다
원은 개념이고, 구현은 노드 해시값의 정렬된 컬렉션이다. 키 조회는 "키 해시보다 크거나 같은 첫 노드 해시"를 찾는 연산 — 정렬 배열의 이진 탐색 또는 균형 트리의 ceiling이다. 없으면(키가 최대 노드 해시보다 큼) 원이므로 맨 앞 노드로 wrap한다. 조회는 O(log V)(V = 링 위 점 개수)다.
// 링: TreeMap<hash, node>. successor는 ceilingEntry로 조회
NavigableMap<Long, String> ring = new TreeMap<>();
String lookup(String key) {
long h = hash(key);
Map.Entry<Long, String> e = ring.ceilingEntry(h); // >= h 인 첫 점
if (e == null) e = ring.firstEntry(); // wrap-around
return e.getValue();
}이 두 줄이 배정 로직의 전부다. K/N 이동성도, 뒤에 나올 균등성도 이 successor 규칙에서 파생된다.
5. 가상 노드 — 균등성은 공짜가 아니다
여기가 내가 잘못 알고 있던 지점이다. 노드를 원에 한 점씩만 놓으면 분포는 오히려 균등하지 않다. 랜덤하게 뿌린 N개 점이 만드는 호의 길이는 편차가 크다(지수분포에 가깝다). 어떤 노드는 큰 호를, 어떤 노드는 작은 호를 갖는다 → 부하 불균형. 게다가 노드가 빠지면 그 부하가 인접한 단 하나의 노드로 전부 쏠린다(핫스팟).
해결책은 물리 노드 하나를 V개의 가상 점(token)으로 링에 뿌리는 것이다 — hash(node_id + "#0"), hash(node_id + "#1"), …. 각 가상 점이 독립적으로 작은 호를 담당하고, 물리 노드의 총 부하는 V개 호의 합이 된다. 표본을 늘리는 것이므로 큰 수의 법칙에 의해 노드당 부하의 상대 편차는 대략 1/√V로 줄어드는 것으로 알려져 있다. Amazon Dynamo 논문(§4.2)은 이 가상 점을 "token"이라 부르며, 큰 서버엔 토큰을 더 많이 주는 식으로 이질적 용량까지 표현한다.
두 번째 이득: 노드가 빠질 때 그 V개 호가 서로 다른 여러 물리 노드의 successor로 흩어져 넘어가므로, 재분배 부하가 한 노드에 몰리지 않고 클러스터 전체에 분산된다. "노드가 빠지면 키가 링 전체에 골고루 재분배된다"는 말도 실은 가상 노드가 있어야 성립한다.
트레이드오프도 있다. V를 키우면 균등성은 올라가지만 링 메타데이터(점 개수 = N·V)와 멤버십 정보량이 커진다. Dynamo는 노드당 수백 토큰 규모를 언급한다.
검증 — 수치로 확인한 K/N vs 거의 전부
TreeMap 링에 V=100으로 노드 3개를 올리고 키 100k개를 배정한 뒤 노드 하나를 추가해 이동한 키 비율을 세어봤다. N=3→4 추가 시 이론상 이동 기대치는 새 노드의 몫 = 1/4 = 25%. 실제로도 가상 노드가 충분하면 24~26%에 수렴했다. 같은 실험을 modulo(%3→%4)로 하면 이동률이 70%대로 치솟는다. 노드별 부하도 V=1이면 20~50%까지 벌어지지만 V=100이면 32~34%(≈1/3)로 좁혀져 1/√V 감소를 눈으로 확인할 수 있었다.
6. 정리
키의 목적지를 N에 대한 나머지가 아니라 링 위 상대 위치(successor)로 정하면, 노드가 하나 바뀔 때 옮겨지는 키는 전체의 약 1/N로 줄어든다. 다만 균등성과 핫스팟 방지는 알고리즘이 공짜로 주지 않고, 가상 노드로 표본을 늘려서 얻는다.
실제 분산 저장소는 여기서 한 발 더 나가, 키를 successor 하나가 아니라 시계방향으로 만나는 서로 다른 물리 노드 N개(Dynamo의 preference list)에 복제한다. 이때도 가상 노드가 없으면 "연속 N개 노드"가 물리적으로 이웃한 서버에 쏠려 장애 도메인이 좁아진다.
더 파고들 만한 주제:
- Consistent Hashing with Bounded Loads(Mirrokni et al., 2016): 균등성을 확률에 맡기지 않고 노드 용량 상한(1+ε)을 두는 변형.
- Rendezvous(HRW) hashing: 링 없이
argmax hash(key, node)로 소유자를 정하는 대안(조회 O(N)).
참고 자료
- Karger et al., "Consistent Hashing and Random Trees" (STOC 1997) §4 — monotonicity/balance/spread/load 4속성 정의
- M. Kleppmann, Designing Data-Intensive Applications Ch.6 "Partitioning"
- G. DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007) §4.2, §6.2
