algorithm - 一貫性のあるハッシュに保証された公平なバリエーションはありますか?

Question

私はConsistent Hashingのようなものを探していますが、配布が可能な限り公平になることを保証します(ランダムキーの平均だけではありません)-そのようなものはありますか?もしそうならどこで見つけることができますか?

編集：私の特定のケースでは、キーのセットは事前にわかっています（そして「小さい」）。これらのキーは常に存在し、任意の時点でそれぞれ正確に 1 つのノードに割り当てる必要があります。

Answer 1

最小限の完璧なハッシュを探しているように私には聞こえます。

Answer 2

ランダムキーの平均だけでなく

これは、コンシステント ハッシュによって提供される保証の正確な説明ではありません。第 1 に、「平均」では、多数の仮想ノードをサークル上にランダムに配置し、ハッシュ関数の適切なファミリ (たとえば、対数的に独立したもの) を使用すると、負荷の不均衡が深刻になるという事実を捉えることができません。大きくなる可能性は低いです (通常の不均衡は、特定のマシンに割り当てられたキーの数の平方根のオーダーになるはずです)。第二に、ランダムに選択されたハッシュ関数に依存しない限り、鍵はランダムである必要はありません (無意識の敵対者)。

常に公正なハッシングが必要なため、ランダム化は役に立ちません。RNG の結果がこれと区別できない可能性があるためです。キーがオフラインで知られている場合を除き、不均衡の可能性なしに静的にノード設定をキーに割り当てることができる決定論的アルゴリズムはありません。

平方根の不均衡を気にするアイテムが十分に少ない場合は、昔ながらのステートフル ロード バランシングを行うことができます。