Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Goでヘッジ・リクエストを実装する

ヘッジ・リクエスト (hedged request)

皆さんはヘッジ・リクエストという言葉を聞いたことがあるでしょうか?

ヘッジ (hedge)とは、フェンス、垣根から転じて、リスクを回避する手段、設計の意味でも使われます。ヘッジ・ファンドが有名ですが、顧客から預かった資産を分散投資しリスク回避することで、不況の時でもハイリターンを出す金融のプロ集団です。

コンピュータ業界でよく出る英語

ヘッジ・リクエストは、HTTPリクエストを1回だけ送信するのではなく、タイミングをずらして2回、3回と後追いで同じリクエストを送信します。つまり、1発目のリクエストが何かしらの原因で応答に遅延があっても、2発目、3発目のリクエストの応答が先にリターンするように、保険をかけておく手法です。

本ブログでは、Goのchannelselectを使用して、ヘッジ・リクエストをエレガントに実装してみます。

本ブログは、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.

2発目のリクエストの送信を、1発目のリクエストのレイテンシーの95%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実装を説明します。

システムのアーキテクチャ

サンプルは、次の3つのモジュールで構成されます。

dummy server
HTTPサーバ。検証用の擬似サービス。95%ileでVariabilityを発生させます。
hedge server
HTTPサーバ。ヘッジ・リクエスト実装。リバースプロキシー。
vegeta
コマンドライン。パフォーマンス測定ツール vegetaで負荷をかけます。

Screen Shot 2020-12-12 at 16.22.55.png

ダミーサービスの作成

HTTPサーバです。15ms スリープさせ、タスクをしてるフリをします。
乱数を使用して Variabilityを発生させます。95%のリクエストは正常に15ms+で応答し、残りの5%のリクエストはVariabilityの影響を受け、115ms+で応答するWebサービスをシュミレートします。

dummy_service.go
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 とガクンと悪化するのが分かります。(そのように実装しましたから)

3つのモジュールすべて、私の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

ヘッジ・リクエストの実装

さていよいよ本題、ヘッジリクエストを実装し、ベジータの攻撃を緩和させましょう。

図で示したように、ヘッジサーバをリバースプロキシーとして、間に立てます。

1発目のリクエストが21msたってもレスポンスがない場合、2発目のヘッジ・リクエストを投げます。2発目もまだ戻らない場合(21ms + 21ms = 42ms)、3発目のヘッジ・リクエストを投げます。

channelを使用して、3つのリクエストの応答をまち、一番速く返ってきた応答で関数を抜け、vegetaへレスポンスを返します。

残りの仕掛かり中のリクエストが宙ぶらりんになりますが、あとで説明

これは、goのchannelselectを使用するとタイムアウトをエレガントに実装できます。

hedged_client.go
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のようなオートスケールな作りで、かつ予算が潤沢にあるのであれば、ヘッジリクエストを同時発行し、パフォーマンスを向上できます。

fanout.go
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 ほどになりました。つまり、同時発行した3つのリクエスト全てにおいて、Variabilityが発生する確率は、$0.05^3 = 0.000125$ になり限りなくゼロに近づきます。

簡単のためコードを端折りましたが、cancelをコールして仕掛かり中のリクエストをキャンセルする必要があります。

ctx, cancel := context.WithCancel(context.Background())
defer cancel()
...
select {
        case r := <-ch:
            cancel()
            return r

Goroutineとchannelを使用すると、並行処理をエレガントに記述できることを紹介しました。
また、私が書いたこちらの記事もご参考にしてみてください。

参考: Go言語の並行処理デザインパターン by Rob Pike 前編

tfutada
シリコンバレー、ニューヨーク(NTTデータUSA)、インド(マヒンドラサティヤム)、ベトナム(フリー)を経て、現在は東南アジアのオフショア開発のコンサルティング会社経営 Kubernetes, GCP, Go, Python, R, Swift, Kotlin, ReactJS 英語(TOEIC895)
https://note.mu/tafutafu
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away