浅析常见限流算法

1. 什么是限流?

限流，也叫速率限制(Rate Limiting)，是一种限制请求速率的技术。通常用于保护服务自身，或在下游服务已知无法保护自身的情况下，保护下游服务。

2. 为什么要限流?

服务需要保护自己，以免被太多的请求淹没(无论是恶意或无意的)，从而保持可用性。

举个生活中的例子，某个景区，平时可能根本没什么人前往，但是一旦到了国庆假日就人满为患，这时景区管理人员就会实施一系列的限流举措，来限制进入的人流量。为什么要这么做呢?假设景区能容纳 1 万人，现在进去了 3 万人，势必摩肩接踵，搞不好还会有踩踏事故发生。这样的结果就是所有人的体验都不好，如果发生了事故，景区可能还要关闭，导致对外不可用。

互联网场景中，这样的例子也随处可见。比如秒杀抢购，通过限流来限制并发和请求量，从而保护自身或下游系统不被巨型流量冲垮。

限流算法大致有：服务限流、单机限流和分布式限流。

没有哪种算法是最好的或者是最差的，具体要根据实际业务场景决定使用哪种实现方式，本质都是提高功能的性价比，利用尽可能小的开发成本，产生尽可能大的收益。今天主要介绍的是目前比较常见的限流算法：

固定窗口(计算器法)

滑动窗口

漏桶算法

令牌桶算法

一、固定窗口算法(计算器算法)

计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。

此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性和线程安全即可轻松实现。

这个算法通常用于QPS限流和统计总访问量，对于秒级以上的时间周期来说，会存在一个非常严重的问题，那就是临界问题，如下图：

假设1min内服务器的负载能力为100，因此一个周期的访问量限制在100，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入100的访问量，虽然没有超过每个周期的限制量，但是整体上10秒内已达到200的访问量，已远远超过服务器的负载能力，由此可见，计数器算法方式限流对于周期比较长的限流，存在很大的弊端。

二、滑动窗口算法

滑动窗口算法是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。

如下图，假设时间周期为1min，将1min再分为2个小周期，统计每个小周期的访问数量，则可以看到，第一个时间周期内，访问数量为75，第二个时间周期内，访问数量为100，超过100的访问则被限流掉了

由此可见，当滑动窗口的格子划分地越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

此算法可以很好地解决固定窗口算法的临界问题。

三、漏桶算法

漏桶算法是访问请求到达时直接放入漏桶，如当前容量已达到上限(限流值)，则进行丢弃(触发限流策略)。漏桶以固定的速率进行释放访问请求(即请求通过)，直到漏桶为空。

四、令牌桶算法

令牌桶算法是程序以r(r=时间周期/限流值)的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略。

总结：

所有的请求在处理之前都需要拿到一个可用的令牌才会被处理;

根据限流大小，设置按照一定的速率往桶里添加令牌;

桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝;

请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除;

令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流。