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

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

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

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

> [コンピュータ業界でよく出る英語](https://qiita.com/tfutada/items/d1b17cd4008876c17bf4)

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

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

> 本ブログは、Ricardo氏のMediumの記事 [Hedged requests — Tackling tail latency](https://medium.com/swlh/hedged-requests-tackling-tail-latency-9cea0a05f577) を少しアレンジして書いています。(本人了承済み)

### 伝説のエンジニア - ジェフ・ディーン

ヘッジ・リクエストは2013年 ACM誌掲載の[The Tail at Scale](https://cacm.acm.org/magazines/2013/2/160173-the-tail-at-scale/fulltext)にて説明されています。また、翌年の[2014のO'Reilly Velocity カンファレンス](https://youtu.be/1-3Ahy7Fxsc?t=980)にて説明されています。

そう、あの[伝説のエンジニア　ジェフ・ディーン](https://qiita.com/umegaya/items/ef69461d6f4967d5c623)によって。

現在、ジェフ・ディーンは`グーグル AI`のリードであり、`TensorFlow`など機械学習関連のイベントなどに登壇しており、[そのお姿を拝見する](https://www.youtube.com/watch?v=G38y1h-cGOg)ことができます。そして、ジェフは`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`という言葉もあります。

> 余談。カタカナ英語はあまり使わない方が良い。[リスニング、英会話を向上させる最短ルート
](https://qiita.com/tfutada/items/91d727ef435c18fb8dba)

## Goコーディングの例

前置きが長くなりましたが、ヘッジ・リクエストのGo実装を説明します。

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

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

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

![Screen Shot 2020-12-12 at 16.22.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/75231/57e3975f-a66d-5ec0-9814-ada4169dfff1.png)

### ダミーサービスの作成

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

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

３つのモジュールすべて、私のMacBookAir上で実行していますが、15ms + 数msのオーバーヘッドで実行できました。
実際には本番サービスの95%ileのレイテンシーを計測し、ヘッジ・リクエストのパラメータ調整することになります。

```zsh:コマンドライン実行
$ 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**を使用すると[タイムアウト](https://gobyexample.com/timeouts)をエレガントに実装できます。

```go: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** と大きく改善しました。

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

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

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

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

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

> [参考: Go言語の並行処理デザインパターン by Rob Pike 前編](https://qiita.com/tfutada/items/dc8db894ac270a79ef2b)