限流的原理以及常用算法
高并发的处理有三个比较常用的手段：缓存、限流和降级。
在一个分布式的高可用系统中，限流是必备的操作。这个流可以是：网络流量，带宽，每秒处理的事务数，每秒请求数，并发请求数，或者业务上的指标等。比如在参加一些秒杀活动的时候，我们可以看到，有时候会出现“系统繁忙，请稍后再试”或者 “请稍等”的提示，那这个系统就很可能是使用了限流的手段。
限流是限制系统的输入和输出流量，以达到保护系统的目的。而限流的实现主要是依靠限流算法，限流算法主要有下面4种。
1、固定时间窗口（计数器）
计数器固定时间窗口算法是最基础也是最简单的一种限流算法。
原理：对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则拒绝该请求；如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。
优点：实现简单，容易理解
缺点：限流策略过于粗略，不够平滑，无法应对两个时间窗口临界时间内的突发流量。
举个栗子：
假设这样一个场景，我们限制用户一分钟下单不超过 10 万次，现在在两个时间窗口的交汇点，前后一秒钟内，分别发送 10 万次请求。也就是说，窗口切换的这两秒钟内，系统接收了 20 万下单请求，这个峰值可能会超过系统阈值，影响服务稳定性。
2、滑动时间窗口
实现：滑动时间窗口算法是对固定时间窗口算法的一种改进,通过切分更细维度的计数器来记录一段时间窗口内请求数量，超过阈值拒绝请求。
优点：准确性更高。
缺点：没有从根本上解决临界问题。基于时间窗口的限流算法，不管是固定时间窗口还是滑动时间窗口，只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。
3、漏桶算法
思路：水（请求）先进入到漏桶里，漏桶以一定速度向外出水。当水流入速度过大，桶会直接溢出。即请求进入一个固定容量的Queue，若Queue满，则拒绝新的请求，可以阻塞，也可以抛异常。
这种模型其实非常类似MQ的思想，利用漏桶削峰填谷，使得Queue的下游具有一个稳定流量。
实现：生产者和消费者
优点：从出口处限制请求速率，并不存在上面计数器法的临界问题，请求曲线始终是平滑的。
缺点：对请求的过滤太精准了，不允许任何的突发流量。比如我们限制每秒下单 10 万次，那 第10 万零 1 次的请求，就会被拒绝。大部分业务场景下，虽然限流了，但还是希望系统允许一定的突发流量，这时候就需要令牌桶算法。
4、令牌桶算法
思路：系统以一个恒定的速率往桶里放入令牌。桶的容量是一定的，如果桶已经满了就不再继续添加。若有请求需要处理，则从令牌桶里获取令牌，当桶里没有令牌，否则拒绝请求或者加入队列进行排队等等。
令牌桶算法并不能实际的控制速率。比如，10秒往桶里放入10000个令牌桶，即10秒内只能处理10000个请求，那么qps就是100。但这种模型可以出现1秒内把10000个令牌全部消费完，即qps为10000。所以令牌桶算法实际是限制的平均流速。具体控制的粒度以放令牌的间隔和每次的量来决定。若想要把流速控制的更加稳定，就要缩短间隔时间。
实现：Redis+Lua
优点：允许一定程度流量突发，但不会超过设置阈值，对用户友好同时有效保护系统。
缺点：请求异步处理，无法同步返回
Google 的 Guava 中工具类 RateLimiter，就是基于令牌桶算法实现流量限制，使用非常方便。
漏桶算法VS令牌桶算法
1） 漏桶算法进水速率是不确定的，但是出水速率是一定的，当大量的请求到达时势必会有很多请求被丢弃。
2） 令牌桶算法会根据限流大小，设置一定的速率往桶中加令牌，这个速率可以很方便的修改，如果我们要提高系统对突发流量的处理，我们可以适当的提高生成token的速率。
参考链接：
https://www.jianshu.com/p/6e4eb31128af
https://juejin.cn/post/6870396751178629127
https://www.cnblogs.com/shijiaqi1066/p/10508115.html