Chapter 05
안정 해시 설계
서버 추가/제거 시 재배치를 최소화하는 해시 기법. 해시 링, 가상 노드, 데이터 분산 불균형 해결.
컨시스턴트 해싱 = 해시 링 + 가상 노드
분산 시스템에서 서버 수가 변해도 키 위치를 거의 흔들지 않는 매핑 알고리즘이다. 두 부품이 각자 다른 문제를 푼다.
- ① 해시 링 — 서버 1대 추가/제거 시 영향받는 키를 1/N로 줄인다 (모듈로 해싱의 80~99%와 정반대)
- ② 가상 노드 — 한 서버를 링 위 100~200개 점으로 분산해 부하를 균등화한다
아래는 ① 왜 기존 방식이 깨지는지 → ② 해시 링이 무엇을 푸는지 → ③ 가상 노드가 무엇을 푸는지 → ④ 어디 쓰고 어디 못 쓰는지 순서.
0. 준비 — 분산 KV에서 키로 값을 찾는 흐름
본론에 들어가기 전에 한 가지 짚고 가자. 컨시스턴트 해싱이 무엇을 푸는지 이해하려면 "키 하나로 값 하나를 찾는 흐름"이 머리에 깔려 있어야 한다.
단일 서버 KV라면 흐름이 단순하다.
그런데 서버가 여러 대인 분산 KV에선 한 단계가 끼어든다 — "이 키의 값은 어느 서버가 가지고 있나?"를 먼저 찾아야 한다.
②번이 분산 시스템이 추가로 풀어야 할 문제다. 그리고 그 답이 바로 hash(key)로 서버를 찾아내는 것 — 키가 데이터의 이름표라면, hash는 그 이름표를 어느 서랍(서버)에 둘지 알려주는 GPS 같은 역할을 한다.
핵심: 클라이언트와 서버가 같은 hash 함수와 같은 서버 목록을 공유해야 라우팅이 일관된다. 그리고 서버 N이 변하면 이 매핑이 흔들리는데 — 그 흔들림을 얼마나 줄일 수 있느냐가 이 챕터의 본문이다.
1. 왜 모듈로 해싱은 분산에서 깨지나
가장 단순한 키-서버 매핑은 hash(key) % N이다. 한 줄짜리 코드. N이 고정이면 잘 동작하고, N이 변하면 거의 모든 키가 다른 서버로 이동한다. 이 한 가지 결함이 분산 환경에서 이 방식을 못 쓰게 만든다.
① 모듈로 해싱의 한계
hash(key) % N · 키 24개💡 슬라이더를 한 칸만 옮겨도 빨간 테두리(이동된 키) 비율이 보통 70% 이상. 이론적으로는 (N-1)/N ≈ 75~88%가 새 서버로 옮겨가야 한다. 분산 캐시·DB에서 서버 한 대만 추가하면 캐시 히트율이 0에 수렴하는 이유.
이론값: N이 1만 변해도 (N-1)/N의 키가 이동
서버 4대 → 5대로 늘릴 때 평균 80%의 키가 다른 서버로 옮겨간다. N=10 → 11이면 91%, N=100 → 101이면 99%. N이 클수록 추가 비용이 더 커진다.
실무 결과 — 단일 사고가 시스템 전체를 무너뜨린다
- 분산 캐시: 옮겨진 서버엔 캐시가 없다 → 캐시 미스 폭주 → 백엔드 DB로 thundering herd → DB 다운
- 분산 DB 샤딩: 키 80%가 옮겨진다는 건 데이터 80%를 네트워크로 전송한다는 뜻. 1TB라면 800GB 마이그레이션
- 세션 스토리지 — 사용자 세션이 다른 서버로 옮겨지면 그 사용자들은 모두 로그아웃된다.
그래서 분산 시스템에서는 "서버가 변해도 키 위치는 거의 그대로" 라는 요건이 거의 절대적이다. 컨시스턴트 해싱이 바로 그 답이다.
🤔 잠깐 — N이 정말 자주 변하나? 한 번 점검 시간 잡아 꾹 참고 옮기면 안 되나?
정당한 의문이다. 결론부터 말하면 규모와 환경에 따라 다르다. 그리고 빈도보다 "변할 때의 충격"이 더 중요하다.
- 작은 시스템 (Redis 1대, 캐시 4대 고정) — N이 1년에 한두 번 변할까 말까. 이런 곳엔 컨시스턴트 해싱이 과한 복잡도다. 점검 시간 잡고 한 번 참는 게 합리적.
- 장애로 인한 예상 못 한 변화 — 100대 클러스터의 연 하드웨어 실패율이 1~3%만 돼도 1년에 1~3번 장애. 새벽 3시 다운은 "꾹 참기"가 안 된다.
- 클라우드 강제 교체 — AWS EC2 retirement 알림, Spot 인스턴스 종료, K8s 파드 재시작은 시도 때도 없이 N을 흔든다.
- 자동 스케일링·롤링 배포 — 트래픽에 따라 또는 매 배포마다 N이 변하는 환경에선 "한 번 참기"가 매일 일어나야 함.
진짜 핵심: 모듈로의 문제는 "드물어도 한 번 터지면 재앙"이라는 점이다. N=4→5의 80% rehash가 캐시 미스 폭주 → DB 폭주 → 전체 다운으로 이어진다. 컨시스턴트 해싱은 잦은 변화에 대비하는 게 아니라 "드물지만 치명적인 사고를 작은 사고로 만드는 보험"에 가깝다.
| 상황 | 권장 |
|---|---|
| 자체 백엔드, 캐시 4대 고정, 수동 운영 | 모듈로 OK |
| K8s 위 자동 스케일링 캐시 | 컨시스턴트 해싱 |
| Cassandra·Dynamo 같은 분산 DB | 컨시스턴트 해싱 (사실상 강제) |
| Redis 단일 인스턴스 | N 개념 없음 — 둘 다 무관 |
요약: 책에서 "표준"처럼 다루는 건 분산 NoSQL·대규모 캐시의 표준이다. 소규모·안정 환경엔 과잉. 자기 시스템에 맞게 선택하면 된다.
2. 해법 1 — 해시 링이 영향 범위를 1/N로 줄인다
컨시스턴트 해싱의 첫 부품이다. 서버 1대를 추가하거나 제거할 때 평균 1/N개의 키만 이동한다 (모듈로의 약 80%와 정반대).
아이디어: 출력 공간을 링으로 본다
- 해시 함수의 출력(0~2³²-1)을 원형 링으로 둔다.
- 서버도 키도 같은 해시 함수로 링 위 한 점에 매핑한다.
- 각 키는 시계방향으로 가다 처음 만나는 서버에 할당한다.
💬 학습자 질문에서 출발한 보강
"그런데 2³²은 어디서 튀어나온 숫자인가?"
2³²은 32비트 부호 없는 정수의 최대값 +1이다. 약 42억(4,294,967,296). 일반적인 32비트 해시 함수(MurmurHash32, CRC32, MD5의 앞 32비트 등)의 출력 범위가 정확히 이 크기다. 그래서 책·튜토리얼이 흔히 0 ~ 2³²-1 링을 예로 든다.
중요한 점: 2³²이라는 숫자 자체는 본질이 아니다. 본질은 "충분히 큰 원형 공간"이다. 실제 시스템마다 쓰는 크기가 다르다.
| 시스템 | 링 크기 | 해시 함수 |
|---|---|---|
| Memcached (ketama) | 2³² (32-bit) | MD5 앞 32비트 |
| Apache Cassandra | 2⁶⁴ (64-bit) | Murmur3-128 잘라낸 64비트 토큰 |
| Amazon Dynamo (논문) | 2¹²⁸ (128-bit) | MD5 전체 |
| Redis Cluster | 16384 (2¹⁴) | CRC16(key) % 16384 슬롯 |
크기가 클수록 해시 충돌 확률이 낮아지지만, 실무에선 32비트(약 42억) 만 돼도 충돌이 무시할 수준이라 충분히 쓴다. Redis Cluster처럼 의도적으로 작게 두고 슬롯 단위로 관리하는 변형도 있다. 어떤 크기를 쓰든 "원형 공간 위 시계방향 다음 서버"라는 알고리즘은 그대로다.
② 해시 링과 키 할당
서버 4대 · 키 12개 · 시계방향 다음 서버에 할당각 키는 자기 위치에서 시계방향(각도 증가)으로 가다 처음 만나는 서버에 할당됩니다. 링 끝에 도달하면 0도로 랩어라운드.
왜 N에 영향받지 않나
모듈로는 모든 키 계산에 N이 들어가서, N이 변하면 모든 위치가 같이 변한다.
링은 다르다. 키의 링 위 위치는 hash(key)로만 결정되고 서버 수와 무관하다. 서버를 추가하든 제거하든 키 위치는 그대로이고, 변하는 건 "누가 그 키의 시계방향 이웃 서버인가"뿐이다.
노드 추가/제거 — 영향 구간만 흔들린다
서버를 추가하면 새 서버 직전 구간의 키만 새 서버로 옮겨가고 다른 모든 키는 그대로 머문다. 제거할 때는 그 구간이 다음 시계방향 서버로 흡수된다. 평균 이동량은 N대 중 1대 변경 시 키 전체의 1/N이다.
③ 노드 추가/제거 — 영향 범위
기준 4서버 · 현재 4서버 · 키 24개| 알고리즘 | 재배치 키 | 비율 |
|---|---|---|
| 모듈로 해싱 | 0 / 24 | 0% |
| 컨시스턴트 해싱 | 0 / 24 | 0% |
🔴 빨간 테두리 = 이번 변경으로 옮겨진 키. 모듈로는 거의 모든 키가 재배치되지만 컨시스턴트 해싱은 영향 구간의 키만 옮겨진다. 노드 N대 중 1대 추가/제거 시 평균 K/N개의 키만 이동.
3. 해법 2 — 가상 노드가 부하를 균등화한다
해시 링만으로는 끝이 아니다. 첫 부품은 "재배치 최소화"를 풀지만 "부하 균등화"는 풀지 못한다. 가상 노드가 그 두 번째 부품이다.
문제: 작은 표본의 함정
서버 4대를 링에 배치하면 각자 담당하는 구간 길이가 들쭉날쭉해진다. 어떤 서버가 링의 40%를 차지하는 동안 어떤 서버는 10%만 담당하기도 한다. 해시 함수가 균등 분포라 해도 4개 점은 너무 적은 표본이어서 위치가 우연히 한쪽으로 몰리기 때문이다.
결과는 다음과 같이 나타난다.
- 한 서버가 평균 부하의 2~3배를 받아 과부하에 빠진다.
- 다른 서버는 자원이 남아돌지만 활용하지 못해 비효율적이다.
- 큰 구간을 담당하던 서버가 다운되면 그 부담이 한 번에 인접 서버로 몰려 도미노 장애로 이어진다.
해법: 한 서버를 링 위 여러 점으로 흩뿌린다
물리 서버 하나를 링 위에 100~200개의 가상 노드로 분산 배치한다. 서버 A는 1개 점이 아니라 200개 점으로 존재하고, 각 점은 hash("server_A#0"), hash("server_A#1")… 식으로 흩어진다.
키 할당 규칙은 그대로다. 시계방향으로 가서 처음 만나는 가상 노드를 찾고, 그 가상 노드가 속한 물리 서버로 라우팅한다. 한 물리 서버가 링의 여러 작은 조각의 합을 담당하게 되면서 큰 수의 법칙이 작동하기 시작한다.
④ 가상 노드 — 분포가 균일해진다
물리 서버 4대 × 가상 노드 1개 = 링 위 4개💡 가상 노드 수가 1일 땐 4개 서버가 링 위에 띄엄띄엄 — 한 서버가 전체의 절반을 담당할 수도 있음. 100~200으로 늘리면 같은 색 점이 링에 골고루 흩뿌려져 부하가 균일해진다. 다음 컴포넌트에서 수치로 확인.
적정 수: 100~200개
많을수록 균등성은 좋아지지만 메모리와 룩업 비용도 같이 늘어난다. 둘 사이의 균형점이 100~200개다.
⑤ 가상 노드 수 vs 부하 균등성
이상적 비중 = 25% (1/4) · 가상 노드 1개💡 가상 노드 1일 땐 최대/최소 비율이 5~10배까지 벌어질 수 있다 (한 서버가 다른 서버의 5배 부하). 100을 넘으면 1.2~1.5배 수준으로, 200~500이면 거의 1.0에 수렴. 실무에선 보통 100~200개를 출발점으로 잡는다 — 그 이상은 메모리만 늘고 균등성 개선은 미미.
- 1개 — 부하 비율이 2~10배까지 벌어져 실무에선 못 쓴다.
- 100~200개 — 부하 비율이 1.05~1.15배로 수렴해 실무 표준이 된다 (Memcached ketama 160, Cassandra 256).
- 1000개 이상 — 비율은 1.0에 가까워지지만 메모리와 룩업 비용만 더 늘 뿐, 균등성 개선은 미미하다. 일반적으로 과잉이다.
4. 실무에서 어디 쓰고 어디 못 쓰나
누가 쓰나 — 노드가 자주 변하면 거의 강제
| 시스템 | 활용 | 비고 |
|---|---|---|
| Amazon DynamoDB | 파티셔닝 | 2007 Dynamo 논문이 대중화의 시작 |
| Apache Cassandra | 토큰 링 | 가상 노드 256개 기본 |
| Discord | 채널 ID → 메시지 샤드 | 대규모 채팅 라우팅 |
| Memcached (ketama) | 클라이언트 측 키 라우팅 | 2007 Last.fm 도입, 사실상 표준 |
| CDN (Akamai 등) | 요청 → 캐시 노드 | 지역 + 콘텐츠 키 조합 |
| Riak, Couchbase | 데이터 분산 | Dynamo 계보 |
한계 — 컨시스턴트 해싱이 풀지 못하는 4가지
- 핫키 문제 — 키 분포는 균등해져도 한 키 자체에 트래픽이 몰리는 건 그대로다. 인플루언서 게시물 같은 키는 어떤 알고리즘으로 분배해도 그 서버 한 대가 폭주한다. 키 복제나 전용 캐시 계층으로 별도 해결해야 한다.
- 부하의 확률적 균등성 — 가상 노드 200개를 둬도 부하 비율이 정확히 1.0이 되진 않고 보통 1.05~1.15에 머문다. 트레이딩 시스템 처럼 매우 민감한 곳에선 추가 rebalancing이 필요할 수 있다.
- 실제 데이터 이동 비용 — 이동 비율이 1/N로 줄어든 것이지 비용 자체가 사라진 건 아니다. 1TB의 5%만 옮겨도 50GB가 네트워크로 전송된다. 큰 운영에선 점진적 마이그레이션과 throttling이 별도로 필요하다.
- 해시 함수 품질에 의존 — 한쪽으로 치우치는 해시(단순 modulo나 잘못 설계된 함수)를 쓰면 분포가 깨진다. 실무에선 MurmurHash· xxHash처럼 균등성이 좋은 해시를 쓴다.
5. 정리
- 모듈로는 N이 변하면 깨진다 — 80~99%의 키가 재배치되어 캐시 히트율이 0이 된다.
- 해시 링이 영향 범위를 1/N로 줄인다 — 키 위치가 서버 수와 무관해지기 때문이다.
- 가상 노드(100~200개)가 부하를 균등화한다 — 부하 비율이 1.05~1.15로 수렴한다.
- 만병통치약은 아니다 — 핫키, 실제 데이터 이동 비용, 해시 함수 품질은 별도로 다뤄야 한다.
다음 챕터(키-값 저장소)에서 이 두 부품이 분산 KV의 데이터 분할 기초로 어떻게 활용되는지를 다룬다.