안정 해시 설계 (대시설기)

수평적 규모 확장성을 달성하기 위해 요청을 서버에 균등하게 나누는 것이 중요한데 안정 해시는 보편적으로 사용하는 기술이다.

해시 키 재배치(rehash) 문제

안정 해시

해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.

k : 키의 개수, n : 슬롯의 개수

해시 공간과 해시 링

해시 서버

해시 키

서버 조회

서버 추가

서버 제거

기본 구현법의 두 가지 문제

기본 절차는 다음과 같다.

1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

2가지 문제

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능 (파티션 : 인접한 서버 사이의 해시 공간)
2. 키의 균등 분포를 달성하기 어렵다.

해당 문제들을 해결하기 위해 제안된 기법이 ‘가상 노드’ 또는 ‘복제’라 불리는 기법이다.

가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. (tradeoff 관계)

재배치할 키 결정

서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다.

마치며

안정 해시 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 된다.
• 핫스팟 키 문제를 줄인다.

안정 해시 사용처 예시

• 아마존 DynamoDB
• 아파치 카산드라
• 디스코트 채팅 어플
• 아카마이 CDN
• 매그레프 네트워크 부하 분산기