アムダール則・ガスタフソン則とスケーラビリティの限界

コアを倍にしても速度が倍にならない理由

サーバーのコア数を2倍にしたのに処理は1.6倍にしかならない、ノードを増やしてもある台数から先はスループットが伸びず、むしろ悪化する——スケールアウトに携われば必ず遭遇する現象です。これは構成ミスや実装の粗さだけが原因ではなく、並列計算に普遍的に働く数理的な天井 です。

その天井を最初に定式化したのが アムダール則、別の前提で楽観的に塗り替えたのが ガスタフソン則、そして現実の分散システムに潜む競合と協調のコストまで織り込んだのが USL（Universal Scalability Law、普遍スケーラビリティ則） です。本記事はこの3つを数理から接続し、「どこまでスケールできるか」を見積もる土台を与えます。

アムダール則：逐次部分が加速を縛る

ある処理のうち、並列化できる割合を p、どうしても逐次実行せざるを得ない割合を f = 1 − p とします。プロセサ数を N 倍にしたときの加速率（スピードアップ）S(N) は次式です。

S(N) = 1 / ( f + (1 − f)/N )

並列部分だけが N で割られて短縮され、逐次部分 f はいくら N を増やしても縮みません。ここで N を無限大に飛ばすと、第2項が消えて次の上限に達します。

S(∞) = 1 / f

逐次部分がわずか5%（f = 0.05）あるだけで、無限のプロセサを投入しても加速率は最大20倍 で頭打ちします。10%なら10倍が天井です。これがアムダール則の核心で、並列化の効果は最も並列化しにくい一点に支配される ことを意味します。

逐次割合 f	上限 S(∞)=1/f	N=16での加速率	N=256での加速率
0.01	100倍	約13.9倍	約72倍
0.05	20倍	約9.1倍	約18.6倍
0.10	10倍	約6.4倍	約9.7倍
0.25	4倍	約3.4倍	約3.9倍

f = 0.05 の行を見ると、コアを16から256へ16倍に増やしても加速率は9.1倍から18.6倍にしか伸びず、上限20倍にじりじり漸近するだけです。コアを足すほど1コアあたりの貢献が逓減 していく、典型的な収益逓減の構図です。

ガスタフソン則：規模拡大という別の前提

アムダール則は 問題サイズを固定 して「同じ仕事をどれだけ速く終えられるか」を問います。しかし実務でプロセサを増やす動機は、たいてい「より大きな問題を同じ時間で解きたい」ことです。この前提の違いに着目したのが ガスタフソン則 です。

問題規模を N プロセサに応じて拡大し、逐次部分の実行時間は規模によらずほぼ一定、並列部分だけが規模とともに増えると考えます。規模拡大後の逐次時間比率を f' とすると、加速率（スケールド・スピードアップ）は次式になります。

S(N) = N − f' × (N − 1)

この式は N に対して線形に伸びます（傾きは 1 − f'）。たとえば f' = 0.05 なら S(N) = N − 0.05(N−1) ≒ 0.95N + 0.05。N=256 で約243倍と、アムダール則の18.6倍とは桁違いの楽観的な値になります。

強スケーリングと弱スケーリングという用語で整理すると、どちらの法則が効くかが明確になります。

USL：競合と一貫性が頭打ちを越えて悪化させる

アムダール則は逐次部分しか織り込みませんが、現実の並列・分散システムにはもう一つのコストがあります。プロセサ同士が共有資源を奪い合う 競合（contention）、そしてキャッシュやレプリカの整合を取り合う 一貫性コスト（coherency／crosstalk） です。これを加えたのが Neil Gunther の USL で、相対スループット（容量）C(N) を次式で与えます。

C(N) = N / ( 1 + α(N − 1) + β·N(N − 1) )

• α（アルファ）：直列化・競合の係数。共有ロックやシングルライタへの集中など。アムダール則の f に対応する項。
• β（ベータ）：一貫性コストの係数。N(N−1) はノード対の総当たり数に比例し、相互の同期・整合通信がノード数の2乗で効くことを表す。

β = 0 のときUSLはアムダール則に一致します。決定的に違うのは β 項の存在です。これがあると C(N) は単調増加せず、ある最適点 N を超えると逆に減少* します。最適点は微分してゼロになる点から次式で求まります。

N* = √( (1 − α) / β )

つまりノードを足しすぎると、同期通信のオーバーヘッドが処理能力を食い潰し、スループットがピークから下り坂に転じる。スケールアウトしたのに遅くなるという現象の正体がこれです。α が直線的な収益逓減を、β が逓減を通り越した逆効果をもたらします。

係数の状態	システムの挙動	典型的な原因
α=0, β=0	理想的な線形スケール	完全に独立な処理（共有なし）
α が大, β=0	1/α に漸近して頭打ち	グローバルロック・単一の直列段
β が非ゼロ	N* でピーク後に低下	全ノード間の同期・分散ロック・整合通信

設計と運用への落とし込み

3つの法則が共通して指し示す実践は明快です。逐次部分・競合・同期を削ることが、台数を足すことよりも本質的に効く という点です。

• 逐次部分 f を測って削る：プロファイリングでホットな直列段（グローバルロック、単一ID採番、集中する書き込み）を特定し、シャーディングやロックフリー化で分割する。1/f の天井を上げる唯一の手段。
• β を作らない設計：全ノードが互いに同期する構造（分散ロック、強整合のブロードキャスト）はノード数の2乗でコストが効く。協調をローカルに閉じる、非同期にする、対象を絞ることで β を抑える。これはマイクロサービス間の結合を疎にする動機にも直結する（/devops/microservices/）。
• 強か弱かを宣言する：レイテンシ短縮（強スケーリング）を狙うのか、扱える規模の拡大（弱スケーリング）を狙うのかでKPIも投資判断も変わる。SLOの設計に反映する（/devops/sre-slo/）。
• N を超えない*：USLのピークを実測から把握し、最適点の手前にヘッドルームを残して止める。足せば足すほど速くなるという素朴な前提を捨てる。

これらは待ち行列理論が示す利用率の天井とも地続きで、どちらも「資源を共有する系には固有の限界がある」ことを別角度から語っています（/devops/queueing-theory-tail-latency/）。

まとめ

• アムダール則 は固定問題の加速率が逐次割合 f で 1/f に頭打ちすることを示す。f=5%なら上限20倍。並列化は最も並列化しにくい一点に支配される。
• ガスタフソン則 は問題規模をプロセサ数に応じて拡大する前提に立ち、加速率は N にほぼ線形に伸びる。アムダール則と矛盾せず、強スケーリングと弱スケーリングという測り方の違い。
• USL は競合 α と一貫性コスト β を加える。β 項により最適点 N* = √((1−α)/β) を超えるとスループットが逆に低下する。
• 実践では台数を足すより、逐次部分・競合・同期を削る ことが本質。USLは実測へのカーブフィットで最適ノード数を外挿でき、データ駆動のキャパシティプランニングに直結する。