exponential backoffのメモ

exponential backoffとは?

データ送信処理が失敗して再送信するときに、失敗回数が増えるに連れて再送信するまでの待ち時間を指数関数的に増やす仕組みを exponential backoff という。

有名な例としては Carrier sense multiple access with collision detection (CSMA/CD) や Carrier sense multiple access with collision avoidance(CSMA/CA) といった通信方式で、失敗回数 N に対して、[0, 2^N-1] からランダムな数を選び、その slot time 分だけ待って再送信するようになっている。

ランダムに選んでいるのは、複数の通信が同じタイミングで失敗した時に、また同じタイミングで再送されないようにするため。

また、失敗回数が一定値を超え場合に、待ち時間に上限を設けているものを truncated exponential backoff と呼ぶ。例えば、失敗回数 N が 10 以上を超えると truncate する場合、失敗回数が 10 でも 16 でも [0, 2^10 - 1] = [0, 1023] の間から選ぶ。16回目だからといって [0, 2^16 - 1] から選んだりはしない。

CSMA/CA のフロー図

English: Diagram of CSMA-CA algorithm with RTS/CTS exchange as provided by 802.11 standard

実際の例

ここからは身近に使われている(=google 検索した時に上位に来る)クライアントライブラリの HTTP 通信時の exponential backoff の例を確認
アルゴリズムに微妙な差異がある

google HTTP client library

http://javadoc.google-http-java-client.googlecode.com/hg/1.15.0-rc/com/google/api/client/http/ExponentialBackOffPolicy.html

retry_interval = retry_interval * multiplier ^ (N - 1)
randomized_interval := retry_interval * (random value in range [1 - randomization_factor, 1 + randomization_factor])
  • HTTP のレスポンスコードが 500 または 503 の場合にリトライ
  • デフォルト値は retry_interval は 0.5 秒,randomization_factor は 0.5, multiplier は 1.5, max_interval は 1 minute, max_elapsed_time は 15 秒
  • retry_interval が max_elapsed_time(15秒) を超えると、リトライをやめる(デフォルト値だと10回目)
request retry_interval randomized_interval
01      00.50          [0.25, 0.75]
02      00.75          [0.38, 1.12]
03      01.12          [0.56, 1.69]
04      01.69          [0.84, 2.53]
05      02.53          [1.27, 3.80]
06      03.80          [1.90, 5.70]
07      05.70          [2.85, 8.54]
08      08.54          [4.27, 12.81]
09      12.81          [6.41, 19.22]
10      19.22          STOP

google drive SDK

https://developers.google.com/drive/handle-errors#implementing_exponential_backoff

randomized_interval := 2 ^ N + (random value in range [0, 1000]) # ミリ秒
  • HTTP ステータスコードが 403 の場合にリトライ。
  • リトライは5回まで。
request randomized_interval
1       [1, 1002]
2       [2, 1003]
3       [4, 1005]
4       [8, 1009]
5       [16, 1017]
6       STOP

AWS SimpleDB

http://aws.amazon.com/articles/Amazon-SimpleDB/1394

randomized_interval := (random value in range [0, 1)) * 100 * 4 ^ N # ミリ秒
  • HTTP ステータスコードが 500 番台の場合にリトライ。
request randomized_interval
1       [0, 400)
2       [0, 1600)
3       [0, 6400)
4       [0, 25600)
5       [0, 102400)
Advertisements
Tagged with:
Posted in algorithm
One comment on “exponential backoffのメモ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 4 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 4 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: