什么是限流器以及常见的服务限流算法

作者：lotusgrm
链接：https://www.jianshu.com/p/0302b86b628a
在开发高并发系统的时候，我们一般通过三种方式去保障系统服务稳定：服务降级、服务限流和缓存。对于缓存在实际开发中使用的比较多，这个是大家的共识没有什么异议的。今天我们的主角是服务限流，在此之前我们先来看下服务限流 和 服务降级 的区别：
服务降级

服务降级是在服务器压力陡增的情况下，利用现有的资源，关闭一些服务接口或者页面，以此来释放服务器资源保证核心任务的正常运行
服务限流

限流本质上是减少流量的访问，而服务的处理能力不变；而对于服务降级来说是降低了部分服务的处理能力，增加另一部分服务处理能力，访问量不变
本篇文章中说到的服务限流不是 nginx 层面的限流，而是业务代码中的逻辑限流。

那么，我们为什么要服务限流？

从服务调用方来说，可以把服务简单的划分为以下几种类型的服务
1.与用户打交道的服务
比如 web 服务，对外 API,这种类型的服务有以下几种可能会导致服务器压力变大：

用户增长过快
热点事件
恶意的攻击/刷单
爬虫
这些情况都是无法预知的，我们不知道什么时候请求流量会突增，如果真的要是碰到这种情况，扩容根本是来不及的
2.对内的 RPC 服务
一个服务 A 的接口可能会被其他 BCDE 多个服务调用，如果其中一个服务的流量突增比如 B 服务，导致 A 服务压力变大甚至挂掉，那么这个时候也不能给 CDE 服务提供服务
这种情况在实际开发中时常发生
常见的限流算法

下面我们来看几种实际业务场景中常用的几种限流算法：计数器算法、漏桶算法、令牌桶算法

计数器算法

计数器算法应该是最简单，最容易想到的限流策略。限流的本质是限制某一个 API 在某个维度单位时间内处理请求的次数。我们可以设置一个计数器对某一时间段内的请求进行计数，当请求量超过事先设定好的阈值，拒绝用户的请求。比如限流的 QPS 是100，算法的实现思路是从第一个请求进来开始计数，在接下来的 1s 内，每来一个请求计数器自动加 1，如果累加的数字超过 100，那么后续的请求就会被拒绝，等到 1s 结束后，计数器开始重置为 0，重新开始计数。
这种方式存在弊端
弊端1：如果在 1s 的前 10ms 请求数已经达到了 100，那么剩下的 990ms，服务调用方就要眼巴巴的看着请求被拒绝
弊端2：如果有一个恶意的用户在 999ms 的时候瞬间发送了 100 次请求，并且又在 1000ms 时瞬间发送了 100 次请求，那么其实这个用户在 1s 内发送了 200 次请求。利用时间窗口的重置节点处突发请求，可以瞬间超过我们服务本身能承受的压力，瞬间压垮服务

针对计数器算法的漏洞一个比较经典的处理方案是采用 滑动窗口。比如我们把上面的 1min 内 100 次请求上限看成是一个大的时间窗口，然后把这个窗口进一步细分，比如每 10 s 一个小窗口，该窗口的频率上限同样设置成 100，这样大窗口包含 16 个小窗口，并且每过 10s 大窗口就移动一个小窗口长度。如果一个恶意用户在 09:59:30~09:59:59 之间发送了 100 次请求，等到了10:00:00~10:00:30 时 100 次计数仍然是有效的，所以，这个时间段新的请求仍然会被拒绝

漏桶算法

漏桶算法是限流方面比较经典的算法。可以把该算法联想成一个具体的漏桶模型，漏桶始终以一个恒定的速率往外排水，如果桶被装满的话则后来涌入的水会溢出。对应到接口限流来说，用户的请求可以看做是水，不管用户的请求量有多大多不均衡，能够被处理的请求速率是恒定的，而且能够接受的请求数也是有上限的，超出上限的请求会被拒绝，在算法实现方面可以准备一个队列来作为漏桶的实现，用这个队列保存请求，通过一个线程池定期从队列中获取请求并执行，也可以一次性获取多个并发请求，如下图：

漏桶算法也存在一个弊端：无法应对短时间的突发流量

令牌桶算法

在令牌桶算法中，存在一个桶，用来存放固定数量的令牌。算法中存在一种机制，以一定的速率往桶中放令牌。每次请求调用需要先获取令牌，只有拿到令牌才有机会继续执行，否则请求选择等待或者服务直接拒绝请求
放令牌这个动作是持续不断的进行，如果桶中令牌数量达到上限，就丢弃令牌，所以，会存在这样的一种情况，桶中一直有大量的令牌，这时进来的请求就可以直接拿到令牌执行。比如我们把 QPS 设置成 100，那么限流器完成初始化 1s 后，桶中已经有 100 个令牌，这时候服务还未完全启动好，等启动完成功对外提供服务时，该限流器可以抵挡瞬时的 100 个请求。所以，当桶中没有令牌时请求才会等待或者被拒绝，当没有请求申请令牌时，那么这个令牌桶会溢出。在这里令牌桶类似一个 buffer,请求密度比较低或者处于冷却状态下，令牌桶会溢出，当请求流量突增时，则过去积累的结余资源直接可以拿来借用，从这里可以看出这点弥补了漏桶算法的不足

实现思路：可以准备一个队列，用于存放令牌，另外通过一个线程池定期生成令牌存放到队列中，没来一个请求就从队列中取出一个令牌，并继续执行

上面我们提到的限流算法主要是针对于单机限流，实际业务场景更加的复杂，业务的需求五花八门，简单的单机限流很难满足需求。
比如为了限制某个资源被某个用户访问的次数，10 s 只能访问 3 次，或者一天只能访问 100 次，这种需求通过单机限流是无法实现的，这时就需要通过集群限流的方式实现

如何实现?为了实现对访问次数的限制，肯定需要一个计数器，那么我们需要把这个计数器放在哪里呢？因为这个限流是在集群层面实现的，集群形式存在的情况才需要分布式限流，由于 redis 天生对分布式支持非常友好，所以 redis 成了一个很好的选择

大致思路：每次有相关的操作时候，我们就向 redis 服务器发送一个 incr 命令。比如限制某个用户访问接口的次数，当用户请求过来时我们使用用户 ID 和 接口名称生成对应 key,每次该用户访问这个接口时，只需要对这个 key 增加 1，并且给这个 key 设置有效期，这样就可以简单的实现指定时间内的访问效率