限流的几种算法
1、固定窗口算法
概念：
这是限流算法中最暴力的一种想法。既然我们希望某个API在一分钟内只能固定被访问Ñ次（可能是出于安全考虑，也可能是出于服务器资源的考虑），那么我们就可以直接统计这一分钟开始对API的访问次数，如果访问次数超过了限定值，则抛弃后续的访问。直到下一分钟开始，再开放对API的访问。
所有的暴力算法的共同点都是容易实现，而固定窗口限流的缺点也同样很明显。假设现在有一个恶意用户在上一分钟的最后一秒和下一分钟的第一秒疯狂的冲击API 。按照固定窗口的限流规则，这些请求都能够访问成功，但是在这一秒内，服务将承受超过规定值的访问冲击（这个规定值很可能是服务器能够承受的最大负载），从而导致服务无法稳定提供。而且因为用户在这一秒内耗光了上一分钟和下一分钟的访问定额，从而导致别的用户无法享受正常的服务，对于服务提供方来说是完全不能接收的。
例：基于redis原子计数的固定窗口算法
常用策略，redis计数器，比如QPS100，1秒钟内允许100次请求，超过了则限流。
写法很简单，redis创建一个key，失效时间1秒，在这个时间内，会先先判断这个key是否大于100，
大于则做失效处理，如果小于100，则作原子自增++1。
2、滑动窗口算法
概念：
固定窗口就像是滑动窗口的一个特例。滑动窗口将固定窗口再等分为多个小的窗口，每一次对一个小的窗口进行流量控制。这种方法可以很好的解决之前的临界问题。
这里找的网上一个图，假设我们将1S划分为4个窗口，则每个窗口对应250ms的。假设恶意用户还是在上一秒的最后一刻和下一秒的第一刻冲击服务，按照滑动窗口的原理，此时统计上一秒的最后750毫秒和下一秒的前250毫秒，这种方式能够判断出用户的访问依旧超过了1秒的访问数量，因此依然会阻拦用户的访问。
hystrix的滑动窗口设计：
Hystrix滑动窗口设计的关键在于其高效的无锁统计。
在统计指标项时，如果每个周期都从零开始统计，那么会得到一个周期性出现锯齿的统计曲线，在系统层面上会表现为对依赖的服务造成herd effect（羊群效应/从众效应）。
因此，Hystrix将一个统计周期分解为更小的段（bucket），通过移动时间窗口淘汰最老的bucket。
Rolling Window
每当需要开始一个新的bucket时，牺牲可容忍的准确性，通过tryLock由一个线程去更新，其他线程依然使用最近的bucket来更新计数。
每个bucket使用LongAdder而不是AtomicLong进一步降低写的并发，减少执行CAS时循环的次数。
3、令牌桶算法
概念：
令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。 当桶满时，新添加的令牌被丢弃或拒绝。
令牌桶算法是比较常见的限流算法之一，大概描述如下：
1）、所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2）、根据限流大小，设置按照一定的速率往桶里添加令牌；
3）、桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝；
4）、请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；
5）、令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流；
例：
guava的RateLimiter的SmoothBursty实现
4、漏桶算法
概念：
漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。
例子：
guava的RateLimiter的 SmoothWarmingUp实现
