가상면접으로 배우는 대규모 시스템 설계 기초
5장 안정 해시 설계
수평적 규모 확장성을 달성하기 위해서 요청 또는 데이터를 서버에 균등하게 나누는게 중요하다
해시키 재배치 문제
n개의 캐시서버의 부하를 균등하게 나누는 보편적인 방법은
serverindex = hash(key) % n(서버 갯수)
위에 방법은 서버 풀이 고정되어 있을때 그리고 데이터 분포가 균등할때 잘 동작한다
하지만 서버가 추가되거나 삭제 될때는 대부분의 키가 재분배 해야 되는 문제가 생긴다.
안정해시
안정해시는 해시테이블의 크기가 조절될때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.
해시 공간과 해시 링
- 해시 공간을 구부리면 해시 링이 만들어 진다.
해시 서버
- 서버는 해시 링에 특정 위치에 존재한다.
해시 키
- 해시 키는 특정 방향으로 가장 가까운 서버에 값을 저장한다.
서버 조회
- 특정 위치에 가장 가까운 서버에게 질의 한다
서버 추가
- 추가가 되도 특정 위치의 해시 키만 다른 서버에 저장된다.
서버 제거
- 제거시에도 첫번째 만나는 서버에만 저장하면 된다.
기본 구현법의 두 가지 문제
- 기본 구현법
- 서버와 키를 균등 분포 해시 함수를 사용해서 링에 배치한다
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.
- 두 가지 문제
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능하다
- 키의 균등 분포를 달성하기가 어렵다
- 해결 방법
- 가상 노드 또는 복제 기법
- 기본 구현법
가상 노드
- 실제 노드 또는 서버를 가리키는 노드로써 하나의 서버는 링 위에 여러 개 가상 노드를 가질 수 있다. 가상노드의 갯수를 늘리면 키의 분포는 점점 균등해진다 표준 편차가 작아져 데이터가 고르 분배
- 시스템 요구 사항에 맞춰 가상 노드 개수를 적절히 조정해야 된다.
재배치할 키 결정
- 서버가 추가 되거나 저거되면 데이터 일부는 재배치 해야 된다
- 삭제된 노드 반시계 방향에 있는 최초 서버 와 시계 방향 첫번째 서버사이에 키들은 재배치 되어야 된다