シャッフルシャーディングの確率論

なぜ普通のシャーディングでは足りないのか

マルチテナントなサービスで、n台のワーカ（サーバー）を用意し、各テナントを一部のワーカへ振り分ける状況を考えます。狙いは 障害分離（blast radius の限定） です。あるテナントが「毒」になったとき（壊れたリクエストでワーカをクラッシュさせる、リトライ嵐でCPUを焼く、など）、その毒が割り当て先のワーカにしか及ばないようにしたい。

素朴な方法は、n台をいくつかの 固定シャード に分割し、各テナントを1つのシャードに割り当てることです。例えばn=8台を4台ずつ2シャードに割れば、毒テナントは自分のシャード4台だけを壊し、もう片方の4台にいるテナントは無傷で済みます。

# 固定シャード方式（2シャード）
シャードA: [w1 w2 w3 w4]   ← テナント群A（毒テナントもここ）
シャードB: [w5 w6 w7 w8]   ← テナント群B（無事）

問題は、同じシャードに同居したテナントは運命共同体 になる点です。シャードAに100テナントいれば、毒テナント1人がそのシャードを落とした瞬間、残り99テナントが全滅します。シャード数を増やせば各シャードのテナント数は減りますが、シャードあたりのワーカも減るので冗長性が落ちる。「巻き込まれる人数」と「1テナントが使える台数」がトレードオフになり、固定分割だけでは両立できません。

シャッフルシャーディングの割り当て

シャッフルシャーディング（shuffle sharding）は、固定シャードを捨て、テナントごとに n台の中から重複なく k台を選ぶ。選び方はテナントIDのハッシュを乱数の種にした擬似ランダムで、同じテナントなら毎回同じ k台になります（決定的）。

# テナントごとに毎回同じ k台を選ぶ（決定的シャッフル）
def shard_for(tenant_id, all_workers, k):
    rng = seeded_rng(hash(tenant_id))   # テナントIDで種を固定
    return rng.sample(all_workers, k)   # n台から重複なくk台を選ぶ

選べる「シャード」の総数は、n台からk台を選ぶ 組合せ数 C(n, k) 通りです。固定シャード方式が n/k 個のシャードしか持てなかったのに対し、シャッフルシャーディングは指数的に多い仮想シャードを持てる。n=100、k=5 なら C(100,5) は約 7500万通り。これだけ選択肢があれば、2人のテナントが偶然まったく同じ5台を引く確率はごく小さくなります。これが効果の源泉です。

完全一致の確率を組合せ論で出す

毒テナントを1人固定し、その k台が決まっているとします。別のテナントが、毒テナントの k台と完全に一致する集合を引く確率 を求めます。

別テナントの集合も n台からk台の一様ランダム。全パターンは C(n, k) 通り。そのうち「毒テナントと完全一致」は ちょうど1通り なので、

# 2テナントの割り当てが完全一致する確率
P(完全一致) = 1 / C(n, k)

しかし本当に怖いのは「完全一致」だけではありません。実務上の関心は 「毒テナントの k台にどれだけ重なるか」 の分布です。被害テナントが毒テナントと j台を共有する確率は、毒の k台から j台を選び、残りを毒以外の n−k台から k−j台選ぶので、超幾何分布になります。

# 被害テナントが毒テナントと ちょうど j台 共有する確率（超幾何分布）
P(共有=j) = C(k, j) * C(n-k, k-j) / C(n, k)

この式から「1台も共有しない（j=0、つまり毒の影響をまったく受けない）」確率が読めます。

# 毒テナントと1台も共有しない確率
P(共有=0) = C(n-k, k) / C(n, k)

なぜ「一部重なり」は致命傷にならないのか

ここが確率論を実利に変える要点です。被害テナントが毒テナントと j台共有していても、j が k 未満なら、共有していない k−j台は健全 です。被害テナントのリクエストが健全ワーカにも振られ、かつクライアントが毒ワーカを避けてリトライできるなら、被害テナントは生き延びます。

# k=4 のとき、毒テナントとの共有台数ごとの生死
共有 0台 : 健全4台 → 完全に無傷
共有 1台 : 健全3台 → ほぼ無傷（毒1台を避ければよい）
共有 2台 : 健全2台 → 縮退するが稼働継続
共有 3台 : 健全1台 → 綱渡り（リトライ次第）
共有 4台 : 健全0台 → 完全巻き込み（これだけが致命）

したがって本当に避けたいのは 共有=k（完全巻き込み） だけ。その確率 1/C(n,k) を小さくすればよく、k を1つ増やすだけで C(n,k) が跳ね上がるため、効果は劇的です。

k を 2 から 5 にするだけで、完全に道連れになる確率は約5000分の1から7500万分の1へ、1万倍以上改善します。テナント専有（完全分離）はワーカ数がテナント数に比例して必要になり非現実的ですが、シャッフルシャーディングは固定 k台のコストで「ほぼ分離」に迫れる。これが 負荷分散アルゴリズム の上に薄く乗せるだけで効く理由です。

毒テナントが複数いるとき・前提条件

確率はテナント数が増えると効きが鈍ります。毒が1人でなく、テナント全体に占める「ある被害テナントを完全に巻き込みうる毒の組」を考えると、被害が出る期待値はテナント数 m とともに増えます。ざっくり、ランダムな2テナントが完全一致する確率が 1/C(n,k) なので、m テナントの中で完全一致ペアが現れる期待数は概ね m^2 / (2 * C(n,k)) 程度。m が C(n,k) の平方根を超えると衝突が現実味を帯びます（誕生日問題と同じ構造）。だからこそ k と n は、想定テナント数 m に対して C(n,k) が m の二乗を十分上回るよう選びます。

実務での位置づけ

シャッフルシャーディングは AWS が Route 53 や API ゲートウェイ系のサービスで採用し、Route 53 では各顧客ドメインを4台の権威ネームサーバーへ割り当てる際にこの方式を使うことで、1顧客へのDDoSが他顧客の名前解決を巻き込まないようにしています。考え方は L7ロードバランサ、コネクションプール、キューのワーカ群、レートリミッタのバケットなど、「テナント × リソース集合」の割り当てがある場所すべて に応用できます。

毒テナントそのものを止める仕組み（アダプティブな負荷遮断 など）と組み合わせると、「毒の影響を狭い集合に閉じ込め、その集合内でも遮断で被害を最小化する」二段構えになります。シャッフルシャーディングは確率で 巻き込まれる相手の数を減らす 設計、負荷遮断は 巻き込まれた後の被害を減らす 設計で、役割が補完的です。

まとめ

• 固定シャードはシャード内テナントが運命共同体になる。シャッフルシャーディングはテナントごとに n台から k台を決定的ランダムに選び、選択肢を C(n,k) 通りへ広げて完全一致を稀にする。
• 2テナントが完全一致する確率は 1/C(n,k)、共有台数の分布は超幾何分布 C(k,j)*C(n-k,k-j)/C(n,k) で表せる。k を1増やすだけで C(n,k) が跳ね上がり、完全巻き込み確率が桁で下がる。
• 致命的なのは共有=kの完全巻き込みだけ。一部重なりは健全ワーカが残るため、リトライで毒ワーカを避ければ生き延びられる。
• 確率の前提は「毒ワーカを避けて健全ワーカへ振り直せること」と「共有資源を持たないこと」。これが崩れると式どおりの隔離は得られない（リトライ予算と増幅、メタステーブル障害 も併読）。
• テナント数 m に対し C(n,k) が m の二乗を十分上回るよう n・k を選ぶ（誕生日問題の構造）。完全分離の高コストなしに、ほぼ分離に迫る隔離が得られる。