#05. 안정 해시 설계

5장. 안정 해시 설계

• 수평적 규모 확장성을 달성하기 위해 데이터를 서버에 균등하게 나누려면?
  • 보편적으로 안정 해시를 사용

1. 해시 키 재배치 문제

• 해시 기술이 풀려고 하는 문제
• N개의 캐시 서버를 균등하게 나누는 보편적인 방법
  • serverIndex = hash(key) % N
  • server pool의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때 효과적
• But, 서버에 장애가 발생하면?
  • %3 으로 키 분포가 변하게 됨
  • 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속
  • 대규모 cache miss 발생
    → 안정 해시: 위 문제를 효과적으로 해결하는 기술

2. 안정 해시

안정 해시

• 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술
• k = 키의 개수 / n = slot의 개수
• 이와 달리, 대부분의 전통적 해시 테이블: slot의 수가 바뀌면 거의 대부분 키를 재배치

해시 공간과 해시 링

• x0 = 0 ~ xn = 2^160 - 1
• 해시 공간의 양쪽을 구부려 접으면 hash ring: x0 과 xn 이 접점
• 해시 서버
  • 해시 함수 f를 사용하면 서버 IP나 이름을 링 위의 어떤 위치에 대응시킬 수 있음
  • f(서버0) = ?
• 해시 키
  • modular 연산 사용 X
  • 캐시할 키 key0, key1, key3 또한 링 위의 지점에 배치 가능

서버 연산

• 서버 조회
  • 어떤 키가 저장되는 서버: 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버
• 서버 추가
  • 서버를 추가하더라도 키 가운데 일부만 재배치
  • 시계방향으로 추가된 서버와 가깝지 않은 키들은 재배치 X
• 서버 제거
  • 하나의 서버가 제거되면 키 가운데 일부만 재배치
  • 나머지 키에는 영향 X

기본 구현법의 두 가지 문제

• 기본 절차
  • 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치
  • 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
• 문제점
  • 서버가 추가, 삭제되는 상황을 감안하면 partition(인접한 서버 사이의 해시 공간)의 크기가 균등하게 유지 X
    → 어떤 서버는 굉장히 작은, 혹은 굉장히 큰 공간을 할당 받는 상황 초래
  • 키의 균등 분포를 달성하기 어렵다
    → 해결법: virtual node(replica, 복제 라고도 불림)

가상 노드

• 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음
• 각 서버는 하나가 아닌 여러 개 partition을 관리
• 가상 노드의 개수 ⬆️
  → 표준 편차 ⬇️
  → 키의 분포 점점 균등
• but, 가상 노드 데이터를 저장할 공간은 더 많이 필요 (tradeoff)

재배치할 키 결정

• 반시계 방향에 있는 첫번째 서버 전까지.

3. 마치며

• 안정 해시의 이점
  • 서버가 추가, 삭제될 때 재배치되는 키의 수 최소화
  • 데이터가 보다 균등하게 분포 → 수평적 규모 확장성 달성
  • hotspot 키 문제 ⬇️
• 안정 해시 예시
  • 아마존 DynamoDB의 파티셔닝 관련 컴포넌트
  • Apache Cassandra 클러스터에서의 데이터 파티셔닝
  • Discord 채팅 어플리케이션
  • Akamai CDN
  • Meglev 네트워크 부하 분산기