限流的五种使用Redis的实现

限流是常考的一道面试题。也是工业界常用的必备功能。用于保护服务以免受到滥用和攻击。一亩三分地也有这个功能：「抱歉，您所在的用户组每小时限制发回帖x个，请稍候再发表」。能够实现Rate Limit的方法很多很多，比如用Nginx。但是如果要实现分布式，高并发，低延迟，似乎离不开Redis。

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

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

非常详细的好文。 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准确度稍高一些。不知道还有没有其他改进的地方。

感谢楼主分享。
有几个问题。
第一个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
   

复制代码

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

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

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

本文被选为03/24/2019全站置顶文章之一。
作者获得大米奖励。谢谢你的分享

也欢迎其他同学分享你对系统设计题目和各种技术的研究心得，都会有积分奖励！

redis真的很火，之前intern还在做redis的项目
感谢楼主，还差20个大米就能看啦～

50 * (30 seconds / 60 seconds) + 30 = 55.  
55 < 60 所以批准。
同时2:04:00-2:05:00的数字加一。
这段能解释下吗

差6分看不到，求加点米

第一种token bucket方法是不是也会有fix window一样的不准确的问题？比如2:03访问，给了15个token（假设limit是15/60s），全集中在2:03:30到2:04之间访问。然后2:04又给了15个token，集中在2:04-2:04:30间访问。那2:03:30-2:04:30间就有30次访问了？

Miaaaaa 发表于 2019-3-25 19:10
第一种token bucket方法是不是也会有fix window一样的不准确的问题？比如2:03访问，给了15个token（假设lim ...

会有。只要时段不是移动窗口都有这样的问题。从精确度来说4 > 5 ～> 1,2,3  注2是Redis的实现，对于原算法来说是扭曲过的。

xiao66xiang 发表于 2019-3-25 11:07
50 * (30 seconds / 60 seconds) + 30 = 55.  
55 < 60 所以批准。
同时2:04:00-2:05:00的数字加一。

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

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

好想看。。差了一百分看不到

呃 就差12分看不到………