안정 해시 (Consistent Hash) - 해시 키 재배치(rehash) 문제

수평적 규모 확장성을 위해 요청 또는 데이터를 서버에 균등하게 분배 하는 것이 중요한데 어떤 기술을 사용하지?

-> 안정 해시 사용

해시 키 재배치(rehash) 문제

Case

- 해시 함수 :  서버인덱스 = hash(key) % n (n = 서버 개수)

- 4개의 데이터베이스

key(데이터)	해시	서버인덱스 (해시 % 4)
data00	1111	3
data01	2222	2
data02	3333	1
data03	4444	0
data04	5555	3
data05	6666	2
data06	7777	1
data07	8888	0

위 key(데이터)들은 아래와 같이 데이터베이스에 저장된다.

이 방법은 서버 풀(server pool)의 크기 또는 서버의 개수가 고정되어 있을때, 데이터 분포가 균등할 때는 잘 동작한다.

하지만 서버가 추가되거나 기존 서버가 삭제(또는 장애)되면 문제가 발생한다.

 

ex) DB-00 서버가 삭제 되었을 경우

key(데이터)	해시	서버인덱스 (해시 % 3)
data00	1111	1
data01	2222	2
data02	3333	0
data03	4444	1
data04	5555	2
data05	6666	0
data06	7777	1
data07	8888	2

DB-00서버가 삭제되면서 보관되어 있는 키 뿐만 아니라 다른 서버에 저장되어 있는 키 대부분이 재분배 되었다.

DB-00서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다는 뜻이다.

-> 대규모 캐시 미스 발생

 

안정 해시 (Consistent Hash)는 이 문제를 효과적으로 해결하는 기술이다.