Multi-probe consistent hashing (2015)
September 6, 2025Karger et al.による原典のConsistent Hashingは、CDNやKVSのノードの負荷を分散するために、ノードとキーを単位区間のハッシュ値に写像し、ハッシュ値で比べたときの最近傍のノードにキーを割り当てる。 ノードの追加と削除を繰り返してもキーの保存数が均等になるように、1つのノードに複数のハッシュ値を割りあてる。 キーと最も近いハッシュ値のノードにキーを保存する。 ノードの負荷をノードに保存するキーの数とすると、最大の負荷と平均の負荷の比率を高確率(\(1-\frac{1}{n^{\Omega(1)}}\))で\(1+\epsilon\)に抑えるには、\(\Theta(\frac{\ln n}{\epsilon^2})\)のハッシュ値を各ノードに割り当てなければならず、空間計算量はノードの数より大きくなる。
Multi-probe consistent hashingは、ノードに複数のハッシュ値を割りあてずに、キーのハッシュ値を\(K\)個生成する。 その後、キーと後続のノードのハッシュ値の距離を比較し、最小の距離にあるノードにキーを割り当てる。 \(2\le K \ll \frac{\sqrt{n}}{\ln n}\)であれば、最大の負荷と平均の負荷の比率は、高確率(\(1-\frac{1}{n^{\Omega(1)}}\))で\(\frac{K}{K-1}\frac{1}{n}+o(\frac{1}{n})\)になる。 原典のConsistent Hashingはキーを最近傍のノードに割り当てるが、Multi-probe consistent hashingは、キーを後続のノードに割り当てる。