Consistent Hashing은 왜 서버가 바뀌어도 전체를 흔들지 않을까
Consistent Hashing의 hash ring, clockwise lookup, virtual node, hot key, rebalancing 비용과 Dynamo, Cassandra, Kafka와의 연결을 정리합니다.
분산 시스템에서 자주 마주치는 질문이 있다.
이 key는 어느 서버가 맡아야 할까?
처음에는 간단해 보인다.
server = hash(key) % N
서버가 4대라면 hash(key) % 4를 계산하면 된다. 구현은 쉽고, 해시 함수가 괜찮다면 분산도 나쁘지 않다.
문제는 서버 수가 바뀌는 순간 시작된다.
N = 4에서 N = 5가 되면 같은 key라도 나머지 연산의 결과가 거의 전부 바뀐다. 서버를 한 대 추가했을 뿐인데, 대다수 key의 소유자가 바뀌고, 캐시도 비고, 데이터도 대량으로 이동해야 한다.
Consistent Hashing은 이 문제를 다르게 푼다.
서버 수가 바뀌어도 전체 key를 다시 흔들지 말고, 영향을 받는 구간만 움직이게 하자.
왜 hash(key) % N으로는 부족할까
서버 수가 고정되어 있다면 modulo hashing도 쓸 수 있다. 문제는 클러스터가 고정되어 있지 않다는 점이다. 서버는 추가되고, 빠지고, 교체된다.
N = 4
server = hash(key) % 4
N = 5
server = hash(key) % 5
이렇게 바뀌면 key 대부분의 목적지가 바뀐다. 실제 시스템에서는 이것이 단순 계산 문제가 아니다.
- 캐시라면 cache miss가 한꺼번에 늘어난다.
- 저장소라면 데이터 이동량이 폭증한다.
- Kafka처럼 key와 partition ordering이 연결된 시스템에서는 mapping 변화가 ordering 기대를 흔들 수 있다.
- LSM 기반 저장소라면 이동된 데이터가 compaction과 tail latency를 건드릴 수 있다.
Consistent Hashing은 서버 수 변경을 “전체 재배치”가 아니라 “일부 구간의 ownership 변경”으로 줄인다.
링 위에 서버와 key를 같이 올린다
Consistent Hashing은 해시 함수의 출력 공간을 원처럼 생각한다.
0 ................................ 2^32 - 1
^ |
|__________________________________|
서버도 해시한다.
hash(nodeA)
hash(nodeB)
hash(nodeC)
key도 해시한다.
hash("user:123")
key는 자기 위치에서 시계 방향으로 이동하다가 처음 만나는 node에 배치된다. 이때 node는 key의 owner가 된다.
서버가 추가되면 일부 구간만 움직인다
새 서버 D가 A와 B 사이에 들어왔다고 하자. 그러면 D 바로 이전 구간에 있던 key들만 D로 이동한다. C 주변의 key, A 이전의 key, B 이후의 key는 그대로 남는다.
반대로 서버가 빠지면 그 서버가 담당하던 구간만 다음 node로 넘어간다. 그래서 Consistent Hashing은 “클러스터 membership 변화에 대한 이동 비용”을 줄이는 알고리즘이다.
그래도 균등 분산은 자동으로 보장되지 않는다
링을 만든다고 모든 문제가 끝나지는 않는다. 서버를 한 점씩만 링 위에 올리면 위치가 운 나쁘게 몰릴 수 있다.
A --------------------------- B -- C
이런 배치에서는 A나 B가 담당하는 구간이 지나치게 커질 수 있다. hash function이 균등하더라도 node가 적으면 구간 길이 편차가 커질 수 있고, 결국 특정 서버에 데이터와 요청이 몰린다.
여기서 virtual node가 등장한다.
Virtual Node는 물리 노드를 여러 점으로 쪼갠다
Virtual node, 줄여서 vnode는 물리 서버 하나를 링 위의 여러 위치로 표현하는 방법이다.
Node A -> A1, A2, A3, A4
Node B -> B1, B2, B3, B4
Node C -> C1, C2, C3, C4
vnode의 장점은 세 가지다.
- 구간 편차가 줄어 load balancing이 좋아진다.
- 새 서버가 들어올 때 여러 서버에서 조금씩 데이터를 받아 올 수 있다.
- 성능이 다른 서버에 더 많은 vnode를 줄 수 있다.
하지만 vnode가 많다고 항상 좋은 것은 아니다. token 관리, streaming, repair, 모니터링의 단위가 늘어난다. Cassandra 문서도 vnode가 load distribution에는 도움을 주지만 token 관리 오버헤드를 늘릴 수 있다고 설명한다.
Consistent Hashing은 partitioning만이 아니다
분산 저장소에서는 partitioning과 replication이 함께 간다.
replication factor가 3이라면 key의 primary owner 하나만 고르는 것이 아니라, 링에서 이어지는 다음 node들까지 replica로 선택할 수 있다.
key K owner: Node B
replica candidates: Node B, Node C, Node D
Dynamo 계열 시스템에서는 이런 ownership과 replica list가 quorum, read repair, anti-entropy와 연결된다.
예를 들어 replica 수 N = 3, write quorum W = 2, read quorum R = 2라면:
R + W > N
조건을 만족하므로 읽기와 쓰기 quorum이 적어도 하나의 replica에서 겹친다. 물론 이것만으로 모든 일관성 문제가 사라지는 것은 아니다. 네트워크 partition, stale replica, conflict resolution, hinted handoff, read repair 같은 운영상의 문제가 뒤따른다.
균등한 hash와 균등한 workload는 다르다
Consistent Hashing은 key space를 나누는 데 도움을 준다. 하지만 실제 트래픽은 균등하지 않다.
데이터 크기 != 요청 수 != CPU 비용
작은 key 하나가 전체 트래픽의 큰 비율을 차지할 수 있다. celebrity user, 인기 게시글, 대형 채팅방, 실시간 경기 이벤트 같은 key는 해시가 아무리 균등해도 한 partition을 뜨겁게 만든다.
이것이 hot key 문제다.
해결 방법은 상황에 따라 달라진다.
- key salting:
user123#0,user123#1처럼 나누어 write를 퍼뜨린다. - read aggregation: salting된 key를 다시 모아서 읽는다.
- adaptive replication: hot partition의 replica를 늘린다.
- dynamic partitioning: load 기준으로 shard를 쪼갠다.
- cache isolation: hot key를 별도 캐시나 경로로 분리한다.
이 모든 방법에는 대가가 있다. 특히 key salting은 쓰기는 퍼뜨리지만 읽기에는 aggregation 비용을 남긴다.
Kafka와는 어떻게 연결될까
Kafka producer도 key가 있는 record를 partition에 배치한다. 가장 단순하게 보면 hash(key) % partition_count 계열의 문제다.
Kafka에서 같은 key를 같은 partition으로 보내는 이유는 보통 per-key ordering 때문이다. 한 partition 안에서는 record order가 보존되지만, 여러 partition 사이에는 전체 순서가 없다.
따라서 partition 수를 늘리면 주의해야 한다. key-to-partition mapping이 바뀔 수 있고, 같은 key가 과거와 다른 partition으로 갈 수 있다. Kafka 문서도 partition 수를 바꾸는 일이 key 기반 ordering과 partitioning에 영향을 줄 수 있음을 설명한다.
여기서 tradeoff가 나온다.
| 선택 | 장점 | 대가 |
|---|---|---|
| 같은 key는 같은 partition | per-key ordering을 유지하기 쉽다. | hot key가 생기면 특정 partition이 막힌다. |
| key를 더 잘게 분산 | 병렬성과 처리량을 높일 수 있다. | ordering과 aggregation이 어려워진다. |
| partition 수 증가 | 병렬 처리 여지를 늘린다. | 기존 key mapping, cache, consumer 배치가 흔들릴 수 있다. |
Rebalancing은 계산보다 운영 비용이 크다
Consistent Hashing은 이동해야 할 key 범위를 줄여준다. 하지만 이동이 “공짜”라는 뜻은 아니다.
노드 추가나 제거가 발생하면 실제로는 다음 비용이 생긴다.
- 네트워크 대역폭: 새 owner에게 데이터를 streaming해야 한다.
- 디스크 I/O: 읽고 쓰는 작업이 foreground traffic과 경쟁한다.
- cache miss: ownership이 바뀐 구간은 cache가 따뜻하지 않다.
- LSM compaction: Cassandra, ScyllaDB 같은 LSM 계열에서는 이동된 SSTable과 compaction이 tail latency를 흔들 수 있다.
- 운영 위험: 장애 복구와 scale-out이 동시에 일어나면 rebalance가 더 오래 걸린다.
그래서 좋은 partitioning은 단지 “어디에 둘까”가 아니라 “바뀔 때 얼마나 조용히 움직일 수 있을까”까지 포함한다.
언제 Consistent Hashing을 떠올려야 할까
다음 조건이 보이면 Consistent Hashing을 검토할 만하다.
- 서버 수가 자주 바뀐다.
- key ownership이 안정적이어야 한다.
- cache miss나 data movement 비용이 크다.
- 중앙 coordinator 없이도 ownership을 계산하고 싶다.
- partitioning과 replication을 함께 설계해야 한다.
반대로 단순하고 작은 시스템이라면 그냥 modulo hashing이나 명시적 shard map이 더 낫다. Consistent Hashing은 분산 시스템의 변화 비용을 줄이는 도구이지, 모든 배치 문제를 자동으로 해결하는 마법은 아니다.
한 문장으로 정리하면
Consistent Hashing은 key와 node를 같은 hash space에 배치해서, node 추가와 제거가 일어나도 전체 key를 다시 흔들지 않고 영향받는 구간만 이동시키는 distributed placement algorithm이다.
하지만 현실의 어려움은 그 다음에 온다. vnode로 구간 편차를 줄이고, replication으로 가용성을 만들고, quorum과 repair로 일관성을 다루고, hot key와 rebalancing 비용을 운영에서 견뎌야 한다. 균등한 hash는 시작일 뿐이고, 좋은 분산 시스템은 데이터 크기와 요청량과 이동 비용이 서로 다르다는 사실을 계속 다룬다.
