Exponential Backoff ってなんじゃらホイ？を Enumerator クラスで書いてみた

### 0. はじめに

今回の記事は Ruby 2.4.1 で動作確認しています 😗

### 1. Exponential Backoff And Jitter?

サーバーリクエストなんかのリトライ処理ってありますよね？

よくあるやっつけ実装が、以下みたいにリトライの最大回数と、待ち時間を定数で設定しておいて。。ってやつです

```ruby
(1..MAX_ATTEMPT).each do |attempt|
  break if request # リクエストが成功したら終了
  sleep RETRY_WAIT
end
```

でその定数ってのが、実装のときに適当に決めた、

- 最大回数 = 5（回）
- 待ち時間 = 5（秒）

とかを使っててそのまま。。ってのは意外とよくあるんじゃないかと思います。

この根拠のないリトライの最大回数と待ち時間について、もうちょっとよい決め方はないのかな〜って検索してみて見つけたのが、以下の記事です。

**参考：** [AWS Solutions Architect ブログ: Exponential Backoff And Jitter](https://aws.typepad.com/sajp/2015/03/backoff.html)

Exponential Backoff And Jitter というテクニックが紹介されています。

言葉の意味は、

- Exponential（指数的）
- Backoff（遅延）
- Jitter（ゆらぎ）

ってことらしいです :eyes: 

### 2. Enumerator を返そう？

それとは別に、こちらの記事で紹介されているテクニックも、どこかで使えないかな〜っと前から気になってました。

**参考：** [Ruby: EnumerableをincludeするよりEnumeratorを返そう（翻訳）](https://techracho.bpsinc.jp/hachi8833/2018_06_29/57698)

記事の趣旨としては、「そのクラスがコレクションなら `include Enumerable` すればいいけど、そうじゃないならメソッドで `Enumerator` オブジェクトを返すようにしとけばいいよ」ってことみたいです。

`Exponential Backoff` と `Enumerator`。

...そう、点と点がつながりましたね 😏

両者を組み合わせてコードにしてみました。

### 3. Exponential Backoff

*※ ここから先、引用されている計算式の引用元は、すべて [先程のブログ記事](https://aws.typepad.com/sajp/2015/03/backoff.html) です*

> sleep = min(cap, base * 2 ** attempt)

まずはゆらぎ（Jitter）のない Exponential Backoff パターンを書いてみました。

こんな感じです。

```ruby
module ExponentialBackoff
  def self.call(max_attempt: Float::INFINITY, capacity: Float::INFINITY, base: 1)
    Enumerator.new do |yielder|
      (1..max_attempt).each do |attempt|
        yielder << [capacity, base * 2 ** attempt].min
      end
    end
  end
end
```

使い方はこんな感じです。

```ruby
irb(main)> eb = ExponentialBackoff.call
=> #<Enumerator: #<Enumerator::Generator:0x007fefe68f5b28>:each>
irb(main)> eb.next
=> 2
irb(main)> eb.next
=> 4
irb(main)> eb.next
=> 8
```

`.call` を呼び出すことによって、Exponential Backoff な数値を列挙する `Enumerator` オブジェクトが得られます。

また、`.call` には３つのキーワード引数が指定できます。

```ruby
irb(main)> ExponentialBackoff.call.take(10) # 未指定の場合
=> [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
irb(main)> ExponentialBackoff.call(max_attempt: 5).take(10) # 最大回数
=> [2, 4, 8, 16, 32]
irb(main)> ExponentialBackoff.call(capacity: 100).take(10) # 最大値
=> [2, 4, 8, 16, 32, 64, 100, 100, 100, 100]
irb(main)> ExponentialBackoff.call(base: 10).take(10) # 倍率
=> [20, 40, 80, 160, 320, 640, 1280, 2560, 5120, 10240]
```

この `ExponentialBackoff` モジュールを利用して冒頭のリトライ処理を改善するとこのようになります。

```ruby
ExponentialBackoff.call(max_attempt: MAX_ATTEMPT).each do |eb|
  break if request # リクエストが成功したら終了
  sleep eb
end
```

ピタッと収まりました！ :smile: 

### 4. Exponential Backoff And Full Jitter

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

次は、ゆらぎ（Jitter）を入れていきます。といっても、コードに大きな違いはないですね。

こんな感じです。

```ruby
module ExponentialBackoffAndFullJitter
  def self.call(max_attempt: Float::INFINITY, capacity: Float::INFINITY, base: 1)
    Enumerator.new do |yielder|
      (1..max_attempt).each do |attempt|
        yielder << [capacity, rand(0..(base * 2 ** attempt))].min
      end
    end
  end
end
```

得られる数値はこんな感じです。

```ruby
irb(main)> ExponentialBackoffAndFullJitter.call.take(10)
=> [2, 4, 0, 2, 19, 26, 25, 107, 476, 513]
```

### 5. Exponential Backoff And Equal Jitter

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

これも、計算部分が異なるだけなので、あまり大きな違いはありません。

こんな感じです。

```ruby
module ExponentialBackoffAndEqualJitter
  def self.call(max_attempt: Float::INFINITY, capacity: Float::INFINITY, base: 1)
    Enumerator.new do |yielder|
      (1..max_attempt).each do |attempt|
        temp = [capacity, base * 2 ** attempt].min
        yielder << temp / 2 + rand(0..(temp / 2))
      end
    end
  end
end
```

得られる数値はこんな感じです。

```ruby
irb(main)> ExponentialBackoffAndEqualJitter.call.take(10)
=> [1, 2, 7, 14, 21, 50, 117, 179, 438, 957]
```

計算に除算が含まれていますが、`#to_f` や `#fdiv` を使っていないので小数は切り捨てです :rolling_eyes: 

### 6. Exponential Backoff And Decorrelated Jitter

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

今度は、計算中に「前回の計算値」が必要になってきます。

こんな感じです。

```ruby
module ExponentialBackoffAndDecorrelatedJitter
  def self.call(max_attempt: Float::INFINITY, capacity: Float::INFINITY, base: 1)
    Enumerator.new do |yielder|
      previous_value = base
      (1..max_attempt).each do |attempt|
        temp = [capacity, rand(base..(previous_value * 3))].min
        yielder << temp
        previous_value = temp
      end
    end
  end
end
```

得られる数値はこんな感じです。

```ruby
irb(main)> ExponentialBackoffAndDecorrelatedJitter.call.take(10)
=> [1, 2, 2, 6, 18, 37, 24, 34, 51, 34]
```

数値の増えたり減ったりが激しめですね :eyes: 

### 7. まとめ

今回の挑戦を通じて、Ruby の `Enumerator` クラスの理解が深まりました :smile: とても有用なクラスだと思いますので、積極的に使っていきたいと思います。

リトライ処理については、今後は少なくとも「5秒ごとに最大5回」よりはちょっとはマシなリトライ処理を、最初から実装しておくことができそうです。

もちろん、どの遅延パターンが最も効果的かについては、ケースごとに効果測定する必要がありますが、Jitter を入れるだけでも、リトライのタイミングを分散させて、サーバーの負荷を減らす効果があるはずです :wink: tabun

みなさんもぜひ使ってみてください :heart: