aiwiki.page
中文
计算机 / 网络与安全 / exponential-backoff

指数退避

指数退避是一种重试策略,在连续失败后按倍数延长等待间隔,通常引入随机性以减少争用和同步重试。

15 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
算法分布式计算随机化算法期望值应用程序接口云计算数据库事务超文本传输协议指数退避

指数退避是一类算法,在反复尝试执行某项操作时,按一定倍数延长两次尝试之间的等待间隔,这个倍数通常为二。当尝试因资源繁忙、网络传输发生碰撞或服务暂时不可用而失败时,就可以采用指数退避。通过拉开失败后的重试间隔,它可以降低重试产生的负载,为系统恢复留出时间。许多实现还会随机调整等待间隔,避免相互争用的参与方反复同时重试。

基本机制

一种简单的指数退避方案为第 kk 次重试设置如下等待时间:

dk=min⁡(dmax⁡,d0bk),k=0,1,2,…,d_k=\min(d_{\max},d_0b^k), \qquad k=0,1,2,\ldots,

其中:

  • d0>0d_0>0 为初始退避间隔;
  • b>1b>1 为增长因子;
  • dmax⁡d_{\max} 为允许的最大间隔;
  • k=0k=0 表示初次尝试失败后的第一次重试。

如果初始间隔为 100 毫秒,增长因子为二,那么不设上限时,各次间隔依次为 100、200、400、800 毫秒,以此类推。最大间隔用于防止等待时间无限增长。

上述公式描述的是一种确定性的时间安排。在随机化实现中,dkd_k 也可以用来定义等待窗口的上界,再从该窗口内抽取实际等待时间。

实现通常还会规定:

  • 哪些失败可以重试;
  • 尝试次数或重试次数的上限;
  • 总体时间限制;
  • 成功后如何重置退避状态;
  • 服务器提供的重试指示如何影响重试安排。

这些选择属于重试策略,而不是指数增长本身必然带来的结果。尤其要注意,最大间隔并不意味着重试次数也有上限:除非其他条件使其停止,否则进程可以一直按达到上限后的间隔重试。

延长等待时间为何有效

立即重试可能使导致最初失败的状况进一步恶化。如果服务已经过载,每次请求失败后立刻再次发出请求,都会消耗额外的处理能力。如果大量客户端都这样做,重试流量就可能拖延恢复,或引发更多故障。

指数退避提供了负反馈:连续失败会促使参与方降低尝试频率。偶发的短暂故障只会带来较短的等待,而持续故障则会带来逐渐延长的暂停。

这种机制在分布式计算系统中尤其有用,因为各参与方并不总能协调对共享资源的访问。每个参与方都可以根据自身观察到的失败调整行为。不过,仅凭失败无法确定原因:过载、网络丢包、依赖项不可用以及无效请求,都可能产生表面相似的结果。只有在适合重试的情况下,退避才有效。

与固定间隔重试相比,指数退避能更快地降低持续重试带来的压力。在线性退避中,等待时间每次增加一个固定值;相比之下,指数退避经过更少的尝试就能达到较长的等待间隔。相应的代价是,一旦参与方的等待间隔已经很长,就需要更长时间才能发现系统已恢复。

随机化与抖动

确定性的退避不一定能错开各客户端的重试。如果数千个客户端同时失败,并采用完全相同的时间安排,它们可能始终保持同步,反复产生突发流量。

重试等待时间中的随机变化通常称为重试抖动。它使重试调度成为一种随机化算法,将各次尝试分散到不同时间。

常见的模式有以下几种,不过各程序库使用的术语可能不同。

全抖动

实际等待时间从零到当前指数退避上界的范围内均匀抽取:

Dk∼Uniform⁡(0,dk).D_k\sim\operatorname{Uniform}(0,d_k).

其期望值为

E[Dk]=dk2.\mathbb{E}[D_k]=\frac{d_k}{2}.

因此,即使上界相同,全抖动策略与确定性策略的平均等待时间也不相同。在比较两者的重试频率时,这一区别很重要。

等量抖动

一种变体将间隔的一半保留为固定等待时间,另一半则随机确定:

Dk=dk2+Uniform⁡ ⁣(0,dk2).D_k=\frac{d_k}{2} +\operatorname{Uniform}\!\left(0,\frac{d_k}{2}\right).

其等待时间的期望值为 3dk/43d_k/4。与全抖动不同,这种构造不会产生任意接近零的等待时间。

去相关抖动

还有一些策略根据上一次随机产生的等待时间来选择下一次等待时间,而不只是依据重试次数。例如:

Dk+1=min⁡ ⁣(dmax⁡,Uniform⁡(d0,3Dk)),D_{k+1} =\min\!\left(d_{\max}, \operatorname{Uniform}(d_0,3D_k)\right),

其中 D0=d0D_0=d_0。这种策略生成的序列不同于在指数增长的窗口内分别独立抽样得到的序列。具体公式和达到上限时的处理方式因实现而异。

随机化可以减少同步尝试,但不能保证完全消除。计时器分辨率过低、随机数序列之间存在相关性,或服务器指定了统一的重试时间,仍可能造成突发流量。

网络领域的起源与应用

共享介质以太网

指数退避早期的一项重要用途,是共享介质、半双工以太网采用的二进制指数退避。在带碰撞检测的载波侦听多路访问机制下,站点能够检测到同时发生的传输产生了碰撞,然后等待一段时间再尝试重传。

某一帧发生第 nn 次碰撞后,站点会从以下形式的范围中选择一个整数,作为等待的时隙数:

r∈{0,1,…,2min⁡(n,10)−1}.r\in\{0,1,\ldots,2^{\min(n,10)}-1\}.

随着碰撞次数增加,随机选择的范围逐步扩大,直至达到上限。经典以太网还规定了有限的尝试次数。“二进制指数”指的是争用窗口成倍扩大,并不意味着每次实际等待时间都恰好是上一次的两倍。

这种碰撞恢复机制适用于共享介质、半双工以太网。现代交换式全双工以太网链路在常规链路访问中不使用碰撞检测和退避。

传输协议

传输控制协议在重传超时连续发生后,会对重传超时时间采用指数退避。其初始超时时间根据测得的往返情况确定,连续超时则会使其增大。

这不同于将每两次数据包传输之间的间隔都加倍。TCP 还包含确认处理和拥塞控制机制,因此不能用单一的退避公式概括其行为。

应用服务

客户端在访问应用程序编程接口、重新连接服务或与云计算基础设施通信时,广泛采用指数退避。它也用于数据库事务因可重试的并发冲突而失败后的重试,以及后台消息处理系统。

在超文本传输协议中,响应可以包含 Retry-After 字段,指示应在何时进行下一次尝试。这一信号独立于客户端自身的指数退避安排,必须根据相关协议和服务策略进行解释。请求是否可以重试,不仅取决于状态码,还取决于操作语义及其可能产生的副作用。

正确性与重试安全

退避控制的是下一次尝试何时发生,并不能保证重复执行操作是安全的。

超时的含义尤其不明确。即使响应未能到达客户端,服务器也可能已经完成操作。因此,重复发送付款、作业提交或资源创建请求,可能导致其效果重复发生。

具有幂等性的操作,重复执行与仅执行一次所产生的预期效果相同。其他操作有时可以借助请求标识符、去重记录或事务协调,实现安全重试。这些机制与退避是相互独立的。

对失败进行分类同样重要。临时连接故障可能值得再次尝试,而无效请求或权限不足通常需要改变相关条件,而不是延长等待时间。重试永久性失败只会消耗资源,并不会提高成功的可能性。

时间安排与运行限制

采用不设上限的确定性策略时,在执行完 mm 次重试之前,累计退避等待时间为

Tm=∑k=0m−1d0bk=d0bm−1b−1.T_m =\sum_{k=0}^{m-1}d_0b^k =d_0\frac{b^m-1}{b-1}.

这不包括执行时间、网络延迟,以及等待每次失败尝试超时所花费的时间。因此,仅靠累计退避间隔,无法可靠地落实总体截止时间。

完整的实现会区分单次尝试的超时时间与整个操作的截止时间。它还会考虑取消操作,以及剩余时间是否足以再进行一次有意义的尝试。在采用异步编程的软件中,计时器可以挂起正在重试的操作,而不阻塞执行线程。

架构中多个层级的重试可能使流量成倍放大。如果三个嵌套层级中,每层最多尝试三次,且包含初次尝试,那么一次顶层操作在最底层最多可能引发 33=273^3=27 次尝试。各层独立的退避策略本身无法防止这种放大效应。

局限性与互补机制

指数退避并不能普遍保证稳定性、公平性或最终成功。

  • 持续过载: 即使拉开了间隔,重试仍然是额外工作。如果系统原有需求已超出容量,仅靠退避可能无法恢复。
  • 恢复感知延迟: 当客户端的等待时间接近最大间隔时,即使服务已经恢复,它也可能仍处于等待状态。
  • 访问机会不均: 成功的参与方可能重置退避状态,而失败的参与方继续等待,导致争用时各方获得的访问机会不均。
  • 同步流量仍然存在: 随机化可以降低客户端之间的同步程度,但无法消除所有突发流量。
  • 执行时间无界: 如果只设置等待时间上限,却不限制尝试次数或设置截止时间,操作就可能永远重试下去。

相关机制可以处理这些问题的不同方面。限流约束一段时间内允许进入的流量。熔断器模式会在连续失败后暂时阻止调用。重试预算限制重试所能产生的额外流量,而负载均衡可以将请求分配给可用实例。这些控制机制可以与指数退避配合使用,但没有任何一种能使原本不宜重复执行的操作变得可以安全重复。