要約

この章では、大きなデータセットをより小さなサブセットに分割するパーティショニングを扱います。データが大量にあり、それを1台のマシンに保存して処理することがもはや不可能な場合に必要です。

パーティショニングの目的は、データとクエリの負荷を複数のマシンに均等に分散し、ホットスポット（負荷が不均衡に高いノード）を避けることです。そのためには、データに適したパーティショニング・スキームを選択し、クラスタにノードを追加または削除したときにパーティションのバランスを調整する必要があります。

前の章

前の章である第5章 レプリケーションはこちらです。

パーティショニング

パーティショニングとレプリケーション

一般的にパーティションはレプリケーションと組み合わされるため、各パーティションのコピーが複数のノードに保存されます。
つまり、各レコードは1つのパーティションに属していますが、フォールトトレランスのために複数の異なるノードに格納される可能性があります。

各ノードは複数のパーティションを格納できます。リーダー・フォロワーレプリケーションモデルを使用する場合、パーティショニングとレプリケーションの組み合わせは上図のようになります。

各パーティションのリーダーは1つのノードに割り当てられ、そのフォロワーは他のノードに割り当てられます。各ノードは、一部のパーティションのリーダーであり、他のパーティションのフォロワーになります。

パーティショニングの問題点

パーティションの目標は、データとクエリの負荷をノード全体に均等に分散することです。

もしパーティショニングが不公平で、あるパーティションが他のパーティションより多くのデータやクエリを持つ場合、それをスキューと呼びます。
スキューがあると、パーティショニングの効果はかなり低下します。
極端な場合、すべての負荷が1つのパーティションに集中し、10ノード中9ノードがアイドル状態になり、ボトルネックはビジー状態の1ノードになります。

不均衡に高い負荷がかかるパーティションはホットスポットと呼ばれます。
ホットスポットを避けるためにレコードをランダムにノードに割り当てる方法があります。

しかし、これには大きな欠点があります。特定のアイテムを読み込もうとするとき、それがどのノードにあるのかを知る方法がないため、すべてのノードに並行して問い合わせなければなりません。

キーバリューデータのパーティショニング

単純なキー・バリュー・データモデルがあり、常に主キーでレコードにアクセスする方法を使用します。
たとえば、すべての項目はタイトルでアルファベット順にソートされた状態を仮定すると、探している項目をすぐに見つけることができます。

キーの範囲に基づくパーティショニング

パーティショニングの1つの方法は各パーティションに連続したキーの範囲を割り当てます（例えば、本の巻数）。
範囲の境界がわかっていれば、どのパーティションにどのキーが含まれているかを簡単に判断できます。どのパーティションがどのノードに割り当てられているかも知っていれば、適切なノードに直接リクエストすることができます。

キーの範囲に基づくパーティショニングの欠点は、特定のアクセスパターンがホットスポットにつながる可能性があることです。

例として、キーがタイムスタンプの場合、パーティションは時間の範囲に対応するので、計測が行われるたびにセンサーからデータベースにデータを書き込みます。その時、すべての書き込みが同じパーティション（同じ日のパーティション）に集中してしまいます。

DWHでよく使用されるGoogle CloudのBigQueryでは、この範囲に基づくパーティションが使用されているようです。

キーのハッシュに基づくパーティショニング

上記のようなスキューやホットスポットのリスクがあるため、多くの分散データストアでは、与えられたキーのパーティションを決定するためにハッシュ関数を使用しています。

これは、パーティション間でキーを公平に分配するのに適しています。
パーティションの境界は等間隔にすることもできるし、擬似的にランダムに選ぶこともできます。

しかし、デメリットとして、効率的な範囲クエリの機能が失われてしまいます。隣接していたキーが全てのパーティションに散らばってしまい、ソート順がわからなくなってしまいます。

パーティションのリバランシング

全ての変更は、データとリクエストをあるノードから別のノードに移動させることを要求します。クラスタ内のあるノードから別のノードに負荷を移動するプロセスをリバランシングと呼びます。

リバランスの戦略

パーティションをノードに割り当てる方法はいくつかあります。

①ハッシュの剰余(ハッシュ mod N)をしない
ハッシュ mod Nアプローチの問題点は、ノードの数Nが変わると、ほとんどのキーをあるノードから別のノードに移動する必要があるからです。

例えば、123456とすると
ノード数が10の場合、このキーはノード6から始まる（123456 mod 10 = 6）。ノード数が11になると、キーはノード3に移動する必要があります。（123456 mod 11 = 3）

②パーティション数の固定
クラスタにノードが追加されると、パーティションが再び公平に分散されるまで、新しいノードはすべての既存ノードからいくつかのパーティションを奪うことができます。
クラスタからノードが削除されると、同じことが逆に起こります。

③動的なパーティショニング
パーティションの境界を手動で再設定するのは非常に面倒です。
動的なパーティショニングを使うことでパーティション数がデータ総量に適応します。データ量が少なければ、少ないパーティション数で十分なため、オーバーヘッドも小さくなるという利点があります。

ただし、空のデータベースは、パーティションの境界をどこに引くかという情報が無いため、単一のパーティションで始まるケースがあるので注意が必要です。

まとめ

以上、パーティショニングについて解説しました。

一般的にパーティションは前章で登場したレプリケーションと組み合わされます。各パーティションのコピーが複数のノードに保存されることで検索性や可用性が高くなったりします。

パーティショニングが必要になるのは、データが大量にあり、それを1台のマシンに保存して処理することがもはや不可能な場合です。

パーティショニングについて特に重要な点を解説しました。ただし、非常に量が多いため解説していない部分が多々あります。詳細は本書を手にとってみて下さい。