限流算法学习

在处理系统高并发问题上，我们常用的策略有三种：缓存、降级、限流。
今天就主要谈谈限流问题。何为限流？限流就是限制流量，你也可以理解为限制用户访问数量。常用的限流算法有四种，下面来一一简单介绍

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、令牌桶算法

对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。桶里能够存放令牌的最高数量，就是允许的突发传输量。比较好的控制了瞬时流量