스케일 아웃을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있다고 하면 이 서버들에 부하를 균등하게 나누는 방법은 보편적으로 아래와 같은 해시 함수를 이용하는 것이다.

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

이 방법은 서버 풀의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다. 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

이 때 rehash를 하면 장애가 발생한 서버에 보관되어 있는 키 뿐만 아니라, 대부분의 키가 재분배 되기 때문에 대규모 캐시 미스가 생긴다. 안정해시는 이 문제를 효과적으로 해결하는 기술이다.

안정 해시

안정 해시는 해시테이블 개수가 조정될 때 평균적으로 오직 k/n 개만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯의 개수이다. 이와 달리 전통적인 해시테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.

• 여기서 k/n 개는 없어지거나 추가된 곳에 보관된 키 개수 정도로 보면 될 것 같고 이 부분만 이동되서 효과적이구나 라고 생각하면 되겠다.

[해시 공간과 해시 링]

• 해시 함수 f = SHA-1을 사용한다고 해보자.
• 함수의 출력값 범위는 x_0, …, x_n 과 같고
• SHA-1의 해시공간은 0 ~ 2^160 - 1 이다.