指数退避算法设计与原理

ivansli 2022/01/29 619℃ 0

重试

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

其他参考

1.https://cloud.google.com/storage/docs/retry-strategy#client-libraries Google Cloud重试策略
2.https://en.wikipedia.org/wiki/Exponential_backoff 维基百科-指数退避

评论啦~