パーティショニング（シャーディング）

定義

パーティショニング（シャーディング）：データセットを複数のサブセットに分割し、異なるノードに配置すること。

目的：単一ノードに収まらないデータ量や、単一ノードが処理できないクエリ負荷に対応する。

2つの基本戦略

キーレンジパーティション

Partition 1: A - G
Partition 2: H - N
Partition 3: O - T
Partition 4: U - Z

辞書順に隣接するキーが同じパーティションに入る。レンジスキャンが効率的。

-- 2024年の全センサーデータを取得（キーが「year-month-day-sensorId」形式）
SELECT * WHERE key BETWEEN '2024-01-01' AND '2024-12-31'
-- → 特定のパーティションだけアクセスすれば済む

問題：ホットスポット
タイムスタンプをキーにすると、常に「今日のパーティション」だけに書き込みが集中する。

対策：センサーIDをプレフィックスに追加して書き込みを分散させる。ただしレンジクエリは全パーティションに問い合わせが必要になる（トレードオフ）。

ハッシュパーティション

hash(key) % N で担当パーティションを決定

hash("user_001") → Partition 3
hash("user_002") → Partition 1
hash("user_003") → Partition 3

均等な分散。特定キーへのアクセス集中（ホットスポット）を防ぐ。

問題：レンジクエリが非効率（キーの順序が失われる）。MongoDBはハッシュインデックスでのレンジクエリを全パーティションブロードキャストで対応。

CassandraはハイブリッドアプローチをConcat主キーで実現：

PRIMARY KEY (user_id, timestamp)

user_idでハッシュパーティション → timestampでレンジソート。1ユーザーの時系列データを効率的に取得できる。

ホットスポット：有名人問題

通常ユーザーへの書き込み → 均等に分散

Justin Bieberのツイート（フォロワー1億）
  → キーが同じなので全書き込みが1パーティションに集中
  → ハッシュパーティションでも解決できない

対策：有名ユーザーのキーにランダムな2桁サフィックスを追加。書き込みは100パーティションに分散。ただし読み取り時は100パーティションを結合する必要がある。

二次インデックスのパーティション

ドキュメントベース（ローカルインデックス）

Partition 1のドキュメント → Partition 1のインデックスに記録
Partition 2のドキュメント → Partition 2のインデックスに記録

問題: 「color=redの車を検索」→ 全パーティションに問い合わせ（スキャッタ/ギャザー）

タームベース（グローバルインデックス）

color=red → Partition 1が担当
color=blue → Partition 2が担当

検索が効率的（1パーティションに問い合わせ）
問題: 書き込みが遅い（複数パーティションを更新する必要がある）

実際のシステムでは多くがローカルインデックスを採用し、書き込み速度を優先している。

リバランシング

ノードの追加・削除時にパーティションを再割り当てすること。

固定数のパーティション

最初に1000パーティション作成（ノード3台）
→ ノード1台追加時: 250パーティション移動するだけ
（パーティション数は変わらない）

ElasticsearchやRiakが採用。パーティション数はデータ量増加を見越して最初に大きめに設定する必要がある（後から変えられない）。

動的パーティション

データ量に応じてパーティションを分割・マージ。HBaseとMongoDB（キーレンジ分割）が採用。小さなデータセットから始められる。

ノード比例パーティション

ノード数に比例してパーティション数を決める。Cassandraが採用。新ノード追加時に既存ノードからパーティションをランダムに分割して引き取る。

パーティションとレプリケーションの組み合わせ

各パーティションは複数ノードに複製される

Node 1: Partition A (leader), Partition B (follower), Partition C (follower)
Node 2: Partition A (follower), Partition B (leader), Partition C (follower)
Node 3: Partition A (follower), Partition B (follower), Partition C (leader)

単一ノード障害で、どのパーティションにもフォロワーが残っている。

パーティションを意識したクエリルーティング

クライアント
  ↓
ルーティング層（どのノードに向けるか）
  ↓
対象ノード

戦略:
  1. クライアント側でルーティング（ドライバーが担当）
  2. ランダムノードに送って転送してもらう
  3. 専用ルーティング層（ZooKeeperなどでノードマップを管理）

出典・参考文献

Martin Kleppmann, Designing Data-Intensive Applications (2017) Chapter 6

定義