해시 키 재배치(rehash) 문제
- N개의 캐시 서버에 부하를 균등하게 나누기 위해 보편적으로 해시 함수를 사용
- 데이터에 대한 해시값에 %를 적용해 서버에 데이터를 분산했다고 가정
- 캐시 서버가 삭제되거나 추가될 경우, 해시 값은 그대로이나 % 결과가 바뀜
- 경우에 따라, 데이터가 균등하지 않게 분포돼 cache miss가 발생할 수 있음
안정해시(consistent hash)
- 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 기술
해시 공간과 해시 링
- 해시 함수가 SHA-1일 때 해시 공간은 0부터 $2^{160} - 1$ 까지
- 해시 함수의 출력 값 범위가 x0 ~ xn까지일 때, x0 = 0 ~ xn = $2^{160} - 1$
- 이 해시 공간의 양쪽을 구부려 접어 xn과 x0을 연결하면 해시 링(hash ring)이 됨
해시 서버
- 해시 함수를 통해 서버 IP나 이름을 해시 링 위에 대응시킬 수 있음
해시 키
- 캐시할 키는 해시를 통해 해시 링 위의 특정 지점에 배치할 수 있음
서버 조회
- 어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 처음으로 만나는 서버
서버 추가
- 서버가 추가되더라도 키 가운데 일부만 재배치됨
- 예를 들어 서버 s0과 s1 사이에 sn이 추가됐을 때(s1이 시계방향으로 후순위로 가정)
- sn과 s1 사이의 데이터들은 그대로 s1에
- s0과 sn 사이의 데이터들만 s1에서 sn으로 재배치
서버 제거
- 서버가 제거되더라도 키 가운데 일부만 재배치됨
- 예를 들어 서버 s0과 s2 사이에 s1이 제거됐을 때(숫자가 클수록 시계방향으로 후순위로 가정)
- s1과 s2 사이의 데이터들은 그대로 s2에
- s0과 s1 사이의 데이터들만 s1에서 s2으로 재배치
기본 구현법의 두 가지 문제
- 기본 구현법
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
- 서버가 추가, 삭제될 경우 파티션(partition) 크기를 균등하게 유지하기 불가능함
- 파티션은 인접한 서버 사이의 해시 공간
- 상황에 따라 어떤 서버는 굉장히 큰 해시 공간을 할당 받는 상황이 생김
- 키의 균등 분포를 달성하기 어려움
가상 노드(virtual node)
- 실제 노드 또는 서버를 가리키는 노드로, 하나의 서버는 여러 개의 가상 노드를 가질 수 있음
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 가상 노드가 가리키는 서버가 키가 저장될 서버
- 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해짐
- 표준 편차가 작아져 데이터가 고르게 분포되기 때문
- 그러나 가상 노드 데이터를 저장할 공간이 많이 필요하게 돼 타협적 결정(tradeoff)이 필요