1.背景本文同时发表在Prodesire公众号和Prodesireblog。最近在云服务API测试项目中，发现有时候会调用大量的API，导致报限流的错误。遇到这样的错误，传统的重试策略是每隔一段时间重试一次。但是由于是定时重试，在重试的时候会有大量的请求同时涌入，会不断的造成限流。这让我想起了两年前，我查看CeleryTask的文档，发现任务可以设置retry_backoff，使得任务失败时以指数退避的方式重试。那么指数退避到底是什么样子的呢？2.Exponentialbackoff根据wiki上Exponentialbackoff的描述，exponentialbackoff是一种算法，通过反馈以指数方式降低进程的速率，逐渐找到一个合适的速率。在以太网中，这种算法通常用于调度冲突后的重传。延迟重传是根据时隙和重传尝试次数确定的。在c次碰撞后（例如失败的请求），选择0到$2^c-1$之间的随机值作为槽数。对于第一次冲突，每个发送方将等待0或1个时隙来发送。第二次碰撞后，发送方会等待0到3个（按$2^2-1$计算）个时隙发送。第三次碰撞后，发送端会等待0到7（$2^3-1$）个时隙发送。依此类推……随着重传次数的增加，延迟程度呈指数增长。说白了就是每次重试的时间间隔是上一次的两倍。3.指数退避的期望值考虑退避时间的均匀分布，退避时间的数学期望是所有可能性的平均值。也就是说，经过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}$$那么对于上面提到的例子：在第一次碰撞之后，退避time期望为$E(1)=\frac{2^1-1}{2}=0.5$第二次碰撞后，退避时间期望为$E(2)=\frac{2^2-1}{2}=1.5$第三次碰撞后退避时间期望为$E(3)=\frac{2^3-1}{2}=3.5$4.指数退避的应用4.1指数退避algorithminCelery获取指数退避时间的函数在celery/utils/time.py:defget_exponential_backoff_interval(factor,retries,maximum,full_jitter=False):"""计算指数退避等待时间。"""#将是如果因子等于0，则为零countdown=factor*(2**retries)#Fulljitteraccordingto#https://www.awsarchitectureblog.com/2015/03/backoff.htmliffull_jitter:countdown=random.randrange(countdown+1)#根据最大??等待时间调整并考虑负值。returnmax(0,min(maximum,countdown))其中factor是退避系数，作用于整体退避时间。而retries对应上面的c（即碰撞次数）。核心内容countdown=factor*(2**retries)和上面提到的指数退避算法是一致的。在此基础上，可以将full_jitter设置为True，意思是在退避时间上做一次“抖动”，具有一定的随机性。最后就是限制给定值不超过最大值，避免无限等待。但是，一旦达到最大退避时间，可能会导致多个任务再次同时执行。有关更多信息，请参见Task.retry_jitter。4.2《UNIX 环境高级编程》中的连接示例在《UNIX 环境高级编程》（第3版）的16.4章节中，也有使用指数退避建立连接的示例：#include"apue.h"#include
