常用的限流算法有哪些？ _限流算法

为什么要做限流呢？举一个生活中的例子，大家早上上班都要挤地铁吧，地铁站在早高峰的时候经常要限制客流，为什么呢？有人会觉得这是人为添堵。真是这样吗？如果不执行客流控制，大家想想会是什么场景呢？站台到处都挤满了乘客，就算你使出洪荒之力也不一定能顺利上车，且非常容易引发肢体碰撞，造成冲突。有了客流控制之后，地铁站才能变得秩序井然，大家才能安全上地铁。
一个系统的处理能力是有上限的，当服务请求量超过处理能力，通常会引起排队，造成响应时间迅速提升。如果对服务占用的资源量没有约束，还可能因为系统资源占用过多而宕机。因此，为了保证系统在遭遇突发流量时，能够正常运行，需要为你的服务加上限流。
常见的限流算法有：漏桶、令牌桶、滑动窗口计数。
分类按照计数范围，可以分为：单机限流、全局限流。单机限流，一般是为了应对突发流量，而全局限流，通常是为了给有限资源进行流量配额。
按照计数周期，可以分为：QPS、并发（连接数）。
按照阈值设定方式的不同，可以分为：固定阈值、动态阈值。
漏桶算法下面这张图，是漏桶的示意图。漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大时，会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。

文章插图
漏桶算法原理
漏桶算法可以使用 redis 队列来实现，生产者发送消息前先检查队列长度是否超过阈值，超过阈值则丢弃消息，否则发送消息到 Redis 队列中；消费者以固定速率从 Redis 队列中取消息。Redis 队列在这里起到了一个缓冲池的作用，起到削峰填谷、流量整形的作用。
令牌桶算法对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。桶里能够存放令牌的最高数量，就是允许的突发传输量。

文章插图
令牌桶算法原理
Guava 中的限流工具 RateLimiter，其原理就是令牌桶算法。
滑动窗口计数法计数法是限流算法里最容易理解的一种，该方法统计最近一段时间的请求量，如果超过一定的阈值，就开始限流。在 TCP 网络协议中，也用到了滑动窗口来限制数据传输速率。

文章插图
滑动窗口计数原理
滑动窗口计数有两个关键的因素：窗口时长、滚动时间间隔。滚动时间间隔一般等于上图中的一个桶 bucket，窗口时长除以滚动时间间隔，就是一个窗口所包含的 bucket 数目。
滑动窗口计数算法的实现，可以查看这篇文章：降级熔断框架 Hystrix 源码解析：滑动窗口统计。
动态限流一般情况下的限流，都需要我们手动设定限流阈值，不仅繁琐，而且容易因系统的发布升级而过时。为此，我们考虑根据系统负载来动态决定是否限流，动态计算限流阈值。可以参考的系统负载参数有：Load、CPU、接口响应时间等。