系统服务是如何实现限流的

服务限流

服务限流其实就是当高并发或者瞬时高并发时，为了保证系统的稳定性、可用性，系统以牺牲部分请求为代价或者延迟处理请求为代价，保证整个服务可用。

限流主要限制请求流量，保证当前服务、依赖服务不会被被大流量彻底压垮而导致雪崩。

比如我们的核心系统最高支持300QPS，但是突然有1000QPS请求打了进来，可能这个时候系统就会直接挂掉，导致后面一个请求都处理不了，但是如果我们有限流的手段，无论他有多大的QPS，我们都只处理300QPS的请求，其他请求都直接拒绝掉，虽然有700的QPS的请求我们拒绝掉了，但是我们的系统没有挂掉，我们系统仍然可以不断的处理后续的请求，这个是我们所期望的。

目前越来越多的企业在大流量高并发的处理场景取得不少的成果，例如：在2020年天猫京东双11购物节、12306在春运期间支撑全国人民的抢火车票、苏宁/淘宝/京东抢购飞天茅台活动，都是对大流量高并发处理的成功案例。

在Google，已经开源工具包Guava中发布了一个限流工具类RateLimiter，RateLimiter基于可配置的速率来分发令牌，在获取到令牌之后才能进行后续处理，从而实现对接口速率的限制。

在Netflix，API团队于2011年开始的弹性工程工作，随着Hystrix不断发展和成熟，Netflix内部的许多团队都采用了它。如今，每天在Netflix上通过Hystrix执行数百亿个线程隔离和数千亿个信号量隔离的调用。

在阿里巴巴，2012~2018年，Sentinel 在阿里巴巴集团内部迅速发展，成为基础技术模块，覆盖了所有的核心场景。

Sentinel 也因此积累了大量的流量控制场景以及生产实践，2018年，阿里巴巴宣布限流降级框架组件 Sentinel 正式开源，在此之前，Sentinel 作为阿里巴巴架构中的基础模块，已经覆盖了阿里的所有核心场景，因此积累了大量的流量归整场景以及生产实践。

限流算法

限流在技术层面，是一种主动调整流量输出速率的措施，它能够采取一定的方法控制指定时间段内发送的流量，有助于减少拥堵。限流控制最早主要用于与网络设备端口流量速率控制，在1997年，思科就提出：专利《采用令牌漏桶进行报文限流的方法》，在2017年 阿里巴巴集团就互联网场景限流，申请的《基于令牌桶进行限流的方法、装置和设备》专利发布，目前此限流广泛在Web应用中使用该技术用于控制网络请求与处理速率。目前互联网服务流量场景，主要算法包括有：时间滑动窗口算法、令牌桶算法、漏桶算法等。

1. 固定时间窗口算法

首先我们来说一下固定时间窗口算法，这个算法比较简单粗暴，我们只需要一个累加变量，然后每个一秒去刷新这个累加的变量，然后再判断这个累计变量是否大于我们的最大QPS。

/**
 * @author Herry Jiang
 * @date 2021/3/8
 */
public class FixRateLimit extends AbstractRateLimit implements RateLimit {
    private long lasTime = System.currentTimeMillis();
    // 当前QPS
    private AtomicInteger curQPS = new AtomicInteger(0);
    public FixRateLimit(int maxQps) {
        super(maxQps);
    }
    public boolean acquire() {
        synchronized (mutex()){
            //获取当前时间
            long now = System.currentTimeMillis();
            if (now - lasTime > 1000){
                lasTime = now;
                curQPS.set(0);
            }
            if (curQPS.addAndGet(1) > maxQps){
                return false;
            }
            return true;
        }
    }
}

1.2 时间滑动窗口算法

滑动时间窗口算法相比固定时间窗口计算算法优化在于，它把时间以一定比例分片。解决了固定时间窗口临界值的问题。相对固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存占用相对多一些。

例如：限流每秒钟处理300个请求，我们可以把1秒分为100个窗口，每隔10毫秒移动一次，每隔窗口只能处理10毫秒只能处理3个请求，通过把窗口分成更小的片，从而解决了固定窗口临界值流量翻倍的问题。虽然侧面切分窗口的方法解决了流量固定窗口翻倍的问题(分的越细控制越精准)，但是此算法不支持突发流量的情况，例如：在前10ms来了300个请求的流量突发场景。代码实现

/**
 * @author Herry Jiang
 * @date 2021/3/8
 */
public class SlideRateLimit extends AbstractRateLimit implements RateLimit {
    //默认窗口个数：100个
    private int windowNum = 100;
    //默认窗口大小：10ms
    private int windowSize = 10;
    //计算每分片个窗口最大QPS
    private int windowMaxQPS;
    //记录整个大窗口开始时间戳
    private long windowBeginTime = System.currentTimeMillis();
    //当前QPS
    private AtomicInteger curQPS = new AtomicInteger(0);
    //记录每个小窗口对应QPS情况
    private Map<Long, AtomicInteger> windowQpsMap = new ConcurrentHashMap<Long, AtomicInteger>();
    public SlideRateLimit(int maxQps) {
        super(maxQps);
        this.windowMaxQPS = maxQps / windowNum;
    }
    public SlideRateLimit(int maxQps, int windowSize) {
        super(maxQps);
        if (windowSize <= 0){
            throw new RuntimeException("窗口大小不能小于0");
        }
        this.windowSize = windowSize;
        this.windowNum = 1000 / windowSize;
        this.windowMaxQPS = maxQps / this.windowNum;
    }
    public boolean acquire() {
        // 统计的请求数小于阈值就记录这个请求时间，并允许通过，反之拒绝
        synchronized (mutex()){
            // 获取当前时间
            long now = System.currentTimeMillis();
            // 每次统计请求时间 至 往前1秒这个时间窗口内请求数，且1秒前数据不保存
            long interval = now - windowBeginTime;
            if (interval > 1000){
                windowQpsMap.clear();
                windowBeginTime = now;
                curQPS.set(0);
                interval = 0;
            }
            if (windowMaxQPS != 0){
                // 计算当前小窗口位置
                Long windowKey = interval / windowSize + 1;
                if (windowQpsMap.containsKey(windowKey)){
                    System.out.println("窗口位:"+windowKey+", QPS:"+windowQpsMap.get(windowKey));
                    if (windowQpsMap.get(windowKey).addAndGet(1) > windowMaxQPS){
                        return false;
                    }
                }else {
                    System.out.println("窗口位:"+windowKey+", QPS:"+windowQpsMap.get(windowKey));
                    windowQpsMap.put(windowKey, new AtomicInteger(1));
                }
            }
            if (curQPS.addAndGet(1) > maxQps){
                return false;
            }
            return true;
        }
    }
}

1.3 令牌桶算法

令牌桶作为常用的网络流量控制算法，可控制网络请求的数量，对一定限度内的突发请求（图片请求量对于令牌桶的数量）也可以发送，令牌桶算法原理如下：

令牌桶的算法思想具体如下： 

1. 假设令牌桶容量可容纳C个令牌，每秒放入r个令牌，W为目前桶内令牌数，如果桶满了，则将多余令牌丢弃；

2. 如果请求b到达，按需求向令牌桶请求令牌，如果上个处理时间为at，此时桶内的令牌数为W’=min(C， W+(bt-at)*r)，如果w’大于1则拿到令牌W‘减一，否则拒绝请求；

3. 代码实现

/**
 * @author Herry Jiang
 * @date 2021/3/9
 */
public class TokenRateLimit extends AbstractRateLimit implements RateLimit {
    private volatile long lasTime = System.currentTimeMillis();
    //每隔多久放一个token，时间单位为微秒
    private long tokenIntervalMicroseconds;
    public static final long CONSTANT_1000 = 1000;
    //当前QPS
    private AtomicLong tokenBucket = new AtomicLong(0);
    public TokenRateLimit(int maxQps) {
        super(maxQps);
        tokenIntervalMicroseconds = 1000 * 1000 / maxQps;
    }
    public boolean acquire() {
        // 放token
        synchronized (mutex()){
            long now = System.currentTimeMillis();
            long interval = now - lasTime;
            if (interval > CONSTANT_1000){
                lasTime = now;
                interval = 1000;
            }
            long putTokenNum = interval * CONSTANT_1000 / tokenIntervalMicroseconds;
            System.out.println("开始>当前令牌桶token数："+tokenBucket.get()+", putTokenNum="+putTokenNum);
            if (putTokenNum != 0){
                lasTime = now;
                System.out.println("当前令牌桶token数："+tokenBucket.get());
            }
            if (tokenBucket.addAndGet(putTokenNum) > maxQps){
                tokenBucket.set(maxQps);
            }
            System.out.println("结束>当前令牌桶token数："+tokenBucket.get());
            if (tokenBucket.get() <= 0 || tokenBucket.decrementAndGet() < 0){
                return false;
            }
            return true;
        }
    }
}

1.4 漏桶算法

漏桶算法是一种能够临时存储一定数量的请求，将它们分组按照规定速率输出的方法，常用于异步传输模式的网络中，目的是控制流量注入网络的速率，平滑处理网络的突发流量。

该算法与漏桶漏水的方式类似，可以将漏桶算法模型比作一个恒定速率漏水的漏桶，漏桶底部的水以固定速率流出。在漏桶顶部，水以不固定的速率进入桶中，当漏桶装满水，之后水会溢出。算法原理如下：

漏桶的算法思想具体如下：

/**
 * @author Herry Jiang
 * @date 2021/3/10
 */
public class BucketRateLimit extends AbstractRateLimit implements RateLimit {
    private volatile long lasTime = System.currentTimeMillis();
    //多少时间流出1滴水，流出水的时间，时间精确到微秒
    private long intervalMicroseconds;
    private AtomicLong bucketCapacity = new AtomicLong(0);;
    public BucketRateLimit(int maxQps) {
        super(maxQps);
        intervalMicroseconds = 1000 * 1000 / maxQps;
    }
    public boolean acquire() {
        synchronized (mutex()){
            long now = System.currentTimeMillis();
            //漏桶流走的水
            long runOutWater = (now - lasTime) * 1000 / intervalMicroseconds;
            if (runOutWater != 0){
                lasTime = now;
            }
            if (bucketCapacity.addAndGet( - runOutWater ) < 0){
                bucketCapacity.set(0);
            }
            if (bucketCapacity.get() + 1 < maxQps){
                bucketCapacity.incrementAndGet();
                return true;
            }
            return false;
        }
    }
}

算法对比总结

1. 固定时间窗口，存在临界点问题，会突破限流的阈值存在被攻击的风险，但效率相对较高；
2. 滑动时间窗口，可以有效的规避临界点的问题，但是仍然存在时间片概念，时间片段越精确流量控制越细致，从而导致计算耗时增加，且不支持突发流量的处理。
3. 令牌桶算法，能够在限制数据的平均速度的同时还能允许某种程度的突发流量；
4. 漏桶算法限制的是常量流出速率，从而平滑突发流量。以上是服务限流的技术底层基础。另外关于限流如何在生产推广及应用，也是比较考验服务限流组件生产力的表现。

限流降级组件

官方对比

Sentinel

这里主要介绍下Sentinel，随着微服务的流行，服务和服务之间的稳定性变得越来越重要。Sentinel 以流量为切入点，从流量控制、熔断降级、系统负载保护等多个维度保护服务的稳定性。Sentinel 具有以下特征：

1.丰富的应用场景：Sentinel 承接了阿里巴巴近 10 年的双十一大促流量的核心场景，例如秒杀（即突发流量控制在系统容量可以承受的范围）、消息削峰填谷、集群流量控制、实时熔断下游不可用应用等；

2.完备的实时监控：Sentinel 同时提供实时的监控功能。您可以在控制台中看到接入应用的单台机器秒级数据，甚至 500 台以下规模的集群的汇总运行情况；

3.广泛的开源生态：Sentinel 提供开箱即用的与其它开源框架/库的整合模块，例如与 Spring Cloud、Dubbo、gRPC 的整合。您只需要引入相应的依赖并进行简单的配置即可快速地接入 Sentinel；

4.完善的 SPI 扩展点：Sentinel 提供简单易用、完善的 SPI 扩展接口。您可以通过实现扩展接口来快速地定制逻辑。例如定制规则管理、适配动态数据源等；

Sentinel 分为两个部分：

1. 核心库（Java 客户端）不依赖任何框架/库，能够运行于所有 Java 运行时环境，同时对 Dubbo / Spring Cloud 等框架也有较好的支持；

2. 控制台（Dashboard）基于 Spring Boot 开发，打包后可以直接运行，不需要额外的 Tomcat 等应用容器；

Sentinel工作流程

默认架构

为了让你更直观的了解Sentinel 的工作流程，可以参考如下图：

生产环境Sentinel应用与实践

看完Sentinel开源默认运行架构，其实还不能直接投入到生产环境，存在以下几点问题：

1. 限流、降级规则默认保存在应用节点内容中，应用重新发布后就会失效，这显然是无法接受的；
2. metrics信息是有Dashboard主动拉取保存到内容，仅仅保留5分钟，无法全天看到秒级QPS流量情况，也无法还原“案发现场”的流量情况；
3. metrics信息是有Dashboard主动拉取，随着应用接入非常多的话，主动拉取metrics的方式是的Dashboard也会存在瓶颈；

优化解耦架构

版本兼容性选型

最后希望大家的系统在大流量场景下都能稳定运行

算法DEMO代码：

https://github.com/j5land/ratelimit-demo

参考文档

• https://patents.google.com/patent/CN1536815A/zh

• https://patents.google.com/patent/CN107547433A/zh https://github.com/alibaba/Sentinel/wiki/Guideline:-%E4%BB%8E-Hystrix-%E8%BF%81%E7%A7%BB%E5%88%B0-Sentinel

• https://www.javadoop.com/post/sentinel

• https://www.iocoder.cn/Sentinel/laoqian/Sentinel-an-open-source-current-limiting-system-of-alibaba-is-fully-analyzed/

• https://www.cnblogs.com/vivotech/p/14137185.html

• https://segmentfault.com/a/1190000023552181

• https://sentinelguard.io/zh-cn/docs/basic-api-resource-rule.html