常见限流算法
1.为什么要限流
一般而言,正常的流量越多越好,比如用户快速增长、热点事件带来蜂拥的人流。但在实际网络流量中,除正常的流量外,还有很多非正常的流量,比如网络攻击、恶意爬虫。
网络攻击不会给业务带来好处,而是会过度地消耗服务资源,所以在高并发的应用中,需要通过限流来保障服务对所有用户的可用性。
限流和缓存、降级一样,也是保护高并发系统的利器。
2.常见的限流措施
- 限制总并发数。如,数据库连接池、线程池。
- 限制瞬时并发数。如,Nginx的limit_conn模块可以限制瞬时并发连接数。
- 限制时间窗口内的平均速率。如,Nginx的limit_req模块。
- 限制消息中间件的消费速率。
- 限制远程接口的调用速率。
- 限制每秒的平均速率。
- 对线程池进行隔离。如果超过线程池的负载,则进行熔断。
- 通过tomcat容器限制线程数来控制并发。
除上述措施外,还可以根据网络连接数、网络流量、时间窗口的平均速度、用户访问频次、IP地址、URI、CPU和内存负载等来限流。
一般限流都在网关层实现,比如使用Nginx、zuul、Spring cloud Gateway、Openresty、Kong等。当然也有人在应用层通过AOP这种方式限流。
3.限流算法
常见的限流算法有:计数器、漏桶、令牌桶。限流算法不是spring cloud gateway独有的,而是一种通用的算法。
3.1. 计数器算法
采用计数器限流,是特别简单和粗暴的。
算法的实现方法是:从第一个请求进来开始计时,在接下来的时间内( 如1S),每来一个请求,就把计数加1;如果累加的数字达到了设定的值( 如QPS为100),则后续的请求就会被全部拒绝;等单位时间结束后把计数恢复成0,重新开始计数。
计数器限流方法存在“突刺现象”:如果在1S(单位时间)内的前100ms已经通过了100个请求,则后面的900ms内的请求全部会被拒绝。
既然存在“突刺现象”,那把单位时间设置得更短些能否解决问题呢?比如设置为10ms。这种想法是可以的,但依旧不能解决“突刺现象”,反而会增加计数器的负担。
为了解决“突刺现象”,可以采取更平滑的限流算法:漏桶算法和令牌桶算法。
3.2 漏桶算法
漏桶(Leaky Bucket)算法的原理是:把请求先放入漏桶里等待,然后漏桶以一定的速度处理进入漏桶中的请求;如果请求的进入速度过大,则导致漏桶装不下请求而拒绝后续请求。
在漏桶算法里有两个变量(桶的大小、漏洞的大小)决定着限流情况。
一般情况下,用于服务的软硬件资源是特定的(即漏桶的漏出速率是固定的),所以即使是在理想状态下(没有拥塞),漏桶算法对于突发流量来说是缺乏效率的。
3.3 令牌桶算法
令牌桶算法(Token Bucket)和现在各大机构使用的叫号机很类似:当请求到达时,先去令牌桶(叫号机)中取得一个令牌(排号),然后等待响应。
这样做的好处是:可以非常方便地改变速率,按需改变放入桶中的令牌速率;可以定时或者根据实时计算增加令牌数量。
采用令牌桶算法的框架主要有RateLimiter、Bucket4j、RateLimitJ。