점프 일관성 해시는 해시 링을 다섯 줄로 대체했다

일관성 해싱은 분산 시스템의 실제 문제를 해결했다. 버킷이 추가되거나 제거될 때 모든 키를 다시 매핑하지 않는 것이다. 그러나 일반적인 Karger 방식의 링은 운영상의 부담을 안고 있었다. 가상 노드, 저장 공간, 그리고 조정해 없애야 하는 불균등함이다.

Lamping과 Veach의 점프 일관성 해시는 더 좁은 질문을 던졌다. 버킷에 순차적으로 번호를 매긴다면, 링을 전혀 저장하지 않고도 키의 목적지를 계산할 수 있을까? 그들의 답은 약 다섯 줄의 코드에 담겼다.

arXiv 논문에 따르면 이 방법은 저장 공간이 필요 없고, Karger 등이 제안한 알고리즘보다 빠르며, 버킷 수가 변할 때 키 공간과 작업 부하를 모두 더 균등하게 나눈다. 그 대가도 명확하다. 버킷 번호가 순차적이어야 하므로 임의의 웹 캐시 멤버십보다 저장소에 더 적합하다.

마지막 버킷 변경으로 바로 점프한다

버킷 ID를 순차적으로 제한함으로써 멤버십 링이 필요 없어졌다.

최소 재매핑은 점프 과정에서 자연스럽게 나온다. 키는 추가된 버킷이 그 키를 차지할 때만 이동한다.

조회 테이블이 없으므로 재구축하거나 배포할 메모리 공간이 없다.

한계는 솔직하고 유용하다. 이 기법은 변동이 심한 캐시 집합보다 저장소 샤드에 더 잘 맞는다.

어떤 데이터 구조가 주로 확률 법칙을 보존하기 위해 존재한다면, 때로는 그 법칙을 직접 샘플링하고 구조는 사라지게 할 수 있다.

점프 일관성 해시는 작은 구현 비용으로 안정적인 배치가 필요한 샤딩 저장소, 데이터베이스, 라이브러리에서 간결한 선택지가 되었다. 그 우아함은 제약에 있다. 임의의 버킷 이름을 포기하면 링 전체가 사라진다.