*<가상 면접 사례로 배우는 대규모 시스템 설계 기초> 을 참고하여 작성한 게시물입니다.
안정 해시 설계
수평적 규모 확장성 달성을 위해, 요청 또는 데이터를 서버에 균등하게 나누도록 할때 보편적으로 사용하는 기술. 이 해시 기술이 풀려고 하는 문제는 다음과 같다.
해시 키 재배치 문제
modular 연산을 이용해서 캐시를 배치. 이는 서버 풀(server pool)의 크기가 고정되어있을 떄, 데이터 븐포가 균등할 때는 잘 동작하지만, 서버가 추가되거나 기존 서버가 삭제되면 문제가 생김. 이때, 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개(k:키의 개수, n:슬롯의 개수)의 키만 재배치하는 기술으로 이를 이용해 문제를 해결할 수 있다. (전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.)
키의 위치에서 링을 시계 방향으로 탐색하는 방식이 안정 해시의 원리로, 기본 절차는 1.서버와 키를 균등 분포 해시 함수를 이용해 해시 링에 배치한다. 2.키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다. 인데, 1)서버가 추가되거나 삭제되는 상황을 감안하면 파티션(인접한 서버 사이의 해시 공간)의 크기를 균등하게 유지하는 것이 불가능. 2)키의 균등 분포를 달성하기가 어려움. 이다.
이를 해결하기 위해 제안된 것이 가상 노드기법이다. 이는 실제 노드 또는 서버를 가리키는 노드로, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 키의 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 되는 것으로, 가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다. 그러나 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야한다.
그리고 다음으로, 서버가 추가되거나 제거되면 데이터의 일부는 재배치해야 하는데, 어느 범위의 키들이 재배치되어야 할까? 삭제/추가에 영향받는 것은 반시계 방향에 있는 첫 번째 서버까지이다. 이 사이에 있는 키들을 재배치해야한다.
안정 해시의 이점
- 서버가 추가되거나 삭제되 대 재배치되는 키의 수가 최소화되나.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
- 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.
