5. 안정 해시 설계안

해시 키 재배치(rehash) 문제

• N개의 캐시 서버가 있으며, 서버들에 부하를 균등하게 나누는 보편적 방법은 아래의 해시 함수를 사용하는 것입니다.

serverIndex = hash(key) % N(서버의 개수)

• 이는 서버 풀 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작하나 서버가 추가되거나 삭제되면 문제가 발생합니다.

안정 해시

• 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술입니다.

아래의 내용들을 알고 있으면 좋습니다.

• 해시 공간과 해시 링
• 해시 서버
• 해시 키
• 서버 조회
• 서버 추가
• 서버 제거
• 기본 구현법의 두가지 문제
  • 첫 번재 문제는 파티션의 크기를 균등하게 유지할 수 없습니다.
  • 두 번째 문제는 키의 균등 분포를 달성하기가 어렵습니다.
• 가상 노드
• 재배치할 키 결정

마치며

• 안정 해시의 이점은 다음과 같습니다.
  • 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화됩니다.
  • 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽습니다.
  • 핫스팟 키 문제를 줄입니다.
• 대표적으로 널리 쓰이는 기술은 다음과 같습니다.
  • 아마존 다이나모 데이터베이스(DyanmoDB)의 파티셔닝 관련 컴포넌트
  • 아파치 카산드라(Apache Cassandra) 클러스에서의 데이터 파티셔닝
  • 디스코드(Discord) 채팅 어플리케이션
  • 아카마이(Akamai) CDN
  • 매그레프(Meglev) 네트워크 부하 분산기