美团面试：Sentinel底层滑动时间窗限流算法怎么实现的？

尼恩说在前面

在40岁老架构师尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格，遇到很多很重要的面试题：

问题1：Sentinel高可用熔断降级，是如何实现的？

问题2：Sentinel底层滑动时间窗限流算法怎么实现的？

最近又有小伙伴在面试阿里，遇到了相关的面试题。

小伙伴说，Sentinel是自己的盲区，可以说一脸懵逼，面试官不满意，面试挂了，非常可惜，如果早点看看这尼恩的面试宝典，年薪60W+的offer就到手了。

亡羊补牢、为时不晚。

在这里，尼恩给大家做一下系统化、体系化的Sentinel 梳理，使得大家内力猛增，展示一下雄厚的 “技术肌肉、技术实力”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提，offer自由”。

当然，这道面试题，以及参考答案，也会收入咱们的《尼恩Java面试宝典PDF》V165版本，供后面的小伙伴参考，提升大家的 3高架构、设计、开发水平。

《尼恩架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请到文末公号【技术自由圈】取

文章目录

- 尼恩说在前面
- 美团面试：Sentinel底层滑动时间窗限流算法怎么实现的？
- 滑动窗口的核心数据结构
- - ArrayMetric 源码
  - LeapArray 源码
  - MetricBucket 源码
  - WindowWrap 源码
- 滑动窗口统计源码实现
- - 如何定位 Bucket?
- 《Sentinel 学习圣经》 PDF 目录
- 说在最后： “offer自由” 很容易的
- 尼恩技术圣经系列PDF

美团面试：Sentinel底层滑动时间窗限流算法怎么实现的？

Sentinel是一个系统性的高可用保障工具，提供了限流、降级、熔断等一系列的能力，基于这些能力做了语意化概念抽象，这些概念对于理解实现机制特别有帮助，所以这里也复述一下。

对于流量控制，有个一个模型：

流量控制有以下几个角度:

资源的调用关系，例如资源的调用链路，资源和资源之间的关系；
运行指标，例如 QPS、线程池、系统负载等；
控制的效果，例如直接限流、冷启动、排队等。

Sentinel 的设计理念是让您自由选择控制的角度，并进行灵活组合，从而达到想要的效果。

Sentinel使用滑动时间窗口算法来实现流量控制，流量统计。

滑动时间窗算法的核心思想是将一段时间划分为多个时间窗口，并在每个时间窗口内对请求进行计数，以确定是否允许继续请求。

以下是Sentinel底层滑动时间窗口限流算法的简要实现步骤：

时间窗口划分：将整个时间范围划分为多个固定大小的时间窗口（例如1秒一个窗口）。这些时间窗口会随着时间的流逝依次滑动。
计数器：为每个时间窗口维护一个计数器，用于记录在该时间窗口内的请求数。
请求计数：当有请求到来时，将其计入当前时间窗口的计数器中。
滑动时间窗口：定期滑动时间窗口，将过期的时间窗口删除，并创建新的时间窗口。这样可以保持时间窗口的滚动。
限流判断：当有请求到来时，Sentinel会检查当前时间窗口内的请求数是否超过了预设的限制阈值。如果超过了限制阈值，请求将被拒绝或执行降级策略。
计数重置：定期重置过期时间窗口的计数器，以确保计数器不会无限增长。

这种滑动时间窗口算法允许在一段时间内平滑控制请求的流量，而不是仅基于瞬时请求速率进行限流。

它考虑了请求的历史分布，更适用于应对突发流量和周期性负载的情况。

我们知道，Sentinel可以用来帮助我们实现流量控制、服务降级、服务熔断，而这些功能的实现都离不开接口被调用的实时指标数据，本文便是关于 Sentinel 是如何实现指标数据统计的。

上图中的右上角就是滑动窗口的示意图，是 StatisticSlot 的具体实现。

StatisticSlot 是 Sentinel 的核心功能插槽之一，用于统计实时的调用数据。

Sentinel 是基于滑动窗口实现的实时指标数据收集统计，底层采用高性能的滑动窗口数据结构 LeapArray 来统计实时的秒级指标数据，可以很好地支撑写多于读的高并发场景。

滑动窗口的核心数据结构

ArrayMetric：滑动窗口核心实现类。
LeapArray：滑动窗口顶层数据结构，包含一个一个的窗口数据。
WindowWrap：每一个滑动窗口的包装类，其内部的数据结构用 MetricBucket 表示。
MetricBucket：指标桶，例如通过数量、阻塞数量、异常数量、成功数量、响应时间，已通过未来配额（抢占下一个滑动窗口的数量）。
MetricEvent：指标类型，例如通过数量、阻塞数量、异常数量、成功数量、响应时间等。

ArrayMetric 源码

滑动窗口的入口类为 ArrayMetric，实现了 Metric 指标收集核心接口，该接口主要定义一个滑动窗口中成功的数量、异常数量、阻塞数量，TPS、响应时间等数据。

public class ArrayMetric implements Metric {

    private final LeapArray<MetricBucket> data;

    public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) {
        if (enableOccupy) {
            this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
        } else {
            this.data = new BucketLeapArray(sampleCount, intervalInMs);
        }
    }

int intervalInMs：表示一个采集的时间间隔，即滑动窗口的总时间，例如 1 分钟。
int sampleCount：在一个采集间隔中抽样的个数，默认为 2，即一个采集间隔中会包含两个相等的区间，一个区间就是一个窗口。
boolean enableOccupy：是否允许抢占，即当前时间戳已经达到限制后，是否可以占用下一个时间窗口的容量。

LeapArray 源码

LeapArray 用来承载滑动窗口，即成员变量 array，类型为 AtomicReferenceArray<WindowWrap<T>>，保证创建窗口的原子性（CAS）。

public abstract class LeapArray<T> {

    //每一个窗口的时间间隔，单位为毫秒
    protected int windowLengthInMs;
    //抽样个数，就一个统计时间间隔中包含的滑动窗口个数
    protected int sampleCount;
    //一个统计的时间间隔
    protected int intervalInMs;
    //滑动窗口的数组，滑动窗口类型为 WindowWrap<MetricBucket>
    protected final AtomicReferenceArray<WindowWrap<T>> array;
    private final ReentrantLock updateLock = new ReentrantLock();
    
    public LeapArray(int sampleCount, int intervalInMs) {
        this.windowLengthInMs = intervalInMs / sampleCount;
        this.intervalInMs = intervalInMs;
        this.sampleCount = sampleCount;
        this.array = new AtomicReferenceArray<>(sampleCount);
    }

MetricBucket 源码

Sentinel 使用 MetricBucket 统计一个窗口时间内的各项指标数据，这些指标数据包括请求总数、成功总数、异常总数、总耗时、最小耗时、最大耗时等，而一个 Bucket 可以是记录一秒内的数据，也可以是 10 毫秒内的数据，这个时间长度称为窗口时间。

public class MetricBucket {
    /**
     * 存储各事件的计数，比如异常总数、请求总数等
     */
    private final LongAdder[] counters;
    /**
     * 这段事件内的最小耗时
     */
    private volatile long minRt;
}

Bucket 记录一段时间内的各项指标数据用的是一个 LongAdder 数组，数组的每个元素分别记录一个时间窗口内的请求总数、异常数、总耗时。也就是说：MetricBucket 包含一个 LongAdder 数组，数组的每个元素代表一类 MetricEvent。
LongAdder 保证了数据修改的原子性，并且性能比 AtomicLong 表现更好。

public enum MetricEvent {
    PASS,
    BLOCK,
    EXCEPTION,
    SUCCESS,
    RT,
    OCCUPIED_PASS
}

当需要获取 Bucket 记录总的成功请求数或者异常总数、总的请求处理耗时，可根据事件类型 (MetricEvent) 从 Bucket 的 LongAdder 数组中获取对应的 LongAdder，并调用 sum 方法获取总数。

public long get(MetricEvent event) {
    return counters[event.ordinal()].sum();
}

当需要 Bucket 记录一个成功请求或者一个异常请求、处理请求的耗时，可根据事件类型（MetricEvent）从 LongAdder 数组中获取对应的 LongAdder，并调用其 add 方法。

public void add(MetricEvent event, long n) {
     counters[event.ordinal()].add(n);
}

WindowWrap 源码

因为 Bucket 自身并不保存时间窗口信息，所以 Sentinel 给 Bucket 加了一个包装类 WindowWrap。
Bucket 用于统计各项指标数据，WindowWrap 用于记录 Bucket 的时间窗口信息（窗口的开始时间、窗口的大小），WindowWrap 数组就是一个滑动窗口。

public class WindowWrap<T> {
    /**
     * 单个窗口的时间长度（毫秒）
     */
    private final long windowLengthInMs;
    /**
     * 窗口的开始时间戳（毫秒）
     */
    private long windowStart;
    /**
     * 统计数据
     */
    private T value;
}

总的来说：

WindowWrap 用于包装 Bucket，随着 Bucket 一起创建。
WindowWrap 数组实现滑动窗口，Bucket 只负责统计各项指标数据，WindowWrap 用于记录 Bucket 的时间窗口信息。
定位 Bucket 实际上是定位 WindowWrap，拿到 WindowWrap 就能拿到 Bucket。

滑动窗口统计源码实现

如果我们希望能够知道某个接口的每秒处理成功请求数（成功 QPS）、每秒处理失败请求数（失败 QPS），以及处理每个成功请求的平均耗时（avg RT），注意这里我们只需要控制 Bucket 统计一秒钟的指标数据即可，但如何才能确保 Bucket 存储的就是精确到 1 秒内的数据呢？

Sentinel 是这样实现的：定义一个 Bucket 数组，根据时间戳来定位到数组的下标。

由于只需要保存最近一分钟的数据。那么 Bucket 数组的大小就可以设置为 60，每个 Bucket 的 windowLengthInMs（窗口时间）大小就是 1 秒。

内存资源是有限的，而这个数组可以循环使用，并且永远只保存最近 1 分钟的数据，这样可以避免频繁的创建 Bucket，减少内存资源的占用。

那如何定位 Bucket 呢？我们只需要将当前时间戳减去毫秒部分，得到当前的秒数，再将得到的秒数与数组长度取余数，就能得到当前时间窗口的 Bucket 在数组中的位置（索引）。

calculateTimeIdx 方法中，取余数就是实现循环利用数组。

如果想要获取连续的一分钟的 Bucket 数据，就不能简单的从头开始遍历数组，而是指定一个开始时间和结束时间，从开始时间戳开始计算 Bucket 存放在数组中的下标，然后循环每次将开始时间戳加上 1 秒，直到开始时间等于结束时间。

private int calculateTimeIdx(long timeMillis) {
    long timeId = timeMillis / windowLengthInMs;
    return (int)(timeId % array.length());
}

由于循环使用的问题，当前时间戳与一分钟之前的时间戳和一分钟之后的时间戳都会映射到数组中的同一个 Bucket，

因此，必须要能够判断取得的 Bucket 是否是统计当前时间窗口内的指标数据，这便要数组每个元素都存储 Bucket 时间窗口的开始时间戳。

比如当前时间戳是 1577017626812，Bucket 统计一秒的数据，将时间戳的毫秒部分全部替换为 0，就能得到 Bucket 时间窗口的开始时间戳为 1577017626000。

//计算时间窗口开始时间戳
protected long calculateWindowStart(long timeMillis) {
    return timeMillis - timeMillis % windowLengthInMs;
}

//判断时间戳是否在当前时间窗口内
public boolean isTimeInWindow(long timeMillis) {
    return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}

如何定位 Bucket?

通过时间戳定位 Bucket的。

当接收到一个请求时，可根据接收到请求的时间戳计算出一个数组索引，从滑动窗口（WindowWrap 数组）中获取一个 WindowWrap，从而获取 WindowWrap 包装的 Bucket，调用 Bucket 的 add 方法记录相应的事件。

/**
 * 根据时间戳获取 bucket
 * @param timeMillis 时间戳（毫秒）
 * @return 如果时间有效，则在提供的时间戳处显示当前存储桶项；如果时间无效，则为空
 */
public WindowWrap<T> currentWindow(long timeMillis) {
    if (timeMillis < 0) {
        return null;
    }
    // 获取时间戳映射到的数组索引
    int idx = calculateTimeIdx(timeMillis);
    // 计算 bucket 时间窗口的开始时间
    long windowStart = calculateWindowStart(timeMillis);

    // 从数组中死循环查找当前的时间窗口，因为可能多个线程都在获取当前时间窗口
    while (true) {
        WindowWrap<T> old = array.get(idx);
        // 一般是项目启动时，时间未到达一个周期，数组还没有存储满，没有到复用阶段，所以数组元素可能为空
        if (old == null) {
            // 创建新的 bucket，并创建一个 bucket 包装器
            WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            // cas 写入，确保线程安全，期望数组下标的元素是空的，否则就不写入，而是复用
            if (array.compareAndSet(idx, null, window)) {
                return window;
            } else {
                Thread.yield();
            }
        }
        // 如果 WindowWrap 的 windowStart 正好是当前时间戳计算出的时间窗口的开始时间，则就是我们想要的 bucket
        else if (windowStart == old.windowStart()) {
            return old;
        }
        // 复用旧的 bucket
        else if (windowStart > old.windowStart()) {
            if (updateLock.tryLock()) {
                try {
                    // 重置 bucket，并指定 bucket 的新时间窗口的开始时间
                    return resetWindowTo(old, windowStart);
                } finally {
                    updateLock.unlock();
                }
            } else {
                Thread.yield();
            }
        }
        // 计算出来的当前 bucket 时间窗口的开始时间比数组当前存储的 bucket 的时间窗口开始时间还小，
        // 直接返回一个空的 bucket 就行
        else if (windowStart < old.windowStart()) {
            return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        }
    }
}

上面代码的实现是：通过当前时间戳计算出当前时间窗口的 (new) Bucket 在数组中的索引，通过索引从数组中取得 (old) Bucket；并计算 (new) Bucket 时间窗口的开始时间，与 (old) Bucket 时间窗口的开始时间作对比。

如果旧的 bucket 不存在，那么我们在 windowStart 处创建一个新的 bucket，然后尝试通过 CAS 操作更新环形数组。只有一个线程可以成功更新，保证原子性。
如果当前 windowStart 等于旧桶的开始时间戳，表示时间在桶内，所以直接返回桶。
如果旧桶的开始时间戳落后于所提供的时间，这意味着桶已弃用，我们可以复用该桶，并将桶重置为当前的 windowStart。注意重置和清理操作很难是原子的，所以我们需要一个更新锁来保证桶更新的正确性。只有当 bucket 已弃用才会上锁，所以在大多数情况下它不会导致性能损失。
不应该通过这里，因为提供的时间已经落后了，一般是时钟回拨导致的。

有关Sentinel的系统化知识，请参见尼恩写的5W字PDF 《Sentinel学习圣经》

目录如下：

《Sentinel 学习圣经》 PDF 目录

Sentinel 相关面试真题
尼恩说在前面
说在最后： “offer自由” 很容易的
美团面试：Sentinel底层滑动时间窗限流算法怎么实现的？
- 滑动窗口的核心数据结构
  - ArrayMetric 源码
  - LeapArray 源码
  - MetricBucket 源码
  - WindowWrap 源码
- 滑动窗口统计源码实现
  - 如何定位 Bucket?
《尼恩学习圣经系列PDF》内容、目标、意义
《sentinel 学习圣经》说明：
- hystrix 服务保护
- Sentinel 服务保护
《Sentinel 学习圣经》版本升级说明
开始《sentinel 学习圣经》：一组核心基本概念
- 1. 响应时间(RT)
- 1. 吞吐量(Throughput)
- 1. 并发用户数
什么是服务雪崩效应？
1、什么是Sentinel:
- Sentinel 具有以下特征
- Sentinel主要特性：
  - Sentinel与Hystrix的区别
  - Hystrix 迁移Sentinel 方案
- sentinel组件介绍
  - Sentinel两个部分
  - sentinel 核心概念
- Sentinel 的使用
- Sentinel中的管理控制台
  - 1）获取 Sentinel 控制台
  - 2）sentinel服务启动
    - 启动 sentinel
    - 控制台端口：
    - 控制台登录
    - 启动日志
- Sentinel 控制台使用
  - 默认用户名和密码都是 sentinel
  - 查看机器列表以及健康情况
- SpringCloud客户端能接入控制台
2、使用 Sentinel 来进行熔断与限流
- 2.1 Java普通应用限流
  - 1. 引入 Sentinel 依赖
  - 1. 定义资源
  - 1. 定义规则
  - 1. 检查效果
  - 1. 接入控制台
- 2.1 定义资源
  - 资源注解@SentinelResource
  - @SentinelResource 注解
    - fallback 函数签名和位置要求
    - defaultFallback 函数签名要求
- 2.3 定义规则
3、sentinel 熔断降级
- 3.1 什么是熔断降级
- 3.2 熔断降级规则
- 3.3 几种降级策略
- 3.4 熔断降级代码实现
- 3.5 控制台降级规则
- 3.6 与Hystrix的熔断对比
4、Sentinel 流控（限流）
- 基本的参数
- 流控的几种strategy
- 4.1 直接失败模式
  - 使用API进行资源定义
  - 代码限流规则
  - 网页限流规则配置
  - 测试
- 4.2 关联模式
  - 使用注解进行资源定义
  - 代码配置关联限流规则
  - 网页限流规则配置
  - 测试
- 4.3 Warm up（预热）模式
  - 使用注解定义资源
  - 代码预热规则
  - 网页预热规则配置
- 4.4 排队等待模式
  - 示例
  - 使用注解定义资源
  - 代码限流规则
  - 网页限流规则配置
  - 通过jmeter进行测试
- 4.5 热点规则 (ParamFlowRule)
  - 自定义资源
  - 限流规则代码：
  - 网页限流规则配置
5、Sentinel 系统保护
- - 系统保护的目的
  - 系统保护规则的应用
  - 网页限流规则配置
6、黑白名单规则
- 访问控制规则 (AuthorityRule)
7、如何定义资源
- 方式一：主流框架的默认适配
- 方式二：抛出异常的方式定义资源
- 方式三：返回布尔值方式定义资源
- 方式四：注解方式定义资源
- 方式五：异步调用支持
8、核心组件源码分析
- Resource
- Context
  - Context的创建与销毁
- Entry
- DefaultNode
- StatisticNode
9、插槽Slot 源码分析
- Sentinel中的责任链模式
- 责任链SlotChain 如何创建？
- 责任链模式的重要性
- NodeSelectorSlot 原理分析+ 源码分析
  - 核心的概念1: Resource
  - 核心的概念2: Context
  - 核心的概念3: Entry
  - 核心的概念4: Node
- 调用链树
  - 构造树干
    - 创建context
    - 创建Entry
    - 退出Entry
  - 构造叶子节点
  - 保存子节点
- ClusterBuilderSlot
- StatistcSlot
- SystemSlot
- AuthoritySlot
- FlowSlot
- DegradeSlot
- DefaultProcessorSlotChain
- slot总结
10、sentinel滑动窗口 sliding window 源码分析
- 10.1 基本原理
- 10.2 sentinel使用滑动窗口都统计啥
- 10.3 滑动窗口源码实现
  - 3.1 MetricBucket 源码分析
  - 3.2 WindowWrap 源码分析
  - 3.3 LeapArray 源码分析
11、使用Nacos存储规则及双向同步
- 1、Sentinel 动态规则扩展
- 2、规则管理及推送
- 3、DataSource 扩展
- DataSource(接口)
  - 1、导入依赖
  - 2、配置
  - 3、Nacos中创建限流规则的配置
12、Nacos与Sentinel互相同步限流规则
- 1、流控推送规则
- 2、改造sentinel-dashboard
13、Sentinel+nacos实现集群限流
- 使用集群的方式设置限流规则
- 集群限流使用场景
- 集群架构示意图
- 建立 sentinel-token-sever
- 进行客户端的限流参数上报
- 未完待续…
作者介绍
技术自由的实现路径 PDF
- 实现你的架构自由
- 实现你的响应式自由
- 实现你的 spring cloud 自由
- 实现你的 linux 自由
- 实现你的网络自由
- 实现你的分布式锁自由
- 实现你的王者组件自由
- 实现你的面试题自由
获11个技术圣经 PDF