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

読了目安 約5分

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

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

2 種類の費用

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

• $C(p)$ ：前章と同じ相対容量。1 個のときの何倍か
• $\alpha$ ：競合の係数。共有リソースを同時に使えず、待ち合わせる費用
• $\beta$ ：協調の係数。参加者どうしで状態を一致させる費用

どちらも 0 なら $C(p) = p$ で、増やした数だけ容量が増えます。 ここでは $0 \leq \alpha \leq 1$ 、 $\beta \geq 0$ の範囲を考えます。

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

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

この式は USL（Universal Scalability Law）と呼ばれます。 競合の項はおおむね $p$ に比例しますが、協調の項は参加者の組み合わせが増えるため $p(p-1)$ に比例します。 $0 \leq \alpha < 1$ 、 $\beta > 0$ のとき、容量が頂点を打つ個数を $p^{*}$ と書くと、こうなります。

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^{*} = \sqrt{0.95 / 0.005} \approx 13.8$ で頂点を打ち、64 個では 2.6 倍まで落ちます。 係数を $\alpha = 0.05$ 、 $\beta = 0.005$ と置いただけで、この差が出ます。

十分な測定点があれば、非線形回帰によって係数を推定できます。 この教材では、まず「増やしたら下がった」という形から協調の費用を疑うために使います。

何が競合で、何が協調か

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

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

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

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

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

1 行ずつ高頻度に更新するほうが速いことがあります。 往復回数 $V$ を減らす手は、直列区間 $\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 つしか通れない場所」がいくつあるかを数えてみてください。