해시 테이블의 크기가 변경될 때 평균적으로 $n / m$개만 옮기면 되는 알고리즘

• $n$은 키의 개수
• $m$은 슬롯의 개수

안정해시의 기본적인 아이디어는 서버와 BLOB을 모두 원에 할당하는 것입니다.

#실제 사용

이 알고리즘은 부하 분산을 할 때 많이 사용됩니다. 예를 들어 BLOB을 서버 클러스터에 캐시하고, BLOB의 해시값으로 요청을 한다고 생각해보겠습니다.

#일반적인 해시

이 경우 일반적인 방식의 해시로 구현을 하게 되면 아래와 같을 것 입니다.

• BLOB의 hash를 계산 ($\beta$)
• 서버가 $n$개면 $mod(\beta, n)$번째 서버에 저장

이 경우 서버가 추가되면 $mod(\beta, n)$의 값이 바뀌기 때문에 잘못된 서버로 요청이 가게될 것입니다. - 혹은 전체 BLOB에 대해 서버가 추가될 때마다 재계산해줘야합니다. 위 문제는 서버가 제거되는 경우에도 같습니다.

#안정해시

하지만, 안정해시를 사용하여 구현을 하게 되면 아래와 같습니다.

• hash를 계산 ($\Phi$)
• 각도를 계산 ($mod(\Phi, 360)$)
• 시계방향으로 다음 서버에 할당 (혹은 반시계 방향으로도)

이 경우 서버가 추가되면 추가된 서버의 각도와 바로 이전 서버의 각도 사이에 존재하는 BLOB들만 새로운 서버로 요청이 들어오게 될 것입니다.

또한 서버가 제거된 경우 전체를 재계산할 필요없이 제거된 서버의 다음 서버에 모두 옮겨주는 방식으로 구현을 할 수도 있습니다.

#참고한 자료

• https://en.wikipedia.org/wiki/Consistent_hashing
• https://songkg7.github.io/posts/Consistent-Hashing/