指數退避（Exponential backoff）在網絡請求中的應用

一、背景

最近做雲服務 API 測試項目的過程中，發現某些時候會大批量調用 API，進而導緻限流的報錯。在遇到這種報錯時，傳統的重試政策是每隔一段時間重試一次。但由于是固定的時間重試一次，重試時又會有大量的請求在同一時刻湧入，會不斷地造成限流。

這讓我回想起兩年前在查閱

Celery Task 文檔

的時候發現可以為任務設定

retry_backoff

的經曆，它讓任務在失敗時以

指數退避

的方式進行重試。那麼指數退避究竟是什麼樣的呢？

二、指數退避

根據 wiki 上對

Exponential backoff

的說明，指數退避是一種通過回報，成倍地降低某個過程的速率，以逐漸找到合适速率的算法。

在以太網中，該算法通常用于沖突後的排程重傳。根據時隙和重傳嘗試次數來決定延遲重傳。

在

c

次碰撞後（比如請求失敗），會選擇 0 和 $2^c-1$ 之間的随機值作為時隙的數量。

• 對于第 1 次碰撞來說，每個發送者将會等待 0 或 1 個時隙進行發送。
• 而在第 2 次碰撞後，發送者将會等待 0 到 3（ 由 $2^2-1$ 計算得到）個時隙進行發送。
• 而在第 3 次碰撞後，發送者将會等待 0 到 7（ 由 $2^3-1$ 計算得到）個時隙進行發送。
• 以此類推……

随着重傳次數的增加，延遲的程度也會指數增長。

說的通俗點，每次重試的時間間隔都是上一次的兩倍。

三、指數退避的期望值

考慮到退避時間的均勻分布，退避時間的數學期望是所有可能性的平均值。也就是說，在

c

次沖突之後，退避時隙數量在

[0,1，...，N]

中，其中 $N=2^c-1$ ，則退避時間的數學期望（以時隙為機關）是

$$E(c)=\frac{1}{N+1}\sum_{i=0}^{N}{i}=\frac{1}{N+1}\frac{N(N+1)}{2}=\frac{N}{2}=\frac{2^c-1}{2}$$

那麼對于前面講到的例子來說：

• 第 1 次碰撞後，退避時間期望為 $E(1)=\frac{2^1-1}{2}=0.5$
• 第 2 次碰撞後，退避時間期望為 $E(2)=\frac{2^2-1}{2}=1.5$
• 第 3 次碰撞後，退避時間期望為 $E(3)=\frac{2^3-1}{2}=3.5$

四、指數退避的應用

4.1 Celery 中的指數退避算法

來看下

celery/utils/time.py

中擷取指數退避時間的函數：

def get_exponential_backoff_interval(
    factor,
    retries,
    maximum,
    full_jitter=False
):
    """Calculate the exponential backoff wait time."""
    # Will be zero if factor equals 0
    countdown = factor * (2 ** retries)
    # Full jitter according to
    # https://www.awsarchitectureblog.com/2015/03/backoff.html
    if full_jitter:
        countdown = random.randrange(countdown + 1)
    # Adjust according to maximum wait time and account for negative values.
    return max(0, min(maximum, countdown))           

這裡

factor

是退避系數，作用于整體的退避時間。而

retries

則對應于上文的

c

（也就是碰撞次數）。核心内容

countdown = factor * (2 ** retries)

和上文提到的指數退避算法思路一緻。

在此基礎上，可以将

full_jitter

設定為

True

，含義是對退避時間做一個“抖動”，以具有一定的随機性。最後呢，則是限定給定值不能超過最大值

maximum

，以避免無限長的等待時間。不過一旦取最大的退避時間，也就可能導緻多個任務同時再次執行。更多見

Task.retry_jitter

。

4.2 《UNIX 環境進階程式設計》中的連接配接示例

在 《UNIX 環境進階程式設計》（第 3 版）的 16.4 章節中，也有一個使用指數退避來建立連接配接的示例：

#include "apue.h"
#include <sys/socket.h>

#define MAXSLEEP 128

int connect_retry(int domain, int type, int protocol,
                  const struct sockaddr *addr, socklen_t alen)
{
    int numsec, fd;

    /*
    * 使用指數退避嘗試連接配接
    */
    for (numsec = 1; numsec < MAXSLEEP; numsec <<= 1)
    {
        if (fd = socket(domain, type, protocol) < 0)
            return (-1);
        if (connect(fd, addr, alen) == 0)
        {
            /*
            * 連接配接接受
            */
            return (fd);
        }
        close(fd);

        /*
        * 延遲後重試
        */
        if (numsec <= MAXSLEEP / 2)
            sleep(numsec);
    }
    return (-1);
}           

如果連接配接失敗，程序會休眠一小段時間（

numsec

），然後進入下次循環再次嘗試。每次循環休眠時間是上一次的 2 倍，直到最大延遲 1 分多鐘，之後便不再重試。

總結

回到開頭的問題，在遇到限流錯誤的時候，通過指數退避算法進行重試，我們可以最大程度地避免再次限流。相比于固定時間重試，指數退避加入了時間放大性和随機性，進而變得更加“智能”。至此，我們再也不用擔心限流讓整個測試程式運作中斷了~