안정 해시 설계
- 수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요.
- 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술.
해시 키 재배치(rehash) 문제
- N개의 캐시 서버에 부하를 균등하게 나누는 보편적인 방법
serverIndex=hash(key) % N (N은 서버의 개수)
- 이 방법은 서버 풀(server pool)의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작함.
- 하지만 서버가 추가되거나 기존 서버가 삭제되면 연산에 따른 서버 인덱스 값이 달라지므로 문제가 발생.
안정 해시
- 안정 해시(consistent hash)는 해시 테이블 크기가 조정될 떄 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술. 여기섯 k는 키의 개수이고, n은 슬롯(slot)의 개수.
해시 공간과 해시 링
- 해시 함수 f로 SHA-1을 사용한다고 가정.
- SHA-1의 해시 공간(hash space) 범위는 0부터 2^160 - 1까지.
- 이 해시 공간의 양쪽을 구부려 접으면 해시 링(hash ring)이 만들어짐.
해시 서버
- 해시 함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있음.
해시 키
- 해시 키 또한 해시 링 위의 어느 지점에 배치.
서버 조회
- 어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번재 서버.
서버 추가
- 서버를 추가하더라도 키 가운데 일부만 재배치하면 됨.
서버 제거
기본 구현법의 두 가지 문제
- 기본 절차
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버.
- 두 가지 문제
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능.
- 키의 균등 분포(uniform distribution)을 달성하기가 어려움.
- 이 문제를 해결하기 위한 기법이 바로
가상 노드
가상 노드
- 가상 노드(virtual node): 실제 노드 또는 서버를 가리키는 노드.
- 하나의 서버는 링 위에 여러 개의 가상 노드를 가지 수 있음.
- 각 서버는 하나가 아닌 여러 개의 파티션을 관리.
- 가상 노드의 개수를 늘리면 키의 분포가 점점 더 균등해짐. 대신 가상 노드 데이터를 저장할 공간이 더 많이 필요하게 됨.
재배치할 키 결정
- 서버가 추가되거나 제거되면 데이터 일부는 재배치해야 함.
- 서버 노드 추가
- 영향 받는 범위는 새로 추가된 노드로부터 그 반시계 방향에 있는 첫번째 서버 사이의 키들 재배치 필요.
- 서버 노드 삭제
- 마찬가지로 영향 받는 범위는 삭제된 노드로부터 그 반시계 방향에 있는 첫번째 서버 사이의 키들 재배치 필요.
마치며
안정 해시의 이점
- 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화.
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
- 핫스팟(hotspot) 키 문제를 줄인다. 특정한 샤드(shard)에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.
출처
