안정해시는 무엇인가?
해시 테이블의 크기가 변경될 때 평균적으로 $n / m$개만 옮기면 되는 알고리즘
- $n$은 키의 개수
- $m$은 슬롯의 개수
안정해시의 기본적인 아이디어는 서버와 BLOB을 모두 원에 할당하는 것입니다.
실제 사용
이 알고리즘은 부하 분산을 할 때 많이 사용됩니다. 예를 들어 BLOB을 서버 클러스터에 캐시하고, BLOB의 해시값으로 요청을 한다고 생각해보겠습니다.
일반적인 해시
이 경우 일반적인 방식의 해시로 구현을 하게 되면 아래와 같을 것 입니다.
- BLOB의 hash를 계산 ($\beta$)
- 서버가 $n$개면 $mod(\beta, n)$번째 서버에 저장
이 경우 서버가 추가되면 $mod(\beta, n)$의 값이 바뀌기 때문에 잘못된 서버로 요청이 가게될 것입니다. - 혹은 전체 BLOB에 대해 서버가 추가될 때마다 재계산해줘야합니다. 위 문제는 서버가 제거되는 경우에도 같습니다.
안정해시
하지만, 안정해시를 사용하여 구현을 하게 되면 아래와 같습니다.
- hash를 계산 ($\Phi$)
- 각도를 계산 ($mod(\Phi, 360)$)
- 시계방향으로 다음 서버에 할당 (혹은 반시계 방향으로도)
이 경우 서버가 추가되면 추가된 서버의 각도와 바로 이전 서버의 각도 사이에 존재하는 BLOB들만 새로운 서버로 요청이 들어오게 될 것입니다.
또한 서버가 제거된 경우 전체를 재계산할 필요없이 제거된 서버의 다음 서버에 모두 옮겨주는 방식으로 구현을 할 수도 있습니다.