一、背景
最近做云服务 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 分多钟,之后便不再重试。
总结
回到开头的问题,在遇到限流错误的时候,通过指数退避算法进行重试,我们可以最大程度地避免再次限流。相比于固定时间重试,指数退避加入了时间放大性和随机性,从而变得更加“智能”。至此,我们再也不用担心限流让整个测试程序运行中断了~