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

我们使用时间戳作为score和member ，有请求过来的时候，就把当前时间戳添加到有序集合里。那么窗口之外的请求，我们可以根据窗口大小，计算出起始时间戳，删除窗口外的请求。这样，有序集合的大小，就是我们这个窗口的请求数了。
zset实现滑动窗口

代码实现

public class SlidingWindowRateLimiter {public static final String KEY = "slidingWindowRateLimiter:";/*** 请求次数限制*/private Long limit;/*** 窗口大小（单位：S）*/private Long windowSize;public SlidingWindowRateLimiter(Long limit, Long windowSize) {this.limit = limit;this.windowSize = windowSize;}public boolean triggerLimit(String path) {RedissonClient redissonClient = RedissonConfig.getInstance();//窗口计数RScoredSortedSet<Long> counter = redissonClient.getScoredSortedSet(KEY + path);//使用分布式锁 ， 避免并发设置初始值的时候 ， 导致窗口计数被覆盖RLock rLock = redissonClient.getLock(KEY + "LOCK:" + path);try {rLock.lock(200, TimeUnit.MILLISECONDS);// 当前时间戳long currentTimestamp = System.currentTimeMillis();// 窗口起始时间戳long windowStartTimestamp = currentTimestamp - windowSize * 1000;// 移除窗口外的时间戳 ， 左闭右开counter.removeRangeByScore(0, true, windowStartTimestamp, false);// 将当前时间戳作为score,也作为member ， // TODO:高并发情况下可能没法保证唯一 ， 可以加一个唯一标识counter.add(currentTimestamp, currentTimestamp);//使用zset的元素个数 ， 作为请求计数long count = counter.size();// 判断时间戳数量是否超过限流阈值if (count > limit) {System.out.println("[triggerLimit] path:" + path + " count:" + count + " over limit:" + limit);return true;}return false;} finally {rLock.unlock();}}}

这里还有一个小的可以完善的点， zset在member相同的情况下，是会覆盖的，也就是说高并发情况下，时间戳可能会重复，那么就有可能统计的请求偏少，这里可以用时间戳+随机数来缓解，也可以生成唯一序列来解决，比如UUID、雪花算法等等。

还是来测试一下

class SlidingWindowRateLimiterTest {ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(30, 50, 10, TimeUnit.SECONDS, new LinkedBlockingDeque<>(10));@Test@DisplayName("滑动窗口限流")void triggerLimit() throws InterruptedException {SlidingWindowRateLimiter slidingWindowRateLimiter = new SlidingWindowRateLimiter(10L, 1L);//模拟在不同时间片内的请求for (int i = 0; i < 8; i++) {CountDownLatch countDownLatch = new CountDownLatch(20);for (int j = 0; j < 20; j++) {threadPoolExecutor.execute(() -> {boolean isLimit = slidingWindowRateLimiter.triggerLimit("/test");System.out.println(isLimit);countDownLatch.countDown();});}countDownLatch.await();//休眠10sTimeUnit.SECONDS.sleep(10L);}}}

用Redis实现了滑动窗口限流，解决了固定窗口限流的边界问题，当然这里也带来了新的问题，因为我们存储了窗口期的所有请求，所以高并发的情况下，可能会比较占内存。
漏桶算法我们可以看到，计数器类的限流，体现的是一个“戛然而止” ，超过限制，立马决绝，但是有时候，我们可能只是希望请求平滑一些，追求的是“波澜不惊” ，这时候就可以考虑使用其它的限流算法。
算法原理漏桶算法（Leaky Bucket），名副其实，就是请求就像水一样以任意速度注入漏桶，而桶会按照固定的速率将水漏掉。
漏桶算法
当进水速率大于出水速率的时候，漏桶会变满，此时新进入的请求将会被丢弃。
漏桶算法的两大作用是网络流量整形（Traffic Shaping）和速度限制（Rate Limiting）。
算法实现我们接着看看具体应该怎么实现。
在滑动窗口限流算法里我们用到了RScoredSortedSet ，非常好用对不对，这里也可以用这个结构，直接使用ZREMRANGEBYSCORE命令来删除旧的请求。
进水就不用多说了，请求进来，判断桶有没有满，满了就拒绝，没满就往桶里丢请求。
那么出水怎么办呢？得保证稳定速率出水，可以用一个定时任务，来定时去删除旧的请求。