Exponential backoff を実例で理解する - リサーチ・アンド・イノベーション開発者ブログ

　RNI dev の K.oshima です。 network mobility が好きです。

　弊社のサービス Mycomment はユーザーのアクセス解析に Woopra と言うサービスを利用しています。先日、Mycomment と Woopra のデータコレクター間の通信が失敗した結果、ログ監視にエラーが大量に上がってくる事象がありました。

　失敗理由は特定データコレクターまでの経路消失です。

　どうすればよかったかというと、一度目の通信失敗後にリトライして欲しかった。リトライすればハズレを引かずに成功する可能性があった。Woopra SDK がリトライしてくれればよかった話なのですが、実際にはリトライ機能がないため SDK を利用する利用者(rni-dev)が失敗したらリトライするように書く必要があります。

　この待ってリトライするときに、一般によくある実装ではリトライが失敗するたびにリトライ間隔を長くしていきます。 Railsで良く使われる Sidekiq や先日紹介したfaktory でも同じロジックがリトライ制御に使われています。 Mycomment のリトライも同様に実装したいと思います。
　なぜそうするのでしょう。

イーサネットの例

　きっかけはアプリケーションからの HTTP の利用なのでレイヤー7の話ですが、これからレイヤー1の話をします。（注意点：レイヤー1の話がそのままレイヤー7にも通じる訳ではないので、そこは分けて考えてください）

　古いイーサネット(Ethernet)は 1本のケーブルに複数の機器をつないで通信する実装です。（今一般的な 1000BASE-T とは違い昔は本当に電線1本だったんです。） AさんもBさんもCさんも同じ1本のケーブルで通信します。

　糸電話を想像してください。タコ糸に紙コップを結ぶあれです。

　二人だけで糸電話で話すと「もしもし」「どうぞ」と話す側と聴く側に別れて通信します。役割分担がうまくいけば、（ランチにカレーを食べに行こう！などの）通信は成立します。

　3人以上で糸を共有（分岐）して糸電話で話すと、もしAさんとBさんが同時に喋った場合は、同じ糸を分岐して聞いていたCさんはAさんとBさんの声が同時に聞こえて何をしゃべっていたのか聞き取れなくなります。

　同時に喋ることがあってもうまいこと通信を成立させるルールのひとつが CSMA/CD (Carrier Sense Multiple Access with Collision Detection) です。（電線の場合は、同時に喋っている人がいるかいないか通信の有無が電圧でわかります。） 1. データを送りたい人はまず受信してみる。
Aさん「（今は誰も話してないぞ）」 2. 他の人が送信中の場合は待つ。（→ 1. へ）他の人が送信していない時は、データを送りたい人が送信する。
Aさん「Bさんランチにカレーを食べに行きませんか？」 3. 自分が送信中に、もし他の人も送信しだした時は通信をあきらめて止める。乱数秒待った後に再度送信をトライする。
Aさんが話している途中にCさんも話し出したら、AさんもCさんも黙る。そしておのおのが乱数秒待つので、次にAさんとCさんが話し出すタイミングはズレるはず。
さらに衝突した場合は、n回目のリトライの時は 0 から 2**n の範囲の待ち時間からランダムに一つ選んで待つ。混んでいると待ち時間が伸びる傾向になる。

　下手をすると、誰も送信していない瞬間をずっと待つ必要がありますがいつかは送信できます。こんな簡単なルールでたいていの場合はうまくいきます。

CSMA/CA

　他のルールとして、無線 LAN で利用されている CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) もあります。 1. データを送りたい人はまず受信してみる。
Aさん「（今は誰も話してないぞ）」 2. 他の人が送信していない時は、データを送りたい人が送信する。
Aさん「Bさんランチにカレーを食べに行きませんか？」 3. 他の人が送信している時は、その人の送信が終わるのを待ってすぐに自分が送信すれば、他に送信の順番を待っている人と同時に送信する可能性がある。
BさんもCさんも喋りたい時に、Aさんの話が終わるのを待って終わった瞬間に話し出すとかぶる可能性が高い。他の人の送信が終わって、乱数秒待ってから送信を開始すると他の誰かとかぶりにくい。

　どちらも簡単なルールで、全員が待ち状態になるデッドロックも起きないうまいやり方です。ただ、5人や10人が1本のケーブルを利用しているすいている時はうまくいっても、100人1000人が1本のケーブルで話そうとすると大渋滞になります。待ってる時間が長くなって、送信できる機会が減るので、通信速度が遅くなったように見えます。

乱数と待ち時間の延長

　待ち時間を決めるのに乱数の要素があるのはなぜか。もし乱数がなければ、1本のケーブル（リソース）を100人が一斉に利用しようとすると、1人が利用開始して残り99人が待ちます。99人は同じ時間待つので次回送信しようとした際に99人の競合になります。乱数で待ち時間が変われば、100人の各々のタイミングがずれてリトライの際に他の誰とも送信がかぶらない可能性があります。リトライの回数が減って待ち時間の合計が減って結果としてスループットが上がる可能性があります。
　待ち時間をリトライのたびに長くするのはなぜか。1本のケーブルを複数人で利用するときに空いてくるのを待つための工夫です。一つのリソースを大勢で使うためにはゆずり合う必要があります。ゆずり合うための工夫です。

　ここまでの話はざっくりとしたレイヤー1の話です。これがそのまま HTTP 経由のサーバーとクライアントの関係に当てはまるわけではありませんが、（現実には Woopra のデータコレクターは複数 IP ありますし、1個の IP あての通信をロードバランサーで受けて裏側の複数のサーバに負荷分散しているはずです。） 1. 混雑を避ける、2. リトライする要素は共通です。

メール送信の例

　待ち時間をリトライのたびにだんだん長くするテクニックは、email の送信にも使われています。宛先を間違えたメールを送信した場合、SMTP サーバがなんども送信を試して最終的に設定されたリミット（2日など）に引っかかり諦めて送信者に MAILER-DEAMON からの不達メールが返ってくることがあります。SMTPサーバ（sendmail, postfix 等）が再送を試す際にもリトライまでの待ち時間をだんだんと長くする技が使われています。受け手のサーバの処理が溢れてパンクしている時にも送信者（ユーザー）の操作なしに SMTPサーバの陰の働きにより送信可能になる時を待ちメールを配達する工夫です。

　以下は、postfix のマニュアルから引用です。

$ man 8 qmgr

http://www.postfix.org/qmgr.8.html

   exponential backoff
         Mail  that  cannot  be  delivered  upon  the  first  attempt  is
         deferred.   The  time interval between delivery attempts is dou-
         bled after each attempt.

TCP プロトコルの例

　リトライのたびに待ち時間を長くするアルゴリズムを Exponential back off と呼びます。

　TCP/IP の TCP でも Exponential back off は使われています。

　以下は NetBSD 5 での TCP 実装ですが、TCP のパケットが届かず再送を要求した時に、 tcp_backoff を引いて再送待ち時間 t_rxtcur を伸ばしていくところです。

https://github.com/IIJ-NetBSD/netbsd-src/blob/458bd6ba699726d5269e01d428ee889762fcffbf/sys/netinet/tcp_timer.c#L384

/*
 * Retransmission timer went off.  Message has not
 * been acked within retransmit interval.  Back off
 * to a longer retransmit interval and retransmit one segment.
 */

if (++tp->t_rxtshift > TCP_MAXRXTSHIFT) {
  tp->t_rxtshift = TCP_MAXRXTSHIFT;
  TCP_STATINC(TCP_STAT_TIMEOUTDROP);
  tp = tcp_drop(tp, tp->t_softerror ?
      tp->t_softerror : ETIMEDOUT);
  goto out;
}
TCP_STATINC(TCP_STAT_REXMTTIMEO);
rto = TCP_REXMTVAL(tp);
if (rto < tp->t_rttmin)
  rto = tp->t_rttmin;
TCPT_RANGESET(tp->t_rxtcur, rto * tcp_backoff[tp->t_rxtshift],
    tp->t_rttmin, TCPTV_REXMTMAX);
TCP_TIMER_ARM(tp, TCPT_REXMT, tp->t_rxtcur);

　ここの計算。

TCPT_RANGESET(tp->t_rxtcur, rto * tcp_backoff[tp->t_rxtshift],
        tp->t_rttmin, TCPTV_REXMTMAX);

　tcp_backoff は

https://github.com/IIJ-NetBSD/netbsd-src/blob/458bd6ba699726d5269e01d428ee889762fcffbf/sys/netinet/tcp_timer.c#L294

const int  tcp_backoff[TCP_MAXRXTSHIFT + 1] =
    { 1, 2, 4, 8, 16, 32, 64, 64, 64, 64, 64, 64, 64 };

とタイムアウトのたびに大きくなり 64 で上限にぶつかる数字になっています。

　注釈: 意外に思われるかもしれませんが、TCPの実装は時代によって変化しているので、OSの種類やバージョンによってはこの再送待ちの挙動は異なります。

QUIC プロトコルの例

　TCP の欠点をつぶそうとしている新しいプロトコル QUIC の例として、 Google Chrome の QUIC 実装を見てみましょう。
　パケット送信する部分で、再送待ちタイマーの値を計算するところ。 consecutive_rto_count_ 分再送の待ち時間を長くしていきます。
https://chromium.googlesource.com/chromium/src/net/+/master/quic/core/quic_sent_packet_manager.cc#830

// Calculate exponential back off.
retransmission_delay =
retransmission_delay *
(1 << std::min<size_t>(consecutive_rto_count_, kMaxRetransmissions));

　このように Google の QUIC プロトコルでも exponential back off アルゴリズムは使われています。

ここに使いたい

　発端となった Woopra SDK で再送信する時に待ち時間を伸ばす理由は、メール送信と同じです。
　相手が受け取れなかったのなら再送信したい。しかし、即再送信しても相手のサーバ負荷が原因だった場合は再び受け取れない可能性が高い。少し待ってから再送信したい。その「少し待って」の時間はどうやって決めるの？失敗する間はリトライの待ち時間を徐々に伸ばしていって、相手が受け取れるタイミングを待つために exponential back off を使います。
　自サイトの（Railsアプリごとの）複数の送信が相手の負荷を再び高めないように、乱数秒追加して再送タイミングもばらけさせるとなお親切ですね。通信相手にも負担にならないし、失敗の原因を一つ減らすので自分のサービスにもプラスです。

お待ちしております

　上のような話に興味を持たれる方。そんなの知っているよ、 Linux 4.15 では違うよ。どちらの感想を持つ方も RNI ではお待ちしております。