限流算法学习
在处理系统高并发问题上,我们常用的策略有三种:缓存、降级、限流。
今天就主要谈谈限流问题。何为限流?限流就是限制流量,你也可以理解为限制用户访问数量。常用的限流算法有四种,下面来一一简单介绍
1、计数器算法
计数器用来记录单位时间内进入系统或者某一接口的请求次数,在限定的次数内的请求则正常接收,超过次数的请求则拒绝掉,或者改为异步处理。
算法原理:
举个例子,对于A接口来说,我们一分钟的访问次数不能超过100次,那么我们可以设置一个计数器counter,每当请求过来的时候,counter加1,如果counter的值大于100,且它与第一个请求的时间间隔小于一分钟,则说明请求过多了;如果该请求与第一个请求的时间间隔大于一分钟,并且counter在100以内。那么重置counter
缺陷:临界问题
假设我们系统中现在只有一个用户,这个用户在59秒的时候发送了100次请求,然后在一分零一秒的时候又发送了100次请求,这个时候实际上在系统当中,一分钟之内就接收了200次请求,可能会导致我们的服务蹦掉。限流算法在这个临界点没有发挥作用
2、滑动窗口
之所以计数器算法会造成临界值的问题,是因为我们在统计Counter的时候精度太低了。而滑动窗口算法则是在此基础之上,进行了优化
在使用滑动时间窗口,我们可以把1分钟分成6格,每格时间长度是10s,每一格又各自管理一个计数器,单位时间用一个长度为60s的窗口描述。一个请求进入系统,对应的时间格子的计数器便会+1,而每过10s,这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限,便会拒绝后面的请求。
3、漏桶算法
一个系统处理请求,就像一个固定容量的水桶去溜进来的水,同时也让水流出去,但是它无法预见有多少水流进来和水流进来的速度,它只能够控制从桶底水流出去的速度,多出来的水,就只好让它从桶边流出去了。这个从桶底流出去的水就是系统正常处理的请求,从旁边流出去的水就是系统拒绝掉的请求。如此一来,我们只要监控系统单位时间内处理请求的速率就可以了,速率超过上限后的请求都给拒绝掉就可以了
4、令牌桶算法
对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。桶里能够存放令牌的最高数量,就是允许的突发传输量。比较好的控制了瞬时流量