5장 안정해시설계

해시 키 재배치 문제
- 보통 해시 function으로 모듈러 연산을 사용하는데 이 방식은 서버 풀 크기가 바뀌게 되면 해시 테이블 내의 키가 재분배되어 높은 확률의 캐시 미스가 발생함

해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술(k = 키의개수, n = 슬롯 개수)
hash space를 링 형태로 이어지도록 관리
해시 함수를 이용해 서버들을 hash space에 위치하도록 함
동일한 해시 함수를 이용해 키들도 링 위에 위치하도록 함
링 위의 키들은 시계 방향으로 링을 탐색하며 만나는 첫 번째 서버에 저장됨
이 같은 방식은 서버가 추가/제거되더라도 자동으로 키가 k/n개만큼만 재배치 됨
- 링 위에서 하나의 노드가 추가되었다면 전체 갯수 중 노드 갯수를 나눈 만큼만 새로운 서버(노드)로 재배치됨
정리
- 서버와 키를 균등 분포 해시 함수를 이용해 해시 링에 균등한 간격으로 배치되도록 한다
- 키의 위치에서 처음으로 만나는 서버가 키가 저장되는 서버이다
문제
- 파티션의 균등 분포를 달성하기 어려움
  - 파티션은 인접한 서버 사이의 해시 공간으로 서버가 어디에 추가되느냐에 따라 각 파티션의 크기는 달라짐
  - 얼마만큼의 서버가 추가되거나 삭제되는 상황에서 균등한 파티션을 유지하는 것이 불가능함
- 키의 균등 분포를 달성하기 어려움

실제 노드 또는 서버를 가리키는 노드로 하나의 서버는 링 위에 다수의 가상 노드를 가질 수 있다.
가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐
- 표준 편차가 작아져서 데이터가 고르게 분포되기 때문 → 정밀하지 않은 느슨한 방법(완벽한 균등 분배를 보장하지 않음)
- 표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도로 100-200개의 가상노드 사용시 표준편차값은 평균의 5프로에서 10프로이다
- 그렇다고 무작정 개수를 늘릴 경우 메모리 이슈가 있으니 trade off를 고려할 것