データ量やアクセス負荷が増大すると、単一データベースでは限界が訪れます。その解決策がシャーディング（Sharding）です。しかし、単にデータを分割するだけでは不十分で、どのようなアルゴリズムで分割するかがシステムの将来を左右します。本記事では、シャーディングアルゴリズム設計の理論と実践を体系的に解説します。
シャーディングとは何か？
シャーディングとは、データを複数の物理ノード（Shard）に分散配置することで、水平スケーリング（Horizontal Scaling）を実現する手法です。
基本構造：
Client ↓ Shard Router ↓ +---------+ +---------+ +---------+ | Shard A | | Shard B | | Shard C | +---------+ +---------+ +---------+ 重要なのは、どのデータをどのShardに配置するかを決めるアルゴリズムです。
代表的なシャーディングアルゴリズム
① レンジベース（Range Sharding）
特定の値範囲ごとにShardを分ける方式です。
Shard A: user_id 1 - 1,000,000 Shard B: user_id 1,000,001 - 2,000,000 メリット
- レンジ検索が高速
- 実装が単純
デメリット
- ホットスポットが発生しやすい
- 後方Shardにアクセス集中のリスク
例：AUTO_INCREMENTのIDは最新Shardに集中する。
② ハッシュベース（Hash Sharding）
キーをハッシュ化し、Shard数で割る方式。
shard_id = hash(user_id) % N メリット
- データ分布が均等になりやすい
- ホットスポット回避に強い
デメリット
- Shard追加時に大規模再配置が発生
Shard数が3→4に増えると、ほぼ全データ再ハッシュが必要になります。
③ コンシステントハッシュ（Consistent Hashing）
分散システムで広く使われる高度なアルゴリズム。
キーとShardを同一ハッシュリング上に配置します。
hash(key) → リング上の位置 → 時計回りに最初に出会うShardへ配置 メリット
- Shard追加時の再配置データが最小限
- スケールアウトに強い
デメリット
- 実装が複雑
- 仮想ノード設計が必要
クラウドネイティブDBや分散キャッシュ（Redis Clusterなど）で採用。
シャーディングキー設計が最重要
アルゴリズム以前に、何をシャーディングキーにするかが最も重要です。
良いキーの条件
- 高いカーディナリティ
- アクセス分布が均一
- JOINを減らせる設計
悪い例
- 都道府県コード（値が47しかない）
- 日付（特定日付に集中）
JOIN問題と分散トランザクション
シャーディング最大の難所はクロスShard JOINです。
- アプリ側でJOIN処理を実装
- データ重複（非正規化）で回避
- グローバルインデックス設計
分散トランザクションは2PC（Two Phase Commit）が必要になり、性能劣化の原因になります。
高度設計：ハイブリッド戦略
実務では単純な方式ではなく、組み合わせが使われます。
- レンジ × ハッシュ（リージョン分割＋内部均等化）
- テナント単位シャーディング（SaaS向け）
- Read Replica + Sharding
数理的観点：均等分布の期待値
ハッシュ分布のばらつきは近似的にポアソン分布に従います。
Shard数を ( N )、データ数を ( M ) とすると、
[ 期待値 = \frac{M}{N} ]
分散：
[ \sigma^2 = \frac{M}{N} ]
Shard数が増えると分散も増えるため、仮想ノードで均等化する設計が必要になります。
設計判断フレームワーク
| 要件 | 推奨方式 |
|---|---|
| 検索がレンジ中心 | レンジベース |
| アクセス均等性重視 | ハッシュ |
| 頻繁なスケールアウト | コンシステントハッシュ |
| SaaSマルチテナント | テナント単位シャーディング |
まとめ
シャーディングアルゴリズム設計は、単なる分割技術ではありません。システムのスケーラビリティ、可用性、保守性を左右するアーキテクチャの核心です。
- レンジ・ハッシュ・コンシステントの特性を理解する
- シャーディングキー設計が最重要
- JOINとトランザクション戦略を事前に検討
- 将来のスケールアウトを見越した設計を行う
本質は「今の負荷」ではなく、3年後の負荷に耐えられる構造を作ることです。
