수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누어야 한다.

안정 해시는 이 목표를 달성하기 위해 보편적으로 사용된다.

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있을 때 보편적으로 아래와 같이 부하를 균등하게 나눈다.

serverIndex = hash(key) & N

분배 예시

이러한 분배 방식은 데이터 분포가 균등할 때는 잘 동작하지만, 서버가 추가되거나 삭제되면 문제가 발생한다!

ex) 1번 서버가 장애가 발생해 서버 풀의 크기가 3으로 줄어들면?

→ 키 분포는 변화하게 되고, 1번 서버에 접속하던 캐시 클라이언트는 데이터가 없는 엉뚱한 서버에 접속된다.

→ 캐시 미스가 발생하며, 성능이 좋지 못함!

⇒ 이를 보완하기 위해 나온 것이 안정 해시

안정 해시

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

여기서 k는 키의 개수이며, n은 슬롯의 갯수이다.