안정 해시 설계 1

수평적 규모 확장성을 달성하기 위해서는 트래픽 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.

 

이를 위한 보편적 기술!

 

안정 해시!

(Consistence Hashing, 일관된 해싱이라 부르기도 함)

 

안정 해시에 대해 알아보기 전, 해시 키 재배치 문제에 대해 알아보자.

N개의 캐시 서버가 있으면, 가장 쉽게 떠오르는 부하 분산 방법은

아래의 해시 함수를 이용하는 것이다.

serverIndex = hash(key) % N

 

위 방법은 서버 개수가 고정되어 있고 데이터 분포가 균등하다면 잘 동작한다.

 

하지만...

서버가 추가되거나 삭제된다면?

N이 바뀌니까.. index가 확 바뀌고.. 대부분의 데이터가 재배치된다..

데이터가 재배치 되면서 균등하지 않게 배치가 될 가능성이 존재한다.

이는 곧바로 대규모 캐시 미스 현상이 나타나게 된다.

(캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속)

 

 

위 문제를 해결하는 기술이 안정 해시다.

안정 해시는 해시 테이블 크기가 조정(캐시 서버 수가 변경) 될 때..

평균적으로 k/n개의 키만 재배치하는 기술이다.

(k: key갯수, n: 슬롯 갯수)

 

 

위 그림(해시 링)을 보며 이해 해보자.

주의 점은 해시 함수는 단순하게 모듈러 연산을 사용하지 않는다.

해시 링이란 해시 데이터 공간을 둥글게 원으로 구부린 가상 공간이라 생각하자

 

server는 총 4개, key는 6개가 있는 상황이다.

어떤 키가 저장되는 서버는,

해당 키의 위치로 부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버이다.

key6은 server1에 매칭

key1, 2는 server2에 매칭

...

 

 

서버가 추가되는 상황을 생각해보자..

key6과 server1 사이에 server5가 추가된다면..

key6은 server5로 재배치가 이루어질 것이며, 다른 key는 재배치가 이루어지지 않게 된다.

 

서버가 제거되는 상황을 생각해보자..

server1이 제거된다면 key6만 server2로 재배치가 이루어지며,

다른 키들은 재배치가 이루어지지 않는다.

 

위와 같이..

안정 해시는

서버가 추가 또는 제거 되더라도 key의 재배치가 일부만 이루어지므로

대규모 캐시 미스 현상은 일어나지 않는다.