令牌桶算法与Guava的实现RateLimiter源码分析

这篇具有很好参考价值的文章主要介绍了令牌桶算法与Guava的实现RateLimiter源码分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

令牌桶RateLimiter

简介

令牌桶算法是一种限流算法。

令牌桶算法的原理就是以一个恒定的速度往桶里放入令牌,每一个请求的处理都需要从桶里先获取一个令牌,当桶里没有令牌时,则请求不会被处理,要么排队等待,要么降级处理,要么直接拒绝服务。当桶里令牌满时,新添加的令牌会被丢弃或拒绝。

令牌桶算法与Guava的实现RateLimiter源码分析,算法,guava

令牌桶算法主要是可以控制请求的平均处理速率,它允许预消费,即可以提前消费令牌,以应对突发请求,但是后面的请求需要为预消费买单(等待更长的时间),以满足请求处理的平均速率是一定的。

RateLimiter使用示例

导入maven依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

编写测试代码

public class RateLimiterTest {
    public void limit() {
        // 创建一个限流器,设置每秒放置的令牌数为1个
        RateLimiter rateLimiter = RateLimiter.create(1);
        IntStream.range(1, 10).forEach(i -> {
            // 一次获取i个令牌
            double waitTime = rateLimiter.acquire(i);
            System.out.println("acquire:" + i + " waitTime:" + waitTime);
        });
    }

    public static void main(String[] args) {
        RateLimiterTest rateLimiterTest = new RateLimiterTest();
        rateLimiterTest.limit();
    }
}

这段代码创建一个限流器,设置每秒放置的令牌数为1个,并循环获取令牌,每次获取i个。
执行结果:
令牌桶算法与Guava的实现RateLimiter源码分析,算法,guava
第一次获取一个令牌时,等待0s立即可获取到(这里之所以不需要等待是因为令牌桶的预消费特性),第二次获取两个令牌,等待时间1s,这个1s就是前面获取一个令牌时因为预消费没有等待延到这次来等待的时间,这次获取两个又是预消费,所以下一次获取(取3个时)就要等待这次预消费需要的2s了,依此类推。可见预消费不需要等待的时间都由下一次来买单,以保障一定的平均处理速率(上例为1s一次)。

RateLimiter的实现

RateLimiter类在guava里是一个抽象类,其有两个具体实现:

  1. SmoothBursty(平滑突发):以恒定的速率生成令牌。
  2. SmoothWarmingUp(顺利热身):令牌生成的速度逐渐提升,直到达到一个稳定的值。

其类图如下:
令牌桶算法与Guava的实现RateLimiter源码分析,算法,guava
他们的关系与作用:

  • RateLimiter是顶层封装,提供新建令牌桶的方法
  • SleepingStopwatch是guava实现的一个时钟类,提供时钟功能
  • SmoothRateLimiter是令牌桶抽象,提供操作令牌桶的抽象方法,其有两个内部类SmoothBursty和SmoothWarmingUp
  • SmoothBursty是恒定速率令牌桶实现
  • SmoothWarmingUp是逐渐加速知道稳定的令牌桶实现

源码解析

SmoothRateLimiter

SmoothRateLimiter是令牌桶抽象,其有四个关键的属性:

/** 当前存储的许可证。 */
double storedPermits;

/** 存储许可证的最大数量。 */
double maxPermits;

/**
 * 两个单位请求之间的间隔,以我们的稳定速率。
 * 例如,每秒 5 个许可的稳定速率具有 200 毫秒的稳定间隔。
 */
double stableIntervalMicros;

/**
 * 授予下一个请求(无论其大小如何)的时间。
 * 在批准请求后,这将在将来进一步推送。大请求比小请求更进一步。
 */
private long nextFreeTicketMicros = 0L; // could be either in the past or future

他们的作用可以看注释。此外还有两个内部类,实现此抽象:

  1. SmoothBursty(平滑突发):以恒定的速率生成令牌。
  2. SmoothWarmingUp(顺利热身):令牌生成的速度逐渐提升,直到达到一个稳定的值。

SmoothBursty恒速

首先来看下恒定速率生成令牌的实现。其使用方法是:

// 创建一个限流器,设置每秒放置的令牌数为1个
RateLimiter rateLimiter = RateLimiter.create(1);

RateLimiter#create:

public static RateLimiter create(double permitsPerSecond) {
  /*
   * The default RateLimiter configuration can save the unused permits of up to one second. This
   * is to avoid unnecessary stalls in situations like this: A RateLimiter of 1qps, and 4 threads,
   * all calling acquire() at these moments:
   *
   * T0 at 0 seconds
   * T1 at 1.05 seconds
   * T2 at 2 seconds
   * T3 at 3 seconds
   *
   * Due to the slight delay of T1, T2 would have to sleep till 2.05 seconds, and T3 would also
   * have to sleep till 3.05 seconds.
   */
  return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
}
static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
}

实际是创建了一个SmoothBursty实例,默认的maxBurstSeconds是1,其中SleepingStopwatch是guava实现的一个时钟类。
代码第三行调用了RateLimiter#setRate:

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

abstract void doSetRate(double permitsPerSecond, long nowMicros);

方法签名为:更新此 RateLimiter的稳定速率, permitsPerSecond 即构造 RateLimiter的工厂方法中提供的参数。当前受限制的 线程不会因此 调用而被唤醒,因此它们不会遵守新的速率,只有后续请求才会。
但请注意,由于每个请求都会偿还(如有必要,通过等待)前一个请求的成本,这意味着调用setRate后的下一个请求将不受新速率的影响,它将支付前一个请求的成本,这是根据以前的速率计算的。

此方法调用了抽象方法doSetRate,这里的实现是SmoothRateLimiter提供的,来看SmoothRateLimiter#doSetRate源码:

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

此方法:

  1. 调用 resync(nowMicros) 对 storedPermits 与 nextFreeTicketMicros 进行了调整——如果当前时间晚于 nextFreeTicketMicros,则计算这段时间内产生的令牌数,累加到 storedPermits 上,并更新下次可获取令牌时间 nextFreeTicketMicros 为当前时间。
  2. 计算stableIntervalMicros的值,此值代表产生令牌的时间间隔,1/permitsPerSecond(每秒几个令牌)
  3. 调用doSetRate(double, double)

其将输入的permitsPerSecond转换为速度,传给SmoothRateLimiter的doSetRate(permitsPerSecond, stableIntervalMicros)方法,doSetRate(permitsPerSecond, stableIntervalMicros)方法是抽象方法

abstract void doSetRate(double permitsPerSecond, double stableIntervalMicros);

由SmoothBursty的实现为:

@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
    double oldMaxPermits = this.maxPermits;
    maxPermits = maxBurstSeconds * permitsPerSecond;
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        // if we don't special-case this, we would get storedPermits == NaN, below
        storedPermits = maxPermits;
    } else {
        storedPermits =
        (oldMaxPermits == 0.0)
        ? 0.0 // initial state
        : storedPermits * maxPermits / oldMaxPermits;
    }
}

此方法计算maxPermits的值maxBurstSeconds * permitsPerSecond。maxBurstSeconds是new SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds)构造方法传进来的,这里离默认是1。

获取令牌

acquire(int)

acquire(int)方法在获取不到令牌时阻塞等待,直到获取到令牌。
获取令牌方法为RateLimiter#acquire(int):

// 从中 RateLimiter获取给定数量的令牌,阻塞直到请求可以被批准。告诉睡眠时间(如果有)
@CanIgnoreReturnValue
public double acquire(int permits) {
  long microsToWait = reserve(permits);
  stopwatch.sleepMicrosUninterruptibly(microsToWait);
  return 1.0 * microsToWait / SECONDS.toMicros(1L);
}

调用RateLimiter#reserve 获取需要等待的时间:

// RateLimiter 保留给定数量的令牌以供将来使用,并返回使用这些令牌需要等待的微秒数。
final long reserve(int permits) {
  checkPermits(permits);
  synchronized (mutex()) {
    return reserveAndGetWaitLength(permits, stopwatch.readMicros());
  }
}

调用RateLimiter#reserveAndGetWaitLength:

//	保留令牌并返回使用者需要等待的时间。
final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
    return max(momentAvailable - nowMicros, 0);
}

调用RateLimiter#reserveEarliestAvailable:

abstract long reserveEarliestAvailable(int permits, long nowMicros);

是抽象方法,具体实现为SmoothRateLimiter#reserveEarliestAvailable:

// 更新下次可取令牌时间点与存储的令牌数,返回本次可取令牌的时间点
@Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros); // 如果nextFreeTicket小于当前时间,更新当前存储的令牌数,和下次可使用令牌的时间为now
    // nextFreeTicketMicros表示下一个可以分配令牌的时间点,这个值返回后,
    // 上一层的函数会调用stopwatch.sleepMicrosUninterruptibly(microsToWait);
    // 即阻塞到这个分配的时间点
    long returnValue = nextFreeTicketMicros;
    // 本次需要用掉的令牌数,取本次需要的和当前可以使用的令牌数的最小值
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    // 需要用的令牌大于暂存的令牌数,计算需要新增的令牌数
    double freshPermits = requiredPermits - storedPermitsToSpend;
    // 计算补齐需要新增的令牌需要等待的时间
    long waitMicros =
    	storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
    	+ (long) (freshPermits * stableIntervalMicros);

    // 将下一个可分配令牌的时间点向后移动!!!!这里是实现与消费的关键
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    // 更新当前存储的令牌数
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
}
// 如果nextFreeTicket小于当前时间,更新当前存储的令牌数,和下次可使用令牌的时间为now
void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    if (nowMicros > nextFreeTicketMicros) {
        double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
        storedPermits = min(maxPermits, storedPermits + newPermits);
        nextFreeTicketMicros = nowMicros;
    }
}

上面是获取令牌的关键方法:

tryAcquire(int,long,TimeUnit)

指定时间内尝试获取令牌,获取到或获取超时返回。

public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
    // 将timeout换算成微秒
    long timeoutMicros = max(unit.toMicros(timeout), 0);
    checkPermits(permits);
    long microsToWait;
    synchronized (mutex()) {
        long nowMicros = stopwatch.readMicros();
        // 判断是否可以在timeoutMicros时间范围内获取令牌
        if (!canAcquire(nowMicros, timeoutMicros)) {
            return false;
        } else {
            // 获取令牌,并返回需要等待的毫秒数
            microsToWait = reserveAndGetWaitLength(permits, nowMicros);
        }
    }
    // 等待microsToWait时间
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return true;
}

private boolean canAcquire(long nowMicros, long timeoutMicros) {
    return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;
}

// 返回可用令牌的最早时间
abstract long queryEarliestAvailable(long nowMicros);

// SmoothRateLimiter#queryEarliestAvailable
final long queryEarliestAvailable(long nowMicros) {
	// 授予下一个请求(无论其大小如何)的时间
	return nextFreeTicketMicros;
}

该方法执行下面三步:

  1. 判断能否在指定超时时间内获取到令牌,通过 nextFreeTicketMicros <= nowMicros + timeoutMicros 是否为true来判断,即当前时间+超时时间 在可取令牌时间 之后,则可取(预消费的特性),否则不可获取。
  2. 如果不可获取,立即返回false。
  3. 如果可获取,则调用 reserveAndGetWaitLength(permits, nowMicros) 来更新下次可取令牌时间点与当前存储的令牌数,返回等待时间(逻辑与acquire(int)相同),并阻塞等待相应的时间,返回true。

存量桶系数

令牌桶算法中,多余的令牌会放到桶里。这个桶的容量是有上限的,决定这个容量的就是存量桶系数,默认为 1.0,即默认存量桶的容量是 1.0 倍的限流值。推荐设置 0.6~1.5 之间。
存量桶系数的影响有两方面:

  • 突发流量第一个周期放过的请求数。如存量桶系数等于 0.6,第一个周期最多放过 1.6 倍限流值的请求数。
  • 影响误杀率。存量桶系数越大,越能容忍流量不均衡问题。误杀率:服务限流是对单机进行限流,线上场景经常会用单机限流模拟集群限流。由于机器之间的秒级流量不够均衡,所以很容易出现误限。例如两台服务器,总限流值 20,每台限流 10,某一秒两台服务器的流量分别是 5、15,这时其中一台就限流了 5 个请求。减小误杀率的两个办法:
    • 拉长限流周期。
    • 使用令牌桶算法,并且调出较好的存量桶系数。

小结

RateLimiter 令牌桶的实现并不是起一个线程不断往桶里放令牌,而是以一种延迟计算的方式(参考resync函数),在每次获取令牌之前计算该段时间内可以产生多少令牌,将产生的令牌加入令牌桶中并更新数据来实现,比起一个线程来不断往桶里放令牌高效得多。(想想如果需要针对每个用户限制某个接口的访问,则针对每个用户都得创建一个RateLimiter,并起一个线程来控制令牌存放的话,如果在线用户数有几十上百万,起线程来控制是一件多么恐怖的事情)

优缺点

优点:

  • 放过的流量比较均匀,有利于保护系统。
  • 存量令牌能应对突发流量,很多时候,我们希望能放过脉冲流量。而对于持续的高流量,后面又能均匀地放过不超过限流值的请求数。

缺点:

  • 存量令牌没有过期时间,突发流量时第一个周期会多放过一些请求,可解释性差。即在突发流量的第一个周期,默认最多会放过 2 倍限流值的请求数。
  • 实际限流数难以预知,跟请求数和流量分布有关。

与漏桶的区别

  • 令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时,则拒绝新的请求。
  • 漏桶则是按照固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝。
  • 令牌桶限制的是平均流入速率(允许突发请求,只要有令牌就可以处理,支持一次拿3个令牌,或4个令牌), 并允许一定程度的突发流量。
  • 漏桶限制的是常量流出速率(即流出速率是一个固定常量值,比如都是1的速率流出,而不能一次是1,下次又是2) , 从而平滑突发流入速率。
  • 令牌桶允许一定程度的突发,而漏桶主要目的是平滑流入速率。

总结

令牌桶算法是一种单机限流算法,已一定速率向桶中添加令牌,允许突发流量,支持预消费,预消费的等待时间由之后的请求承担。
当QPS小于100时,比较适合使用。文章来源地址https://www.toymoban.com/news/detail-808843.html

到了这里,关于令牌桶算法与Guava的实现RateLimiter源码分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Guava-RateLimiter详解

    简介:  常用的限流算法有漏桶算法和令牌桶算法,guava的RateLimiter使用的是令牌桶算法,也就是以固定的频率向桶中放入令牌,例如一秒钟10枚令牌,实际业务在每次响应请求之前都从桶中获取令牌,只有取到令牌的请求才会被成功响应,获取的方式有两种:阻塞等待令牌或

    2024年02月06日
    浏览(37)
  • com.google.guava:guava 组件安全漏洞及健康分析

    维护者 google组织 许可证类型 Apache-2.0 首次发布 2010 年 4 月 26 日 最新发布时间 2023 年 8 月 1 日 GitHub Star 48189 GitHub Fork 10716 依赖包 28,694 依赖存储库 219,576 Guava 是 Google 的一组核心 Java 库,其中包括新的集合类型(例如 multimap 和 multiset)、不可变集合、图形库以及用于并发、

    2024年02月10日
    浏览(47)
  • SpringBoot利用Guava实现单机app限流访问

    物料准备: 1.引入Guava依赖 2.定义一个限流注解作用于api接口的方法上 3.定义一个切面,对注解标注的方法实现一个限流访问 使用方法,把@RateLimitAspect 注解添加到需要限流的API接口上即可,如 添加到@GetMapping 或 @PostMapping上

    2024年02月11日
    浏览(35)
  • 布隆过滤器四种实现(Java,Guava,hutool,Redisson)

    为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据库中进

    2024年01月16日
    浏览(36)
  • 【Guava笔记01】Guava Cache本地缓存的常用操作方法

    这篇文章,主要介绍Guava Cache本地缓存的常用操作方法。 目录 一、Guava Cache本地缓存 1.1、引入guava依赖 1.2、CacheBuilder类 1.3、Guava-Cache使用案例

    2024年01月23日
    浏览(40)
  • 【Guava】Guava: Google Core Libraries for Java 好用工具类

    Guava是Google的一组核心Java库,其中包括 新的集合类型 (如multimap和multiset) 、 不可变集合 、 图库 ,以及用于 并发、I/O、哈希、缓存、基元、字符串 等的实用程序!它 被广泛用于谷歌内的大多数Java项目,并被许多人广泛使用。 Guava是一种基于开源的Java库 ,Google Guava源于

    2024年02月11日
    浏览(39)
  • Guava Cache 介绍

    Guava 是 Google 提供的一套 Java 工具包,而 Guava Cache 是该工具包中提供的一套完善的 JVM 级别高并发缓存框架;本文主要介绍它的相关功能及基本使用,文中所使用到的软件版本:Java 1.8.0_341、Guava 32.1.3-jre。 缓存在很多情况下非常有用。例如,当某个值的计算或检索代价很高,

    2024年02月05日
    浏览(42)
  • 再见,Guava!再见,Ehcache!

    缓存(Cache)在代码世界中无处不在。从底层的CPU多级缓存,到客户端的页面缓存,处处都存在着缓存的身影。缓存从本质上来说,是一种空间换时间的手段,通过对数据进行一定的空间安排,使得下次进行数据访问时起到加速的效果。 就Java而言,其常用的缓存解决方案有很多

    2024年02月13日
    浏览(34)
  • Guava:Ordering 排序工具

    排序器  Ordering  是 Guava流畅风格比较器  Comparator  的实现,它可以用来为构建复杂的比较器,以完成集合排序的功能。 从实现上说,Ordering 实例就是一个特殊的 Comparator 实例。Ordering 把很多基于 Comparator 的静态方法(如  Collections.max )包装为自己的实例方法(非静态方法

    2024年02月01日
    浏览(36)
  • Google 开源库Guava详解

    Guava 是一组来自Google的核心Java库,包括新的集合类型(如多映射和多集)、不可变集合、图库和并发、I/O、哈希、原语、字符串等实用程序!它广泛用于Google中的大多数Java项目,也被许多其他公司广泛使用。 Guava 开发要求 : JRE风格需要JDK 1.8或更高版本。 如果您需要支持

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包