같은 key·epoch는 어디서 계산해도 같은 담당 범위를 반환합니다.
일관된 해싱 설계
노드가 늘고 줄어도 데이터 이동을 인접 범위로 제한하는 파티셔닝 패턴입니다. 해시 링은 출발점일 뿐이며, 실제 설계의 품질은 가상 노드, 복제 배치, 리밸런싱 검증, hot partition 대응에서 갈립니다.
개념 이해리밸런싱운영 관점진도 저장
30초 핵심 요약
키와 노드를 같은 해시 공간의 원 위에 놓고, 키에서 시계 방향으로 처음 만나는 노드를 담당자로 선택합니다. 노드 하나가 바뀌면 원 전체가 아니라 그 노드 주변의 범위만 재배치됩니다. 가상 노드는 범위 편차를 줄이지만, 특정 키 한 개에 몰린 트래픽은 분산하지 못합니다.
핵심 규칙시계 방향 첫 토큰
분산 보정물리 노드당 다수 vnode
운영 순서stream → verify → cutover
01 · REQUIREMENTS
# 요구사항키 이동을 작게, 소유권은 명확하게
일관된 해싱은 데이터베이스가 아니라 배치 규칙입니다. 라우팅하는 주체와 저장하는 주체가 어떤 링 epoch를 믿는지, 복제본을 어떻게 고르는지까지 계약해야 합니다.
가입·제거 시 전체 키가 아니라 인접 token 범위만 옮깁니다.
다음 토큰을 선택하되 물리 노드와 영역 중복을 피합니다.
토큰 변경, 이동률, 체크섬, epoch 수렴을 관측합니다.
02 · HASH RING
# 아키텍처링, 가상 노드, 추가 노드의 이동 범위
아래 그림은 하나의 해시 함수와 세 물리 노드를 예시로 든 자체 SVG입니다. 하단 패널은 새 노드가 들어왔을 때 새 토큰의 이전 구간만 넘겨받는 모습을 보여 줍니다.
일관된 해싱의 세 가지 시각 SVG DIAGRAM · 예시 토큰 배치
노드 A 범위노드 B 범위노드 C 범위새 노드 D가 받는 범위
03 · ROUTING & REBALANCE
# 흐름조회는 짧게, 이동은 검증하며
조회 경로의 핵심은 불변 링 스냅샷입니다. 리밸런싱은 데이터 정합성과 고객 트래픽을 동시에 보호하는 별도 제어 흐름으로 취급합니다.
클라이언트는 짧은 TTL의 스냅샷을 갖고 token 목록을 이진 탐색합니다.
첫 vnode 뒤를 순회하며 서로 다른 물리 노드·영역을 우선합니다.
새 소유자는 데이터와 체크포인트를 받고 checksum까지 검사합니다.
검증 뒤 새 epoch를 게시하고 유예 뒤 소스 사본을 제거합니다.
중요한 경계 · 해시 링이 알려 주는 것은 “어디에 둘지”입니다. 쓰기 정족수, 버전 충돌, 읽기 수리와 같은 일관성 정책을 대신하지 않습니다.
04 · TRADEOFFS
# 트레이드오프가상 노드의 이득과 비용
실제 토큰 수는 노드의 수명, 용량 차이, 제어면 전달 비용과 함께 선택해야 합니다. 여기의 숫자는 설계 가정이지 권장 기본값이 아닙니다.
선택
얻는 것
잃는 것
설계 판단
물리 노드 1개 = 토큰 1개
구현과 디버깅 단순
구간 크기 편차가 커질 수 있음
소규모·고정 멤버
다수의 가상 노드
기대 부하와 이동량의 편차 완화
메타데이터·이동 작업·관측 카디널리티 증가
일반 분산 저장
capacity weight
서로 다른 디스크·CPU 활용
복제 분산과 재배치 계산이 복잡
이기종 노드
키 salting
일부 hot key를 여러 버킷으로 분산
합치기·범위 조회·삭제 계약이 달라짐
도메인 동의 필요
05 · FAILURE MODES
# 장애장애를 상태 전이와 검증까지 설계한다
운영자는 “누가 실패했는가”뿐 아니라 “어느 epoch의 어느 범위가 어느 단계에서 멈췄는가”를 알아야 합니다.
노드 프로세스 중단
주 담당 vnode가 응답하지 않아도 복제본이 요청을 받을 수 있습니다.
대응 · heartbeat와 ACK 감소로 감지하고, 복제본 우회 후 복귀 노드에 누락 범위를 동기화합니다.
네트워크 분단
두 영역이 서로 다른 멤버십을 보고 소유권을 바꾸려 할 수 있습니다.
대응 · 제어면 quorum 없이 epoch를 확정하지 않고, 해소 뒤 버전·범위 해시를 비교합니다.
리밸런싱 중 소스 장애
새 노드가 일부 세그먼트만 받았는데 원본을 지우면 데이터가 사라집니다.
대응 · checkpoint에서 다른 복제본으로 재개하며, checksum 검증 전 cleanup을 금지합니다.
hot partition
특정 키·테넌트가 한 vnode의 CPU, 큐, p99를 독점합니다.
대응 · 토큰별 QPS를 보고 캐시·키 분할·요청 병합을 선택합니다. vnode 증설만으로는 부족합니다.
잘못된 링 배포
오래된 클라이언트가 이전 epoch의 노드로 요청을 보냅니다.
대응 · 원자 스냅샷, epoch 불일치 응답, 서명 검증과 한정 재시도를 사용합니다.
대상 디스크 부족
새 범위를 받는 노드에서 compaction과 스트리밍이 함께 막힙니다.
대응 · 범위별 바이트와 free space로 admission control을 걸고 이동 속도를 낮춥니다.
06 · OPERATIONS
# 운영보안·관측·비용을 한 화면에서
해시 값은 민감한 원문 키를 감추는 만능 수단이 아니며, 이동은 저장·네트워크·운영 비용을 동시에 만든다는 전제로 운영합니다.
제어면은 mTLS, 역할 권한, epoch 감사 로그로 보호합니다. 이동 스트림과 임시 파일도 암호화·삭제·보존 정책에 포함합니다.
토큰별 QPS·바이트·p99, epoch 수렴, 이동 checkpoint, 복제 영역 중복, free space를 함께 관측합니다.
복제 계수, 이중 보관 기간, 영역 간 스트리밍, compaction이 비용입니다. 이동량은 키 수와 바이트 모두로 예산화합니다.
면접 모드 · 추가 질문05:00
“24대 링에 노드를 1대 추가할 때 왜 모든 키를 다시 배치하지 않아도 되는지 설명하고, 가상 노드가 해결하는 문제와 해결하지 못하는 hot key 문제를 구분해 보세요. 이동 중 소스 노드가 죽으면 어떤 검증을 거쳐 cutover 하겠습니까?”
문제 → 링 규칙vnode → 부하 편차stream → verifyhot key 한계
NEXT CASE STUDY분산 Key-Value Store 설계
EDITORIAL NOTES
작성·검토·참고 자료
참고 자료
- **1차 논문**: Karger et al., *Consistent Hashing and Random Trees* (STOC 1997), ACM Digital Library. 일관된 해싱의 원래 문제와 성질을 다룬다.
- **1차 논문**: DeCandia et al., *Dynamo: Amazon's Highly Available Key-value Store* (SOSP 2007), ACM Digital Library. 가상 노드, 파티셔닝, 복제 운용 맥락을 확인한다.
- **공식 문서**: Apache Cassandra, Consistent hashing using virtual nodes. Cassandra의 vnodes 설명과 제품별 세부 사항을 확인한다.
- **공식 문서**: Apache Cassandra, Operations: adding a node. 노드 추가 작업은 제품과 버전에 따라 달라질 수 있으므로 실제 운영에서는 해당 버전 문서를 따른다. 참고 자료의 알고리즘 설명은 **사실**, 본문에 명시한 노드 수·가상 노드 수·SLO·운영 절차는 **설계 가정 또는 편집 의견**으로 분리했다.
사실 오류·출처 정정은 문의·정정 페이지로 알려 주세요.