随笔分类
服务限流的常见算法:
服务限流,主要目的便是通过限制并发访问数或者单位时间内的请求数量以来保护系统
本质上讲,限流的主要作用便是 损失一部分用户的可用性,为大部分用户提供稳定可靠的服务
实际上,限流无处不在,直观体现便是线程池中核心线程数的 "预热",这本质上也是一种限流
常见的限流算法:
计数器算法
这是一种比较简单的限流实现算法,在指定周期内累计服务访问次数,当访问次数达到指定阈值时,触发限流的策略,当进入下一个访问周期时访问次数清零
这种算法可以用在短信发送的频次限制上,如限制某 ip地址或某用户指定时间周期内触发短信发送的次数
但这种算法本身并不能很好的去处理突刺性流量增长问题,比如说限定了一分钟内能够处理请求的数目为 100,若在该时间周期内的第二秒时流量突刺性增长(超过了 100),第二秒后系统并没有过多请求,这就会显得系统在第二秒后直至一分钟时服务都将不可用
其实,计算器算法还存在一个边界问题,若是在第一分钟的 0:58和第二分钟的 1:02这个时间段内,分别出现了 100个请求,那么从整体上来看 4s内的请求量就达到了 200,超过了所设置的阈值,然限流并未被触发!
究根到底,还是本身计数器算法过于简单的问题,本没有做到灵活弹性的去对突刺性流量进行处理
滑动窗口算法
滑动窗口算法的引入,解决了计数器算法在达到触发限流规则后,服务不可用的问题
滑动窗口算法是一种流量控制技术,在 TCP网络协议中,就采用了流量控制的技术去解决网络拥塞的问题
简单来说,滑动窗口的原理就是对固定窗口(实际就是规定的时间周期)进行分割,分割出多个小时间窗口,分别在每个小时间窗口中记录访问次数,然后根据时间将窗口往前移动并删除过期的小时间窗口;即最终只需要累计滑动窗口范围内的所有小时间窗口总的计数即可
这不就解决了计数器算法中的边界问题了吗!
实际上,Sentinel中流控效果对应的快速失败便是基于滑动窗口算法实现的
令牌桶限流算法
令牌桶是网络流量整形和速率控制中最常用的一种算法;对于每个请求,都首先需要从令牌桶中获取一枚令牌,如果没有获得令牌,将会触发限流策略
如图所示,系统会以一个恒定的速度生成令牌并将其放置于固定容量大小的令牌桶中,若此时客户端请求过来,则需要从令牌桶中拿到令牌以来获取访问资格
由于令牌桶有固定大小,因此当请求速度小于令牌生成速度时,桶会很快被填满;so,填满的令牌桶就起到了预热的效果,能够去处理突发流量,也就是短时间内的新增流量系统能够去进行处理,这就是令牌桶的特性
so,这一块有点类似于线程池加上 Semaphore的实际对吧!
漏桶限流算法
漏桶限流算法主要作用是控制数据注入网络的速度,平衡网络上的突发容量
思想:内部维护着一个容器,这个容器会以恒定速度出水,不管上面的水流速度多快,容器水滴的流出速度始终保持不变;实际上,消息中间件便是利用此思想,不管生产者的请求量有多大,消息的处理能力取决于消费者,即对应 削峰填谷之功效
实际上,我认为在 Socket缓冲区以及 Flow背压,其实也该思想的设计在其中
漏桶限流算法和令牌桶限流算法实现的原理相差不多,最大的区别在于漏桶限流算法并不能去处理短时间内突发容量,漏桶限流算法是一种恒定速度的限流算法!