分布式系统限流方案

一、服务限流场景

在高并发大流量系统中，由于并发大造成服务资源不足，负载过高，进而引发致一系列问题，这里的流量一般都是突发性的，由于系统准备不足，很难短期扩容来应对，进行限流是最常用的手段，所以说限流也是服务稳定性治理重要的手段。
限流可能发生在多个层面：

用户网络层：突发的流量场景如热点事件流量（秒杀事件、热门抢购，微博热搜），恶意刷流，竞对爬虫等。
内部应用层：上游服务的异常调用，脚本异常请求，失败重试策略造成流量突发。

常用的限流方法主要有三种：计数器算法，漏斗桶算法，令牌桶算法。

二、计数器限流

2.1 固定窗口计数器限流

计数限流是最为简单的限流算法，日常开发中，我们说的限流很多都是说固定窗口计数限流算法，比如某一个接口或服务1s最多只能接收1000个请求，那么我们就会设置其限流为1000QPS。该算法的实现思路非常简单，维护一个固定单位时间内的计数器，如果检测到单位时间已经过去就重置计数器为零。
固定窗口计数器原理

其操作步骤：

时间线划分为多个独立且固定大小窗口；
落在每一个时间窗口内的请求就将计数器加1；
如果计数器超过了限流阈值，则后续落在该窗口的请求都会被拒绝。但时间达到下一个时间窗口时，计数器会被重置为0。

2.2 滑动窗口计数器

滑动时间窗口算法是对固定时间窗口算法的一种改进，这词被大众所知实在TCP的流量控制中。固定窗口计数器可以说是滑动窗口计数器的一种特例，滑动窗口的操作步骤：

将单位时间划分为多个区间，一般都是均分为多个小的时间段；
每一个区间内都有一个计数器，有一个请求落在该区间内，则该区间内的计数器就会加一；
每过一个时间段，时间窗口就会往右滑动一格，抛弃最老的一个区间，并纳入新的一个区间；
计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器，计数总和超过了限制数量，则本窗口内所有的请求都被丢弃。
时间窗口划分的越细，并且按照时间”滑动”，这种算法避免了固定窗口计数器出现的上述两个问题。缺点是时间区间的精度越高，算法所需的空间容量就越大。

常见的实现方式主要有基于redis zset的方式和循环队列实现。基于redis zset可将Key为限流标识ID，Value保持唯一，可以用UUID生成，Score 也记为同一时间戳，最好是纳秒级的。使用redis提供的 ZADD、EXPIRE、ZCOUNT 和 zremrangebyscore 来实现，并同时注意开启 Pipeline 来尽可能提升性能。实现很简单，但是缺点就是zset的数据结构会越来越大。

三、漏斗桶限流

漏桶算法是水先进入到漏桶里，漏桶再以一定的速率出水，当流入水的数量大于流出水时，多余的水直接溢出。把水换成请求来看，漏桶相当于服务器队列，但请求量大于限流阈值时，多出来的请求就会被拒绝服务。漏桶算法使用队列实现，可以以固定的速率控制流量的访问速度，可以做到流量的“平整化”处理。

漏桶算法原理

漏桶算法实现步骤：

将每个请求放入固定大小的队列进行存储；
队列以固定速率向外流出请求，如果队列为空则停止流出；
如队列满了则多余的请求会被直接拒绝·
漏桶算法有一个明显的缺陷：当短时间内有大量的突发请求时，即使服务器负载不高，每个请求也都得在队列中等待一段时间才能被响应。

漏斗桶适用场景

漏斗桶更像是对流量进行整形Traffic Shaping，所有流量过来都要进行排队，依次出去，可用于做一些论坛博客发帖频率限制。
相对于计数器限流，达到限流后该时间窗口会丢弃一切请求，漏斗在桶满后，由于还会有持续流出，新到达请求还有机会流入。
局限：由于出口处理速率是匀速的，短时有大量突发请求，即使负载压力不大，请求仍需要在队列等待处理。
改进（根据消费速度，控制放行速度）