점프 일관 해시 계산기

메모리를 하나도 쓰지 않습니다. 링 해시(consistent hashing)는 가상 노드 수백 개를 정렬해 들고 있다가 이진탐색으로 찾는데, 점프 해시는 난수 몇 번으로 끝나 표도 정렬도 이진탐색도 없습니다. 반복 횟수의 기댓값이 O(log n)이라 버킷이 10개든 10만 개든 서너 번에서 예닐곱 번 사이입니다.

알고리즘이 «버킷을 1개부터 하나씩 늘려 갈 때 언제 옮겨지는가»를 따라가는 구조이기 때문입니다. n에서 n+1로 갈 때 각 키는 확률 1/(n+1)로 새 버킷 n으로 옮겨 가고 아니면 그대로 있습니다. 기존 버킷 사이를 오가는 경우는 아예 생길 수 없어, 재배치가 언제나 최소입니다.

버킷을 맨 뒤에서만 뺄 수 있다는 것이 큰 대가입니다. 가운데 샤드 하나를 빼는 것이 안 됩니다. 링 해시는 아무 노드나 뺄 수 있으므로, 노드가 임의로 죽고 살아나는 환경에서는 링 해시나 랑데부 해싱이 맞습니다. 점프 해시는 «샤드 수를 늘리기만 하는» 경우에 어울립니다.

묻는 것이 다릅니다. 부하 불균형 쪽은 «고르게 뿌려도 가장 무거운 샤드는 평균보다 얼마나 무거운가»를 묻고, 이 계산기는 «어느 샤드로 보낼 것인가, 그리고 샤드를 늘리면 얼마나 옮겨야 하는가»를 묻습니다. 함께 보시면 샤딩 설계의 두 축이 됩니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.