固定パーティション

問題

データをクラスターノードのセットに分割するには、それぞれのデータアイテムをそれらのノードにマッピングする必要があります。データをクラスターノードにマッピングするためには、2 つの要件があります。

• 分散は均一であるべきです。
• すべてのノードにリクエストを行わなくても、特定のデータアイテムが格納されているクラスターノードを知ることができる必要があります。

多くのストレージシステムの適切なプロキシであるキーバリューストアを考えてみましょう。ハッシュキーを使用して剰余演算を実行し、クラスターノードにマッピングすることで、両方の要件を満たすことができます。 3 ノードのクラスターがある場合、次のようにキーの Alice、Bob、Mary、Philip をマッピングできます。

† ノードインデックス = ハッシュ %3

ただし、この方法ではクラスターサイズが変更されると問題が発生します。クラスターに 2 つのノードを追加すると、5 つのノードができます。その場合、マッピングは次のようになります。

† ノードインデックス = ハッシュ % 5

この方法では、ほとんどすべてのキーのマッピングが変更されます。わずか数個の新しいクラスターノードを追加しただけでも、すべてのデータを移動する必要があります。データサイズが大きい場合、これは望ましくありません。