指数退避和抖动

引入 OCC

添加退避机制

添加抖动机制

小结

引入 OCC
乐观并发控制（Optimistic Concurrency Control，OCC）是一种既能保证多个写入者安全地修改单个对象又能避免丢失写入的古老方法
OCC具有三个优点：只要底层存储可用，它总能取得进展；易于理解，易于实现
DynamoDB 的条件写入使OCC成为DynamoDB 用户的自然选择，并且DynamoDBMapper 客户端原生支持OCC
尽管OCC可以保证有进展，但在高争用情况下它的表现仍然很差
所谓高争用(是指在多个线程或进程同时访问或修改共享资源时的情况，这可能导致竞争条件和性能问题；它与"高并发"有一定的关联，但并不完全相同("高并发"强调的是系统同时处理多个并发请求的能力，通常表示系统在单位时间内可以处理的并发请求数量非常大；而"高争用"则强调的是在共享资源上的竞争程度，即多个并发操作对同一个资源的竞争情况)(因此，"高争用"更专注于资源竞争的概念，而"高并发"更关注系统整体的并发处理能力；当存在高争用情况时，可能会出现性能瓶颈和竞争条件，需要采取合适的并发控制和优化策略来解决这些问题))
这些争用情况中最简单的是当大量客户端同时启动并尝试更新同一数据库行时
由于每轮保证有一个客户端成功，因此完成所有更新所需的时间与争用程度呈线性增长
在本文的图表中，使用了一个小型模拟器来模拟 OCC 在带有延迟（以及延迟方差）的网络中对远程数据库的行为
在这个模拟中，网络引入了平均 10ms 的延迟和 4ms 的方差
第一个模拟展示了随着争用程度增加，完成时间如何呈线性增长
这种线性增长是因为每轮只有一个客户端成功，所以需要N轮才能让所有N个客户端都成功
不幸的是，这还不是全部
当有N个客户端竞争时，系统所完成的总工作量将以N的平方增加
添加退避机制
这里的问题是有 N 个客户端在第一轮中竞争，N-1 个客户端在第二轮中竞争，依次类推
让每个客户端在每一轮中都竞争是浪费的
减缓客户端的速度可能有所帮助，而经典的减缓客户端的速度的方法是采用有上限的指数退避(限制指数退避)
有上限的指数退避意味着客户端在每次尝试后都会将退避时间乘以一个常数，直到达到某个最大值
在我们的例子中，每次尝试失败后，客户端会睡眠一段时间：
重新运行模拟显示，退避机制在一定程度上有所帮助，但并不能解决问题；客户端的工作量仅有轻微减少
查看问题的最佳方法是查看指数退避调用发生的时间
很明显，指数退避起到了作用，因为调用发生的频率越来越低
然而，问题也显而易见：仍然存在调用的集群
我们并没有减少每轮竞争的客户端数量，只是引入了一些没有任何客户端竞争的时间段
尽管网络延迟的自然变化导致了一些分散，但竞争并没有得到很大程度的减少
添加抖动机制
解决方案并不是移除退避机制，而是添加抖动机制
最初，抖动似乎是一个违反直觉的想法：试图通过添加随机性来提高系统的性能
然而，上述时间序列提供了使用抖动的充分理由——我们希望将峰值分散到相对恒定的速率
添加抖动只需要对睡眠函数进行微小修改即可
那个时间序列看起来好很多
间隔不再存在，除了最初的峰值外，呼叫的速率大致保持恒定
这对于总呼叫次数也产生了很好的效果
在有100个竞争客户端的情况下，我们将呼叫次数减少了一半以上
与不使用抖动的指数退避相比，我们还大幅改善了完成时间
有几种方法可以实现这些定时退避循环
我们将上述算法称为“完全抖动”，并考虑两种替代方案
第一种替代方案是“相等抖动”，它总是将一些退避和抖动保持较小的量：
这种方法的原理是，它防止了非常短的延迟，始终保留一部分退避的减速效果
第二种替代方案是“去关联抖动”，与“完全抖动”类似，但是我们还会根据上一个随机值来增加最大抖动范围
小结
在计算机网络中，指数退避和抖动是一种常见的错误恢复和重试策略
当发生网络传输错误或拥塞时，指数退避和抖动策略可以帮助减少冲突和重试的负载，提高系统的稳定性和效率
指数退避是指在发生错误后(竞争失败后)，等待一段时间然后重试的操作，并且在每次重试时增加等待时间的策略
具体来说，等待时间是根据指数函数逐渐增加的，通常是当前重试次数的指数幂
这样做可以在网络拥塞的情况下，给予网络更多时间来恢复，并避免短时间内的连续冲突
抖动是指在等待时间的基础上引入一个随机因素，使得重试的时间间隔稍微有所变化
这样做的目的是避免在网络中出现周期性的重试，避免网络拥塞或错误引起的冲突
通过结合指数退避和抖动策略，可以在网络中更有效地处理错误和重试操作，提高系统的可靠性和性能
哪种方法最好？
从客户端工作量的角度来看，无论是“完全抖动”还是“相等抖动”，调用次数都大致相同，而“去关联抖动”的调用次数更高
相对于无抖动方法，这两种方法都大大减少了工作量
没有抖动的指数退避方法显然是失败者
它不仅需要更多的工作量，而且比带有抖动的方法需要更长的时间
实际上，它需要更多的时间，我们不得不将其从图表中删除，以便更好地比较其他方法
在带有抖动的方法中，“相等抖动”是失败者
它的工作量略高于“完全抖动”，而且耗时更长
而在“去关联抖动”和“完全抖动”之间的选择则不那么明确
“完全抖动”方法的工作量更少，但需要稍微更长的时间
但两种方法都大大减少了客户端工作量和服务器负载
值得注意的是，这些方法都没有从根本上改变要完成的工作的N2特性，但在适度的竞争水平下，它们显著减少了工作量
使用抖动的指数退避的实施复杂度回报是巨大的，因此应该被视为远程客户端的标准方法