DB sharding & partitioning 完全ガイド 2025: 水平スケーリング、Range/Hash/Directory、resharding、Vitess

TL;DR

• sharding = 水平スケーリングの答え: 単一 DB で捌けない規模では必須
• shard key の選択が運命を決める: 選択を誤ると hot spot と resharding 地獄
• 3 大戦略: Range、Hash、Directory (Lookup) — それぞれに長所と短所
• 分散トランザクションが難しい: 2PC は遅い、Saga が現実的
• Vitess が標準: YouTube/Slack/GitHub が使用。MySQL 上の分散レイヤー

1. sharding とは?

1.1 単一 DB の限界

[Single DB]
  ├─ CPU: 1 台分まで
  ├─ RAM: 256GB? 512GB?
  ├─ Disk: 30TB
  └─ Network: 25 Gbps

→ いずれ限界に到達

vertical scaling:

• より大きなマシン
• 限界がある (最大の EC2 = 24TB RAM、$20+/時間)
• 単一障害点

horizontal scaling:

• 複数のマシン
• 無限にスケール
• 複雑度が増す

1.2 read replica で解決?

[Primary] (書き込み)
   ↓ replication
[Replica 1] [Replica 2] [Replica 3] (読み取り)

効果: 読み取りトラフィックを分散。

限界: 書き込みは依然として Primary 1 台。書き込みがボトルネックなら役に立たない。

→ sharding が必要。

1.3 sharding の定義

sharding = データを複数の独立した DB (shard) に分散すること。

[users テーブル]
  ↓ shard by user_id
[Shard 1: user_id 1-1M]
[Shard 2: user_id 1M-2M]
[Shard 3: user_id 2M-3M]
...

各 shard は 完全に独立 した DB。固有の CPU、RAM、ディスクを持つ。

1.4 sharding の効果

100 倍の性能 + 5 倍のコスト = ROI は良好。ただし 複雑度が大きな問題。

2. shard key の選択 — 最も重要な決定

2.1 良い shard key の条件

1. 均等分布 — 全 shard に均等に分散
2. 不変 — 一度決まったらほぼ変わらない
3. クエリパターンと一致 — 一緒に参照されるデータは同じ shard に
4. カーディナリティが高い — 十分な数のユニーク値
5. 単調増加しない — auto-increment ID は hot spot のリスク

2.2 よくある shard key 候補

user_id:

• ユーザーのデータを 1 つの shard にまとめる (関連データが一緒)
• 大規模ユーザーが hot spot に
• user 間の JOIN が難しい

created_at:

• 単調増加 → すべての新データが 1 つの shard に (hot spot)
• 時系列データには OK

hash(id):

• 均等分布
• 範囲クエリ不可
• 関連データが別 shard に

country:

• geographic な効率性
• 非常に不均等 (US は巨大、モナコは小さい)

organization_id:

• B2B SaaS に最適
• 大規模組織が hot spot に

2.3 Slack のケース

Slack の shard key = workspace_id。

理由:

• 同じ workspace のすべてのデータを 1 つの shard に → 高速参照
• workspace 間の JOIN はほとんどない
• workspace 単位で自然な隔離

欠点: 巨大な enterprise workspace が単一 shard を圧倒する → "Whale shard" 問題。

解決: 巨大 workspace には専用 shard を割り当てる。

3. sharding 戦略

3.1 Range sharding

データを key の 範囲 で分割。

Shard 1: id 1 ~ 1,000,000
Shard 2: id 1,000,001 ~ 2,000,000
Shard 3: id 2,000,001 ~ 3,000,000

長所:

• 範囲クエリが効率的 (WHERE id BETWEEN 500000 AND 600000)
• ルーティングがシンプル
• 新しい shard を追加しやすい

短所:

• hot spot リスク: 単調増加 key だと新データがすべて最後の shard に
• 不均等分布になりうる

ユースケース: 時系列データ、BigTable、HBase

3.2 Hash sharding

shard key の hash で分割。

shard_id = hash(user_id) % num_shards

長所:

• 均等分布 — hash が良ければ
• 単調増加 key でも安全

短所:

• 範囲クエリ不可 (WHERE id BETWEEN ...)
• shard 追加時にほぼ全データの再配分が必要 (% num_shards が変わるため)

解決: Consistent Hashing — shard の追加/削除時に一部のデータのみ移動。

3.3 Consistent Hashing

[円形ハッシュ空間]
        Shard A
       /
  Shard D
       \
        Shard B
       /
  Shard C

各 shard とデータを同じハッシュ空間にマッピング。データは時計回りで最も近い shard へ。

shard 追加時: 該当部分のみ再配分 (全体の 1/N)。

Virtual Nodes: 各 shard を複数の仮想ノードで表現 → より均等な分布。

使用: Cassandra、DynamoDB、Riak、Memcached。

3.4 Directory-based sharding

lookup テーブル でどのデータがどの shard にあるかを明示的にマッピング。

[Lookup]
user_1 → Shard A
user_2 → Shard B
user_3 → Shard A
...

長所:

• 柔軟: 任意のマッピングが可能
• 不均等な分布にも対応
• マイグレーションが容易

短所:

• lookup 自体がボトルネック (キャッシュ必須)
• 追加のインフラ (Redis、Consul)
• 単一障害点

使用: Vitess (このアプローチの変形)

3.5 Geographic sharding

位置ごとの shard:

• US ユーザー → US shard
• EU ユーザー → EU shard
• Asia ユーザー → Asia shard

長所:

• ユーザーに近い → 低 latency
• 規制遵守 (GDPR — EU データは EU に)
• 自然な分割

短所:

• ユーザー移動時に困難
• グローバルクエリが難しい
• 非常に不均等 (地域ごとのユーザー数)

3.6 比較表

4. Hot spot 問題

4.1 Hot spot とは?

特定の shard にトラフィックやデータが集中する現象。

原因:

• 誤った shard key (人気ユーザー、人気商品)
• 単調増加 key (created_at)
• 不均等な分布 (少数の巨大組織)

4.2 影響

[Shard 1: トラフィック 10%]
[Shard 2: トラフィック 5%]
[Shard 3: トラフィック 80%] ← Hot spot! 死亡
[Shard 4: トラフィック 5%]

システム全体が 最も弱い shard で決まる。

4.3 検出

-- shard 別データ量
SELECT shard_id, COUNT(*) as row_count
FROM users
GROUP BY shard_id;

-- shard 別クエリ数 (アプリケーションメトリクス)

警告サイン:

• 1 つの shard が平均より 5 倍以上大きい
• 1 つの shard の CPU/IO が 100%

4.4 解決策

1. shard key の変更

• 最良だが最も困難 (resharding が必要)

2. Composite key

shard_key = hash(user_id + timestamp_bucket)

時間ベース + ユーザーベースの組み合わせ。

3. Sub-sharding

• Hot shard をさらに細かく分割
• "Whale shard" の処理

4. キャッシュ

• ホットデータを Redis に
• DB 負荷を軽減

5. read replica

• 読み取り負荷を分散
• 書き込みは依然 hot

4.5 例: Twitter の Celebrity Problem

問題: セレブユーザー (例: イーロン・マスク) がツイート → 数億 followers の timeline を更新。

解決:

• Fan-out on write (一般ユーザー): ツイート時に followers の timeline に事前に書き込む
• Fan-in on read (セレブ): ツイート時に timeline を作らず、読み取り時に取得
• ハイブリッド: アクティブな followers は fan-out、非アクティブは fan-in

5. 分散クエリの難しさ

5.1 単一 shard クエリ

SELECT * FROM users WHERE user_id = 12345;

→ user_id で shard を決定 → その shard のみクエリ。非常に高速。

5.2 Cross-shard クエリ

SELECT COUNT(*) FROM users WHERE country = 'KR';

→ 全 shard にクエリ → 結果を合計。遅い + 負荷。

5.3 JOIN の難しさ

SELECT u.name, o.total
FROM users u
JOIN orders o ON o.user_id = u.user_id
WHERE u.country = 'KR';

users と orders が別々の shard にある場合は? 分散 JOIN が必要。

戦略:

1. Co-location: 同じ user_id の users と orders を同じ shard に
2. Denormalization: orders に user 情報をコピー
3. 分散クエリエンジン: Vitess、Citus が自動処理
4. CQRS: クエリ用に別の DW (Snowflake) を使用

5.4 分散トランザクション

def transfer(from_user, to_user, amount):
    # 2 ユーザーが別 shard にある可能性
    db.update(f"... WHERE user_id={from_user}", -amount)
    db.update(f"... WHERE user_id={to_user}", +amount)

問題: 最初の update 成功 + 2 回目失敗 → お金が消える。

解決:

1. 2PC (Two-Phase Commit):

• Prepare → Commit
• すべての shard が同意すれば commit
• 遅い + 単一障害点 → 非推奨

2. Saga パターン:

• 補償トランザクション
• Eventually consistent
• 実践の標準

3. 同じ shard に収める:

• 可能なら送信者/受信者を同じ shard に
• 常に可能とは限らない

6. resharding — 最も恐ろしい作業

6.1 なぜ resharding は難しいのか?

• データ移動: 数十 TB を移動
• 無停止: ユーザーに影響なし
• ロールバック: 問題発生時のリカバリ
• 一貫性: 移動中の書き込み/読み取りの処理

6.2 resharding シナリオ

1. shard の追加: 4 shard → 8 shard 2. shard の分割: 巨大な shard を 2 つに 3. shard の統合: 小さい shard を合併 4. shard key の変更: 最難関

6.3 resharding パターン

1. Bulk Copy + Switchover:

1. 新しい shard にデータをコピー
2. 短い maintenance window
3. トラフィックを切り替え
4. 旧 shard を削除

欠点: ダウンタイム。

2. CDC + Dual Write:

1. CDC で旧 → 新 shard を同期
2. アプリケーションが旧 + 新の両方に書き込み (dual write)
3. データの一致確認
4. 読み取りを新に切り替え
5. 旧 shard を廃止

無停止、ただし複雑。

3. Online Migration:

• Vitess の VReplication
• 自動化された無停止マイグレーション
• 進捗モニタリング

6.4 事例: Slack の sharding 進化

• 2017: 単一 MySQL → replica
• 2018: 初回 sharding (workspace_id)
• 2020: Vitess 導入
• 2022: whale workspace 対応
• 2024: 数千 shard、ペタバイト

教訓: sharding は一度で終わらない。継続的な進化。

7. Vitess — MySQL 上の分散レイヤー

7.1 Vitess とは?

YouTube が作った MySQL sharding ソリューション。CNCF 卒業。

[Client]
   ↓
[VTGate] (クエリルーター)
   ↓
[VTTablet] [VTTablet] [VTTablet]
   ↓        ↓          ↓
[MySQL]  [MySQL]    [MySQL]

長所:

• MySQL 互換 — 既存コードそのまま
• 自動 sharding — key ベースのルーティング
• スキーママイグレーション — 安全な DDL
• VReplication — 無停止 resharding
• 実績ある規模 — YouTube、Slack、GitHub、Square

7.2 使用企業

• YouTube (創始者、ペタバイト)
• Slack (大規模)
• GitHub (MySQL → Vitess に移行)
• Square
• Pinterest
• JD.com (中国最大の e-commerce)

7.3 VSchema 例

{
  "sharded": true,
  "vindexes": {
    "hash": {
      "type": "hash"
    }
  },
  "tables": {
    "users": {
      "column_vindexes": [
        {
          "column": "user_id",
          "name": "hash"
        }
      ]
    }
  }
}

→ VTGate が user_id ベースで自動的に sharding。

8. 他の分散 DB オプション

8.1 Citus (PostgreSQL)

PostgreSQL の拡張。分散クエリ、分散トランザクションをサポート。

SELECT create_distributed_table('events', 'user_id');

長所: PostgreSQL 互換、SQL そのまま。 短所: PostgreSQL の限界 (Vitess より成熟度が低い)。

8.2 CockroachDB

最初から分散 SQL DB として設計。

長所:

• PostgreSQL 互換
• 自動 sharding (range-based)
• グローバル分散 をサポート
• 分散 ACID トランザクション

短所:

• 一部の PG 機能が未対応
• 運用コストが高い
• 学習曲線

使用: DoorDash、Bose、Comcast。

8.3 YugabyteDB

CockroachDB と類似。PostgreSQL 互換 + Cassandra 互換 を同時に実現。

8.4 TiDB

MySQL 互換 + 自動分散。中国で人気。

8.5 比較表

9. 実践 — e-commerce sharding 設計

9.1 シナリオ

• 1 億ユーザー
• 1 日 1000 万注文
• 単一 PostgreSQL が限界に到達

9.2 分析

テーブル:

• users (1 億行)
• orders (10 億行)
• products (100 万行)
• reviews (50 億行)

9.3 sharding の決定

1. users:

• shard key: user_id (hash)
• 16 shard
• 均等分布

2. orders:

• shard key: user_id (hash、users と同じ shard)
• 同じユーザーの user + orders が同じ shard に → JOIN が高速

3. products:

• 小規模 (100 万行)
• sharding しない — 単一 DB + read replica
• またはすべての shard に複製

4. reviews:

• shard key: product_id (hash)
• product 基準の分析に適合

9.4 クエリパターン

-- ユーザーの注文 (同じ shard)
SELECT * FROM orders WHERE user_id = 12345;
-- 高速

-- ユーザー情報 + 注文 (同じ shard、JOIN OK)
SELECT u.*, o.*
FROM users u JOIN orders o ON o.user_id = u.user_id
WHERE u.user_id = 12345;
-- 高速

-- 商品レビュー (別 shard)
SELECT * FROM reviews WHERE product_id = 67890;
-- 高速

-- ユーザーが書いたすべてのレビュー (cross-shard)
SELECT * FROM reviews WHERE user_id = 12345;
-- 遅い — すべての reviews shard を検索

-- 解決: 非正規化。users shard にもレビューサマリを保存。

9.5 インフラ

[Application]
    ↓
[ProxySQL / Vitess]
    ↓
[16 user shards]
[16 order shards (co-located)]
[1 products DB + 5 read replicas]
[8 reviews shards]

9.6 モニタリング

• shard 別クエリ数
• shard 別ディスク使用量
• cross-shard クエリの比率
• hot spot の検出

10. sharding の落とし穴と教訓

10.1 早すぎる sharding

誤った決定: トラフィックが 1000 QPS なのに sharding。

現実:

• 単一 PostgreSQL = 50,000 QPS+
• read replica = 200,000 QPS+
• 適切なインデックス + キャッシュ = さらに多く

→ sharding する前に、他のすべての最適化を先に試すこと。

10.2 誤った shard key

GitHub の 最初の sharding 試行 が失敗した事例:

• repo_id で sharding → 人気 repo が hot spot に
• Linus の linux repository が単一 shard を圧倒
• resharding が必要 (数ヶ月の作業)

教訓: shard key は 変更が非常に困難。最初から慎重に。

10.3 分散トランザクションの回避

分散トランザクションは本当に難しい。可能な限り 同じ shard 内でのみトランザクション を保証する。

設計時: 書き込みトランザクションが常に単一 shard に収まるようデータモデルを設計する。

10.4 運用の複雑さ

sharding したシステムは:

• バックアップが複雑 (16 shard を同時に)
• モニタリングが複雑
• デバッグが困難 (どの shard?)
• マイグレーションが困難

→ 自動化 が必須。運用人員を十分に。

10.5 NewSQL が答えか?

CockroachDB、YugabyteDB のような NewSQL は自動 sharding + 分散トランザクションを提供。手動 sharding の複雑さがない。

NewSQL を選ぶとき:

• 新規プロジェクト
• 強い一貫性が必要
• 運用人員が不足

手動 sharding を選ぶとき:

• 既存の MySQL/PostgreSQL
• 極端な性能が必要
• NewSQL の成熟度が懸念

クイズ

参考資料

• Designing Data-Intensive Applications — Martin Kleppmann (sharding 章)
• Vitess — YouTube 公式
• Citus Data
• CockroachDB Docs
• YugabyteDB
• TiDB
• Slack's Data Stores — Vitess マイグレーション
• GitHub MySQL → Vitess
• Stripe's Sharding Approach
• Discord's Trillion Messages — Cassandra 使用
• Pinterest Sharding