해시 링을 사용한 안정 해시 설계

안정 해시 설계

해시 키 재배치 문제

서버가 추가되거나 기존 서버가 삭제되면 해시값 인덱스가 달라져서 재배치 해야한다.

대부분의 키가 재분배 되면 대규모 캐시 미스가 발생할 것 이다.

 

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

 

 

해시 링

해시 공간을 구부려 접어서 해시 링을 만들고, 서버 IP나 이름을 이 위치에 대응시킬 수 있다.

해시 키도 링 위의 어느 지점에 배치한다. 시계 방향으로 링을 탐색해서 만나는 첫 번째 서버에 대응된다.

위 사진에서의 해시 링에서 서버 10.5.5.2, 10.9.5.1, 10.1.2.3을 각각 빨강, 파랑, 초록색으로 해시 링 공간에 대응하였다.

그리면 Venus에 해당하는 해시는 링을 탐색해서 만나는 첫 번째 서버인 파란색에 대응할 것이다.

Mars에 해당하는 해시값은 초록 서버에 대응하게 된다. 이렇게 사용하면, 서버를 추가/제거하더라도 키 가운데 일부만 재배치하면 된다.

 

문제점

• 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가능하다. 어떤 공간은 큰 해시 공간을 할당 받을 수 있다.
• 키의 균등 분포를 달성하기가 어렵다.

위 문제점은 가상 노드를 사용하면 어느 정도 해소할 수 있다. 가상 노드란 실제 노드 또는 서버를 가리키는 노드로, 하나의 서버가 링 위에 여러 개의 가상 노드를 가질 수 있다. 서버 0을 링에 배치하기 위해서 s0_0, s0_1, s0_2를 사용하여 배치한다.

 

 

 

위 사진에서 A 서버에 해당하는 가상 노드는 3개가 있고, D 서버에 해당하는 가상 노드는 2개가 있다. 다음과 같이 가상 노드를 여러개 배치하여 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 물론, 노드 데이터를 저장할 공간은 더 많이 필요하다는 TradeOff가 있다. 때문에 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야할 것이다.

 

해시 링을 사용하면 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.

이는 특정한 샤드에 지나치게 빈번한 서버 과부하가 생기는 것 핫 스팟 키 문제를 줄인다. 

 

참고

https://akshatm.svbtle.com/consistent-hash-rings-theory-and-implementation
https://dev.to/arslan_ah/how-to-use-consistent-hashing-in-a-system-design-interview-33ge
가상 면접 사례로 배우는 대규모 시스템 설계 5장