랑데부 해싱(HRW) 계산기

키 하나에 대해 모든 노드와 짝지어 해시를 구하고 값이 가장 큰 노드를 고르는 방식입니다. HRW(Highest Random Weight)라고도 합니다. 링도 가상 노드도 미리 만들어 두는 표도 없이 노드 이름 목록만 있으면 어디서 계산해도 같은 답이 나오므로, 조정자 없이 여러 클라이언트가 같은 배치를 얻을 수 있습니다.

노드 X를 빼면 각 키의 점수 목록에서 X의 항목 하나가 사라질 뿐이기 때문입니다. X가 1위가 아니었던 키는 1위가 그대로여서 움직이지 않고, X가 1위였던 키만 2위로 넘어갑니다. 그래서 노드가 n개일 때 정확히 1/n만 옮겨 가고 남은 노드끼리는 키가 오가지 않습니다. 이 계산기가 실제로 세어 확인해 줍니다.

n이 바뀔 때 옮겨 가는 양이 다릅니다. 나머지 연산은 n이 하나만 바뀌어도 거의 모든 키의 배치가 달라져 캐시 전체가 무효가 됩니다. 랑데부 해싱은 1/n만 옮겨 가고, 그것도 사라진 노드가 맡던 몫뿐입니다.

가상 노드가 필요 없다는 것이 가장 큰 차이입니다. 해시 링은 노드를 원 위에 흩뿌리는데 노드 수가 적으면 간격이 들쭉날쭉해져 부하가 크게 기울므로, 노드 하나를 수백 개의 가상 노드로 쪼개 뿌리고 그 목록을 들고 있어야 합니다. 랑데부 해싱은 그런 장치 없이도 고르게 나뉩니다. 대신 키 하나를 배치하는 데 노드 수만큼 해시를 계산해야 해서, 노드가 수천 개면 링을 이진 탐색하는 쪽이 훨씬 빠릅니다.

점수를 w / (−ln u)로 매깁니다. u는 (0,1) 사이의 해시값이고 −ln u가 평균 1인 지수분포를 따르므로, 이 점수의 최댓값을 고르면 노드 i가 뽑힐 확률이 정확히 wᵢ/Σw가 됩니다. 가중치가 모두 같으면 그냥 해시가 가장 큰 노드를 고르는 것과 같은 순서가 되므로, 한 식으로 두 경우를 모두 다룰 수 있습니다.

노드가 수십에서 수백 개인 경우입니다. 캐시 계층, 샤드 배치, 작업 분배가 대표적입니다. 노드가 수천 개를 넘으면 키마다 그만큼 해시를 계산해야 해서 링 방식이 유리해지고, 노드가 두세 개뿐이면 어느 방식을 써도 차이가 없습니다.

이 계산기는 FNV-1a에 murmur3의 마무리 함수를 씌운 32비트 해시를 씁니다. 분포는 고르지만 암호학적으로 안전하지 않아, 특정 노드로 몰리는 키를 일부러 찾아내는 것을 막지는 못합니다. 공격자가 키 이름을 정할 수 있는 환경이라면 SipHash처럼 비밀 키를 쓰는 해시를 써야 합니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 적은 노드 이름은 이 기기에만 남습니다.