5. 안정 해시 설계

해시 키 재배치(Rehash) 문제
- N개의 캐시 서버가 있을 때 서버에 부하를 균등하게 나누는 보편적 방법은 해시 함수를 사용하는 것
```
serverIndex = hash(key) % N(서버의 개수)
```
- 이 방법은 서버 풀(Server pool)의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때 잘 동작
- 서버가 추가되거나 기존 서버가 삭제되면 문제가 생김 → 대규모 캐시 미스 발생
안정 해시(Consistent Hash)
- 해시 테이블 크기가 조정될 때 평균적으로 오직 K / N개의 키만 재배치하는 해시 기술
  - K는 키의 개수, N은 슬롯의 개수
- 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치
- 해시 공간과 해시 링
  - 해시 함수 f로 SHA-1을 사용하고, 출력 값 범위는 x0, x1 … xn으로 가정
  - SHA-1의 해시 공간의 범위는 0부터 2^160 - 1까지
  - 해시 공간을 원형으로 만들면 해시 링이 만들어 짐
- 해시 서버
  - 해시 함수 f를 사용하면 서버 IP나 이름을 링 위에 대응시킬 수 있음
- 해시 키
  - 캐시할 키 또한 해시 링 위에 배치할 수 있음
- 서버 조회
  - 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버임
    - key0는 서버 0에 저장되고, key1은 서버 1… 등
- 서버 추가
  - 서버를 추가하더라도 키 가운데 일부만 재배치하면 됨
    - 새로운 서버 4가 추가된 뒤에 key0만 재배치 됨
- 서버 제거
  - 서버를 제거하더라도 키 가운데 일부만 재배치 됨
    - 서버 1이 삭제되었을 때, key1만이 서버 2로 재배치 됨
- 기본 구현법의 두 가지 문제
  - 안정 해시 알고리즘의 절차
    1. 서버와 키를 균등 분포(Uniform Distribution) 해시 함수를 사용해 해시 링에 배치
    2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
  - 문제점
    1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능
      - s1이 삭제되어 s2의 파티션이 다른 파티션 대비 약 두 배로 커짐
      - 파티션(Partition) : 인접한 서버 사이의 해시 공간
    2. 키의 균등 분포(Uniform Distribution)를 달성하기 어려움
      - 서버 1과 서버 3는 아무 데이터도 갖지 않지만, 대부분의 키는 서버 2에 보관
- 가상 노드(Virtual Node)
  - 기본 구현법을 해결하기 위한 기법
  - 실제 노드 또는 서버를 가리키는 노드
  - 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음
    - 서버 0과 서버 1은 3개의 가상 노드를 가짐
  - 각 서버는 한 개가 아닌 여러 개의 파티션을 관리해야 함
    - 키위 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버
    - k0가 저장되는 서버는 서버 1
  - 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐 → 표준 편차가 작아져서 데이터가 고르게 분포되기 때문
- 재배치할 키 결정
  - 서버가 추가되거나 제거되면 데이터 일부는 재배치해야 함
    - 서버 4가 추가된 경우, 서버 3부터 서버 4 사이에 있는 키들을 서버 4로 재배치하여야 함
    - 서버 1이 삭제된 경우 서버 1부터 서버 0 사이에 있는 키들이 서버 2로 재배치되어야 함
- 장점
  1. 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화
  2. 데이터가 보다 균등하게 분포되므로 수평적 규모 확장성을 달성하기 쉬움
  3. 핫스팟(Hotspot) 키 문제를 줄임. 특정한 샤드(Shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있음 → 안정 해시는 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄임

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 5장

5. 안정 해시 설계