令牌桶算法限流
其他限流方式
之前去面试的时候,面试官出了一题,要求对每个用户的请求进行限流,假设限制用户每分钟请求100次,我的方案是这样的:
-
用户访问的时候我们
ttl limit如果该字段存活则认为60秒内访问过,直接读取limit的数值;如果ttl未存活则认为是首次访问. -
通过ttl的返回数据,判断用户是否处应该被限制访问.
- 如果ttl的结果小于0, 我们
setEx limit 60 100,继续执向下执行. - 如果ttl的结果大于0,我们
incr limit,同时判断incr的返回值如果大于100,则停止执行且提示请等待ttl秒.
- 如果ttl的结果小于0, 我们
-
如果对限流有更精细话的要求可以对每10秒也做一下限制,然后使用setNx配合更加精细的逻辑判断,避免并发.
不过我的方案被否认了,面试官推荐了令牌桶算法.当时没想到,回去一想,令牌桶算法并不适用于对单个用户的限流.
令牌桶算法更加适合对整个服务器的限流.
令牌桶算法
简而言之就是,每隔一段时间向桶内(这个桶可以是一个队列,也可以是一个数字,如果是一个数字就需要自己控制并发),放置一定数量的令牌.
每个访问的用户从桶内拿出一个令牌,如果令牌消耗完毕则禁止访问.直到新的令牌被放入桶内后用户才可以再次获取令牌进行访问.
实现方式有很多种,有使用Redis队列或string(注意处理并发),如果是常驻内存的进程的也可以使用数组队列.
如果使用一个数字,要要注意并发问题可以使用Redis的getSet,setNx,expire或者配合一个其他字段做更新时间即可.
