- 수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
해시 키 재배치(rehash) 문제
- 나머지 연산으로 해시를 배치하는 것은 데이터 분포가 균등할 떄만 잘 동작한다.
- 또한, 서버가 추가되거나 기존 서버가 삭제되면 대부분의 키가 재분배된다.
안정 해시
- 안정 해시: 해시 테이블 크기가 조정될 떄 평균적으로 k/n개의 키만 재배치하는 기술
- k: 키의 개수
- n: 슬롯의 개수
기본 구현법
해시 함수를 사용해서 서버 IP나 이름으로 링 위에 서버를 배치한다.
해시 키도 똑같이 배치한다.
어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향을 링을 탐색해나가면서 만나는 첫 번째 서버다.
아래와 같이 서버를 추가하거나 삭제해도 키 일부만 재배치하면 된다.
- 문제점 2가지
- 서버를 추가/삭제할 떄, 파티션의 크기를 균등하게 유지하는게 불가능하다.
- 키의 균등 분포를 달성하기가 어렵다.
가상 노드
- 하나의 서버가 링 위에 여러 개의 가상 노드를 가진다.
- 가상 노드의 개수를 늘리면 키의 분포가 균등해진다.
- 가상 노드의 개수가 늘어날수록 균등해지지만, 가상 노드 데이터를 저장할 공간이 많아진다.
