配ると、いちばん遅い1台が全体を決める
実装:
resilience/scatter// 実行:go test ./resilience/scatter/
同じ問い合わせを何台にも配って全部の答えを待つと、いちばん遅い1台が全体の時間を決める。1台あたり5%しかない遅い応答が、100台に配ると99%の確率でどこかに現れた。切り方は2つある。答えが揃う前に打ち切るか、遅い台にだけもう1本投げるか。前者は時間を買って答えを減らし、後者は答えを保ったまま本数を5%増やした。
この章で作るもの
1台への問い合わせを速くする話は、この本にいくつもある。インデックスを張る、キャッシュに載せる、バッファプールで読み直しを減らす。
ところが台数を増やすと、1台を速くしても効かない場面が出てくる。検索を100台に分けて配り、全部の答えを混ぜて1つの結果にする形がそれだ。100台が全員速くないと、結果は返らない。
ここで効くのが裾になる。ほとんどの応答は速いが、たまに遅いものが混じる。1台に問い合わせるだけなら「たまに」で済む。100台に配ると、その「たまに」を100回引くことになる。
1 台に問い合わせる
├──────┤ ほとんどは速い
↑ 20 回に 1 回だけ遅い
100 台に配って全部待つ
├──┤
├───┤
├──┤ ← 速い 95 台は、待っているだけ
...
├──────────────────────┤ ← 遅い 1 台
↑
ここで初めて答えが揃う
1 台あたり 5% の裾が、100 台では 99.4% になる順に見ていく。
- 全部揃うまで待つと、いちばん遅い1台が全体を決める: 裾は台数ぶん引くことになる
- 揃う前に打ち切る: 時間は縮むが、集まる答えが減る
- 遅い台にだけもう1本投げる: 答えは減らないが、投げる本数が増える
- 2つは買っているものが違う: 片方は答えを払い、片方は本数を払う
① 全部揃うまで待つと、いちばん遅い1台が全体を決める
まず、裾のある応答時間を決定的に作る。20回に1回だけ遅く、それ以外は速い。
func Took(node, attempt int) int {
s := lcg(node*31 + attempt*7919)
if s%SlowEvery == 0 {
return Slow
}
return Fast + s%FastWidth
}attempt を引数に取っているのが後で効く。同じ台でも、投げ直せば別の値になる。実物でも、遅いのは台そのものではなく、そのときの混み具合や置き場所のことが多い。
配って全部待つ形はこうなる。
func All(n int) Result {
done, sent, slows := finishes(n, 0)
wait := 0
for _, d := range done {
if d > wait {
wait = d
}
}
return Result{Wait: wait, Got: n, Sent: sent, Slows: slows}
}揃うのはいちばん遅い1台が返ったときなので、待ち時間は最大値になる。台数を変えて測った。
| 台数 | 揃うまで | 投げた本数 | 遅かった台 | 誰かが遅い割合 |
|---|---|---|---|---|
| 1 | 17 | 1 | 0 | 5.00% |
| 5 | 200 | 5 | 1 | 22.63% |
| 20 | 200 | 20 | 1 | 64.16% |
| 100 | 200 | 100 | 5 | 99.41% |
いちばん右の列がこの節の中身になる。1台あたりの裾は5%で変わっていない。変わったのは、その5%を何回引くかだ。100台に配れば、ほぼ確実にどこかで遅い応答を踏む。
読み方を1つ足しておく。5台の時点で、既に揃うまでが200になっている。100台の200と同じ値だ。つまり悪化は台数に比例するのではなく、早い段階で天井に張り付く。台数を10倍にしても、もう悪くなりようがないところまで最初に行ってしまう。
そして95台は、速く返ったのに待たされている。この待ち時間は誰の役にも立っていない。
② 揃う前に打ち切る
いちばん素直な手は、全部揃うのを諦めることだ。100台のうち90台から返ってきたら、そこで答えを作る。
func FirstK(n, k int) Result {
if k > n {
k = n
}
done, sent, slows := finishes(n, 0)
return Result{Wait: kth(done, k), Got: k, Sent: sent, Slows: slows}
}| 何台で打ち切るか | 揃うまで | 集まった答え | 投げた本数 |
|---|---|---|---|
| 50 | 15 | 50 | 100 |
| 90 | 19 | 90 | 100 |
| 99 | 200 | 99 | 100 |
| 100 | 200 | 100 | 100 |
90台で打ち切ると、待ち時間が 200 から 19 へ落ちた。10分の1以下になる。
ところが99台にすると、200に戻ってしまう。この模型では100台のうち5台が遅いので、99台を揃えるには遅い台を待つことになるからだ。打ち切る位置は、裾の太さより手前に置かないと効かない。9割で切るか、95%で切るかは、遅い台がどれくらいあるかで決まる。
払っているものも見ておく。投げた本数は100のまま変わらない。打ち切っても、投げたものは投げたままだ。相手側の仕事は減っていない。減ったのは、こちらが待つ時間と、手元に集まる答えの数になる。
答えが1割足りない結果を返してよいかは、仕事による。検索の並び順なら、たいてい許される。残高の合計なら許されない。
③ 遅い台にだけもう1本投げる
答えを減らしたくない場合の手がもう1つある。しばらく待っても返ってこない台に、同じ問い合わせをもう1本投げる。先に返ってきたほうを採る。
func Hedged(n, after int) Result {
done, sent, slows := finishes(n, after)
wait := 0
for _, d := range done {
if d > wait {
wait = d
}
}
return Result{Wait: wait, Got: n, Sent: sent, Slows: slows}
}①で Took が attempt を取るようにしたのはこのためだ。2本目は1本目と別の値になるので、1本目が遅い台でも2本目は速いことが多い。
| 揃うまで | 集まった答え | 投げた本数 | |
|---|---|---|---|
| 全部待つ | 200 | 100 | 100 |
| 2本目あり | 37 | 100 | 105 |
待ち時間が 200 から 37 へ落ちて、答えは1つも減っていない。増えたのは投げた本数で、100 から 105、つまり**5%**だ。
5%で済むのは、2本目を投げるのが遅かった台だけだからになる。速い台は最初の1本で返っているので、追加の仕事は起きない。裾に当たった台のぶんしか払わない、というのがこの手の性質になる。
では、待つ時間をもっと短くしたらどうなるか。
| 何を過ぎたら2本目 | 揃うまで | 投げた本数 |
|---|---|---|
| 5 | 22 | 200 |
| 20 | 37 | 105 |
| 50 | 67 | 105 |
| 150 | 167 | 105 |
5で切ると、揃うまでは22まで縮むが、投げた本数が200、つまり全台が2本になった。速い台の応答時間そのものが 10 から 19 の幅にあるので、5 を過ぎるのは全台だからだ。
待つ時間を、速い応答が返り終わるところに置く。それより手前にすると、裾ではなく全部に払うことになる。ここが設定の勘所になる。
④ 2つは買っているものが違う
3つを並べる。
| 揃うまで | 集まった答え | 投げた本数 | |
|---|---|---|---|
| 全部待つ | 200 | 100 | 100 |
| 打ち切る | 19 | 90 | 100 |
| 2本目 | 37 | 100 | 105 |
どちらも時間を買っている。払っているものが違う。
打ち切りは答えの数を払う。相手にかかる負荷は変わらないので、下流が既に苦しいときでも使える。ただし結果が不完全になる。
2本目は投げる本数を払う。答えは完全なままだが、下流の仕事が増える。相手が過負荷で遅いなら、この手は傷を広げる。
ここから使い分けが出る。遅い理由が下流の過負荷なら、2本目は打ってはいけない。混んでいる相手にもう1本投げれば、もっと混む。リトライとバックオフでリトライ嵐を見たが、あれと同じ形が起きる。逆に、遅い理由が特定の台のばらつきなら、2本目が効く。
そして打ち切りにも前提がある。答えが1つ足りないと成立しない仕事では使えない。合計、残高、在庫数。こういうものは9割の答えで作れない。
動かす
下のデモは、台数と切り方を変えて配りを見る。台数を増やすと、遅い台が現れる確率と揃うまでの時間がどう動くかを追える。打ち切る位置を動かすと、時間と答えの数が反対向きに動く。2本目を投げ始める時刻を動かすと、時間と本数が反対向きに動く。
1 台を速くする工夫は、配る台数が増えると効きにくくなる。全部揃うのを待つ形では、 速く返った台は待っているだけで、遅い 1 台が全体の時間を決めるからだ。 打ち切りは答えを払って時間を買い、2 本目は下流の仕事を払って時間を買う。 遅い理由が下流の混雑なら、2 本目は混雑を増やす側に回る。
設計の観点
- 裾は台数ぶん引く: 1台あたりの遅さが変わらなくても、配る台数を増やせば必ず踏む。1台の速さを測っていると、この悪化は見えない
- 悪化は早い段階で天井に張り付く: 台数に比例して悪くなるのではなく、数台の時点でもう最大値に届く。台数を減らしても効かない
- 打ち切る位置は裾の太さより手前に置く: 遅い台が5%あるのに99%で切っても、待ち時間は縮まない
- 2本目を投げ始める時刻は、速い応答が返り終わるところ: 手前に置くと、裾ではなく全台に払うことになる
- 遅い理由を先に決める: 下流の過負荷なら2本目は傷を広げる。特定の台のばらつきなら効く
- 答えが欠けてよいか先に決める: 並び順は欠けてよく、合計は欠けてはいけない。打ち切りが使えるかはここで決まる
- 速く返った台の待ち時間は誰の役にも立っていない: 100台のうち95台が、遅い1台のために待たされている
対照と実例
| 全部待つ | 打ち切る | 2本目を投げる | |
|---|---|---|---|
| 揃うまで | 200 | 19 | 37 |
| 集まった答え | 100 | 90 | 100 |
| 投げた本数 | 100 | 100 | 105 |
| 払うもの | なし | 答えの数 | 下流の仕事 |
| 下流が過負荷のとき | 遅いまま | 使える | 使えない |
| 答えが欠けてはいけない仕事 | 使える | 使えない | 使える |
裾を切る手は、この本の他の章にも別の形で出ている。ロードバランサが遅い相手を外すのは、配る前に裾を減らす形になる。クォーラムが過半数で答えるのは、②の打ち切りを正しさの条件として書き下したものになる。サーキットブレーカーは、裾ではなく壊れた相手を切り離す。
裏どり:
- 数字はすべて手元の測定: 台数の表も、打ち切りの表も、2本目の表も、この章の実装をテストで固定したもの。実物の分散検索を測ったものではない
- 応答時間の模型: 20回に1回だけ遅い、という置き方はこちらが決めたもの。実物の裾はもっとなだらかで、遅さの度合いにも幅がある。裾があるという性質だけを取り出している
- 「誰かが遅い割合」の計算: 1台あたりの割合を
pとして1-(1-p)^nを整数のまま計算している。台ごとの遅さが独立だという前提が入っていて、実物では同じ原因で複数台が同時に遅くなることがある - 2本目を投げる手の名前: 英語では hedged request と呼ばれる。Dean と Barroso の "The Tail at Scale" が広く引かれる出典で、そこでは 95 パーセンタイルを過ぎた要求に 2 本目を出す形で、追加の負荷は数パーセントに収まったと報告されている。この章の 5% という数字は手元の模型のもので、その報告の数字ではない
- 打ち切る形の呼び名: 実物では partial result、あるいは クォーラムの一種として扱われる。この章では正しさの条件までは踏み込んでいない
簡略化したこと
- 時間を整数の刻みにしている: 実物のばらつきは連続で、刻みの中の差が見えない
- 台ごとの遅さが独立だとしている: 実物では、同じ棚や同じ回線の台が一緒に遅くなる。独立でないと、裾はもっと太くなる
- 2本目を1本しか投げていない: 3本目、4本目を投げる形もある。どこで止めるかは扱っていない
- 打ち切ったあとの答えを捨てている: 遅れて返ってきた答えを次に活かす形は実装していない
- 投げる側の資源を数えていない: 2本目を投げるには、こちら側にも接続と待ち行列が要る
- 答えの中身を扱っていない: 集めた答えをどう混ぜるかは、この章の外になる
参考資料
- The Tail at Scale — 裾がなぜ台数で効いてくるかと、2本目を投げる手
- 前提: リトライとバックオフ / クォーラム
- 関連: ロードバランサ / サーキットブレーカー / 配ると何が増えるか
- 実装: resilience/scatter