ヘッジ・リクエスト (hedged request)
皆さんはヘッジ・リクエストという言葉を聞いたことがあるでしょうか？
ヘッジ (hedge)とは、フェンス、垣根から転じて、リスクを回避する手段、設計の意味でも使われます。ヘッジ・ファンドが有名ですが、顧客から預かった資産を分散投資しリスク回避することで、不況の時でもハイリターンを出す金融のプロ集団です。
ヘッジ・リクエストは、HTTPリクエストを1回だけ送信するのではなく、タイミングをずらして2回、3回と後追いで同じリクエストを送信します。つまり、１発目のリクエストが何かしらの原因で応答に遅延があっても、２発目、３発目のリクエストの応答が先にリターンするように、保険をかけておく手法です。
本ブログでは、Goのchannelとselectを使用して、ヘッジ・リクエストをエレガントに実装してみます。
本ブログは、Ricardo氏のMediumの記事 Hedged requests — Tackling tail latency を少しアレンジして書いています。(本人了承済み)
伝説のエンジニア - ジェフ・ディーン
ヘッジ・リクエストは2013年 ACM誌掲載のThe Tail at Scaleにて説明されています。また、翌年の2014のO'Reilly Velocity カンファレンスにて説明されています。
そう、あの伝説のエンジニア ジェフ・ディーンによって。
現在、ジェフ・ディーンはグーグル AIのリードであり、TensorFlowなど機械学習関連のイベントなどに登壇しており、そのお姿を拝見することができます。そして、ジェフはBigTableなどのグーグルの分散システムの開発に携わったエキスパートでもあります。
そのペーパーには下記の記述があり、グーグルのBigTableで実際に効果があったことが示されています。
Hedged requests. One such approach is to defer sending a secondary request until the first request has been outstanding for more than the 95th-percentile expected latency for this class of requests.
２発目のリクエストの送信を、１発目のリクエストのレイテンシーの９５%ile以上に遅らせる。
For example, in a Google benchmark that reads the values for 1,000 keys stored in a BigTable table distributed across 100 different servers, sending a hedging request after a 10ms delay reduces the 99.9th-percentile latency for retrieving all 1,000 values from 1,800ms to 74ms while sending just 2% more requests.
グーグルのベンチマークでは、100台のサーバに分散したBigTableから1000個のキーをreadするテストにて、10msの遅延でヘッジ・リクエストを送信することで、レイテンシーの99.9%ileの値を、1800msから74msに短縮した。
Variability
統計学でいう、偏差(deviation)と同じ、値のばらつき、分散、外れ値のような意味です。
分散システムはレイテンシーに影響を与える外部的な要因があります。それは
ネットワーク、ルータ、電源、ガーベージコレクション、ディスク、他人が起動したプロセス、インスタンスのスピンアップ時のコールドスタートなど、いろいろな要素がレイテンシーにVariabilityを発生させます。
オンラインサービスのWeb、スマフォアプリから叩かれるバックエンドAPIは安定したレスポンスが要求されます。
レイテンシーの95%ileを改善する(the tail at scale)でサービスレベルが向上します。
Tail Tolerant
しっぽの部分も対応するシステム設計とでも訳しましょうか？
マーケティングの世界では、ロング・ティルといい、一年に数回しか売れないようなレアアイテムも、在庫を持つ必要がないオンラインショッピングで取り扱うことで収益を上げる戦略があります。
あえて外れ値の顧客をターゲットにする、ニッチ・マーケティング、Vertical Marketingという言葉もあります。
余談。カタカナ英語はあまり使わない方が良い。リスニング、英会話を向上させる最短ルート
Goコーディングの例
前置きが長くなりましたが、ヘッジ・リクエストのGo実装を説明します。
システムのアーキテクチャ
サンプルは、次の３つのモジュールで構成されます。
- dummy server
- HTTPサーバ。検証用の擬似サービス。95%ileでVariabilityを発生させます。
- hedge server
- HTTPサーバ。ヘッジ・リクエスト実装。リバースプロキシー。
- vegeta
- コマンドライン。パフォーマンス測定ツール vegetaで負荷をかけます。
ダミーサービスの作成
HTTPサーバです。15ms スリープさせ、タスクをしてるフリをします。
乱数を使用して Variabilityを発生させます。95%のリクエストは正常に15ms+で応答し、残りの5%のリクエストはVariabilityの影響を受け、115ms+で応答するWebサービスをシュミレートします。
package main
import (
"math/rand"
"net/http"
"time"
"github.com/gorilla/mux"
)
func main() {
router := mux.NewRouter()
router.HandleFunc("/ishealthy", func(w http.ResponseWriter, r *http.Request) {
rd := rand.New(rand.NewSource(time.Now().UnixNano()))
requestPercentile := rd.Intn(100)
waitTime := 0
// 乱数で強制的にVariabilityを発生させる。
if requestPercentile > 96 {
waitTime = 100
}
// スリープでタスクをしてるフリ
time.Sleep(time.Duration(waitTime+15) * time.Millisecond)
w.WriteHeader(http.StatusOK)
w.Write([]byte("Healthy"))
}).Methods(http.MethodGet)
http.ListenAndServe(":8080", router)
}
ベジータ様の攻撃を受ける
vegeta attack でパフォーマンステストします。(cURLでもなんでも良いです)
狙い通りに、レイテンシーの99%ileが 116ms とガクンと悪化するのが分かります。(そのように実装しましたから)
３つのモジュールすべて、私のMacBookAir上で実行していますが、15ms + 数msのオーバーヘッドで実行できました。
実際には本番サービスの95%ileのレイテンシーを計測し、ヘッジ・リクエストのパラメータ調整することになります。
$ echo "GET http://localhost:8080/ishealthy" | vegeta attack -duration=5s -rate 100/1s -workers 10 -connections 10 --insecure | tee results.bin | vegeta report
Requests [total, rate, throughput] 500, 100.25, 99.92
Duration [total, attack, wait] 5.004s, 4.988s, 16.379ms
Latencies [min, mean, 50, 90, 95, 99, max] 15.44ms, 19.035ms, 16.99ms, 17.374ms, 17.575ms, 116.935ms, 117.383ms
Bytes In [total, mean] 3500, 7.00
Bytes Out [total, mean] 0, 0.00
Success [ratio] 100.00%
Status Codes [code:count] 200:500
ヘッジ・リクエストの実装
さていよいよ本題、ヘッジリクエストを実装し、ベジータの攻撃を緩和させましょう。
図で示したように、ヘッジサーバをリバースプロキシーとして、間に立てます。
１発目のリクエストが21msたってもレスポンスがない場合、２発目のヘッジ・リクエストを投げます。２発目もまだ戻らない場合(21ms + 21ms = 42ms)、３発目のヘッジ・リクエストを投げます。
channelを使用して、３つのリクエストの応答をまち、一番速く返ってきた応答で関数を抜け、vegetaへレスポンスを返します。
残りの仕掛かり中のリクエストが宙ぶらりんになりますが、あとで説明
これは、goのchannelとselectを使用するとタイムアウトをエレガントに実装できます。
func queryWithHedgedRequests(urls []string) string {
ch := make(chan string, len(urls))
for _, url := range urls {
// ダミーサービスにリクエストを投げ、戻り値をchannelに送信
go func(u string, c chan string) {
c <- executeQuery(u)
}(url, ch)
// 21msたってもレスポンスがないとタイムアウトさせ、ループを進める。
select {
case r := <-ch:
return r
case <-time.After(21 * time.Millisecond):
}
}
// 最悪なケースはここまで到達する。 21 + 21 + 21 = 63ms
return <-ch
}
func executeQuery(url string) string {
// HTTPクライアントの処理
response, _ := http.Get(url)
// 本質に関係ないので省略。。。
return (レスポンスのボディ)
}
func main() {
router := mux.NewRouter()
// 実際にはロードバランサーなどの分散環境へのエンドポイント
urls := []string{"http://localhost:8080/ishealthy", "http://localhost:8080/ishealthy", "http://localhost:8080/ishealthy"}
router.HandleFunc("/queryWithHedgedRequests", func(w http.ResponseWriter, r *http.Request) {
result := queryWithHedgedRequests(urls)
w.WriteHeader(http.StatusOK)
w.Write([]byte(result))
}).Methods(http.MethodGet)
http.ListenAndServe(":8081", router)
}
再度、ベジータ様の攻撃を受けるの巻
再度、vegetaでパフォーマンステストしてみましょう。
なんということでしょう。レイテンシーの99%ileが 40ms と大きく改善しました。
$ echo "GET http://localhost:8081/queryWithHedgedRequests" | vegeta attack -duration=5s -rate 100/1s -workers 10 -connections 10 --insecure | tee results.bin | vegeta report
Requests [total, rate, throughput] 500, 100.19, 99.85
Duration [total, attack, wait] 5.007s, 4.99s, 17.104ms
Latencies [min, mean, 50, 90, 95, 99, max] 16.044ms, 18.469ms, 17.952ms, 18.518ms, 19.19ms, 40.79ms, 41.39ms
Bytes In [total, mean] 22000, 44.00
Bytes Out [total, mean] 0, 0.00
Success [ratio] 100.00%
Status Codes [code:count] 200:500
よりアグレッシブに
もし皆さんのバックエンド環境が、AWSやGCP上のkubernetesのようなオートスケールな作りで、かつ予算が潤沢にあるのであれば、ヘッジリクエストを同時発行し、パフォーマンスを向上できます。
func queryFanOut(urls []string) string {
ch := make(chan string, len(urls))
// リクエストを同時発行してしまう。
for _, url := range urls {
go func(u string) {
ch <- executeQuery(u)
}(url)
}
// 速いもんがち。残りのリクエストのリターンは無視する。
return <-ch
}
この場合、99%ile は 20ms ほどになりました。つまり、同時発行した３つのリクエスト全てにおいて、Variabilityが発生する確率は、$0.05^3 = 0.000125$ になり限りなくゼロに近づきます。
簡単のためコードを端折りましたが、cancelをコールして仕掛かり中のリクエストをキャンセルする必要があります。
ctx, cancel := context.WithCancel(context.Background())
defer cancel()
...
select {
case r := <-ch:
cancel()
return r
Goroutineとchannelを使用すると、並行処理をエレガントに記述できることを紹介しました。
また、私が書いたこちらの記事もご参考にしてみてください。