샤드 부하 불균형(최대 샤드) 계산기

유한한 개수를 무작위로 나누면 원래 생기는 흔들림 때문입니다. 동전을 아무리 잘 던져도 앞면이 정확히 절반이 나오지 않는 것과 같습니다. 샤드 하나의 부하는 이항분포 B(n, 1/m)이고 표준편차가 √(n/m)쯤이라, 샤드가 많을수록 그 가운데 가장 큰 값이 평균에서 더 멀리 떨어집니다.

샤드당 키가 넉넉하면 n/m + √(2·(n/m)·ln m)쯤입니다. 「λ+x를 넘는 샤드의 기대 개수 m·exp(−x²/2λ)가 1이 되는 x」에서 나온 값입니다. 키 100만 개를 64개 샤드에 뿌리면 평균 15,625개에 최대는 16,000개 남짓으로 약 2.3% 더 무겁습니다.

반대입니다. 평균 부하는 줄지만 상대 불균형은 커집니다. 초과분을 평균으로 나누면 √(2 ln m / λ)인데 샤드를 늘리면 λ = n/m이 줄어 이 비가 커지기 때문입니다. 잘게 쪼갤수록 샤드마다 더 큰 여유를 둬야 합니다.

안 됩니다. 모든 샤드가 같은 크기의 기계에 올라간다면 가장 무거운 샤드가 들어가야 전체가 돕니다. 평균으로 잡으면 절반 가까운 샤드가 넘치며, 규모가 커질수록 「어딘가 하나는 많이 튄다」가 확실해집니다.

해시로는 못 고칩니다. 특정 키 하나가 전체 트래픽의 10%를 먹는다면 그 키가 어느 샤드로 가든 그 샤드가 10%를 집니다. 해시는 키를 고르게 흩뿌릴 뿐 키 자체의 치우침을 없애지 못하므로, 그때는 샤드를 늘리는 대신 키를 쪼개거나 앞에 캐시를 둬야 합니다.

식이 달라집니다. n ≈ m처럼 성긴 영역에서는 정규근사가 무너지고 최대 부하가 ln m / ln ln m 규모가 됩니다. 샤드 1000개에 키 1000개를 뿌리면 평균은 1인데 가장 무거운 곳에는 5~6개가 들어가 상대 불균형이 수백 %가 됩니다.

다루는 문제가 다릅니다. 이 도구는 이미 고르게 뿌려졌다고 보고 그때의 부하 불균형만 봅니다. 「어느 샤드로 보낼까」와 「샤드를 더하거나 뺄 때 얼마나 옮겨야 하는가」는 일관성 해싱·랑데부 해싱이 다루는 주제입니다.

전송되지 않습니다. 계산과 시뮬레이션 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.