使用指数退避的好处是什么？

Question

当代码在等待某些延迟时间不确定的条件时，许多人选择使用指数退避，即等待N秒，检查条件是否满足；如果不满足，则等待2N秒，再次检查条件等。相对于在恒定/线性递增的时间段内进行检查，这种方法的好处是什么？

- xis

Answer 1

指数退避在同时尝试做某事会相互干扰以至于没有成功的情况下非常有用。在这种情况下，让设备在一个太小的时间窗口内随机尝试操作将导致大多数尝试失败并需要重试。只有当时间窗口变得足够大时，才有任何显著成功的可能性。

如果人们预先知道有16个设备想要通信，就可以选择最适合该负载水平的时间窗口大小。但实际上，竞争设备的数量通常是未知的。指数退避的优点是，在每次重试中时间窗口的大小加倍，无论竞争实体的数量如何：

1. 绝大多数操作成功的窗口大小通常在大多数操作成功的最小窗口大小的两倍范围内，

2. 在那个时间窗口大小失败的大多数操作将在下一次尝试中成功（因为较早的大多数操作将已经成功，这将使不到一半的操作竞争一个两倍大的时间窗口），并且

3. 所有尝试所需的总时间最终只会比上次尝试所需的时间多约两倍。

如果不是每次加倍，而是通过增加固定数量来扩大时间窗口，则重试操作直到时间窗口达到可用大小所花费的时间将与所需窗口大小的平方成比例。虽然最终的时间窗口大小可能会比使用指数退避小，但所有尝试的总成本会大得多。

- supercat

Answer 2

这是TCP拥塞控制的行为。如果网络极度拥塞，将没有流量通过。如果每个节点在检查之前等待固定时间，则仅用于检查的流量将继续堵塞网络，并且拥塞永远不会解决。同样地，对于线性增加的检查时间，可能需要很长时间才能解决拥塞问题。

- mattm

Answer 3

假设您是在执行操作之前测试条件，那么指数退避在成本测试等于执行操作的情况下非常有益(例如在网络拥塞时)。而如果测试条件的成本要小得多(甚至可以忽略不计)，则线性或恒定等待可能更有效，只要条件变化的时间也可以忽略不计。

例如，如果您的条件是针对数据库的复杂(慢速)查询，而操作是相同数据库的更新，则每次检查条件都会对数据库性能产生负面影响。没有指数退避，在某些情况下，多个参与者检查条件就足以使用所有数据库资源。

但是，如果条件只是轻量级存储器检查(例如关键节)，而操作仍然是数据库的更新(最好比检查快几万倍)，且在操作的开头一段微不足道的时间内翻转条件(通过进入关键部分)，那么恒定或线性退避是可以的。实际上，在这种特殊情况下，指数退避会产生负面影响，因为它会在低负载情况下引入延迟，并且在高负载情况下更容易导致超时(即使处理带宽足够)。

因此，总结一下，指数退避是一把锤子：对于钉子它非常有效，但对于螺丝就不太好用了 :)

- Eric Grange