四种限流算法

1.固定时间窗口的限流算法

也就是最简单的每固定时间内允许一定数量的请求通过。比如限流为100QPS，也就是限制每1s钟内最大只能有100个请求通过。

这种限流算法有个不好的地方就是不能平滑限流，也就是可能在第1s内前999ms内没有流量，在最后1ms内有100个流量通过，这样有可能把系统打垮掉。甚至如果在第2s的第一个1ms内有100个请求，那就是在2ms内收200个请求了，非常不安全，这是固定时间窗口限流算法的缺点，一般不用，只作为理论算法。

2.滑动时间窗口的限流算法

针对固定时间窗口限流算法的缺点，有人想出了滑动时间窗口限流算法，也就是在任意1s内只让固定梳理的请求通过，比如1s内只让100个请求通过。

维持一个大小为100的数组，每次来一个请求，都去看一下数组内最近1s时间内请求数量有没有超过100，如果超过则拒绝当前请求，否则通过当前请求，且把当前请求的时间记录到数组中。

滑动时间窗口可以解决固定时间窗口的2ms内200个请求的情况，但是解决不了1sm内100个请求的情况。

3.漏桶算法

漏桶算法，以固定速度像桶内流入水流，即产生可允许请求通过的凭证，当桶满了则不再产生。以固定速度流出水流，即放行请求。

漏桶算法永远不会超过限制，比如限制100QPS，即1s钟允许100个请求通过，它可以限制任意两个请求的时间间隔最小为10ms，即任意10ms内不会有2个请求通过。

漏桶算法的缺点是永远以固定速度放行请求，不会有瞬时大流量通过，这个也是不太符合预期的。因为如果桶内有大量充足的水（即有一段时间可能没有请求过来），说明这个时候网络非常好、下游处理速度非常快，或者说上有没有什么请求，也可以说明当前网络里面没什么请求，这个时候如果突然有大量请求过来，应该可以允许通过，这样可以加快处理速度、提升效率。当桶内水量用完后再限制流出速度，就比较完美了。

4.令牌桶算法

以固定速度向桶内产生令牌，当请求过来时从桶内获取令牌，只要取到令牌才允许请求通过。当一段时间内没有请求，则桶内令牌越来越多，直到桶满，多余的令牌丢弃。当突然有一波请求同时到达的时候，可以一次性获取桶内多个令牌甚至所以令牌，这样就实现了突击流量的放行，但是又有桶大小的限制，最多只能放行桶大小的流量。当桶为空，则后续流量只能拒绝或者等待桶内产生新的令牌。

令牌桶算法解决了漏桶算法不能处理激增流量的缺点。