指数退避算法设计与原理

ivansli2022-01-292023-10-31

重试

在业务开发过程中，经常会听到有人说：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

// openWatchClient retries opening a watch client until success or halt.
// manually retry in case "ws==nil && err==nil"
// TODO: remove FailFast=false
func (w *watchGrpcStream) openWatchClient() (ws pb.Watch_WatchClient, err error) {
	backoff := time.Millisecond // 初始等待时间为1毫秒
	for {
		select {
		case <-w.ctx.Done():
			if err == nil {
				return nil, w.ctx.Err()
			}
			return nil, err
		default:
		}
		if ws, err = w.remote.Watch(w.ctx, w.callOpts...); ws != nil && err == nil {
			break
		}
		if isHaltErr(w.ctx, err) {
			return nil, v3rpc.Error(err)
		}

		if isUnavailableErr(w.ctx, err) {
			// retry, but backoff
			if backoff < maxBackoff {
				// 25% backoff factor
				backoff = backoff + backoff/4  // 每次回退时间在原基础上递增1/4
				if backoff > maxBackoff { // 大于上限，则使用上限值
					backoff = maxBackoff
				}
			}

			time.Sleep(backoff) // 休眠等待
		}
	}
	return ws, nil
}

重试时间从 1毫秒开始，每次在上次等待时间之上增加 1/4，直到 maxBackoff（超过 maxBackoff ，则使用 maxBackoff）。

grpc-go

backoff/backoff.go

package backoff

import "time"

// Config defines the configuration options for backoff.
type Config struct {
	// BaseDelay is the amount of time to backoff after the first failure.
	BaseDelay time.Duration
	// Multiplier is the factor with which to multiply backoffs after a
	// failed retry. Should ideally be greater than 1.
	Multiplier float64
	// Jitter is the factor with which backoffs are randomized.
	Jitter float64
	// MaxDelay is the upper bound of backoff delay.
	MaxDelay time.Duration
}

// DefaultConfig is a backoff configuration with the default values specfied
// at https://github.com/grpc/grpc/blob/master/doc/connection-backoff.md.
//
// This should be useful for callers who want to configure backoff with
// non-default values only for a subset of the options.
var DefaultConfig = Config{
	BaseDelay:  1.0 * time.Second,
	Multiplier: 1.6,
	Jitter:     0.2,
	MaxDelay:   120 * time.Second,
}

一般来说在涉及截断退避算法实现时，需要以下几个信息：
1.回退的起始等待时间 (BaseDelay)
2.每次回退的递增系数，应该大于等于1 (Multiplier)
3.随机数系数 (Jitter)
4.最大的回退上限 (MaxDelay)

使用方式
internal/backoff/backoff.go

// Backoff returns the amount of time to wait before the next retry given the
// number of retries.
func (bc Exponential) Backoff(retries int) time.Duration {
	if retries == 0 {
		return bc.Config.BaseDelay
	}

  // 起始大小，最大上限
	backoff, max := float64(bc.Config.BaseDelay), float64(bc.Config.MaxDelay)

  // 计算 第retries次 的回退数值
	for backoff < max && retries > 0 {
		backoff *= bc.Config.Multiplier
		retries--
	}

  // 如果得到的回退数字大于最大上限，则使用最大上限值
	if backoff > max {
		backoff = max
	}

  // 增加随机数
	// Randomize backoff delays so that if a cluster of requests start at
	// the same time, they won't operate in lockstep.
	backoff *= 1 + bc.Config.Jitter*(grpcrand.Float64()*2-1)
	if backoff < 0 {
		return 0
	}
	return time.Duration(backoff)
}