[대규모 시스템 설계 기초] 안정 해시 설계, Consistent hashing

안정 해시 설계, consistent hashing

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

그리고 이를 실현시키는 기술로 안정 해시가 있다.

 

해시 키 재배치 문제, rehashing

먼저, 왜 안정 해시가 필요한지를 문제 상황을 통해 알아보자.

 

N개의 캐시 서버가 있다고 가정하면, 요청에 응답하는 서버를 할당하기 위해 다음의 수식(modular arithmetic)을 사용한다.

몇 번째 server = hash(key) % N

URI, 고유 식별자와 같은 요청에 적합한 key값을 선택하고 해시 함수의 결과를 N으로 나누어 서버에 요청을 보낸다.

서버에 개수가 일정하게 유지된다면 위 설계는 문제없이 작동한다.

 

하지만 auto scale로 서버가 추가되거나 장애로 서버가 죽는다면 매우 큰 문제가 생긴다.

기존에는 클라이언트의 요청에 유의미한 cache hit rate를 보였다면,

서버가 추가되는 순간마다 수많은 cache miss를 경험하게 될 것이다.

 

안정 해시

웹서버의 개수가 변동하는 가운데 요청을 분산하는 방법을 말한다. 해시테이블의 크기가 변할 때, 평균적으로 K/n의 키만 재매핑되면 된다. 즉 노드나 슬롯의 개수가 바뀔 때, 노드의 추가나 삭제를 할 때, 오직 K/n의 아이템만 다시 섞이면 되는 것이다. - wiki

 

동작

그림처럼 해시 공간을 구부려 해시 링을 만든다.

 

서버와 요청을 해시 공간의 한 점으로 표현하면 다음과 같다.

요청의 key값과 서버의 인덱스가 그림에 나타나고 있다.

요청을 처리할 서버는 반시계 방향으로 먼저 마주치는 서버이다.

이 방식은 서버가 추가될 때, 제거될 때 기존의 방식에서 개선된 동작을 보인다.

 

서버가 추가될 때

위 그림을 보면 기존에 없던 s4가 추가되었다.

동작대로, key0를 가지는 요청이 s4 서버에 할당되는 모습이다.

기존에는 전체 노드에 대한 해시 재배치가 이뤄진 것에서 일부 요청만이 재배치된 모습이다.

 

서버가 삭제될 때

s1 서버가 삭제된 그림이다.

s1이 처리하던 요청 k1이 반시계 방향에서 가장 가까운 s2로 처리되는 모습이다.

마찬가지로 일부 요청만이 재배치된 모습이다.

 

또 다른 문제

이 구조 또한 다음의 문제를 가지고 있다.

• 서버가 추가되거나 삭제되는 상황에서 인접한 서버 사이의 해시 공간을 균등하게 유지할 수 없다.
• 키의 균등 분포를 달성하기 어렵다.

 

두 문제는 모두 특정 서버에 과부하가 걸릴 수 있음을 암시한다.

이를 해결할 수 있는 방법을 간단하게 설명하면, 하나의 서버를 하나의 점으로 표현하지 않고

여러 가상 노드를 통해 키의 분포를 균등하게 만드는 것이다.

 

가상 노드의 개수를 늘리는 것은 인접한 서버 사이의 공간의 표준편차를 작게해서 균등하게 만드는 목표에는 가까워지지만,

가상 노드 데이터 공간이 많아짐에 따라 trade off 가 생길 수 있음을 알아야한다.

 

출처

https://ko.wikipedia.org/wiki/일관된_해싱

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 인사이트