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

计数器算法是一种简单的限流算法，用于在特定时间窗口内累加访问次数，并根据预设的限流值决定是否触发限流策略。它的基本原理是在一个固定的时间窗口内使用一个计数器来记录请求的次数，当计数器达到设定的限流值时，后续的请求将被限制。下一个时间窗口开始时，计数器被重置为零，重新开始计数。 #### 实现原理 在单机或分布式环境中，计数器算法的实现都非常简单。使用 Redis 的 `INCR` 原子自增操作和其线程安全特性即可轻松实现计数器算法。 #### 实现示例 假设限制每分钟的请求次数为 100： 1. 每次请求时，使用 Redis 的 `INCR` 命令对计数器进行自增操作。 2. 判断计数器的值是否超过限制值。 3. 如果超过限制值，则触发限流策略。 4. 使用 Redis 的 `EXPIRE` 命令设置计数器的过期时间为 60 秒，以便在每分钟开始时重置计数器。 ```java public class RateLimiter { private static final int LIMIT = 100; private static final int WINDOW_SIZE = 60; // in seconds private Jedis jedis; public RateLimiter(Jedis jedis) { this.jedis = jedis; } public boolean isAllowed(String key) { long count = jedis.incr(key); if (count == 1) { jedis.expire(key, WINDOW_SIZE); } return count <= LIMIT; } } ``` #### 临界问题 计数器算法在秒级以上的时间周期内会出现临界问题，即在一个时间窗口的末尾和下一个时间窗口的开始时，可能会有大量请求涌入，导致短时间内的请求数远远超过设定的限流值。 **示例：** 假设每分钟限制的请求次数为 100： - 在第一个时间窗口的最后5秒内，有100个请求。 - 在下一个时间窗口的前5秒内，又有100个请求。 虽然每个时间窗口内的请求数都没有超过限制，但在这10秒内，总请求数达到了200，超过了服务器的负载能力。 #### 解决方案 为了缓解临界问题，可以考虑使用滑动窗口算法或令牌桶算法等其他限流策略，这些算法在一定程度上能够平滑请求数，避免在时间窗口切换时出现瞬时请求量过大的情况。 **滑动窗口算法：** 滑动窗口算法通过将时间窗口细分为更小的子窗口来统计请求数，从而平滑限流效果。每次请求时统计多个子窗口内的请求总数，以决定是否触发限流。 **令牌桶算法：** 令牌桶算法通过在固定速率下生成令牌，并在请求到达时消耗令牌，保证请求的速率在一定范围内，适合处理突发流量。 ### 总结 计数器算法是一种简单且易于实现的限流算法，适用于秒级以下的短时间窗口限流场景。但对于较长时间窗口（如分钟级别）的限流场景，计数器算法会存在临界问题，可能导致瞬时请求量超过系统的负载能力。为解决此问题，可以考虑使用滑动窗口算法或令牌桶算法等更复杂的限流策略。