说说什么是计数器（固定窗口）算法

本是古典何须时尚 2024-02-05 14:27 72阅读 0赞

计数器（固定窗口）算法是一种常用的数据统计方法，主要用于在给定的数据窗口内统计窗口内元素出现的次数。这种方法在处理如点击流数据（user-behavior data，例如用户点击、查看、购买等行为数据）时特别有用。

算法的主要步骤通常包括：

1.  **初始化**：定义一个窗口大小（通常是一个固定的大小，如N），并在数据流中维护这个窗口。
2.  **遍历数据流**：对于每个新到达的数据点，检查它是否已经存在于当前窗口中。
    
     *  如果数据点已经在窗口中，计数器增加1。
     *  如果数据点不在窗口中，把它添加到窗口中，同时计数器也增加1。
3.  **输出统计结果**：在遍历完所有数据点后，可以输出窗口内每个元素出现的次数。

这种算法的一个关键特性是它只对在窗口内出现的新元素进行计数，而不会重复计算已经在窗口中的元素。这使得它特别适合处理大量数据，因为它只需要存储和操作当前窗口内的元素，而不需要跟踪所有的历史数据。

另外，这种算法还可以通过各种方式进行优化，例如使用哈希表来加快元素在窗口中的查找速度，或者使用更复杂的策略来处理窗口大小的变化（例如滑动窗口）。

值得注意的是，计数器（固定窗口）算法常常用于诸如用户行为分析、推荐系统、实时数据分析等场景中  
计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。  
此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性和线程安全即可轻松实现。  
![在这里插入图片描述][369025b008e948f2b4407ec185925466.png]  
这个算法通常用于QPS限流和统计总访问量，对于秒级以上的时间周期来说，会存在一个非常严重的问题，那就是临界问题，如下图：  
![在这里插入图片描述][c7354a6ead4b4d349da4f898bfb53074.png]  
假设1min内服务器的负载能力为100，因此一个周期的访问量限制在100，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入100的访问量，虽然没有超过每个周期的限制 量，但是整体上10秒内已达到200的访问量，已远远超过服务器的负载能力，由此可见，计数器算法方式限流对于周期比较长的限流，存在很大的弊端。

[369025b008e948f2b4407ec185925466.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/2231a2c52d90418c91cbb169d82a7f6c.png
[c7354a6ead4b4d349da4f898bfb53074.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/25e8cd3cd37f45878ab85eec20064c2a.png