速くしても全体はそこまで速くならない

読了目安約3分

アムダールの法則で改善の上限を見積もり、ボトルネックが順に移動していく理由を理解します。

この章の目次

いちばん遅いクエリを 10 倍速くしても、全体は 10 倍になりません。どこまで速くなるかは、そのクエリが全体の何割を占めるかで決まります。

改善の上限

全体のうち一部だけを速くしたとき、全体が何倍速くなるかを表す式があります。

S = \frac{1}{(1-f) + \dfrac{f}{r}}

全体の 60 パーセントを占めるクエリを 10 倍速くするなら、 $f = 0.6$ 、 $r = 10$ です。

S = \frac{1}{(1-0.6) + \dfrac{0.6}{10}} = \frac{1}{0.4 + 0.06} \approx 2.17

これがアムダールの法則です。残りの 40 パーセントは 1 ミリ秒も減らないので、そこが天井を作ります。

$f$ （占める割合）	$r=2$	$r=10$	$r=\infty$
0.2	1.11	1.22	1.25
0.6	1.43	2.17	2.50
0.9	1.82	5.26	10.0

占める割合が小さいものは、無限に速くしても意味がありません。

ここから、計測結果の読み方が決まります。 1 回が最も遅いクエリではなく、呼ばれた回数を掛けた合計時間が最大のものから直します。

1 回 500 ミリ秒でも 1 分に 1 回しか呼ばれないクエリより、1 回 5 ミリ秒でも毎秒 200 回呼ばれるクエリのほうが、全体に占める割合は大きくなります。 alp とスロークエリログを合計時間順に並べるのは、f の大きいものを先に見つけるためです。

例外は、規定の応答時間を超えて失格や減点になる場合です。合計時間が小さくても、規定を破っているものは先に直します。

f の大きいものを直すと、その部分の割合は小さくなります。すると次に大きいものが繰り上がり、ボトルネックが移動します。

典型的な移り方です。

大事なのは、移動したあとの構成では以前の計測が無効になっていることです。 1 つ直したら測り直します。前のラウンドの犯人を追い続けると、すでに f が 5 パーセントしかないものを磨くことになります。

$r$ を無限大にしたときの上限は $\dfrac{1}{1-f}$ です。どれだけ手を尽くしても、直列に残る部分より速くはなりません。

ISUCON では、次のようなものが直列部分として残ります。

前の 2 つは削れない固定費として受け入れます。 3 つ目は、依存していないなら並べれば消えるので、真っ先に疑う価値があります。

前章の計測の続きです。データベースのサービス需要 9 ミリ秒の内訳が、次のようだったとします。

中身	1 件あたり
インデックスが無く全件走査しているクエリ	6 ミリ秒
その他のクエリ	3 ミリ秒

答えを見る

$f$ は 0.67。 $S = 1 / (0.33 + 0.67/20) \approx 2.7$ 倍。 $D$ は 9 ミリ秒から 3.3 ミリ秒に下がるので、上限は 222 件/秒から約 600 件/秒へ動きます。

20 倍速くしても全体は 2.7 倍です。それでも上限が 3 倍近くへ動くのは、そこが全体の 3 分の 2 を占めていたからです。