안정 해시 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 "안정 해시 설계"을 요약한 내용입니다.

• 수평적 규모 확장을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요
• 해시 기술이 풀려고 하는 문제부터 좀더 자세히 살펴보기

해시 키 재배치 문제

• N개의 캐시 서버가 균등하게 부하를 나누는 방법으로 해시 함수를 사용한다.
  • serverIndex = hash(key) % N
• 특정 키가 보관된 서버를 알아내기 위해, 나머지연산을 적용
  • hash(key0) % 4 == 1
  • 서버 1에 접속하여 보관된 데이터를 가져올 수 있다.
  • 
• n번 서버가 장애가 발생할 경우 서버 풀의 크기는 3으로 변한다
  • 모듈러 연산에 의해 서버의 인덱스가 달라지는 문제가 발생
  • 대부분 캐시 클라이언트가 데이터가 없는 서버에 접속하게 되고 대규모 캐시 미스가 발생하게 됨
  • 

안정 해시

• 안정 해시는 해시 테이블 크기가 조정 될 때 평균적으로 오지 k/n개의 키만 재배치하는 해시 기술
  • k는 키의 개수이고, n은 슬롯의 개수다.

해시 공간과 해시 링

해시 서버

• 해시 함수 f를 사용하면 서버 IP나 이름을 이링 위의 어떤 위치에 대응시킬 수 있다.

해시 키

• 해시 키 재배치 문제에 언급된 함수와는 다르며, 나머지 연산 %는 사용하지 않고 있음

서버 조회

• 어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버다.

서버 추가

• 서버를 추가 하더라도 키 가운대 일부만 재배치 하면 된다.

서버 제거

• 하나의 서버가 제거되면 키 가운데 일부만 재배치 된다.

기본 구현법의 두가지 문제

• 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장된 서버다

두가지 문제가 있음

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는게 불가능하다
   1. 어떤 서버는 굉장히 작은 해시 공간을 할당 받고 어떤 서버는 굉장히 큰 해시 공간을 할당 방는 상황이 발생할 수 있다.
2. 키의 균등 배포를 달성하기가 어렵다
   1. 서버 1과 서버3은 아무 데이터도 갖지 않는 반면, 대부분의 키는 서버 2에 보관될 것이다.

가상 노드

• 가상 노드는 실제 노드 또는 서버를 가르키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

• 가상의 노드의 개수를 늘리면 키의 분포는 점점더 균등해진다.
  • 표준 편차가 작아져서 데이터가 고르게 분포되기 때문

재배치할 키 결정

• 서버가 추가 되거나 제거되면 데이터 일부는 재배치해야 한다. 어느 범위의 키들이 재배치 되어야 할까?

마치며

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화 된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다
• 핫스팟키 문제를 줄인다.
  • 특정한 샤드에 대한 접근이 지나치게 빈번하다면 서버 과부하 문제가 생길 수 있다.

안정 해시의 사용 사례

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카마이 CDN
• 매그레프 네트워크 부하 분산기
• 수평적 규모 확장을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요
• 해시 기술이 풀려고 하는 문제부터 좀더 자세히 살펴보기해시 키 재배치 문제