🔩 ねじき教室 Go と Web の教室

増やすほど遅くなることがある

読了目安 約4分

リソースを増やしすぎると容量が落ちる現象を、競合と協調の 2 つの係数で表し、線形にスケールするとは何かに答えます。

この章の目次

ワーカー数やコネクション数を増やしていくと、あるところから逆に遅くなります。 これは調整の失敗ではなく、増やすこと自体に費用があるからです。

2 種類の費用

リソースを pp 個に増やしたときの相対容量は、2 つの係数でよく説明できます。

C(p)=p1+α(p−1)+βp(p−1) C(p) = \frac{p}{1 + \alpha(p-1) + \beta p(p-1)}
  • C(p)C(p) ：前章と同じ相対容量。1 個のときの何倍か
  • α\alpha ：競合の係数。同時に 1 つしか通れない場所の大きさ
  • β\beta ：協調の係数。参加者どうしが足並みを揃える費用

どちらも 0 なら C(p)=pC(p) = p で、増やした数だけ容量が増えます。

この 2 つは、曲線の形が違います。

  • α\alpha だけがあるとき、容量は増えなくなるが下がりはしない
  • β\beta があると、あるところで頂点を越えて下がっていく

この式は USL（Universal Scalability Law）と呼ばれます。 α\alpha は 1 対多で済みますが、 β\beta は参加者が増えるほど組み合わせが増えるからです。 容量が頂点を打つ個数を p∗p^{*} と書くと、こうなります。

p∗=1−αβ p^{*} = \sqrt{\frac{1-\alpha}{\beta}}
Go 
package main

import "fmt"

func usl(p, alpha, beta float64) float64 {
	return p / (1 + alpha*(p-1) + beta*p*(p-1))
}

func main() {
	fmt.Println("  p    理想   競合あり   競合+協調あり")
	for _, p := range []float64{1, 2, 4, 8, 16, 32, 64} {
		fmt.Printf("%3.0f %7.2f %9.2f %13.2f\n",
			p, p, usl(p, 0.05, 0), usl(p, 0.05, 0.005))
	}
}

競合だけなら 64 個で 15 倍まで伸び続けます。 協調が加わると、 p∗=0.95/0.005≈13.8p^{*} = \sqrt{0.95 / 0.005} \approx 13.8 で頂点を打ち、64 個では 2.6 倍まで落ちます。 5 パーセントの競合と 0.5 パーセントの協調で、この差が出ます。

係数を実測から推定することは、現場ではまずやりません。 「増やしたら下がった」を見たら協調の費用を疑う、という定性で使います。

何が競合で、何が協調か

係数実際に該当するもの
α\alpha 競合全体を守る 1 つのロック、1 本しかない接続、同じ行への更新、ログ出力の排他
β\beta 協調全台へのキャッシュ失効の通知、状態の同期、台数ぶん増える一斉通信

α\alpha を減らす作業は、ロックの範囲を狭めることと、守る対象を分割することです。 更新するキーごとにロックを分ければ、別のキーを触る処理は待たなくなります。

β\beta を減らす作業は、そもそも足並みを揃えなくて済む設計にすることです。 サーバーをまたいで即座に一致させる必要が本当にあるのかを疑うと、多くは「数秒遅れてよい」に落ちます。

まとめすぎると競合が増える

往復を減らすつもりの改善が、 α\alpha を増やすことがあります。

実例があります。 高頻度の更新をメモリに溜めて、定期的に 1 つの大きなトランザクションでまとめて書き込むようにしたところ、スコアが 3 分の 2 に落ちました。 往復の回数は確かに減りましたが、まとめたぶんロックを長く持つようになり、待たされる処理が規定時間を超えたためです。

1 行ずつ高頻度に更新するほうが速いことがあります。 往復回数 VV を減らす手は、直列区間 α\alpha を伸ばしていないかとセットで見ます。

溜めてから書く実装を採るなら、ロックを取る順序をキーの順で固定します。順序が揃っていないと、待ち合わせが循環して止まります。

線形にスケールするとは

ここまでの道具が、1 つの問いに答えます。

線形にスケールするとは、リソースを増やしたぶんだけ容量が増えることです。 そして、それを妨げるものは 3 つしかありません。

  1. 増やしていない共有リソースが先に飽和している（台数を増やすと何が起きるか）
  2. 同時に 1 つしか通れない場所がある（ α\alpha ）
  3. 参加者どうしを揃える費用が台数とともに増える（ β\beta ）

ISUCON の 8 時間でやっているのは、この 3 つを削る作業です。 1 リクエストあたりのリソースの使用量（サービス需要）を削って飽和点を右へずらし、ロックの範囲を狭めて α\alpha を削り、揃えなくてよいものを揃えるのをやめて β\beta を削ります。

スコアが 2 倍になった、で終わりにしないでください。 どのリソースの需要がどれだけ減り、飽和する件数がどこまで動いたのかを見ておくと、次にどこが限界になるかが先に分かります。

試してみよう

シミュレーションの α\alpha と β\beta を変えて、頂点が来る位置を調べてください。

  1. β\beta を 0.005 のまま α\alpha を 0.2 に上げると、頂点はどちらへ動きますか
  2. α\alpha を 0 にして β\beta だけ 0.01 にすると、何個で頂点を打ちますか

そのうえで、いま触っている実装の中に「同時に 1 つしか通れない場所」がいくつあるかを数えてみてください。