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. 해시 링 (Hash Ring)

4.1 해시 링이란?

• 해시 링은 Consistent Hashing의 핵심 자료구조입니다.
• 일반적인 해시 테이블이 배열 형태의 선형 구조라면, 해시 링은 원형 구조입니다.
• 해시 함수의 출력 범위(예: 0 ~ 2^32-1)를 원형으로 연결한다고 상상해보세요.
  • 가장 큰 값(2^32-1) 다음에 가장 작은 값(0)이 오도록 끝과 끝을 이어붙인 형태입니다.
  • 마치 시계처럼 12시 다음에 다시 1시가 오는 것과 같습니다.

4.2 왜 원형인가?

• 원형 구조의 핵심 장점은 경계가 없다는 것입니다.
• 선형 구조에서는 "끝"이 존재합니다.
• 배열의 마지막 인덱스에 도달하면 더 이상 갈 곳이 없습니다.
• 하지만 원형 구조에서는 계속해서 다음 위치로 이동할 수 있습니다.
• 이 특성 덕분에 어떤 위치에서 시작하든 시계방향으로 돌면서 다음 노드를 찾을 수 있습니다.

4.3 노드와 데이터 배치

• 해시 링에는 두 가지가 배치됩니다
  • 서버(노드) 배치
  • 데이터 배치

4.3.1 서버(노드) 배치

• 각 서버는 자신만의 식별자(IP 주소, 호스트명 등)를 해시하여 링 위의 특정 위치에 배치됩니다.

해시 링 범위: 0 ~ 100
- 서버 A: hash("server-a.example.com") → 25
- 서버 B: hash("server-b.example.com") → 50
- 서버 C: hash("server-c.example.com") → 75

4.3.2 데이터 배치

저장할 데이터의 키도 동일한 해시 함수로 링 위의 위치를 결정합니다.

데이터 X: hash("user:123") → 35
데이터 Y: hash("order:456") → 60

4.4 데이터가 저장될 서버 찾기

• 데이터가 어느 서버에 저장되어야 할지 결정하는 규칙은 단순합니다.
• 데이터의 위치에서 시계방향으로 이동하여 처음 만나는 서버가 해당 데이터를 담당합니다.
• 위 예시에서
  • 데이터 X(35): 시계방향으로 돌면 → 서버 B(50)가 담당
  • 데이터 Y(60): 시계방향으로 돌면 → 서버 C(75)가 담당

4.5 각 서버의 담당 범위

• 결과적으로 각 서버는 자신의 바로 이전 서버(시계 반대 방향)부터 자신까지의 구간에 해당하는 모든 데이터를 담당합니다.

서버 A(25): 76 ~ 25 구간 담당 (서버 C 이후 ~ 서버 A까지, 0을 지나감)
서버 B(50): 26 ~ 50 구간 담당 (서버 A 이후 ~ 서버 B까지)
서버 C(75): 51 ~ 75 구간 담당 (서버 B 이후 ~ 서버 C까지)

5. 가상 노드 (Virtual Node)

5.1 기본 해시 링의 문제점

• 해시 링에 서버를 단순히 하나씩 배치하면 부하 불균형 문제가 발생합니다.
• 해시 함수는 값을 균등하게 분포시키지만, 서버가 몇 개 없으면 운이 나쁘게 한쪽에 몰릴 수 있습니다.
• 예를 들어 3개의 서버가 링의 한쪽에만 모여 있다면, 어떤 서버는 전체 데이터의 60%를 담당하고 다른 서버는 10%만 담당하는 상황이 생길 수 있습니다.
• 또한 서버가 제거되면 그 서버의 모든 데이터가 단 하나의 서버로 몰립니다. 시계방향으로 바로 다음에 있는 서버가 제거된 서버의 전체 부하를 떠안게 되는 것입니다.

5.2 가상 노드란?

• 가상 노드(Virtual Node, VNode)는 하나의 물리적 서버를 링 위의 여러 위치에 배치하는 기법입니다.
• 실제로 서버가 3대 있다면, 각 서버를 링 위에 1개가 아니라 100개, 200개씩 배치합니다.
• 서버 A는 "server-a-1", "server-a-2", ... "server-a-100" 같은 식으로 여러 개의 가상 노드를 만들어 링 전체에 흩뿌립니다.

물리 서버 3대 × 가상 노드 100개 = 링 위에 300개의 포인트

서버 A: hash("A-1"), hash("A-2"), ... hash("A-100") → 100개 위치
서버 B: hash("B-1"), hash("B-2"), ... hash("B-100") → 100개 위치
서버 C: hash("C-1"), hash("C-2"), ... hash("C-100") → 100개 위치

5.3 가상 노드의 효과

• 부하 균등화
  • 가상 노드가 링 전체에 골고루 분포하므로, 각 물리 서버가 담당하는 데이터 양이 비슷해집니다. 가상 노드 수가 많을수록 분포는 더 균등해집니다.
• 서버 제거 시 부하 분산
  • 서버가 제거되면 그 서버의 가상 노드 100개가 모두 사라집니다.
  • 하지만 각 가상 노드의 데이터는 시계방향의 다음 가상 노드가 담당하게 되는데, 이 다음 노드들은 다양한 물리 서버에 속해 있습니다.
  • 결과적으로 제거된 서버의 부하가 남은 모든 서버에 골고루 분산됩니다.
• 서버 용량 차등 적용
  • 고성능 서버에는 가상 노드를 더 많이 배치하고, 저성능 서버에는 적게 배치하여 서버 용량에 비례한 부하 분산이 가능합니다.

5.4 가상 노드 수 결정

• 가상 노드 수는 트레이드오프가 있습니다:
  • 너무 적으면: 부하 불균형 발생
  • 너무 많으면: 메모리 사용량 증가, 노드 조회 시간 증가

6. 동작 원리

6.1 버킷 제거

버킷(노드)이 이용 불가능해지면:

1. 해시 링에서 해당 버킷(가상 노드 포함)이 제거됩니다.
2. 그 버킷이 담당하던 데이터 요청은 시계방향의 다음 버킷으로 전달됩니다.
3. 가상 노드를 사용하면 제거된 버킷의 데이터가 여러 버킷에 분산됩니다.
4. 다른 버킷에 매핑된 데이터는 그대로 유지되며 이동할 필요가 없습니다.

6.2 버킷 추가

버킷을 추가할 때:

1. 새로운 버킷을 해시 링에 배치합니다.
2. 새 버킷은 이전 버킷(시계 반대 방향)과 자신 사이의 리소스를 담당합니다.
3. 이 리소스들은 원래 다음 버킷(시계 방향)이 담당하던 것입니다.
4. 결과적으로 다음 버킷의 담당 범위가 줄어듭니다.

예시 (해시 링 범위: 0 ~ 100):
초기: A(0) → B(30) → D(60)
- D의 담당 범위: 31 ~ 60

C(45) 추가: A(0) → B(30) → C(45) → D(60)
- C의 담당 범위: 31 ~ 45 (B와 C 사이)
- D의 담당 범위: 46 ~ 60 (줄어듦)

이동: 31 ~ 45 데이터가 D → C로 이동

핵심 포인트

새 버킷이 추가되면, 그 버킷의 시계 반대 방향에 있는 리소스들을 가져옵니다. 이 리소스들은 원래 시계 방향의 다음 버킷이 담당하던 것이므로, 결과적으로 다음 버킷의 부담이 줄어듭니다.

7. 요약

7.1 핵심 개념

• 최소 재배치: 노드 변경 시 K/n개의 데이터만 이동
• 해시 링: 해시 공간을 원형으로 연결하여 경계 없는 탐색 가능
• 시계방향 검색: 데이터 위치에서 시계방향으로 처음 만나는 노드가 담당
• 가상 노드: 하나의 물리 노드를 여러 위치에 배치하여 부하 균등화
• 안정성: 노드 변경 시 나머지 노드는 영향받지 않음

7.2 장점

• 노드 추가/제거 시 최소한의 데이터만 이동
• 부분적 장애가 전체 시스템에 미치는 영향 최소화
• 가상 노드를 통한 부하 균등화
• 분산 캐싱 및 DHT 구현에 필수적인 기술

참고

• Wikipedia - Consistent hashing