5장

해시 키 재배치 문제

• N개 캐시 서버가 있고, mod N을 써서 나누면, 서버 개수가 바뀔 때 문제가 생긴다.

  • 균등하게 몰리지 않고 불균형이 생길 수 있다.

• 이렇게 서버 개수가 바뀌어서 해시 키를 재배치해야할 때 어떻게 해야 균등하게 배치할 수 있는가?

안정 해시란?

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

• 동작 원리

• 해시 링

  • 출력 공간 범위가 0에서 2^160-1일 때, 시작과 끝을 구부려 접는다

  • 해시 함수는 SHA-1을 사용한다.

  • 안정 해시 알고리즘 - MIT에서 처음 제안됨

    1. 서버를 링 위에 배치한다.

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

  • 재배치 시 어떻게 균등 분포를 달성하는가?

    • 가상 노드를 사용한다 → 서버 1의 가상 노드 50개, 2의 가상 노드 50개 등

    • 가상 노드를 늘릴수록 분포가 균등해진다.

    • 가상노드가 삭제되거나 추가되면, 그 사이에 있는 키들만 재배치하면 된다.

• 안정해시는 실제로 널리 쓰이는 기술이다.

  • 다이나모 DB의 파티셔닝 관련 컴포넌트

  • 아파치 카산드라 클러스터에서의 데이터 파티셔닝

  • 디스코드 채팅 어플리케이션

  • 아카마이 CDN

  • 매그래프 네트워크 부하 분산기