シャーディング方式：レンジ vs ハッシュ vs ディレクトリ

シャーディング方式を分ける3つの軸

シャーディングとは、1つの大きなデータ集合をシャードキーに基づいて複数のサーバー（シャード）へ水平分割することです。どのキーをどのシャードへ置くかを決める「割り当て関数」の選び方が、性能特性をほぼ決定づけます。実用上の選択肢は大きく3系統に分かれます。

• レンジ分割（range）: シャードキーの値域を連続した区間に切り、[a, b) のような帯ごとにシャードへ割り当てる。
• ハッシュ分割（hash）: キーをハッシュ関数に通し、その出力でシャードを決める。連続したキーが意図的に散らばる。
• ディレクトリ分割（directory / lookup）: キーとシャードの対応を明示的なルックアップ表で持ち、表を引いて宛先を決める。

この3つを評価する軸は主に (1) 再分散コスト、(2) ホットスポット耐性、(3) 範囲クエリ適性 の3つです。順に原理を見ていきます。

レンジ分割：境界で切る

レンジ分割は、シャードキーの値域を順序付きの区間に切ります。たとえばタイムスタンプを 2026-01、2026-02… の月ごとに、あるいはユーザー ID を 1–999999、1000000–1999999… の帯に割り当てます。各シャードは境界キー（split key）の組で表現され、メタデータとして「どの区間がどのシャードか」を保持します。

宛先の決定は、キーが属する区間を二分探索で引くだけで O(log P)（P はパーティション数）で済みます。

境界テーブル（ソート済み）
  (-∞, 1000000)        -> shard A
  [1000000, 2000000)   -> shard B
  [2000000, 3000000)   -> shard C
  [3000000, +∞)        -> shard D

key=1500000 -> 二分探索で [1000000,2000000) -> shard B

最大の利点は範囲クエリの局所性です。WHERE id BETWEEN 1200000 AND 1300000 のような問い合わせは単一シャード（または隣接する少数のシャード）で完結し、連続スキャンが効きます。時系列データの「直近1週間」取得などはレンジ分割の独擅場です。

ハッシュ分割：散らして均す

ハッシュ分割は、キーを h = hash(key) に通し、その値でシャードを決めます。良いハッシュ関数は出力を一様分布させるため、連続したキーが別々のシャードへ散り、負荷とデータ量が均等になりやすいのが本質的な強みです。末尾ホットスポットは構造的に起きません。

問題は再分散コストで、ここで素朴な実装と洗練された実装が分かれます。最も単純な shard = hash(key) % N（mod N 方式）は、シャード数 N が変わった瞬間に剰余の周期が変わり、ほとんどのキーが別シャードへ移動します。10台を11台にしただけで9割近いキーが再配置対象になる計算で、運用中のシステムでは破綻します。

実務ではこれを避けるため、固定スロットを挟みます。物理シャード数とは独立に、ハッシュ空間をあらかじめ多数のスロット（仮想ノード／トークン）に分け、スロットを物理シャードへ割り当てる二段構えにするのです。

key -> hash -> slot（固定多数、例 4096個）-> シャード（可変少数）

slot = hash(key) % 4096          # スロット数は不変
shard = slot_to_shard[slot]      # 割り当て表だけを書き換える

シャードを増減するときはスロットの割り当てだけを付け替えます。動くのは移譲したスロットぶんのデータだけで、移動量は全体の約 1/N に抑えられます。これがコンシステントハッシュ法の発想で、Cassandra や DynamoDB 系の分散ストアが採用する標準解です。

ディレクトリ分割：対応表で明示する

ディレクトリ分割は、割り当てを関数で計算する代わりに、キー（またはキー群）→ シャードの対応を独立したルックアップサービスに持たせます。書き込み・読み取りの前にまず表を引き、宛先シャードを得てから本体へアクセスします。

最大の利点は柔軟性です。任意のキーを任意のシャードへ置けるため、ホットなテナントだけを専用シャードへ隔離する、容量の空いたシャードへ個別に寄せる、といった運用が表の更新だけで可能です。再分散も「表のエントリを書き換えて該当データを移す」だけで、関数の制約に縛られません。

ルックアップ表（テナント単位の例）
  tenant=ACME    -> shard C （大口・専用）
  tenant=foo     -> shard A
  tenant=bar     -> shard A
  tenant=baz     -> shard B  （旧 A から個別移動）

参照のたびに表を引いてから本体へ

代償は間接層のコストです。表は全アクセスの経路上にあるため、可用性とレイテンシのボトルネックになりえます。表を持つサービスが落ちれば全体が止まる単一障害点になりかねず、実際には表自体をレプリケーション・キャッシュして守る必要があります。表が巨大になりすぎないよう、行単位ではなくテナントや範囲のまとまり単位で対応を持つのが定石です。

3方式の対比

実システムは純粋な1方式とは限りません。たとえば「テナントはディレクトリで振り分け、テナント内はレンジ」のような複合方式が一般的です。

自動分割（split）と自動マージ（merge）の原理

レンジ分割系のストアは、データの増減に応じてパーティションを動的に分割・統合します。これが自動シャーディングの中核です。

自動分割（split） は、あるパーティションのサイズや負荷がしきい値を超えたとき、その区間を二分する処理です。境界をどこに置くかが肝で、キーが偏在していると単純な中点では均等になりません。実装は**中央値に近いキー（median key）**を選んで分割点とします。

split の擬似コード

if partition.size > SPLIT_THRESHOLD:
    mid = approximate_median_key(partition)   # サンプリングで近似
    left  = partition.range_below(mid)        # [start, mid)
    right = partition.range_from(mid)         # [mid, end)
    metadata.replace(partition, [left, right])
    schedule_move(right, pick_target_shard()) # 片方を別シャードへ移す

ポイントは、分割が境界メタデータの更新であり、データ本体を物理的に並べ替える必要が原則ない点です。区間が二つに割れ、片方の担当が新しいシャードへ移譲されるだけなので、影響は局所に閉じます。中央値はストレージの統計（ヒストグラムやサンプリング）から近似します。

自動マージ（merge） はその逆で、隣接する小さなパーティションを統合します。古いデータの削除や TTL でスカスカになった区間を放置するとパーティション数だけが膨れ、メタデータと管理コストが無駄に増えるためです。マージはキー順で隣接するパーティション同士でしか行えません（区間の連続性を保つ必要があるため）。ハッシュ分割では隣接概念が値域上にないので、マージは主にレンジ系の操作です。

まとめ