精度不够，滑动时间来凑「限流算法第二把法器：滑动时间窗口算法」

作者：Cpp五条 | 2024-03-20 15:44:27

踩

滑动时间窗口算法

一、回顾：计算器算法存在问题

对于秒级以上的时间周期来说，会存在一个非常严重的问题，那就是临界问题。

从上图中我们可以看到

假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。

我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求，可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

那么今天就说说如何解决这个问题。

计算器的问题其实是因为我们统计的精度太低（统计的1秒内的流量情况，只有1个值进行记录）。那么如何很好地处理这个问题呢？或者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。

二、滑动窗口算法

滑动窗口，又称rolling window。为了解决计数器法统计精度太低的问题，引入了滑动窗口算法。下面这张图，很好地解释了滑动窗口算法:

是一分钟。然后我们将时间窗口进行划分，比如图中，我们就将

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/274745