四种分布式限流算法实现！( 二 ) _限流

固定窗口限流算法算法原理固定窗口算法，很多参考资料也称之为计数器算法，当然我个人理解，计数器算法是固定窗口算法的一种特例，当然我们不纠结那么多。
固定窗口算法，是一种比较简单的限流算法，它把时间划分为固定的时间窗口，每个窗口内允许的请求次数设置限制。如果在一个时间窗口内，请求次数超过了上限，那么就会触发限流。
在这里插入图片描述
算法实现基于Redisson的实现固定窗口相当简单。在每个窗口期内，我们可以通过incrementAndGet操作来统计请求的数量。一旦窗口期结束，我们可以利用Redis的键过期功能来自动重置计数。

来看下代码实现：

public class FixedWindowRateLimiter {public static final String KEY = "fixedWindowRateLimiter:";/*** 请求限制数量*/private Long limit;/*** 窗口大小（单位：S）*/private Long windowsize;public FixedWindowRateLimiter(Long limit, Long windowSize) {this.limit = limit;this.windowSize = windowSize;}/*** 固定窗口限流*/public boolean triggerLimit(String path) {RedissonClient redissonClient = RedissonConfig.getInstance();//加分布式锁 ， 防止并发情况下窗口初始化时间不一致问题RLock rLock = redissonClient.getLock(KEY + "LOCK:" + path);try {rLock.lock(100, TimeUnit.MILLISECONDS);String redisKey = KEY + path;RAtomicLong counter = redissonClient.getAtomicLong(redisKey);//计数long count = counter.incrementAndGet();//如果为1的话 ， 就说明窗口刚初始化if (count == 1) {//直接设置过期时间 ， 作为窗口counter.expire(windowSize, TimeUnit.SECONDS);}//触发限流if (count > limit) {//触发限流的不记在请求数量中counter.decrementAndGet();return true;}return false;} finally {rLock.unlock();}}}

这里还额外用了一个分布式锁，来解决并发情况下，窗口的初始化问题。

再来测试一下

class FixedWindowRateLimiterTest {ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(20, 50, 10, TimeUnit.SECONDS, new LinkedBlockingDeque<>(10));@Test@DisplayName("1min限制10次请求固定窗口测试")void triggerLimit() throws InterruptedException {FixedWindowRateLimiter fixedWindowRateLimiter = new FixedWindowRateLimiter(10L,60L);//模拟不同窗口内的调用for (int i = 0; i < 3; i++) {CountDownLatch countDownLatch = new CountDownLatch(20);//20个线程并发调用for (int j = 0; j < 20; j++) {threadPoolExecutor.execute(() -> {boolean isLimit = fixedWindowRateLimiter.triggerLimit("/test");System.out.println(isLimit);countDownLatch.countDown();});}countDownLatch.await();//休眠1minTimeUnit.MINUTES.sleep(1);}}}

当然大家也可以写个接口，用Jmeter之类的压测工具来进行测试。
固定窗口算法的优点是实现简单，占用空间小，但是它存在临界问题，由于窗口的切换是瞬间完成的，因此请求的处理并不平滑，可能会在窗口切换的瞬间出现流量的剧烈波动。
比如这个例子，假如在00:02 ，突然有大量请求过来，但是我们这时候计数重置了，那么就没法限制突发的这些流量。
临界值问题
滑动窗口算法为了缓解固定窗口的突发流量问题，可以采用滑动窗口算法，计算机网络中TCP的流量控制就是采用滑动窗口算法。
算法原理滑动窗口限流算法的原理是将一个大的时间窗口划分为多个小的时间窗口，每个小的窗口都有独立的计数。
请求过来的时候，判断请求的次数是否超过整个窗口的限制。窗口的移动是每次向前滑动一个小的单元窗口。
例如下面这个滑动窗口，将大时间窗口1min分成了5个小窗口，每个小窗口的时间是12s 。
每个单元格有自己独立的计数器，每过12s就会向前移动一格。
假如有请求在00:01的时候过来，这时候窗口的计数就是3+12+9+15=39 ，也能起到限流的作用。
滑动窗口算法示意图
这就是为什么滑动窗口能解决临界问题，滑的格子越多，那么整体的滑动就会越平滑,限流的效果就会越精准。
算法实现那么我们这里怎么实现滑动窗口限流算法呢？非常简单，我们可以直接使用Redis的有序集合（zset）结构。