Brain471. 컨시스턴트 해싱 (Consistent Hashing)
⚠️ 이 문서는 해시 샤딩(Hash Sharding)을 할 때 서버를 1대만 추가해도 1억 명의 데이터가 전부 이사를 해야 하는 끔찍한 대재앙(Re-sharding)을 막기 위해, **데이터와 서버를 거대한 '원형 링(Ring)' 위에 배치하여 서버 증설 시 딱 필요한 데이터만 이사하게 만드는 천재적인 알고리즘인 '컨시스턴트 해싱'**을 다룹니다.
핵심 인사이트 (3줄 요약)
- 본질: 해시 함수의 결괏값을 0부터 최대치($2^{32}-1$)까지 연결된 하나의 둥근 링(Ring)으로 가정하고, 그 링 위에 데이터와 서버를 함께 배치하는 알고리즘이다.
- 규칙: 데이터는 링 위에 떨어진 자기 위치에서 **'시계 방향으로 돌다가 가장 먼저 만나는 서버'**에 저장된다.
- 가치: 이 규칙 덕분에 서버를 새로 1대 추가하더라도, 전체 데이터의 $1/N$ 정도만 새 서버로 이사를 가면 되고 나머지 $N-1$개의 서버 데이터는 전혀 건드릴 필요가 없어 무중단 스케일 아웃이 가능해진다.
Ⅰ. 개요: 지옥의 모듈러 연산 탈출 (Context & Necessity)
단순한 해시 샤딩(470번 문서)은 ID % 서버 대수(3) 공식을 쓴다.
서버가 3대에서 4대로 늘어나면 공식이 % 4로 바뀐다.
10 % 3 = 1였는데,10 % 4 = 2가 된다.- 모든 데이터의 나머지가 바뀌어버리므로, 기존 서버에 있던 데이터 90%가 캐리어를 싸고 다른 서버로 이사를 가야 한다. (캐시 미스 대폭발, DB 마비)
**컨시스턴트 해싱(일관된 해싱)**은 이 "나누는 수(서버 대수)" 자체를 고정해 버렸다. "서버가 몇 대든 상관없이, 해시 함수는 무조건 엄청나게 큰 고정된 원판(Ring) 안의 주소를 뱉어내게 하자!"
📢 섹션 요약 비유: 컨시스턴트 해싱은 **'회전초밥집의 자리 배정'**과 같습니다. 손님(데이터)이 초밥집 레일에 서 있으면, 시계 방향으로 걷다가 가장 먼저 만나는 의자(서버)에 무조건 앉습니다. 중간에 새 의자(서버)를 하나 더 가져다 놓더라도, 그 새 의자 근처에 있던 몇 명의 손님만 새 의자로 자리를 옮기면 될 뿐 저 멀리 앉아있는 손님들은 일어날 필요가 전혀 없습니다.
Ⅱ. 컨시스턴트 해싱의 작동 원리 ★
머릿속에 둥근 시계(Ring)를 하나 상상해야 한다.
- 서버 배치:
Hash(서버 1의 IP)를 쳐서 나온 주소에 1번 서버를 배치한다. (예: 12시 방향). 같은 방식으로 2번 서버(4시 방향), 3번 서버(8시 방향)를 원판 위에 띄엄띄엄 배치한다. - 데이터 배치: 유저가 가입하면
Hash(유저 ID)를 친다. 그 결과가 2시 방향이라고 치자. - 서버 찾기: 2시 방향에서 시계 방향(오른쪽)으로 걷기 시작한다. 가장 먼저 만나는 서버는? 4시 방향에 있는 2번 서버다! 유저는 여기에 저장된다.
🚨 마법의 순간: 서버를 추가할 때
- 4번 서버를 새로 사 와서 6시 방향에 배치했다.
- 기존의 12시, 4시, 8시 서버는 제자리에 그대로 있다.
- 누가 이사 가는가?: 4시와 6시 사이에 있던 유저들은 원래 8시 방향(3번 서버)으로 가고 있었다. 하지만 이제 시계 방향으로 걷다가 6시 방향(4번 서버)을 먼저 만나게 된다. 이 유저들만 3번 서버에서 4번 서버로 이사(Re-sharding) 가면 끝이다!
- 12시 근처, 2시 근처의 유저들은 4번 서버가 생겼는지조차 모른 채 평화롭게 기존 서버에 머문다.
Ⅲ. 치명적 단점: 가상 노드 (Virtual Node)로 해결
컨시스턴트 해싱도 완벽하진 않다. 운이 나쁘면 서버들이 한곳에 몰려서 배치될 수 있다.
- 1번 서버(12시), 2번 서버(1시), 3번 서버(2시)
- 이렇게 몰려있으면, 2시부터 12시 사이에 있는 거대한 원판의 모든 데이터를 1번 서버가 독박을 쓰게 된다. (데이터 불균형, 핫스팟)
이걸 막기 위해 가상 노드 (Virtual Node / vNode) 꼼수를 쓴다. 실제 서버는 3대지만, 해시 함수를 조작해서 원판 위에는 가짜 서버 3,000대를 아주 촘촘하게 배치해 버리는 것이다. (예: 서버 1-A, 서버 1-B, 서버 1-C...) 이렇게 하면 원판이 피자 조각처럼 아주 예쁘게 균등 분할되며, 트래픽이 3대의 실제 서버로 완벽하게 $1/N$ 분산된다.
┌──────────────────────────────────────────────────────────────┐
│ 컨시스턴트 해싱 (Consistent Hashing) 원판 시각화 │
├──────────────────────────────────────────────────────────────┤
│ │
│ [ 🖥️ Node A (12시) ] │
│ / \ │
│ (데이터 1) / \ (데이터 2) │
│ / \ │
│ / \ │
│ [ 🖥️ Node C (8시) ] [ 🖥️ Node B (4시) ] │
│ \ / │
│ \ / │
│ (데이터 3) \ / (데이터 4) │
│ \ / │
│ [ 🌟 NEW Node D (6시) ] │
│ │
│ ★ 특징: Node D가 새로 들어오면, Node B와 D 사이에 있던 '데이터 4'만 │
│ Node C에서 Node D로 이사 가면 된다. 나머지 데이터는 평온하다! │
└──────────────────────────────────────────────────────────────┘
Ⅳ. 결론
"분산 시스템은 결국 '이사(Migration)' 비용을 줄이는 싸움이다." 컨시스턴트 해싱은 데이터베이스 샤딩(Sharding)뿐만 아니라, Redis 캐시 클러스터링, CDN(Content Delivery Network), 로드 밸런서 등 트래픽을 분산해야 하는 전 세계 모든 인프라 아키텍처의 근간이 되는 전설적인 알고리즘이다. 만약 백엔드 개발 면접에서 "서버를 Scale-out 할 때 기존 캐시 데이터가 다 날아가면 어떡할래요?"라는 질문을 받았다면, 면접관은 당신의 입에서 이 '일관된 해싱'이라는 단어가 나오기만을 기다리고 있는 것이다.
📌 관련 개념 맵
- 해결하려는 문제: Hash Sharding의 Re-sharding 대참사 (470번 문서)
- 적용 사례: Amazon DynamoDB, Apache Cassandra, Redis Cluster
- 해결 기술: Virtual Node (가상 노드 - 핫스팟 문제 해결)
- 보조 기술: Gossip Protocol (서버들끼리 원판 모양이 어떻게 생겼는지 상태를 공유하는 통신 방식)
👶 어린이를 위한 3줄 비유 설명
- 커다란 피자에 토핑(데이터)이 골고루 뿌려져 있어요. 친구 3명이 시계 방향으로 피자를 120도씩 잘라서 먹기로 했죠.
- 갑자기 친구 1명이 더 왔어요! 예전 방식(해시 샤딩)이면 120도로 잘린 피자를 다 믹서기에 갈아서 다시 90도씩 예쁘게 뭉쳐서(대참사) 나눠줘야 해요.
- 컨시스턴트 해싱은 기존 피자 모양은 가만히 놔두고, 친구 1명만 슬쩍 끼어들어서 옆 친구가 먹으려던 피자 조각의 일부만 양보받아 먹는 거랍니다! (혼란 제어)