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

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

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

本篇最大的亮点并不是简单对SmoothWarmingUp上的注释进行翻译,而是进行总结与提炼。

1、类图


从上文也详细介绍了 RateLimiter 相关的类图,本文就不详细介绍。

2、SmoothWarmingUp 创建流程


创建 SmoothWarmingUp 限速器的入口为 RateLimiter 的 create 方法,其代码如下: RateLimiter#create

public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {  // @1
    checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
    return create(
        SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit, 3.0);
}

代码@1:首先先来看一下参数列表:

  • double permitsPerSecond 每秒发放许可数量,即所谓的QPS。
  • long warmupPeriod 设置预热时间。
  • TimeUnit unit warmupPeriod 的时间单位。

代码@2:调用内部的重载方法创建 SmoothWarmingUp 。

RateLimiter#create

static RateLimiter create( SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit, double coldFactor) {
    RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit, coldFactor);  // @1
    rateLimiter.setRate(permitsPerSecond); // @2
    return rateLimiter;
}

创建 SmoothWarmingUp 两个主要步骤分别是调用其构造方法首先创建 SmoothWarmingUp 实例,然后调用其 setRate 方法进行初始化速率。这里先突出 coldFactor,默认为 3.0,该属性的作用将在下文详细介绍。

我们先来重点探讨一下 setRate 方法的实现。最终会调用其父类 SmoothRateLimiter 的doSetRate 方法。

SmoothRateLimiter#doSetRate

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

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

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

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

在介绍 SmoothWarmingUp 的 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:根据当前时间可增加的许可数量,由于 SmoothWarmingUp 实现了预热机制,平均生成一个许可的时间并不是固定不变的。具体由 coolDownIntervalMicros 方法实现,稍候详细介绍。

代码@3:计算当前可用的许可,将新增的这些许可添加到许可池,但不会超过其最大值。

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

SmoothWarmingUp#coolDownIntervalMicros

double coolDownIntervalMicros() {
    return warmupPeriodMicros / maxPermits;
}

这个方法的实现其实简单,用生成这些许可的总时间除以现在已经生成的许可数,即可得到当前时间点平均一个许可的生成时间。

接下来重点探讨 SmoothWarmingUp 的 doSetRate 方法。 为了方便理解 SmoothWarmingUp doSetRate 方法,我根据 SmoothWarmingUp 类的注释,结合代码,给出如下示例图:

首先我们先来根据 SmoothWarmingUp 的相关注释来理解一下上述这张图的几个要点。

  • 图中有两个阴影面积,一个用 stable,另外一个warm up period。在预热算法中,这两个阴影面积的关系与冷却因子相关。
  • 冷却因子 coldFactor 表示的含义为 coldIntervalMicros 与 stableIntervalMicros 的比值。
  • warm up period 阴影面积 与 stable 阴影面积的比值等于 (coldIntervalMicros - stableIntervalMicros ) / stableIntervalMicros ,例如 SmoothWarmingUp 固定的冷却因子为3,那么 coldIntervalMicros 与 stableIntervalMicros 的比值为 3,那 (coldIntervalMicros - stableIntervalMicros ) / stableIntervalMicros 则为 2。
  • 在预热算法中与数学中的积分相关(笔者对这方面的数学知识一窍不通),故这里只展示结论,而不做推导,阴影 WARM UP PERIOD 的面积等于 warmupPeriod,那阴影stable的面积等于 warmupPeriod/2。
  • 存在如下等式 warmupPeriod/2 = thresholdPermits * stableIntervalMicros (长方形的面积)
  • 同样存在如下等式 warmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits) (梯形面积,(上底 + 下底 * 高 / 2) )

有了上述基本知识,我们再来看一下代码。

SmoothWarmingUp#doSetRate

void doSetRate(double permitsPerSecond, double stableIntervalMicros) { 
    double oldMaxPermits = maxPermits;
    double coldIntervalMicros = stableIntervalMicros * coldFactor;                // @1
    thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;    // @2
    maxPermits =
          thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);   // @3
    slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);  // @4
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        storedPermits = 0.0;
    } else {
        storedPermits =
            (oldMaxPermits == 0.0)
                ? maxPermits // initial state is cold
                : storedPermits * maxPermits / oldMaxPermits;    // @5
    }
}

代码@1:根据冷却因子(coldFactor)来计算冷却间隔(单位为微秒),等于冷却因子与 stableIntervalMicros 的乘积。从这里我们可以得出如下几个基本的概念。冷却因子 coldFactor 为 冷却间隔与稳定间隔的比例。

代码@2:通过 warmupPeriod/2 = thresholdPermits * stableIntervalMicros 等式,求出 thresholdPermits 的值。

代码@3:根据 warmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits) 表示可求出 maxPermits 的数量。

代码@4:斜率,表示的是从 stableIntervalMicros 到 coldIntervalMicros 这段时间,许可数量从 thresholdPermits 变为 maxPermits 的增长速率。

代码@5:根据 maxPermits 更新当前存储的许可,即当前剩余可消耗的许可数量。

3、SmoothWarmingUp acquire 流程


首先 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

inal 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 方法返回的,另外一部分以稳定速率生成需要的许可,其需要时间为 freshPermits * stableIntervalMicros,稍后我们详细分析一下 storedPermitsToWaitTime 方法的实现。

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

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

代码@7:请注意这里返回的 returnValue 的值,并没有包含由于剩余许可需要等待创建新许可的时间,即允许一定的突发流量,故本次计算需要的等待时间将对下一次请求生效。

接下来重点探讨一下 SmoothWarmingUp 的 storedPermitsToWaitTime 方法。

SmoothWarmingUp#SmoothWarmingUp

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  // @1
    double availablePermitsAboveThreshold = storedPermits - thresholdPermits;   // @2
    long micros = 0;
    if (availablePermitsAboveThreshold > 0.0) {  // @3
        double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);  // @31 
                // TODO(cpovirk): Figure out a good name for this variable.
                double length = permitsToTime(availablePermitsAboveThreshold)
                     + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake);             // @32
                micros = (long) (permitsAboveThresholdToTake * length / 2.0);                                                      // @33
                permitsToTake -= permitsAboveThresholdToTake;                                                                          // @34
         }
        // measuring the integral on the left part of the function (the horizontal line)
        micros += (stableIntervalMicros * permitsToTake);   // @4
        return micros;
}

代码@1:首先介绍其两个参数的含义:

  • double storedPermits 当前存储的许可数量。
  • double permitsToTake 本次申请需要的许可数量。

代码@2:availablePermitsAboveThreshold ,当前超出 thresholdPermits 的许可个数,如果超过 thresholdPermits ,申请许可将来源于超过的部分,只有其不足后,才会从 thresholdPermits 中申请,这部分的详细逻辑见代码@3。

代码@3:如果当前存储的许可数量超过了稳定许可 thresholdPermits,即存在预热的许可数量的申请逻辑,其实现关键点如下:

  • 获取本次从预热区间申请的许可数量。
  • 从预热区间获取一个许可的时间其算法有点晦涩难懂,具体实现为@32~@34。

代码@4:从稳定区间获取一个许可的时间,就容易理解,为固定的 stableIntervalMicros 。

温馨提示:从预热区间计算获取多个许可的算法,与 slope 有关,笔者并未完成感悟(走过路过的朋友如果对这块比较熟悉,欢迎留言探讨),但至少我们需要明白的是,从 剩余许可(storedPermits)中申请许可时,优先消耗(大于thresholdPermits 的许可,即消耗 (thresholdPermits ~ maxPermit ) 之间的许可)。

SmoothWarmingUp 的 acquire 流程就介绍到这里了。

4、总结


SmoothWarmingUp 的 acquire 的流程与 SmoothBursty 类似,故其流程图与下图通用,主要的区别生成一个许可的时间有变化,主要是提供了预热机制。

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    上篇详细介绍了Sentinel FlowSlot 限流实现原理(文末附流程图与总结)的限流实现机制,但主要介绍的策略限流的快速失败机制,在Sentinel 中除...

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

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

    程序员历小冰
  • 搞懂限流算法这一篇就够了 No.154

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

    大蕉
  • 电商系统中的秒杀高并发单机限流实战

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

    业余草
  • 再谈高并发下限流算法的设计

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

    架构师修行之路
  • 面试官:来谈谈限流-RateLimiter源码分析

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

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

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

    李红
  • RateLimiter没有用到集合,核心是一个时间值

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

    温安适
  • 源码分析 Kafka 消息发送流程(文末附流程图)

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

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

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

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

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

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

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

    芋道源码
  • 高并发之限流

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

    lyb-geek
  • Guava RateLimiter限流源码解析和实例应用

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

    算法之名
  • 一篇文章弄懂限流怎么做

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

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

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

    普通程序员
  • 源码分析Kafka 消息拉取流程(文末两张流程图)

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

    丁威
  • 结合 Sentinel 专栏谈谈我的源码阅读方法

    Sentinel 系列共包含15篇文章,主要以源码分析为手段,图文并茂的方式对 Sentinel 的架构设计理念、核心实现要点进行了一一剖析,并加以实战分析与思...

    丁威
  • Google平滑限流方案——Guava

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

    黑洞代码

扫码关注云+社区

领取腾讯云代金券