退避算法

退避算法（Backoff Algorithm）是一种在网络通信或并发系统中，当出现冲突、失败或过载时，通过等待一段时间后再尝试重新进行操作的策略。该算法的关键思想是：遇到问题时，不是立即重试，而是等待一段时间，且等待的时间长度逐渐增加。通过这种方式，避免了系统频繁尝试而导致过载、资源竞争或者死锁。

退避算法的常见类型包括：

1. 固定时间退避：每次重试之前，等待固定的一段时间。
2. 指数退避（Exponential Backoff）：每次重试之前，等待时间以指数倍增加。比如，第一次等待 1 秒，第二次等待 2 秒，第三次等待 4 秒，依此类推。
3. 带随机抖动的指数退避：在指数退避的基础上，加入一些随机性，使得重试的时间并不是固定的，而是随机的，这样可以避免多个请求同时重试导致系统再次过载。

常见应用场景

网络通信：

• TCP 协议：退避算法用于处理网络拥塞问题，避免过多的数据包重传导致网络拥塞进一步加剧。TCP 协议中的慢启动（Slow Start）机制和拥塞避免（Congestion Avoidance）都使用了指数退避的思想。
• Linux 内核中的 TCP 协议：TCP 协议本身实现了指数退避机制来处理网络拥塞问题。例如，在包丢失或超时的情况下，发送端会通过指数退避减少传输速度，并逐步增加重试时间

分布式系统：

• 在分布式系统中，当多个节点同时访问相同的资源或服务时，退避算法可以帮助减少冲突。例如，当多个客户端同时向数据库发起请求时，可以使用退避算法来减少竞争，避免数据库过载。
• 比如 Etcd 使用退避算法处理客户端与服务器的通信重试，防止过载。Kubernetes 的控制器和调度器在管理 Pod 和服务的启动和调度过程中，遇到冲突或失败时，会使用退避算法逐渐延长重试时间，避免高频率重试对集群的压力。

并发控制：

• 在多线程或多进程系统中，多个线程可能会争抢同一个锁或资源。退避算法可以用来减少资源竞争。例如，在自旋锁的实现中，线程可能会使用退避算法等待一段时间后再尝试获取锁。
• 在实现分布式锁时，退避算法可以用于解决竞争条件。如果多个客户端同时争夺锁，使用退避机制可以减少锁竞争，避免过度重试带来的性能问题。

API 请求重试：

• 当 API 请求失败时（如因网络故障或服务不可用），退避算法可以控制重试的间隔时间，避免立即发起过多的重试请求导致服务器压力过大。

指数退避算法

维基百科：指数退避是一种使用反馈以乘法方式降低某个进程的速率以逐渐找到可接受速率的算法。这些算法在各种系统和进程中得到广泛应用，其中无线电网络和计算机网络尤为引人注目。

其中指数退避算法/带抖动的指数退避算法使用的更广泛，在工作的项目和开源项目中都随处可见。

速率降低可以建模为指数函数： 或者

这里，t是操作之间应用的时间延迟，b是乘数或底数，c是观察到的不良事件数，f是过程的频率（或速率，即每单位时间的操作数）。每次观察到不良事件时， c的值都会增加，导致延迟呈指数上升，因此速率成反比。b = 2 的指数退避算法称为二进制指数退避算法。

例如b = 2，c的初始值为0：

• 第一次重试：
• 第二次重试：
• 第三次重试：

带抖动的指数退避算法

在工程领域上，都会在指数退避的基础上加入一些随机性，让t成指数增长的同时处于一种抖动状态，这样可以避免多个请求同时重试导致系统再次过载。

类似加入随机性的场景比如 Redis 的数据预热，一般会在预热的时候会为数据加入的过期时间偏移量，防止缓存雪崩。

使用 go 实现的带抖动的指数退避算法：

package main

import (
	"errors"
	"fmt"
	"math"
	"math/rand"
	"time"
)

func main() {
	// 重试的基本参数
	initialBackoff := 100 * time.Millisecond // 初始等待时间
	maxBackoff := 5 * time.Second            // 最大等待时间
	backoffFactor := 2.0                     // 退避倍数
	maxRetries := 10                         // 重试的最大次数

	// 重试逻辑
	for retries := 0; retries < maxRetries; retries++ {
		err := doSomething()
		if err == nil {
			break // 如果成功，结束重试
		}

		// 计算退避时间（指数增长）
		backoffTime := initialBackoff * time.Duration(math.Pow(backoffFactor, float64(retries)))

		// 限制最大退避时间，避免无限长时间的等待
		if backoffTime > maxBackoff {
			backoffTime = maxBackoff
		}

		// 引入随机抖动，避免竞争
		jitter := time.Duration(rand.Int63n(int64(backoffTime)))
		fmt.Println(backoffTime, jitter)

		// 等待重试
		time.Sleep(jitter)
	}
}

func doSomething() error {
	return errors.New("请重试")
}