指数関数的バックオフ (Exponential backoff) を確認と最小限の実装をしてみたメモ。
指数関数的バックオフ
指数関数的バックオフとは
指数関数的バックオフとは、プログラムやネットワーク機器がデータの送信処理に失敗したときに失敗回数に応じて再送信処理を実行するまでの待ち時間を指数関数的に増やす仕組みのことをいうらしい。 wikipedia の Exponential backoff ページを見ると CSMA/CA とか CSMA/CD は送信したデータの衝突を検出するとしばらく待ってからデータを再送信するけど、しばらく待つ時間は指数関数的に増やしていくみたいなのが書かれてる。そういえばそうだったなーみたいな感想だけどあらためて考えてみるとかなり古くから実装されているアルゴリズムなのだなと再認識した。
CSMA/CA とか CSMA/CD とかはデータの衝突を検出したらデータを再送信するのだけど、このときは再送信するときはできるだけデータが衝突するのを避けるために指数関数的バックオフのアルゴリズムを使っているようだ。
指数関数的バックオフを使うとき
プログラムとくにアプリケーションプログラムやツールとしてのプログラムはどんなときに指数関数的バックオフのアルゴリズムを使うとよさそうか。
プログラムとくにアプリケーションプログラムやツールとしてのプログラムはどんなときに指数関数的バックオフのアルゴリズムを使うのかを考えてみたけど、パッとイメージできるのは外部や内部のサービスの API を呼び出すときに指数関数的バックオフのアルゴリズムを使うとよさそう。プログラムが API サービスのクライアントとして API サービスにリクエストを送るとき、サーバーからのレスポンスのステータスコードは以下のいずれかに分類できる。
200
OK4xx
Client Error- 429 Too Many Requests
5xx
Server Error
このうち 200
は送信したリクエストが成功しているのでリトライの必要はなくて 4xx
はサーバーが「エラーになってるのはクライアントが原因」といってるので通常はリトライの必要はないというかリトライしてはいけないのだけど、サーバーが 429
を返してくるときはサーバーが「API のレートリミットに引っかかってるよ」といってるのでクライアントはリクエストの送信をリトライしたら成功する可能性がある。
あとサーバー5xx
を返してくるときだけど、サーバーが 5xx
を返してくるときはリクエストの送信をリトライするとリクエストが成功する可能性がある。
たとえばサーバーが 504
Gateway Timeout を返してくるときはサーバーのバックエンドタスクが過負荷に陥っていてリクエストがタイムアウトしているのを示しているので、クライアントはリクエストの送信をリトライしたら成功する可能性がある。
クライアントはサーバーが 429
とか 504
を返してくるときはリクエストの送信をリトライしたら成功する可能性があるけど、もし API のレートリミットに引っかかってサーバーが 429
を返してくるときはクライアントがすぐにリクエストを再送信してもまたレートリミットに引っかかる可能性が高い。
また、サーバーのバックエンドタスクが過負荷に陥っていてリクエストがタイムアウトしてサーバーが 504
を返してくるときは、クライアントがすぐにリクエストを再送信するとバックエンドタスクはまだ過負荷状態である可能性が高くて再送信したリクエストがまたタイムアウトになる可能性が高いし、バックエンドタスクが過負荷状態にあるときにすぐにリクエストを再送信するとさらにバックエンドタスクの負荷が高まってしまってバックエンドタスクがなかなか過負荷状態から抜け出せないかもしれない。
どちらのケースも単純に実装するなら「クライアントは十分な時間を待ってからリクエストを再送信する」でいいけど、十分な時間を待つというのはそれだけ待たされるということなので、できればそんなには待ちないのが望ましい……というときは指数関数的バックオフがいい感じにハマりそう。
クライアントはリクエストを送信 (再送信) してサーバーから 429
とか 504
が返されたら、すぐもしくは 少しだけ
待ってから1回目のリトライでリクエストを再送信する。たとえばもともとのリクエストに対して 429
が返ってきてたときは、1回目のリトライまでに API 呼び出しがレートリミットのしきい値を下回っててリクエストは1回目のリトライで成功するかもしれない。
指数関数的バックオフは、もし1回目のリトライが失敗したら 少しだけ
x 少しだけ
待ってから2回目のリトライでリクエストを再送信するけど、もし2回目のリトライも失敗したら今度は 少しだけ
x 少しだけ
x 少しだけ
待ってから3回目のリトライをして、もし3回目のリトライも失敗したら今度は 少しだけ
x 少しだけ
x 少しだけ
x 少しだけ
待ってから4回目のリトライをして……という感じにやっていく。
指数関数的バックオフの最小限の実装
Go で指数関数的バックオフの最小限の実装をしてみた。
実装コードを少しずつ見ていく。実装コードの全文は最後に記載しておく。
リトライをする処理はこんな感じのインタフェースを実装していく。
type Retryer interface { Process() ShouldRetry() bool MaxRetries() int }
リトライはこんな感じに実装した。
backoff()
関数は Retryer
インタフェースを実装した構造体を受け取ってリトライ回数に応じた待ち時間後に実際の処理 Retryer.Process()
を呼び出して Retryer.ShouldRetry() == true
ならまたリトライ回数に応じた待ち時間後に実際の処理 Retryer.Process()
を呼び出して……という感じにやっていく。
あとリトライは Retryer.MaxRetries()
以下までやるようにループ処理している (最初の処理は0回目のリトライと解釈)
func backoff(r Retryer) { for i := 0; i <= r.MaxRetries(); i++ { waitTime := getWaitTimeExp(i, 100) fmt.Printf("waitTime: %d\n", waitTime) // wait ... r.Process() if r.ShouldRetry() == false { return } } } func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) { if retryCount == 0 { return 0 } return int(math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds)) }
リトライをする処理はこんな感じで実装していく。
今回の関心事は指数関数的バックオフの実装なので実際にやる処理を実装する Process()
は何もしないでおく。
type MyRetryer struct { maxRetry int } func (m *MyRetryer) Process() { // 関心事はリトライの実行間隔なので特に処理することはない } func (m *MyRetryer) ShouldRetry() bool { // いまの関心事はリトライの実行間隔なので必ずリトライするように return true } func (m *MyRetryer) MaxRetries() int { return m.maxRetry }
実装するとこんな感じで待ち時間が指数関数的に増えていくのが確認できた。
waitTime: 0 waitTime: 200 waitTime: 400 waitTime: 800 waitTime: 1600 waitTime: 3200
実装コード全文
package main import ( "fmt" "math" ) type Retryer interface { Process() ShouldRetry() bool MaxRetries() int } type MyRetryer struct { maxRetry int } func (m *MyRetryer) Process() { // いまの関心事はリトライの実行間隔なので特に処理することはない } func (m *MyRetryer) ShouldRetry() bool { // いまの関心事はリトライの実行間隔なので必ずリトライするように return true } func (m *MyRetryer) MaxRetries() int { return m.maxRetry } func main() { r := &MyRetryer{maxRetry: 5} backoff(r) } func backoff(r Retryer) { for i := 0; i <= r.MaxRetries(); i++ { waitTime := getWaitTimeExp(i, 100) fmt.Printf("waitTime: %d\n", waitTime) // wait ... r.Process() if r.ShouldRetry() == false { return } } } func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) { if retryCount == 0 { return 0 } return int(math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds)) }
ジッター (ランダムな遅延時間)
指数関数的バックオフはだいたいジッターと呼ばれるランダムな遅延時間をサポートするようにしている。
ジッターはたとえば複数のクライアントが送信したリクエストに対してサーバーのバックエンドタスクが過負荷状態になっててサーバーが 504
を返しているとき、複数のクライアントすべてが同時にリクエストを再送信するとまたバックエンドタスクが過負荷状態に陥ってリクエストが失敗する可能性を低くするやり方のことらしい。
さっきのコードがジッターを実装するとこんな感じ。
import ( "fmt" "math" + "math/rand" + "time" )
backoff(r) } +func init() { + rand.Seed(time.Now().UnixNano()) +}
func getWaitTimeExp(retryCount int, baseDelayMilliSeconds int) (delayMilliSeconds int) { if retryCount == 0 { return 0 } + jitter := rand.Float64() + return int(jitter * math.Pow(2, float64(retryCount)) * float64(baseDelayMilliSeconds)) }
ジッターを実装するとこんな感じで待ち時間がバラけるのが確認できた。
waitTime: 0 waitTime: 163 waitTime: 216 waitTime: 702 waitTime: 1242 waitTime: 1799
AWS のエラー試行と指数関数的バックオフ
自分は仕事で AWS を使ってて CLI とか SDK から AWS の API を利用してるるけど、AWS の SDK は指数関数的バックオフを実装してるので SDK を利用するユーザーは特に意識することなく指数関数的バックオフとリトライできるようになっている。
AWS SDK for Go の指数関数的バックオフの実装はこのへん。 自分で指数関数的バックオフの最小限の実装をしたあとに SDK for Go のソースコードを見てインタフェースの名前とかメソッドの名前は参考にさせてもらった。
// AfterRetryHandler performs final checks to determine if the request should // be retried and how long to delay. var AfterRetryHandler = request.NamedHandler{ Name: "core.AfterRetryHandler", Fn: func(r *request.Request) { // If one of the other handlers already set the retry state // we don't want to override it based on the service's state if r.Retryable == nil || aws.BoolValue(r.Config.EnforceShouldRetryCheck) { r.Retryable = aws.Bool(r.ShouldRetry(r)) } if r.WillRetry() { r.RetryDelay = r.RetryRules(r) if sleepFn := r.Config.SleepDelay; sleepFn != nil { // Support SleepDelay for backwards compatibility and testing sleepFn(r.RetryDelay) } else if err := aws.SleepWithContext(r.Context(), r.RetryDelay); err != nil { r.Error = awserr.New(request.CanceledErrorCode, "request context canceled", err) r.Retryable = aws.Bool(false) return } // when the expired token exception occurs the credentials // need to be expired locally so that the next request to // get credentials will trigger a credentials refresh. if r.IsErrorExpired() { r.Config.Credentials.Expire() } r.RetryCount++ r.Error = nil } }}