专栏首页中间件兴趣圈源码分析 RateLimiter SmoothBursty 实现原理(文末附流程图)

源码分析 RateLimiter SmoothBursty 实现原理(文末附流程图)

上篇详细介绍了Sentinel FlowSlot 限流实现原理(文末附流程图与总结)的限流实现机制,但主要介绍的策略限流的快速失败机制,在Sentinel 中除了快速失败,还提供了匀速排队,预热等限流策略,但我发现 Sentinel 的匀速排队、预热机制是基于 guava 的 RateLimiter,为了更加彻底的理解 Sentienl 限流相关的内容,从本文开始先来学习一下 RateLimiter 的相关实现原理。

温馨提示:文章的末尾会总结 SmoothBursty 的核心流程图与实现原理,本文将展示笔者是如何一步一步揭晓其实现原理的方法。

1、RateLimiter 类设计图


  • RateLimiter 限流抽象类,定义限流器的基本接口。
  • SmoothRateLimiter 平滑限流实现器,也是一个抽象类。
  • SmoothWarmingUp 自带预热机制的限流器实现类型。
  • SmoothBursty 适应于突发流量的限流器。

上述类这些属性,在讲解 SmoothBursty、SmoothWarmingUp 时再详细介绍。

温馨提示:可以看看这些类上的注释,先初步了解其设计思想。

2、寻找入口


我们首先从 guava 的测试用例中尝试寻找一下 RateLimiter 的测试类,测试代码如下。

public void testSimple() {
    RateLimiter limiter = RateLimiter.create(stopwatch, 5.0);
    limiter.acquire(); // R0.00, since it's the first request
    limiter.acquire(); // R0.20
    limiter.acquire(); // R0.20
    assertEvents("R0.00", "R0.20", "R0.20");
}

从这里基本可以看出,首先通过 RateLimiter.create 的静态方法创建一个限流器,然后应用程序在执行业务逻辑之前先调研限流器的 acquire 方法申请许可,接下来我们将循着这个流程来探讨其实现思路。

3、探究 SmoothBursty 实现原理


3.1 SmoothBursty 创建流程

从上面的示例来看,应用程序首先通过 RateLimiter 的静态方法创建一个限流器,其代码如下:

RateLimiter#create

static RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond) { // @1
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0);                                  // @2
    rateLimiter.setRate(permitsPerSecond);                                                                    // @3
    return rateLimiter;
}

代码@1:首先先介绍方法的参数:

  • SleepingStopwatch stopwatch 秒表,主要是实现当前从启动开始已消耗的时间,有点类似计算一个操作耗时,实现精度纳秒。
  • double permitsPerSecond 每秒的许可数,即通常我们说的限流TPS。

代码@2:创建 SmoothBursty 对象。

代码@3:调用 setRate API 设置其速率器。

接下来我们对其进行展开。

3.1.1 SmoothBursty 构造函数

SmoothBursty 构造函数

SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
    super(stopwatch);
    this.maxBurstSeconds = maxBurstSeconds;
}

这里主要是为 stopWatch 与 maxBurstSeconds 赋值,其中 maxBurstSeconds 为允许的突发流量的时间,这里默认为 1.0,表示一秒,会影响最大可存储的许可数。

3.1.2 RateLimiter setRate 方法详解

RateLimiter#setRate

public final void setRate(double permitsPerSecond) {
    checkArgument(
        permitsPerSecond > 0.0 && !Double.isNaN(permitsPerSecond), "rate must be positive");
    synchronized (mutex()) { // @1
      doSetRate(permitsPerSecond, stopwatch.readMicros()); // @2
    }
}

代码@1:该方法需要获取该类的监视器,在同步代码块中执行,实现线程安全性。

代码@2:调用 doSetRate 设置速率,将调用其具体实现类 SmoothRateLimiter 的 doSetRate 方法。

SmoothRateLimiter#doSetRate

final void doSetRate(double permitsPerSecond, long nowMicros) { // @1
    resync(nowMicros);   // @2
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;  // @3
    this.stableIntervalMicros = stableIntervalMicros;                                              
    doSetRate(permitsPerSecond, stableIntervalMicros);                                      // @4
}

代码@1:先来介绍一下该方法的参数的含义:

  • double permitsPerSecond 每秒的许可数,即TPS。
  • long nowMicros 系统已运行时间。

代码@2:基于当前时间重置 SmoothRateLimiter 内部的 storedPermits (已存储的许可数量) 与 nextFreeTicketMicros (下一次可以免费获取许可的时间) 值,所谓的免费指的是无需等待就可以获取设定速率的许可,该方法对理解限流许可的产生非常关键,稍后详细介绍。

代码@3:根据 TPS 算出一个稳定的获取1个许可的时间。以一秒发放5个许可,即限速为5TPS,那发放一个许可的世界间隔为 200ms,stableIntervalMicros 变量是以微秒为单位。

代码@4:调用 SmoothRateLimiter 的抽象方法 doSetRate 设置速率,这里会调用 SmoothBursty 的 doSetRate 方法。

在介绍 SmoothBursty 的 doSetRate 方法之前,我们先来看看 resync 方法的实现细节。

SmoothRateLimiter#resync

void resync(long nowMicros) {
    if (nowMicros > nextFreeTicketMicros) {  // @1 
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();  // @2
      storedPermits = min(maxPermits, storedPermits + newPermits);    // @3
      nextFreeTicketMicros = nowMicros;   // @4
    }
}

代码@1:如果当前已启动时间大于 nextFreeTicketMicros(下一次可以免费获取许可的时间),则需要重新计算许可,即又可以向许可池中添加许可。

代码@2:根据当前时间可增加的许可数量,在 SmoothBursty 的 coolDownIntervalMicros 方法返回的就是上文提到的 stableIntervalMicros (发放一个许可所需要的时间),故本次可以增加的许可数的算法也好理解,即用当前时间戳减去 nextFreeTicketMicros 的差值,再除以发送一个许可所需要的时间即可。

代码@3:计算当前可用的许可。

代码@4:更新下一次可增加计算许可的时间。

接下来再继续看 SmoothBursty 的 doSetRate 方法。

SmoothBursty#doSetRate

void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
    double oldMaxPermits = this.maxPermits;
    maxPermits = maxBurstSeconds * permitsPerSecond;
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        storedPermits = maxPermits;
    } else {
        storedPermits =
            (oldMaxPermits == 0.0)
                ? 0.0 // initial state
                : storedPermits * maxPermits / oldMaxPermits;
    }
}

这里主要是初始化 storedPermits 的值,该限速器支持在运行过程中动态改变 permitsPerSecond 的值。

3.2 SmoothBursty acquire 工作流程

RateLimiter 中的 acquire 方法如下:

public double acquire(int permits) {
    long microsToWait = reserve(permits);    // @1
    stopwatch.sleepMicrosUninterruptibly(microsToWait);   // @2
    return 1.0 * microsToWait / SECONDS.toMicros(1L);   // @3
}

代码@1:根据当前剩余的许可与本次申请的许可来判断本次申请需要等待的时长,如果返回0则表示无需等待。

代码@2:如果需要等待的时间不为0,表示触发限速,睡眠指定时间后唤醒。

代码@3:返回本次申请等待的时长。

接下来重点介绍 reserve 方法的实现原理。

RateLimiter#reserve

final long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {  // @1
      return reserveAndGetWaitLength(permits, stopwatch.readMicros()); // @2
    }
}

代码@1:限速器主要维护的重要数据字段( storedPermits ),对其进行维护时都需要先获取锁。

代码@2:调用内部方法 reserveAndGetWaitLength 来计算需要等待时间。

继续跟踪 reserveAndGetWaitLength 方法。

final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);   // @1
    return max(momentAvailable - nowMicros, 0);  // @2
}

代码@1:根据当前拥有的许可数量、当前时间判断待申请许可最早能得到满足的最早时间,用momentAvailable 表示。

代码@2:然后计算 momentAvailable 与 nowMicros 的差值与0做比较,得出需要等待的时间。

继续跟踪 reserveEarliestAvailable方法,该方法在 RateLimiter 中一个抽象方法,具体实现在其子类 SmoothRateLimiter 中。

SmoothRateLimiter#reserveEarliestAvailable

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros);   // @1
    long returnValue = nextFreeTicketMicros;
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits); // @2
    double freshPermits = requiredPermits - storedPermitsToSpend; // @3
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);  // @4

    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);  // @5
    this.storedPermits -= storedPermitsToSpend;    // @6
    return returnValue;
}

代码@1:在尝试申请许可之前,先根据当前时间即发放许可速率更新 storedPermits 与 nextFreeTicketMicros(下一次可以免费获取许可的时间)。

代码@2:计算本次能从 storedPermits 中消耗的许可数量,取需要申请的许可数量与当前可用的许可数量的最小值,用 storedPermitsToSpend 表示。

代码@3:如果需要申请的许可数量( requiredPermits )大于当前剩余许可数量( storedPermits ),则还需要等待新的许可生成,用 freshPermits 表示,即如果该值大于0,则表示本次申请需要阻塞一定时间。

代码@4:计算本次申请需要等待的时间,storedPermitsToWaitTime 方法在 SmoothBursty 的实现中默认返回 0,即 SmoothBursty 的等待时间主要来自按照速率生成 freshPermits 个许可的时间,生成一个许可的时间为 stableIntervalMicros,故需要等待的时长为 freshPermits * stableIntervalMicros。

代码@5:更新 nextFreeTicketMicros 为当前时间加上需要等待的时间。

代码@6:更新 storedPermits 的值,即减少本次已消耗的许可数量。

代码@7:请注意这里返回的 returnValue 的值,并没有包含由于剩余许可需要等待创建新许可的时间,即允许一定的突发流量,故本次计算需要的等待时间将对下一次请求生效,这也是框架作者将该限速器取名为 SmoothBursty 的缘由。

SmoothBursty 的 acquire 方法就介绍到这里了。

4、总结


由于源码分析会显得枯燥与不直观,我们先给出如下流程图:

SmoothBursty 的核心设计思想基本与令牌桶类似,但还是有些不同。基本思想:

  1. SmoothBursty 以指定的速率生成许可,在 SmoothBursty 中用 storedPermits 表示。
  2. 当一个请求需要申请许可时,如果需要申请的许可数小于 storedPermits ,则消耗指定许可,直接返回,无需等待。
  3. 当一个请求需要申请的许可大于 storedPermits 时,则计算需要等待的时间,更新下一次许可可发放时间,直接返回,即当请求消耗掉所有许可后,当前请求并不会阻塞,而是影响下一个请求,即支持突发流量。

本文分享自微信公众号 - 中间件兴趣圈(dingwpmz_zjj),作者:丁威

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 源码分析RateLimiter SmoothWarmingUp 实现原理(文末附流程图)

    上一篇详细介绍了 SmoothBursty 的实现原理,本文将介绍带有预热机制的限速器实现原理。

    丁威
  • 使用Guava RateLimiter限流以及源码解析

    首先通过RateLimiter.create(1);创建一个限流器,参数代表每秒生成的令牌数,通过limiter.acquire(i);来以阻塞的方式获取令牌,...

    用户6182664
  • 面试官:来谈谈限流-RateLimiter源码分析

    RateLimiter有两个实现类:SmoothBursty和SmoothWarmingUp,其都是令牌桶算法的变种实现,区别在于SmoothBursty加令牌...

    李红
  • 面试官:来谈谈限流-RateLimiter源码分析

    RateLimiter有两个实现类:SmoothBursty和SmoothWarmingUp,其都是令牌桶算法的变种实现,区别在于SmoothBursty加令牌...

    李红
  • Guava RateLimiter限流源码解析和实例应用

    Guava有两种限流模式,一种为稳定模式(SmoothBursty:令牌生成速度恒定),一种为渐进模式(SmoothWarmingUp:令牌生成速度缓慢提升直到...

    算法之名
  • 搞懂限流算法这一篇就够了 No.154

    大家都知道,对于高并发的业务场景,我们为了保障服务的稳定,经常会祭出三大利器:缓存、熔断降级和服务限流。

    大蕉
  • 再谈高并发下限流算法的设计

    行业大佬:大蕉,一个有七块腹肌的普通程序员,主要分享与大后端技术栈以及后端成长技术路线相关的方方面面,擅长帮助迷茫的大三大四应届生和职场新人明确校招以及职场道路...

    架构师修行之路
  • RateLimiter没有用到集合,核心是一个时间值

    令牌桶的图,网上到处可见,按图实现也非常简单,无非是定时添加令牌桶,并提供一个获取令牌的函数,博主实现了一遍代码如下:

    温安适
  • 电商系统中的秒杀高并发单机限流实战

    今天,抽空,我给大家介绍一下限流。目前关于限流的框架和工具都比较多,比如 Redis、阿里的 Sentinel、Nginx、OpenResty 等。今天我先给大...

    业余草
  • 高并发之限流,到底限的什么鬼 (精品长文)

    你可能知道高并发系统需要限流这个东西,但具体是限制的什么,该如何去做,还是模凌两可。我们接下来系统性的给它归个小类,希望对你有所帮助。

    xjjdog
  • 超详细的Guava RateLimiter限流原理解析

     限流是保护高并发系统的三把利器之一,另外两个是缓存和降级。限流在很多场景中用来限制并发和请求量,比如说秒杀抢购,保护自身系统和下游系统不被巨型流量冲垮等。

    程序员历小冰
  • 源码分析 Kafka 消息发送流程(文末附流程图)

    从上文 初识 Kafka Producer 生产者,可以通过 KafkaProducer 的 send 方法发送消息,send 方法的声明如下:

    丁威
  • 慌了,居然被问到怎么做高并发系统的限流

    在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。本文结合作者的一些经验介绍限流的相关概念、算法和常规的实现方式。

    zhisheng
  • 高并发之 API 接口,分布式,防刷限流,如何做?

    降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高峰或者问题解决后再打开

    芋道源码
  • 高并发之限流

    在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。本文结合作者的一些经验介绍限流的相关概念、算法和常规的实现方式。

    lyb-geek
  • 一篇文章弄懂限流怎么做

    限流是保护高并发系统的三把利器(限流、缓存、降级)之一。限流在很多场景中用来限制并发和请求量,保护自身系统和下游系统不被巨型流量冲垮。比如秒杀业务或者一些访问量...

    Criss@陈磊
  • 一篇文章弄懂限流怎么做

    限流是保护高并发系统的三把利器(限流、缓存、降级)之一。限流在很多场景中用来限制并发和请求量,保护自身系统和下游系统不被巨型流量冲垮。比如秒杀业务或者一些访问量...

    普通程序员
  • Google平滑限流方案——Guava

    ·acceptCount:如果Tomcat的线程都忙于响应,新来的连接会进入队列排队,如果超出排队大小,则拒绝连接

    黑洞代码
  • 源码分析Kafka 消息拉取流程(文末两张流程图)

    代码@1:参数为超时时间,使用 java 的 Duration 来定义。 代码@2:调用内部的 poll 方法。

    丁威

扫码关注云+社区

领取腾讯云代金券