1. Consistent Hashing이란?
일관된 해싱(Consistent Hashing)은 분산 시스템에서 데이터를 여러 노드에 효율적으로 분배하면서 노드를 추가하거나 삭제할 때 데이터 재배치를 최소화하는 방식입니다.
1.1 핵심 특징
해시 테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑하면 됩니다.
K: 전체 아이템(키) 개수
n: 전체 노드 개수
재매핑 비율: K/n (전체의 1/n만 이동)
노드나 슬롯의 개수가 바뀔 때, 노드를 추가하거나 삭제할 때, 오직 K/n의 아이템만 다시 섞으면 됩니다.
기존 해싱:
- 슬롯(노드)의 개수 변화 시 거의 모든 키가 재매핑 필요
- 키와 슬롯 간 매핑이 모듈러 연산(
hash(key) mod n)으로 정의되기 때문
Consistent Hashing:
- 노드 변경 시 K/n개의 키만 재매핑
- 나머지 데이터는 그대로 유지
2. 사용되는 상황
2.1 분산 캐싱
Consistent Hashing은 분산 캐싱을 위해 개발되었습니다.
- 변화하는 웹 서버 수에 대응: 서버 추가/제거 시에도 안정적으로 요청 분산
- 부분적 장애 완화: 일부 서버 장애가 전체 시스템에 미치는 영향 최소화
- 강력한 캐시 활용: 시스템 전반의 장애 없이 캐시 시스템 운영
2.2 분산 해시 테이블 (DHT)
분산 해시 테이블(Distributed Hash Table) 디자인에 적용할 수 있습니다.
- 키 공간 파티셔닝: 분산된 노드들 사이에서 전체 키 공간을 파티셔닝
- 오버레이 네트워크: 노드들을 연결하여 키를 효과적으로 위치시킬 수 있는 네트워크 제공
3. 필요성
3.1 기존 방식의 문제점
일반적으로 n개의 캐싱 서버를 로드밸런싱하는 방법은 모듈러 해싱을 사용합니다:
서버 선택 = hash(데이터) mod n
문제점:
캐싱 서버가 늘어나거나 줄어들면 n이 바뀌면서 모든 데이터들이 새로운 곳에 해시되어야 합니다.
초기: 3개 서버 (n=3)
- key1 → hash(key1) mod 3 = 1 → 서버 1
서버 추가: 4개 서버 (n=4)
- key1 → hash(key1) mod 4 = 2 → 서버 2 (변경!)
3.2 치명적인 결과
모든 데이터가 새로운 서버로 재배치되면 기존 데이터가 있는 원본 서버가 캐싱 서버로부터의 요청으로 과부하가 걸릴 수 있습니다.
캐시 서버를 추가/제거할 때 거의 모든 캐시가 무효화되면:
- 모든 요청이 원본 서버(DB, 백엔드)로 몰림
- 원본 서버 과부하로 전체 시스템 다운 가능
- 캐시 시스템의 의미 상실
Consistent Hashing은 이러한 서버 과부하를 방지하기 위해 필 요합니다.
3.3 Consistent Hashing의 해결 방법
Consistent Hashing은 데이터를 가능한 한 같은 캐싱 서버에 해싱시킵니다.
- 캐싱 서버 추가 시: 추가되는 서버가 다른 모든 서버들로부터 일부 데이터만 가져옴
- 캐싱 서버 제거 시: 제거되는 서버의 데이터들이 남아있는 서버들 사이에서 재분산됨
4. 핵심 목적과 동작
4.1 핵심 목적
Consistent Hashing의 핵심 목적은 각 캐시를 해시 값 구간과 연관시키는 것입니다.
- 구간의 경계는 각 캐시 identifier의 해시를 계산하면서 결정됩니다.
- 캐시가 제거되면, 그 캐시의 구간은 인접 구간과 함께 다른 캐시에 의해 인수됩니다.
- 남아있는 모든 캐시는 변하지 않습니다.
4.2 버킷 제거 시 동작
버킷(노드)이 이용 불가능해지면:
- Hash Ring에서 버킷의 포인트가 제거됩니다.
- 그 버킷에 매핑된 모든 데이터에 대한 요청은 다음 포인트에 매핑됩니다.
- 사라진 버킷이 소유했던 데이터들은 남아있는 버킷들로 재분산됩니다.
- 다른 버킷에 매핑된 값은 그대로 유지되며 이동할 필요가 없습니다.
각 버킷은 무수한 랜덤하게 분산된 포인트들과 연관됩니다. 이를 VNode(Virtual Node) 또는 **VBucket(Virtual Bucket)**이라고 합니다.
- 각 버킷의 가상 버전들을 해시 링 곳곳에 배치
- 노드 제거 시 부하 불균형을 해결
- 제거된 노드의 데이터가 여러 다른 버킷들에 골고루 분산됨
5. 기술 (동작 원리)
5.1 Hash Ring
Consistent Hashing은 모든 데이터를 Hash Ring의 각 지점에 매핑하는 것에 기반을 둡니다.
시스템은 각각의 이용 가능한 서버를 Hash Ring의 여러 랜덤하게 분산된 포인트에 매핑시킵니다.
┌─────────────────────┐
│ │
│ Hash Ring │
│ (0 ~ 2^32-1) │
│ │
└─────────────────────┘
서버 A → 여러 위치에 VNode로 배치
서버 B → 여러 위치에 VNode로 배치
서버 C → 여러 위치에 VNode로 배치
5.2 데이터 위치 찾기
데이터가 어디에 위치해야 하는지 찾는 과정:
- Hash Ring에서 데이터 키의 위치를 찾습니다.
- 시계방향으로 돌면서 처음 만나는 버킷에 도달할 때까지 이동합니다.
- 각 버킷은 그 버킷의 포인트와 이전 버킷의 포인트 사이에 존재하는 모든 리소스를 포함합니다.
예시:
hash(key1) = 100 → 시계방향 → 첫 번째 버킷: 서버 A
hash(key2) = 250 → 시계방향 → 첫 번째 버킷: 서버 B
5.3 버킷 추가
버킷을 추가할 때:
- 새로운 버킷을 Hash Ring에 배치합니다.
- 이전 버킷과 새 버킷 사이의 모든 리소스가 새로운 버킷에 추가됩니다.
- 이 리소스들은 원래 다음 버킷(시계방향의 다음 버킷)이 담당하던 것입니다.
- 이제 이 리소스들은 더 이상 다음 버킷과 연관되지 않습니다.
예시:
초기: A(0°) → B(120°) → C(240°)
- C의 담당 범위: 120° ~ 240°
D(180°) 추가: A(0°) → B(120°) → D(180°) → C(240°)
- D의 담당 범위: 120° ~ 180° (B와 D 사이)
- C의 담당 범위: 180° ~ 240° (줄어듦)
이동: 120° ~ 180° 데이터가 C → D로 이동
각 버킷과 연관된 키의 비율은 버킷이 매핑된 포인트 개수가 변함에 따라 바뀔 수 있습니다. 이는 가상 노드(VNode)를 통해 조정할 수 있습니다.
6. 요약
6.1 핵심 개념
- 최소 재배치: K/n개의 데이터만 이동
- 해시 링: 데이터와 노드를 원형 공간에 배치
- 시계방향 검색: 가장 먼저 만나는 노드에 데이터 저장
- 가상 노드: 부하 균등화를 위한 다중 매핑
- 안정성: 노드 변경 시 나머지 노드는 영향받지 않음
6.2 장점
- 노드 추가/제거 시 최소한의 데이터만 이동
- 부분적 장애가 전체 시스템에 미치는 영향 최소화
- 가상 노드를 통한 부하 균등화
- 분산 캐싱 및 DHT 구현에 필수적인 기술