안정 해시 설계에 대해 알아보자

대규모의 서비스는 하나의 서버가 아니라 다수의 서버를 통해 운영된다. (수평적 확장)

스케일 아웃된 서버의 효과적인 동작을 위해서는 서비스의 데이터들이 균등하게 분배되어야 한다.

 

간단한 방식으로는 해시 함수를 통한 처리가 있다.

N개의 캐시 서버가 있다고 해보자.

serverIndex = hash(key) % N과 같이 간단한 모듈러 연산을 통해 서버를 선정한다.

 

하지만 위 방식의 경우 서버의 추가, 삭제가 일어났을 때 문제가 발생한다.

키에 대한 해시 값은 변화하지 않지만 서버의 개수인 N의 값이 달라지므로 서버 인덱스 값이 달라지게 된다.

따라서 대부분의 캐시 클라이언트가 데이터가 없는 엉뚱한 서버로 접속하게 된다. (대규모의 캐시 미스 발생)

 

안정 해시는 이러한 문제를 효과적으로 해결해준다.

해시 링 위에 서버를 배치한다.

키가 저장되는 서버는 해당 키로부터 시계 방향으로 링을 탐색하여 만나는 첫 번째 서버다.

ex) k0 → s0, k1 → s1

 

위와 같이 server4가 추가되었을 경우 k0만 s4로 재배치한다.

s1 서버가 제거되었을 경우 k1은 s2로 재배치한다

 

서버가 추가될 경우, 추가된 서버부터 반시계 방향에 있는 첫 번째 서버 사이에 있는 키들을 추가된 서버로 재배치한다.

서버가 제거될 경우, 제거된 서버로부터 반시계 방향에 있는 첫 번째 서버 사이에 있는 키들을 제거된 서버의 다음에 있는 서버로 재배치한다.