【云原生】服务限流熔断概述、常见限流算法

1、服务雪崩

一个服务失败，导致整条链路的服务都失败的情形，我们称之为服务雪崩。

• 比如服务A请求服务B，服务B再请求服务C，服务由于某种原因hand住了请求，呈现一个假死的状态，这是会导致服务A和服务B都级联崩溃。

服务熔断和服务降级就可以视为解决服务雪崩的手段。

1）服务熔断

当某个服务提供者无法正常为服务调用者提供服务时，为了防止服务雪崩，暂时将出现故障的接口隔离起来，后续一段时间内调用该服务的请求都会直接失败，直到目标服务恢复正常。

熔断其实是一个框架级的处理，熔断机制的设计基本上采用的都是断路器模式：

• 断路器模式包含三种状态：Closed、Open、Half Open。

2）服务降级

服务降级有两种表现：

• 下游服务因为某种原因响应过慢，下游服务主动停掉一些不太重要的业务，释放出服务器资源，增加响应速度；
• 当下游的服务因为某种原因不可用，上游主动调用本地的一些降级逻辑，避免卡顿，迅速返回给用户；

服务降级大多是一种业务级别的处理，比如：

• 开关降级。做个开关，然后将开关放在配置中心；在配置中心更改开关，决定哪些服务进行降级。

一般我们会梳理出核心业务流程和非核心业务流程。然后在非核心业务流程上加上开关，一旦发现系统扛不住，关掉开关，结束次要流程；

3）服务熔断降级的几种常见方案

1> 平均响应时间

比如1秒内持续进入5个请求，对应时刻的平均响应时间均超过阈值，那么接下来在一个固定的时间窗口内，对这个方法的访问都会自动熔断。

2> 异常比例

当某个方法每秒调用所获得的异常总数的比例超过设定的阈值时，该资源会自动进入降级状态，也就是在接下来的一个固定时间窗口中，对这个方法的调用都会自动熔断。

3> 异常数量

和异常比例类似，当某个方法在指定时间窗口内获得的异常数量超过阈值时，会触发熔断。

2、限流概述

限流是指在系统面临高并发、大流量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。

• 假如，系统可以处理1万的并发，但是某一时刻并发数是2万；限流机制会保证1万的用户是正常使用的。否则，请求量过大，会将系统可用性拖垮。

在计算机网络中，限流指控制网络接口发送或接收请求的速率，它可防止DoS攻击和限制Web爬虫。

1）为什么要有限流？

日常的业务上有一些类似秒杀、双十一大促 或 突发新闻等场景，用户的流量突增，但是后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮，级联导致整个系统崩溃！

亦或是爬虫等不正常流量，我们对外暴露的服务都要以最大恶意去防备我们的调用者。因为我们完全不清楚调用者会如何调用我们的服务。甚至还有DDos攻击。

限流的主要目的：

• 通过限制并发访问数 或者 限制一个时间窗口内允许处理的请求数量来保护系统，一旦达到限制流量，则对当前 请求进行处理采取对应的拒绝策略，如：跳转错误页面、进行排队、服务降级等。

2）DDos攻击

DDos是Distributed Denial of Service的缩写，意为：分布式拒绝服务攻击，俗称洪水攻击。

DDOS的攻击策略侧重于通过很多“僵尸主机”（被攻击者入侵过的 或 可以间接利用的主机）向受害主机发送大量看似合法的网络包，从而造成网络阻塞 或 服务器资源耗 进而导致拒绝服务；

分布式拒绝服务攻击一旦被实施，攻击网络包就会犹如洪水般涌向受害主机，从而把合法用户的网络包淹没，导致合法用户无法正常访问服务器的网络资源。

3、常见限流算法

常见的限流算法有五种：计数器法（又名固定窗口算法）、滑动窗口算法、漏桶算法、令牌桶算法；

1）计数器法

计数器法是限流算法里最简单也是最容易实现的一种算法；无论是在单机还是分布式环境，单机使用Atomic原子类，分布式使用Redis incr。

计数器法使用计数器在周期内（一般1s一个周期）累计访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，清零访问次数，计数器重置为0，重新计数。

存在的问题？

• 对于秒级以上的时间周期来说，会存在一个非常严重的问题：窗口切换时的临界问题。

  假设1min内服务器的负载能力为10000，因此一个周期（1min）的访问量限制在10000，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入10000的访问量，虽然没有超过每个周期的限制量，但是整体上10秒内已达到20000的访问量，已远远超过服务器的负载能力。

2）滑动窗口算法

计数器法的临界问题在于统计的精度太低，可以通过将窗口变小来优化临界问题，窗口划分的越多越小，限流就越精准。

滑动窗口（Rolling Window）算法正是对固定窗口算法的改进，滑动窗口算法将一个时间周期切分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期，一个小周期对应一个小窗口；

• 每个小窗口对应不同的时间点，拥有独立的计数器；
• 当请求的时间点大于当前窗口的最大时间点时，则将窗口向前平移一个小窗口（将第一个小窗口的数据舍弃，第二个小窗口变成第一个小窗口，当前请求放在最后一个小窗口）；

相对于固定窗口，滑动窗口除了引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此滑动窗口对内存的占用会更多。

3）漏桶算法

漏桶算法解决了时间窗口类算法的痛点，可以使流量更加的平滑；

漏桶（Leaky Bucket）算法可以理解为注水漏水的过程，往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。

• 流入的水滴，可以看作是访问系统的请求，这个流入速率是不确定的；
• 桶的容量一般用来表示系统所能处理的请求数；
  • 如果桶的容量满了，也就达到限流的阀值，会丢弃水滴（即：拒绝请求）；
• 流出的水滴，是恒定速率的，用来表示服务按照固定的速率处理请求。

消息中间件MQ采用的正是漏桶的思想，水滴的流入和留出可以看做是生产者消费者模式；

• 请求是一个生产者，每一个请求都如一滴水，请求到来后放到一个队列（漏桶）中；
• 桶底有一个孔，不断的漏出水滴，就像消费者不断的消费队列中的内容，并且消费的速率（漏出的速度）等于限流阈值。

4）令牌桶算法

令牌桶（Token Bucket）算法是对漏桶算法的一种改进，不仅能够平滑限流，还允许一定程度的流量突发；它是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。

令牌桶的实现思路也类似于生产者和消费之间的关系：

• 系统服务作为生产者，按照指定频率向桶（容器）中添加令牌，如 QPS 为 500，每 2ms 向桶中添加一个令牌，如果桶中令牌数量达到阈值，则不再添加。

• 请求的执行作为消费者，每个请求都需要去桶中拿取一个令牌，取到令牌则继续执行；

• 如果桶中无令牌可取，就触发拒绝策略，可以是超时等待，也可以是直接拒绝请求，以此达到限流目的。

令牌桶的实现特点：

1. 1s / 限流阈值（QPS） = 令牌添加时间间隔；
2. 桶的容量可以大于限流的阈值（做一定的冗余），令牌数量达到桶容量时，不再添加；
3. 可以适应流量突发，N 个请求到来只需要从桶中获取 N 个令牌就可以继续处理；
4. 令牌桶启动时桶中无令牌，启动后按照令牌添加时间间隔添加令牌，若启动时就有阈值数量的请求过来，会因为桶中没有足够的令牌而触发拒绝策略，不过如 RateLimiter 限流工具已经优化了这个问题。

Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一个实现

5）计数器法和滑动窗口对比

• 计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。
  • 有临界突发流量问题，瞬时流量最大可以达到阈值的N倍（N不可控）。
• 滑动窗口优化了临界突发流量问题，但需要存储多份的计数器（每一个窗口存一份），即：需要更多的存储空间。也就是说如果滑动窗口的精度越高，需要的存储空间就越大。
  • 流量到达阈值时会瞬间掐断流量，流量不够平滑；
• 滑动窗口和固定窗口都无法解决短时间之内集中流量的突击；

6）漏桶算法和令牌桶算法对比

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发；

• 默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过；

• 再从实现上来讲：

  • 漏桶算法漏桶水滴的流出速度始终保持不变；使请求流出速率均匀；
  • 令牌桶算法令牌匀速往令牌桶中添加令牌，使请求可以获取到的token流入速率均匀，这也是令牌桶算法可以应对突发流量的体现。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。

当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。

7）各个算法细节对比

5、后续

四面四种限流算法仅仅是个概念，如果让我们自己实现，如何手撕限流算法，感兴趣的可以自己实现试试；

Redis实现限流的方式可以看以下文章：

• Redis INCR：https://redis.io/commands/incr
• Rate Limiting Wikipedia：https://en.wikipedia.org/wiki/Rate_limiting