해시 키 재배치(refresh) 문제

서버들에 부하를 균등하게 나누기

해시 함수: severIndex=hash(key) % N (N: 서버 개수)

→ 서버 풀의 크기 고정, 데이터 분포 균등 시 사용

But, 서버 추가/삭제 시 대규모 캐시 미스 발생 가능

안정 해시(consistent hash)

해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술

(k: 키 개수, n: 슬롯 개수)

↔ 전통적 해시 테이블: 슬롯 수 변경 → 대부분 키 재배치

해시 공간과 해시 링

해시 함수 f: SHA-1/ 출력 값 범위: x0, x1, x2, …, xn

→SHA-1 해시 공간 범위: 0 ~ $2^{160}$- 1

⇒ x0 = 0, xn = $2^{160}$- 1

→ 해시 공간 양쪽 구부리면 해시 링

해시 서버

해시 함수 f 사용 → 서버 IP/이름을 링 위의 어떤 위치에 대응시킬 수 있음