指数退避算法设计与原理
指数退避算法设计与原理
ivansli重试
在业务开发过程中,经常会听到有人说:xx 问题在失败的情况下,可以进行重试,就能增加成功的概率。
那么,重试是什么?
举个现实中的小例子:
时间:
古时候某个朝代的某一天
事情:
妈妈让小明去叔叔家找叔叔问件事情
问题:
小明去叔叔家后发现家里没人。那么,小明应该怎么办?
方案:
① 在叔叔家门口一直等到他回来
② 先回自己家,等段时间再去叔叔家,看看他回来没
③ 留个字条贴到叔叔家门上,等他回来看到后,来找自己
为什么设定为古时候?
是因为设定在当代的话,可能有人会说给叔叔打个电话不就行了。这里仅仅是为了设定某种场景来抛出问题
映射到实际开发中,分别对应:
① 阻塞等待
② 重试
③ 回调
在本文中,讨论的重点是②以及小明应该回自己家等待多久再去找叔叔。
可重试与不可重试
重试应该针对具体情况进行,不应该是在发生任何错误的情况下都进行重试。
假设:有两个服务A、B,调用关系A调用B
,在 B 发生错误之后, A需要重试。
举2个case:
① A调用B服务时,传递的参数有误,导致B服务处理失败
② A调用B服务时,由于B服务计算资源紧张/网络问题,导致B服务处理超时/失败
上面2个case,可以看出:
对情况①进行重试毫无意义。因为每次重试都会返回错误,重试反而会造成资源的浪费
对情况②进行重试意义非凡。因为一般会在预期时间内重试成功
所以,针对可重试与不可重试,小结如下:
可重试的情况
暂时性问题相关的响应,通常可以重试不可重试的情况
与永久错误相关的响应,表明需要进行更改(例如更改授权、配置与参数),然后重试请求才有用
重试策略
通常某服务发生故障后,一般会使用固定时间间隔再重试一次。
但会带来一些问题:同一时间可能有很多请求在重试,可能会造成无意义的请求。
为什么会有很多请求在重试?
如今编程一般是多线程、协程的模式,多个线程、协程都在同一时刻重试就会造成大量请求在重试。
为什么会造成无意义的请求?
如果在某一时刻服务还没有恢复,此刻的重试就是无意义的重试。
解决方案:
截断指数退避算法,利用指数递增+随机
的方式获取下次重试的时间。
简而言之:把均匀时间间隔的重试变成指数递增时间间隔的重试
截断指数退避算法
以不具有随机特性的指数退避为例,如下所示:
设置 | 默认值(以秒为单位) |
---|---|
初始等待时间 | 1 |
每次迭代的等待时间乘数 | 2 |
最长等待时间 | 60 |
默认截止时间 | 120 |
具体次数与等待时间的关系,如下所示:
第N次重试 | 等待时间 |
---|---|
1 | 1 |
2 | 2 |
3 | 4 |
4 | 8 |
5 | 16 |
6 | 32 |
7 | 60 |
8 | 60 |
… | … |
N-1 | 总时长小于120 |
你是否注意到截断这个词,那么问题来了:截断是什么意思?
通过指数的递增来获取下一次重试的时间值没问题,问题就在于:不可能无限的重试下去,一定会有一个上限值
当下一次重试的时间值达到了上限值,则就会被截断为 上限值
一些实现
在各种开源项目以及第三方SDK中经常可以见到对应的实现,这里以 etcd、grpc-go为例说明。
etcd
client/v3/watch.go
1 | // openWatchClient retries opening a watch client until success or halt. |
重试时间从 1毫秒 开始,每次在上次等待时间之上增加 1/4,直到 maxBackoff(超过 maxBackoff ,则使用 maxBackoff)。
grpc-go
backoff/backoff.go
1 | package backoff |
一般来说在涉及截断退避算法
实现时,需要以下几个信息:
1.回退的起始等待时间 (BaseDelay)
2.每次回退的递增系数,应该大于等于1 (Multiplier)
3.随机数系数 (Jitter)
4.最大的回退上限 (MaxDelay)
使用方式internal/backoff/backoff.go
1 | // Backoff returns the amount of time to wait before the next retry given the |
其他参考
1.https://cloud.google.com/storage/docs/retry-strategy#client-libraries Google Cloud重试策略
2.https://en.wikipedia.org/wiki/Exponential_backoff 维基百科-指数退避