[CH5] 안정 해시 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (알렉스 쉬 저)를 읽고 정리합니다.

📢 안정 해시 : 수평적 규모 확장성을 위해 요청 또는 데이터를 서버에 균등하게 나누는 기술

안정 해시

0️⃣ 해시 키 재배치 (rehash)

• N개의 캐시 서버에 부하를 균등하게 나누는 해시 함수

  serverIndex = hash(key) % N

  • 특정 키가 보관된 서버를 찾기 위한 나머지 연산을 수행
  • 추천 환경
    • 서버 풀 (server pool) 크기 고정된 환경
    • 데이터 분포가 균등한 환경
  • 비추천 환경
    • 서버가 추가되거나, 기존 서버가 삭제될 가능성이 있는 환경
    • 즉, 키 분포가 변화 될 가능성이 있을 경우 대규모 캐시 미스 (cache miss) 발생 가능성 존재
• 위 문제를 해결하기 위해 안정 해시 사용
  • 전통적 해시 테이블은 보통 슬롯 수가 바뀌면 전체 키를 재배치한다

1️⃣ 안정 해시 (consistent hash)

• 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술
  • k = 키의 개수
  • n = 슬롯 개수
• 동작 원리
  • 기본 용어
    • 해시 공간 : 해시 함수의 출력 값 범위 공간
    • 해시 링 : 해시 공간의 양쪽을 구부려 접은 것
    • 해시 서버 : 해시 함수 f를 사용해 서버 IP 또는 이름을 해시 링 위에 배치
    • 해시 키 : 해시 함수를 이용, 캐시할 키를 해시 링 위에 배치
  • 서버와 키 배치 : 균등 분포 해시 함수를 이용해, 해시 링에 서버와 키 배치
  • 서버 조회 : 해당 키의 위치로부터 시계 방향으로 링을 탐색하는 중 만나는 첫 번째 서버에 키가 저장된다.
  • 서버가 추가/제거될 경우, 키 가운데 일부를 재배치한다.
• 문제
  • 서버 추가/제거 상황에서 파티션 크기를 균등하게 유지할 수 없다.
    • 파티션 : 인접한 서버 사이의 해시 공간
  • 키의 균등 분포 (uniform distribution)을 달성하기 어렵다.
  • 위 문제를 해결하기 위해 가상 노드 (= 복제) 기술 사용

2️⃣ 가상 노드 (virtual node) = 복제 (replica)

• 가상 노드 : 실제 노드 또는 서버를 가리키는 노드
  • 서버를 링에 배치할 때 여러 개의 가상 노드를 이용, 여러 개의 파티션을 관리한다.
• 서버 조회 : 해당 키의 위치로부터 시계 방향으로 링을 탐색하는 중 만나는 첫 번째 가상 노드가 나타내는 서버에 키가 저장된다.
  • 가상 노드 개수가 많을 수록 표준 편차가 작아져, 키의 분포가 균등해진다.
    • 표준 편차 : 데이터가 어떻게 퍼져 나갔는지 보이는 척도
    • 단, 가상 노드를 저장할 공간이 증가하니 trade-off 필요
• 재배치할 키 결정
  • 서버 추가 / 삭제 : 새로 추가 / 삭제된 노드부터 반시계 방향에 있는 첫 번째 서버 까지에 있는 키들을 재배치

3️⃣ 안정 해시의 이점

• 서버 추가 / 삭제될 때 재배치되는 키의 수를 최소화할 수 있다.
• 데이터가 보다 균등하게 분포되어 수평적 규모 확장성을 달성하기 쉽고, 따라서 핫스팟 키 문제를 줄일 수 있다.
  • 핫스팟 : 특정 샤드에 대한 접근이 지나치게 빈번할 때 서버 과부하 문제가 생길 수 있다.
• 예시
  • 아마존 dynamoDB의 파티셔닝 관련 컴포넌트
  • 아파치 카산드라 클러스터에서의 데이터 파티셔닝
  • 디스코드 채팅 어플리케이션 등…..