5장 안정 해시 설계

•

N개의 캐시 서버에서 보통은 serverIndex = hash(key)%N

•

보편적이고 직관적인 방법이지만 서버가 추가되거나 삭제되면 문제가 발생

•

분포가 달라질 수 있고 대부분의 키를 재배치해야한다.

•

안정 해시를 적용하면 오직 k/n 개만의 키만 재배치된다.

•

나머지 연산으로 해시 키값을 구하는 것이 아니고 해시 공간의 양쪽을 구부려 해시 링을 만든다.

•

생성된 키들을 해시 링 위의 어느 지점에 배치한다.

•

시계방향으로 돌면서 가장 먼저 만나는 서버에 저장된다.

•

서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

k2, k3, k4 는 그대로 유지되고 k1 만 서버 1에서 서버 5로 이동한다.

•

서버가 제거되어도 키 가운데 일부만 재배치된다.

•

서버간 할당 크기를 균등하게 유지하는게 불가능하다.

◦

위의 제거 예시에서 s1 은 s3~s1 까지의 크기를 모두 감당해야 한다.

•

키의 균등 분포를 당성하기 어렵다.

◦

앞선 문제 등으로 인해 서버들 사이에서 키의 분포가 다를 수 있다.

•

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서 링 위에 여러 개의 가상 노드를 가지는 방법

•

표준 편차가 작아져서 데이터가 고르게 분포되기 때문에 가상 노드의 개수를 늘릴수록 키의 분포는 점점 더 균등해진다.

•

너무 많이 늘리면 가상 노드 데이터를 저장할 공간이 필요해서 트레이드 오프가 필요하다.

•

안정 해시의 이점

◦

서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.

◦

데이터가 보다 균등하게 분포하게 되어 수평적 규모 확장에 유리하다.

◦

표준 편차가 작아져 핫스팟 키 문제를 줄인다.