限流的五种使用Redis的实现

差6分看不到，求加点米

差80分看不到

可惜没有米看不到

非常详细的好文。 sliding window log 那个算法，可以做一些优化，但是会牺牲掉一点accuracy。不需要记录每一次请求的时间，可以把整个time frame 分割成sub time frame比如我们的rate limiter 是20 requests/ min. 我们可以把一分钟分割成60 个 秒， 在每一秒以内记录request counts, 比如第一个request 是14:33:14.23来的 我们就记成 14:33:14  : 1, 第二个request 是14:33:14.26 来的 我们就update counter to 2  14:33:14  : 2. 最终 我们得到类似于， 1st second:5, 2nd second:3, 3rd second: 6 ......... 这一分钟内的总的request 就是所有counter的和 O(60)可以的到， 新的request 来，如果总和小于limitation， 接受并update counter， 如果等于，比较当前 timestamp 和 1st second 的时间, 如果差别大于等于60s, 则remove 队列头（1st second), 这里可以采用lazy remove 的办法每次只remove 一个，只要我可以被接受就不管后面的了，后面新来的request 自己处理自己的， 所以是O(1).  如果不能remove 则拒绝。 这种算法的空间复杂度 大概是O（60）， 缺点就是每一秒内的request 我把他当成了一个整体，所以在判断拒绝接受的时候并不那么准确，但相对来说感觉还是要比 Sliding Window Prorate准确度稍高一些。不知道还有没有其他改进的地方。

还差30米 努力

恰巧看到GUAVAL限流器的实现代码，其中源码最前面的注释部分有个比较详尽的注释文档，这个限流器在基本QPS的功能上加入underutiliized的判别这一更加高级功能，设计思想值得学习：

您好！
本帖隐藏的内容需要积分高于 99 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 99 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢楼主，还差50个大米能看

好想看，，，可是积分不够看不了...求大家帮下忙~哭唧唧

感谢楼主分享。
有几个问题。
第一个token bucket,  如果在第一个set 和decr 之间expire 是否最后还要decr 一下，或者少set一个，否则这个request就被忽略了？当然这样可能还是可以近似到ratelimiter的效果。
还有也是第一个token bucket，感觉这么做还是会有很多race conditions。比如如果在pttl 和后一个 set 之间被别的client SET USERA 15 EX 60  XX 了然后又一个client decr 了一下，那此时再执行 SET USERA 15 EX 60  XX  是否就不对了。
所以第一种是不是应该用 redis 的lua scripting 既可以实现atomic 还能根据前一个command的返回决定后一个command怎么执行

1. Set key $token_cnt EX 10 NX # set key to 15 if the key doesn’t exist
   
2. decrResult = DECR key
   
3. If (decrResult >= 0) {
   
4.     Return OK
   
5. } else {
   
6.     pttlResult = PTTL key # check key expiration status
   
7.     If (pttlResult == -1) {
   
8.         # key exists but has no associated expire which means key expires between setnx and decr
   
9.        Set key ($token_cnt - 1) EX 10
   
10.        Return OK
    
11.     } else {
    
12.        Return fail;
    
13.     }
    
14. }
    

复制代码

第四个sliding window log； 楼主把score 和value 设成同一个值即当前时间，极端情况是不是会有多个相同的value 的情况，而由于用的是set， 这种情况不会被多记，就导致结果不准确了？
所以是不是应该搞个counter 产生unique value？ 然后用lua 可以省去先加再删的情况，直接看一下是否满了，没满再加？

伪代码：

1. ZREMRANGEBYSCORE key -inf  current_time - window
   
2. Len = ZCARD key
   
3. If (len > limit) return fail;
   
4. value=INCR key+”_counter”
   
5. ZADD key value timestamp
   
6. Return ok
   

复制代码

我还差98分积分，非常想看分享