Exponential Backoff And JitterをGoで実装

Exponential Backoff And Jitterとは

リクエストが失敗した際のリトライ間隔を調整するためのアルゴリズムです
リトライのタイミングをずらすことによりリクエストの成功率を高くします。

Exponential Backoff

Exponential Backoffはリトライの間隔を指数関数的に増やしながらリトライを行う方法です

• 1回目のリクエスト失敗： 1秒待ってからリトライ
• 2回目のリクエスト失敗： 2秒待ってからリトライ
• 3回目のリクエスト失敗： 4秒待ってからリトライ

というように待機時間を増加させていきます。

Jitter

Exponential Backoffは一定間隔でリトライを行うため、多数のリクエストでリトライが発生した場合、リトライの実行タイミングが同じになってしまうという問題があります。

そのため、Jitterと呼ばれるランダム値を取り入れることによりリトライのタイミングをばらけさせる事ができます。

Exponential Backoff And Jitterの詳細は以下のブログにまとめられているのでご参照ください。
https://aws.typepad.com/sajp/2015/03/backoff.html

今回はこのブログで紹介されているJitter3パターンをそれぞれGo言語で実装してみました。

実装例

Exponential Backoff And Full Jitter

sleep = random_between(0 min(cap, base * 2 ** attempt))

※式の引用元：Exponential Backoff And Jitter

実装

main.go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

const base int = 1000
const cap int = 10000

func main() {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 5; i++ {
		Sleep(i)
	}
}

func Sleep(retryCount int) {
	temp := base * int(math.Pow(2, float64(retryCount)))
	if temp > cap {
		temp = cap
	}

	sleep := rand.Intn(temp)
	fmt.Printf("sleep: %d ms\n", sleep)
	time.Sleep(time.Duration(sleep) * time.Millisecond)
}

実行結果

$ go run main.go
sleep: 692 ms
sleep: 259 ms
sleep: 1846 ms
sleep: 7535 ms
sleep: 673 ms

Exponential Backoff And Equal Jitter

temp = min(cap, base * 2 ** attempt)
sleep = temp / 2 + random_between(0, temp / 2)

※式の引用元：Exponential Backoff And Jitter

実装

main.go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

const base int = 1000
const cap int = 10000

func main() {
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 5; i++ {
		Sleep(i)
	}
}

func Sleep(retryCount int) {
	temp := base * int(math.Pow(2, float64(retryCount)))
	if temp > cap {
		temp = cap
	}

	sleep := temp/2 + rand.Intn(temp/2)
	fmt.Printf("sleep: %d ms\n", sleep)
	time.Sleep(time.Duration(sleep) * time.Millisecond)
}

実行結果

$ go run main.go
sleep: 817 ms
sleep: 1889 ms
sleep: 3260 ms
sleep: 5198 ms
sleep: 9337 ms

Exponential Backoff And Decorrlated Jitter

sleep = min(cap, random_between(base, sleep * 3))

※式の引用元：Exponential Backoff And Jitter

実装

main.go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const base int = 1000
const cap int = 10000

func main() {
	rand.Seed(time.Now().UnixNano())
	prevSleep := base
	for i := 0; i < 5; i++ {
		prevSleep = Sleep(prevSleep, i)
	}
}

func Sleep(prevSleep int, retryCount int) int {
	sleep := rand.Intn((prevSleep*3)-base+1) + base
	if sleep > cap {
		sleep = cap
	}

	fmt.Printf("sleep: %d ms\n", sleep)
	time.Sleep(time.Duration(sleep) * time.Millisecond)
	return sleep
}

実行結果

$ go run main.go
sleep: 2218 ms
sleep: 2060 ms
sleep: 1845 ms
sleep: 4990 ms
sleep: 10000 ms

おわり

クライアントとサーバの負荷を軽減するために適切なリトライを！