使用指数退避有什么好处？

Question

当代码等待延迟时间不确定的某种情况时,看起来很多人选择使用指数退避,即等待N秒,检查条件是否满足; 如果没有,等待2N秒,检查条件等.这对于检查恒定/线性增加的时间跨度有什么好处？

Answer 1

假设您指的是在执行操作之前测试条件：

• 当测试条件的成本与执行操作的成本相当时（例如在网络拥塞时），指数退避是有益的。
• 如果测试条件的成本要小得多（或可以忽略不计），那么线性或恒定等待可以更好地工作，前提是条件改变所需的时间也可以忽略不计。

例如，如果您的条件是针对数据库的复杂（缓慢）查询，并且操作是同一数据库的更新，则每次检查条件都会对数据库性能产生负面影响，并且在某些时候，没有指数退避，由多个参与者检查条件可能足以使用所有数据库资源。

但是，如果条件只是轻量级内存检查（例如关键部分），并且操作仍然是数据库的更新（最多比检查慢万分之一），并且如果条件翻转可以忽略不计动作一开始的时间（通过进入临界区），那么恒定或线性退避就可以了。实际上，在这种特定场景下，指数退避是有害的，因为它会在低负载情况下引入延迟，并且更有可能在高负载情况下导致超时（即使处理带宽足够）。

总而言之，指数退避是一把锤子：它对于钉子很有效，但对于螺钉则不太有效:)

Answer 2

这是TCP拥塞控制的行为。如果网络非常拥塞，则实际上没有流量通过。如果每个节点在检查之前都等待固定的时间，则仅用于检查的流量将继续阻塞网络，并且拥塞永远无法解决。类似地，对于检查之间的线性增加时间，拥塞解决可能需要很长时间。

Answer 3

在同时尝试做某事会相互干扰而无法成功的情况下，指数回退很有用。在这种情况下，让设备在太小的窗口中随机尝试操作将导致大多数尝试失败并必须重试。只有当窗口足够大时，尝试才会有很大的成功可能性。

如果事先知道要通信的设备有16个，则可以选择最适合该负载级别的窗口大小。但是实际上，竞争设备的数量通常是未知的。在每次重试时窗口大小加倍的指数补偿的优点在于，与竞争实体的数量无关：

1. 大多数操作成功的窗口大小通常是大多数操作成功的最小窗口大小的两倍，

2. 在该窗口大小下失败的大多数操作将在下一次尝试时成功（因为大多数先前的操作将成功，因此将剩下不到一半的竞争竞争两倍大的窗口），并且

3. 所有尝试所需的总时间最终只会是最后一次所需时间的两倍。

如果窗口不是每次都增加一倍，而是简单地增加一个恒定量，那么重试操作直到窗口达到可用大小所花费的时间将与所需窗口大小的平方成正比。尽管最终的窗口大小可能会比使用指数补偿的窗口小，但所有尝试的总成本将大得多。