服务限流常用的几种算法

谁践踏了优雅 2022-11-18 10:55 23阅读 0赞

## ##

限流、熔断、降级，是我们经常听到的三个名词，但对三者的区别和关系，很多人傻傻分不清楚。那我会根据我的理解，尽量讲明白三者的区别，以及如何落地应用到实际项目中。

我们知道，互联网系统，流量的突然暴涨很常见，有些场景是可以预见的，比如双11、双12活动；而有些场景则是不可预见的，比如一个明星的突然官宣。如果对高流量不做任何保护措施，当请求超过服务器承载极限的时候，系统就会奔溃，导致服务不可用。

那么，在高流量的场景下，如何保证服务集群整体稳定和可用性呢？主要有两个方向，一是通过资源扩容来提升系统整体的容量，缺点就是成本比较高，且考虑到 **ROI（投入产出比）**，也不可能无限扩容。而另一个更经济可行的选择就是**限流**。

所谓**限流**，是指当系统资源不足以应对高流量的时候，为了保证有限的资源能够正常服务，按照预设的规则，对系统进行流量限制。预设的规则中，核心指标可能是 QPS、总并发数、并发线程数，甚至是 IP 白名单，根据这些指标预设的值来决定是否对后续的请求进行拦截。

常见的限流算法有四种：**计数器算法、滑动窗口算法、漏桶算法、令牌桶算法**。

**（1）计数器算法**，也称为**固定窗口算法**，比较简单粗暴，就是在固定的时间周期内（即时间窗口）累加访问次数，当达到设定的阀值时，触发限流策略，比如拒绝请求。下一个周期开始时，进行清零，重新计数。这个算法虽然简单，但存在一个严重的问题，那就是**临界问题**。假设 1 分钟内服务器的负载能力为 100，因此一个周期的访问量限制在 100，然而在第一个周期的最后 1 秒（0:59）和下一个周期的开始 1 秒（1:00）时间段内，分别涌入了 100 的访问量，虽然没有超过每个周期的限制量，但是整体上 2 秒内已达到 200 的访问量，已远超过服务器的负载能力。如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70][]

计数器算法-临界问题

**（2）滑动窗口算法**，就能降低临界问题的影响，它的基本原理就是将一个时间窗口进行分割，比如将 1 分钟的时间窗口分割成 6 格，则每格代表 10 秒钟，且每一格都有自己独立的计数器。每过 10 秒钟，就把整个 1 分钟的时间窗口往右滑动 1 格。而时间窗口内的总计数，则是将该窗口内的所有格子的计数总和出来的。如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70 1][]

滑动窗口算法，那么，再来看看刚才的临界问题。0:59 的 100 个请求会落在灰色的格子里，而 1:00 到达的请求则落在橘黄色的格子里。当时间到达 1:00 时，时间窗口会往右移一格，而这时，整个窗口的总计数其实已经达到了 100，所以，1:00 之后到达的请求其实就会触发限流策略了。由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。不过，滑动窗口算法依然无法应对细时间粒度的突发流量，对流量的整形效果在细时间粒度上不够平滑。

**（3）漏桶算法：**我们可以把系统看成一个水桶，进来的请求理解为往桶里注水，处理请求就是桶中的水流出。水桶有固定容量，如果满了就溢出。不管注入水（请求进入）的快慢如何，只按照恒定的速率出水（处理请求）。因为桶容量是不变的，保证了整体的速率。不过，也因为速率是固定的，所以应对突发流量时就显得效率低下了。Java 自带的信号量组件 **Semaphore** 就是典型的基于漏桶算法实现的

**（4）令牌桶算法：**应该算是最灵活的限流算法了，基本原理直接看下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70 2][]

令牌桶算法理论：

令牌桶算法可以在运行时控制和调整数据处理的速率，一旦需要提高速率，则按需提高放入桶中的令牌的速率。一般会定时(比如100毫秒)往桶中增加一定数量的令牌，有些变种算法则实时的计算应该增加的令牌的数量。因此，令牌桶就可以应对突发流量了。不过，其实现相对也更复杂一些。**Google Guava 的 RateLimiter** 组件就是采用令牌桶算法实现的。

在实际应用中，尤其在分布式系统中，使用最广泛的组件应属 **Sentinel**，它的定位就是**面向分布式服务架构的高可用流量控制组件**。Sentinel 提供的主要功能不仅是限流，也提供了熔断降级、系统负载保护。对多语言的支持方面，除了 Java，也支持了 Go 和 C++。另外，限流方面，Sentinel 除了支持单机限流，也支持集群限流。

而具体到我们的交易系统中，应该在哪些地方做限流呢？主要就是对接口做限流，而我们的接口可以分为几大类：**管理端 API、客户端 API、开放 API、服务内部 API**。管理端 API 基本不会有突发流量的产生，所以也没必要做限流。客户端 API 和开放 API 则需要做限流，但两者的限流规则应该不一样，对开放 API 的限流规则应该严格一些，因为更容易被攻击。服务内部 API 在目前阶段也可以不做限流，一般微服务的规模比较大，某些服务的调用方比较多的时候需要做限流；或者其他一些场景导致下游出现突发流量的时候，比如上游调用方多线程并发跑定时任务调用下游服务的接口，这种情况下为了防止接口被过度调用，就需要对每个调用方进行细粒度的访问限流。

所以，我们就先给客户端 API 和开放 API 加限流，那么，就需要在客户端 API 网关和开放 API 网关集成限流组件，组件的选型就直接用 **Sentinel**。这两个 API 网关应该都是多实例部署的，所以分别需要做集群限流。部署方式采用独立部署 Sentinel 服务端的方式，且每个网关实例需要引入 Sentinel 客户端依赖。

*  限流规则的粒度方面，除了需要限制集群整体的访问频率，还需要限制某类接口甚至某个具体接口的访问频率。
 *  网关层的限流只能做到粗粒度的集群整体的限流，以及按不同路由名称进行限流。而具体到某个接口的，则只能在业务层的微服务进行限流了，所以还需要给对应的微服务集成限流组件客户端。
 *  具体接口层面，应该对下单请求进行限流，而限流策略可以用匀速器方式，对应的则是漏桶算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70]: /images/20221022/96a83d7489ca4fa0ae8a0d16373051b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70 1]: /images/20221022/69e4295ba6bd4001836a8d9bd6ad7c26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkzMjc0_size_16_color_FFFFFF_t_70 2]: /images/20221022/70727596b54143ad927a5dcc3ba78824.png