같은 key·epoch는 어디서 계산해도 같은 담당 범위를 반환합니다.
일관된 해싱 설계
링 그림만으로는 노드 증감이 안전해지지 않습니다. 실제 설계는 이동 중 소유권, 누락 검증, hot partition, 롤백 유예를 어떻게 끝낼지에서 갈립니다.
개념 이해리밸런싱운영 관점진도 저장
30초 핵심 요약
일관된 해싱의 핵심은 해시 함수보다 노드 변경 절차입니다. 범위를 옮긴 뒤 키 수·바이트·checksum을 검증하고 새 epoch로 전환하며, 롤백 유예가 끝난 뒤에만 원본을 정리합니다.
핵심 규칙시계 방향 첫 토큰
분산 보정물리 노드당 다수 vnode
운영 순서stream → verify → cutover
01 · REQUIREMENTS
# 요구사항키 이동을 작게, 소유권은 명확하게
일관된 해싱은 데이터베이스가 아니라 배치 규칙입니다. 라우팅하는 주체와 저장하는 주체가 어떤 링 epoch를 믿는지, 복제본을 어떻게 고르는지까지 계약해야 합니다.
가입·제거 시 전체 키가 아니라 인접 token 범위만 옮깁니다.
다음 토큰을 선택하되 물리 노드와 영역 중복을 피합니다.
토큰 변경, 이동률, 체크섬, epoch 수렴을 관측합니다.
02 · HASH RING
# 아키텍처링, 가상 노드, 추가 노드의 이동 범위
아래 그림은 하나의 해시 함수와 세 물리 노드를 예시로 든 자체 SVG입니다. 하단 패널은 새 노드가 들어왔을 때 새 토큰의 이전 구간만 넘겨받는 모습을 보여 줍니다.
일관된 해싱의 세 가지 시각 SVG DIAGRAM · 예시 토큰 배치
노드 A 범위노드 B 범위노드 C 범위새 노드 D가 받는 범위
범위 이동과 소유권 전환을 어떤 순서로 안전하게 끝낼 것인가?
예시 물리 노드
24대
설계 가정
예시 토큰 수
3,072개
계산 결과
예시 복제 계수
3
설계 가정
가상 노드 링 + stream·verify·cutover·cleanup
새 노드는 담당 범위를 스트리밍받은 뒤 키 수·바이트·체크섬을 검증합니다. 새 epoch는 검증 후에만 게시하고, 원본 사본은 롤백 유예가 끝난 뒤 제거합니다.
선택 이유
- 노드 추가 때 인접 범위만 이동해 전체 재배치를 피합니다.
- 데이터 복사와 트래픽 소유권을 분리해 중간 실패에서 롤백할 수 있습니다.
- epoch 수렴과 범위 검증을 노드 추가의 완료 조건으로 사용할 수 있습니다.
스트리밍 완료 즉시 원본 삭제
타깃 인덱스·체크섬·라우터 epoch가 아직 수렴하지 않았을 수 있어 누락 범위와 되돌릴 수 없는 장애를 만듭니다.
감수한 단점
- 가상 노드와 epoch 메타데이터를 운영해야 합니다.
- 이동 중 이중 쓰기 또는 변경 로그 재생이 필요합니다.
- hot key와 사본 충돌은 별도 데이터 모델·복제 정책이 필요합니다.
03 · ROUTING & REBALANCE
# 흐름조회는 짧게, 이동은 검증하며
조회 경로의 핵심은 불변 링 스냅샷입니다. 리밸런싱은 데이터 정합성과 고객 트래픽을 동시에 보호하는 별도 제어 흐름으로 취급합니다.
클라이언트는 짧은 TTL의 스냅샷을 갖고 token 목록을 이진 탐색합니다.
첫 vnode 뒤를 순회하며 서로 다른 물리 노드·영역을 우선합니다.
새 소유자는 데이터와 체크포인트를 받고 checksum까지 검사합니다.
검증 뒤 새 epoch를 게시하고 유예 뒤 소스 사본을 제거합니다.
중요한 경계 · 해시 링이 알려 주는 것은 “어디에 둘지”입니다. 쓰기 정족수, 버전 충돌, 읽기 수리와 같은 일관성 정책을 대신하지 않습니다.
04 · TRADEOFFS
# 트레이드오프가상 노드의 이득과 비용
가상 노드를 많이 두면 균형은 좋아지지만 제어면·메모리·이동 작업이 늘어납니다. 토큰 수 하나로 결정하지 않고 실제 bytes·QPS 편차와 복구 시간을 함께 보고 선택합니다.
선택
얻는 것
잃는 것
설계 판단
물리 노드 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 한계
답변 구조 보기 6단계
- “노드 수가 바뀌는 상황에서
mod N의 재배치 문제가 있다”로 문제를 정의한다. - 해시 링, 시계 방향 소유, 가상 노드, 복제본 선택을 한 그림으로 설명한다.
- 노드 추가 시 인접 토큰 구간만 이동한다는 성질과, 균일 분포라는 가정을 구분한다.
- 리밸런싱의
stream → verify → cutover → cleanup순서와 롤백 기준을 제시한다. - “hot key는 가상 노드로 해결되지 않는다”, “일관된 해싱은 일관성 모델이 아니다”라는 한계를 말한다.
- 노드 장애, 분단, 이동 중 장애, 잘못된 epoch, 디스크 부족 중 두 가지 이상을 감지·대응·검증까지 답한다. 면접의 추가 질문은 “노드 1대를 급히 제거해야 할 때 어떤 사본을 언제 지우겠는가?”, “불균등 용량 노드에는 토큰을 어떻게 배정하겠는가?”, “스캔이 필요한 테이블에도 같은 방식을 쓰겠는가?”가 적절하다. 이번 선택: 노드 증감은 범위 이동과 epoch 전환을 분리한다. 깨지는 신호: 체크섬 불일치, epoch 분기, 특정 범위 p99가 동시에 증가한다. 다음 검증: 이동 중 소스 장애와 라우터 구버전을 주입해 epoch 18로 롤백 가능한지 확인한다.
노드 D의 120GB 범위를 옮기고 epoch 19로 전환하기
링 설명 뒤 실제 소유권 이전 순서와 롤백을 답합니다.
- 이동 범위와 속도 상한을 먼저 계산합니다.
- 키 수·바이트·체크섬 검증 뒤 epoch를 게시합니다.
- 유예 기간 뒤 원본을 지우고 hot key 한계를 말합니다.
이동 중 장애와 구버전 라우터를 함께 주입합니다.
- 체크포인트에서 스트리밍을 재개합니다.
- 모든 라우터의 epoch 19 수렴을 확인합니다.
- 불일치면 원본을 유지한 채 epoch 18로 롤백합니다.
이 문제와 이어지는 문서분산 Key-Value Store
키 배치 뒤 복제와 충돌 처리를 이어갑니다.
TECHNICAL DOCUMENTS & CONTACT
기술 규격·공식 문서
- 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·운영 절차는 설계 조건이며 환경에 맞게 검증해야 한다.
사실 오류·출처 정정은 문의·정정 페이지로 알려 주세요.