极客时间已完结课程限时免费阅读

38 | 案例分析（一）：高性能限流器Guava RateLimiter

38 | 案例分析（一）：高性能限流器Guava RateLimiter-极客时间

38 | 案例分析（一）：高性能限流器Guava RateLimiter

2019-05-25 王宝令 来自北京
《Java并发编程实战》
课程介绍

讲述：王宝令

时长09:11大小8.40M

从今天开始，我们就进入案例分析模块了。 这个模块我们将分析四个经典的开源框架，看看它们是如何处理并发问题的，通过这四个案例的学习，相信你会对如何解决并发问题有个更深入的认识。
首先我们来看看 Guava RateLimiter 是如何解决高并发场景下的限流问题的。Guava 是 Google 开源的 Java 类库，提供了一个工具类 RateLimiter。我们先来看看 RateLimiter 的使用，让你对限流有个感官的印象。假设我们有一个线程池，它每秒只能处理两个任务，如果提交的任务过快，可能导致系统不稳定，这个时候就需要用到限流。
在下面的示例代码中，我们创建了一个流速为 2 个请求 / 秒的限流器，这里的流速该怎么理解呢？直观地看，2 个请求 / 秒指的是每秒最多允许 2 个请求通过限流器，其实在 Guava 中，流速还有更深一层的意思：是一种匀速的概念，2 个请求 / 秒等价于 1 个请求 /500 毫秒。
在向线程池提交任务之前，调用 acquire() 方法就能起到限流的作用。通过示例代码的执行结果，任务提交到线程池的时间间隔基本上稳定在 500 毫秒。
//限流器流速：2个请求/秒
RateLimiter limiter =
RateLimiter.create(2.0);
//执行任务的线程池
ExecutorService es = Executors
.newFixedThreadPool(1);
//记录上一次执行时间
prev = System.nanoTime();
//测试执行20次
for (int i=0; i<20; i++){
//限流器限流
limiter.acquire();
//提交任务异步执行
es.execute(()->{
long cur=System.nanoTime();
//打印时间间隔：毫秒
System.out.println(
(cur-prev)/1000_000);
prev = cur;
});
}
输出结果：
...
500
499
499
500
499

经典限流算法：令牌桶算法

Guava 的限流器使用上还是很简单的，那它是如何实现的呢？Guava 采用的是令牌桶算法，其核心是要想通过限流器，必须拿到令牌。也就是说，只要我们能够限制发放令牌的速率，那么就能控制流速了。令牌桶算法的详细描述如下：
令牌以固定的速率添加到令牌桶中，假设限流的速率是 r/ 秒，则令牌每 1/r 秒会添加一个；
假设令牌桶的容量是 b ，如果令牌桶已满，则新的令牌会被丢弃；
请求能够通过限流器的前提是令牌桶中有令牌。
这个算法中，限流的速率 r 还是比较容易理解的，但令牌桶的容量 b 该怎么理解呢？b 其实是 burst 的简写，意义是限流器允许的最大突发流量。比如 b=10，而且令牌桶中的令牌已满，此时限流器允许 10 个请求同时通过限流器，当然只是突发流量而已，这 10 个请求会带走 10 个令牌，所以后续的流量只能按照速率 r 通过限流器。
令牌桶这个算法，如何用 Java 实现呢？很可能你的直觉会告诉你生产者 - 消费者模式：一个生产者线程定时向阻塞队列中添加令牌，而试图通过限流器的线程则作为消费者线程，只有从阻塞队列中获取到令牌，才允许通过限流器。
这个算法看上去非常完美，而且实现起来非常简单，如果并发量不大，这个实现并没有什么问题。可实际情况却是使用限流的场景大部分都是高并发场景，而且系统压力已经临近极限了，此时这个实现就有问题了。问题就出在定时器上，在高并发场景下，当系统压力已经临近极限的时候，定时器的精度误差会非常大，同时定时器本身会创建调度线程，也会对系统的性能产生影响。
那还有什么好的实现方式呢？当然有，Guava 的实现就没有使用定时器，下面我们就来看看它是如何实现的。

Guava 如何实现令牌桶算法

Guava 实现令牌桶算法，用了一个很简单的办法，其关键是记录并动态计算下一令牌发放的时间。下面我们以一个最简单的场景来介绍该算法的执行过程。假设令牌桶的容量为 b=1，限流速率 r = 1 个请求 / 秒，如下图所示，如果当前令牌桶中没有令牌，下一个令牌的发放时间是在第 3 秒，而在第 2 秒的时候有一个线程 T1 请求令牌，此时该如何处理呢？
线程 T1 请求令牌示意图
对于这个请求令牌的线程而言，很显然需要等待 1 秒，因为 1 秒以后（第 3 秒）它就能拿到令牌了。此时需要注意的是，下一个令牌发放的时间也要增加 1 秒，为什么呢？因为第 3 秒发放的令牌已经被线程 T1 预占了。处理之后如下图所示。
线程 T1 请求结束示意图
假设 T1 在预占了第 3 秒的令牌之后，马上又有一个线程 T2 请求令牌，如下图所示。
线程 T2 请求令牌示意图
很显然，由于下一个令牌产生的时间是第 4 秒，所以线程 T2 要等待两秒的时间，才能获取到令牌，同时由于 T2 预占了第 4 秒的令牌，所以下一令牌产生时间还要增加 1 秒，完全处理之后，如下图所示。
线程 T2 请求结束示意图
上面线程 T1、T2 都是在下一令牌产生时间之前请求令牌，如果线程在下一令牌产生时间之后请求令牌会如何呢？假设在线程 T1 请求令牌之后的 5 秒，也就是第 7 秒，线程 T3 请求令牌，如下图所示。
线程 T3 请求令牌示意图
由于在第 5 秒已经产生了一个令牌，所以此时线程 T3 可以直接拿到令牌，而无需等待。在第 7 秒，实际上限流器能够产生 3 个令牌，第 5、6、7 秒各产生一个令牌。由于我们假设令牌桶的容量是 1，所以第 6、7 秒产生的令牌就丢弃了，其实等价地你也可以认为是保留的第 7 秒的令牌，丢弃的第 5、6 秒的令牌，也就是说第 7 秒的令牌被线程 T3 占有了，于是下一令牌的的产生时间应该是第 8 秒，如下图所示。
线程 T3 请求结束示意图
通过上面简要地分析，你会发现，我们只需要记录一个下一令牌产生的时间，并动态更新它，就能够轻松完成限流功能。我们可以将上面的这个算法代码化，示例代码如下所示，依然假设令牌桶的容量是 1。关键是 reserve() 方法，这个方法会为请求令牌的线程预分配令牌，同时返回该线程能够获取令牌的时间。其实现逻辑就是上面提到的：如果线程请求令牌的时间在下一令牌产生时间之后，那么该线程立刻就能够获取令牌；反之，如果请求时间在下一令牌产生时间之前，那么该线程是在下一令牌产生的时间获取令牌。由于此时下一令牌已经被该线程预占，所以下一令牌产生的时间需要加上 1 秒。
class SimpleLimiter {
//下一令牌产生时间
long next = System.nanoTime();
//发放令牌间隔：纳秒
long interval = 1000_000_000;
//预占令牌，返回能够获取令牌的时间
synchronized long reserve(long now){
//请求时间在下一令牌产生时间之后
//重新计算下一令牌产生时间
if (now > next){
//将下一令牌产生时间重置为当前时间
next = now;
}
//能够获取令牌的时间
long at=next;
//设置下一令牌产生时间
next += interval;
//返回线程需要等待的时间
return Math.max(at, 0L);
}
//申请令牌
void acquire() {
//申请令牌时的时间
long now = System.nanoTime();
//预占令牌
long at=reserve(now);
long waitTime=max(at-now, 0);
//按照条件等待
if(waitTime > 0) {
try {
TimeUnit.NANOSECONDS
.sleep(waitTime);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}
如果令牌桶的容量大于 1，又该如何处理呢？按照令牌桶算法，令牌要首先从令牌桶中出，所以我们需要按需计算令牌桶中的数量，当有线程请求令牌时，先从令牌桶中出。具体的代码实现如下所示。我们增加了一个 resync() 方法，在这个方法中，如果线程请求令牌的时间在下一令牌产生时间之后，会重新计算令牌桶中的令牌数，新产生的令牌的计算公式是：(now-next)/interval，你可对照上面的示意图来理解。reserve() 方法中，则增加了先从令牌桶中出令牌的逻辑，不过需要注意的是，如果令牌是从令牌桶中出的，那么 next 就无需增加一个 interval 了。
class SimpleLimiter {
//当前令牌桶中的令牌数量
long storedPermits = 0;
//令牌桶的容量
long maxPermits = 3;
//下一令牌产生时间
long next = System.nanoTime();
//发放令牌间隔：纳秒
long interval = 1000_000_000;
//请求时间在下一令牌产生时间之后,则
// 1.重新计算令牌桶中的令牌数
// 2.将下一个令牌发放时间重置为当前时间
void resync(long now) {
if (now > next) {
//新产生的令牌数
long newPermits=(now-next)/interval;
//新令牌增加到令牌桶
storedPermits=min(maxPermits,
storedPermits + newPermits);
//将下一个令牌发放时间重置为当前时间
next = now;
}
}
//预占令牌，返回能够获取令牌的时间
synchronized long reserve(long now){
resync(now);
//能够获取令牌的时间
long at = next;
//令牌桶中能提供的令牌
long fb=min(1, storedPermits);
//令牌净需求：首先减掉令牌桶中的令牌
long nr = 1 - fb;
//重新计算下一令牌产生时间
next = next + nr*interval;
//重新计算令牌桶中的令牌
this.storedPermits -= fb;
return at;
}
//申请令牌
void acquire() {
//申请令牌时的时间
long now = System.nanoTime();
//预占令牌
long at=reserve(now);
long waitTime=max(at-now, 0);
//按照条件等待
if(waitTime > 0) {
try {
TimeUnit.NANOSECONDS
.sleep(waitTime);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}

总结

经典的限流算法有两个，一个是令牌桶算法（Token Bucket），另一个是漏桶算法（Leaky Bucket）。令牌桶算法是定时向令牌桶发送令牌，请求能够从令牌桶中拿到令牌，然后才能通过限流器；而漏桶算法里，请求就像水一样注入漏桶，漏桶会按照一定的速率自动将水漏掉，只有漏桶里还能注入水的时候，请求才能通过限流器。令牌桶算法和漏桶算法很像一个硬币的正反面，所以你可以参考令牌桶算法的实现来实现漏桶算法。
上面我们介绍了 Guava 是如何实现令牌桶算法的，我们的示例代码是对 Guava RateLimiter 的简化，Guava RateLimiter 扩展了标准的令牌桶算法，比如还能支持预热功能。对于按需加载的缓存来说，预热后缓存能支持 5 万 TPS 的并发，但是在预热前 5 万 TPS 的并发直接就把缓存击垮了，所以如果需要给该缓存限流，限流器也需要支持预热功能，在初始阶段，限制的流速 r 很小，但是动态增长的。预热功能的实现非常复杂，Guava 构建了一个积分函数来解决这个问题，如果你感兴趣，可以继续深入研究。
欢迎在留言区与我分享你的想法，也欢迎你在留言区记录你的思考过程。感谢阅读，如果你觉得这篇文章对你有帮助的话，也欢迎把它分享给更多的朋友。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 36

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
37 | 设计模式模块热点问题答疑
下一篇
39 | 案例分析（二）：高性能网络应用框架Netty
unpreview
 写留言

精选留言(60)

  • null
    2019-08-09
    re：为什么令牌是从令牌桶中出的，那么 next 就无需增加一个 interval？ next 变量的意思是下一个令牌的生成时间，可以理解为当前线程请求的令牌的生成时刻，如第一张图所示：线程 T1 的令牌的生成时刻是第三秒。 线程 T 请求时，存在三种场景： 1. 桶里有剩余令牌。 2. 刚创建令牌，线程同时请求。 3. 桶里无剩余令牌。 场景 2 可以想象成线程请求的同时令牌刚好生成，没来得及放入桶内就被线程 T 拿走了。因此将场景 2 和场景 3 合并成一种情况，那就是桶里没令牌。即线程请求时，桶里可分为有令牌和没令牌。 “桶里没令牌”，线程 T 需要等待；需要等待则意味着 now(线程 T 请求时刻) 小于等于 next(线程 T 所需的令牌的生成时刻)。这里可以想象一下线程 T 在苦苦等待令牌生成的场景，只要线程 T 等待那么久之后，就会被放行。放行这一刻令牌同时生成，立马被线程拿走，令牌没放入桶里。对应到代码就是 resync 方法没有进入 if 语句内。 “桶里有令牌”，线程 T 不需要等待。说明线程 T 对应的令牌已经早早生成，已在桶内。代码就是：now > next（请求时刻大于对应令牌的生成时刻）。因此在分配令牌给线程之前，需要计算线程 T 迟到了多久，迟到的这段时间，有多少个令牌生成¹；然后放入桶内，满了则丢弃²；未来的线程的令牌在这个时刻已经生成放入桶内³（即 resync 方法的逻辑）。线程无需等待，所以不需要增加一个 interval 了。 角标分别对应 resync 方法内的代码： ¹: long newPermits=(now-next)/interval; ²: storedPermits=min(maxPermits, storedPermits + newPermits); ³: next = now;
    展开

    作者回复: 👍条理清晰

    共 6 条评论
    66
  • 花儿少年
    2019-06-18
    很精髓的就是reserve方法，我来试着稍微解释一下 首先肯定是计算令牌桶里面的令牌数量 然后取令牌桶中的令牌数量storedPermits 与当前的需要的令牌数量 1 做比较，大于等于 1，说明令牌桶至少有一个令牌，此时下一令牌的获取是不需要等待的，表现为 next 不需要变化；而当令牌桶中的令牌没有了即storedPermits等于 0 时，next 就会变化为下一个令牌的获取时间，注意 nr 的值变化
    展开

    作者回复: 👍

    共 7 条评论
    24
  • 梦倚栏杆
    2019-12-13
    有个疑问：高并发情况下单独一个线程维护一个队列放令牌，性能上扛不住，那么获取令牌时每次加锁去计算性能就可以抗的主？是根据什么依据来判断性能的呢？

    作者回复: 高并发场景下，CPU忙碌，大概率会出现就绪的线程被积压，对于定时放令牌的线程，其定时器会被大概率的延迟

    共 4 条评论
    19
  • Darren
    2019-05-26
    老师，请教一下，限流器和信号量为什么感觉一样的，那为什么2个还都存在？是因为业务场景不同吗？请老师解惑下

    作者回复: 限流器不需要释放操作，信号量没办法控制带时间范围的限流，只能用于非常简单的场景

    共 2 条评论
    17
  • zsh0103
    2019-05-26
    老师好，问个问题。文中代码b=3，r=1/s时，如果在next之后同时来了3个请求，应该时都可以获得令牌的对吧。就是说这3个请求都可以执行。那岂不是违背了r=1/s的限制吗。

    作者回复: 按照令牌桶算法是这样的，所以b不能搞得太大

    8
  • the geek
    2019-06-04
    老师，当b>1时的reserve方法写的有问题吧，long at = next;不应该是第一行，而应该在// 重新计算下一令牌产生时间 next = next + nr*interval; 这行代码之后吧
    共 5 条评论
    5
  • 辣椒
    2019-06-04
    // 令牌净需求：首先减掉令牌桶中的令牌 long nr = 1 - fb; // 重新计算下一令牌产生时间 next = next + nr*interval; // 重新计算令牌桶中的令牌 this.storedPermits -= fb; 老师这儿没有看懂，能不能解释一下？
    展开
    共 10 条评论
    5
  • 又双叒叕是一年啊
    2019-05-30
    long interval = 1000_000_000; 这是什么写法
    共 2 条评论
    5
  • 侧耳倾听
    2020-04-22
    时间那个其实就是当前请求时间超过上次令牌的取得时间，我就发令牌，令牌满了就不发只取，有空间了继续发，总之就是一秒一个，通过时间差算出，来一个请求就算一次时间，没必要通过定时器去实现
    4
  • 刘鸿博
    2019-08-26
    newPermits, storePermits, fb, nr 都应该是double, 而不是long.

    作者回复: 示例代码只是为了更容易理解，实际应用还是要参考guava的实现

    共 2 条评论
    4
  • 爱吃回锅肉的瘦子
    2019-05-26
    老师，有没什么资料推荐关于guava预热功能呢？主要网上资料太繁杂，不知道要如何甄别哪些是比较经典的

    作者回复: 能把为什么用的是那个积分函数，而不是用其他积分函数讲清楚的，应该是比较好的。最好是看guava的代码注视，写的非常详细。

    4
  • 高源
    2019-05-25
    还有就是老师我问一下因为我不是在互联网公司工作接触高并发场景少，我又喜欢学习研究提高自己，是不是得多看多练，实战

    作者回复: 最好还是找个互联网企业，有些问题只有在很高的并发压力下才会爆发。不过技术没有互联网之分，只要基础牢，成长会很快。多看基础性的东西，一定带着问题去看。

    4
  • 小强（jacky）
    2020-10-14
    老师请教个问题，maxPermits/next 的变量在程序里面，不同线程之间存在依赖关系，这不是数据竞争吗？为啥这里没有加对应的锁？

    作者回复: 主要是通过synchronized关键字搞的

    3
  • 锦
    2019-05-25
    很精彩！老师应该去讲数据结构与算法:)

    作者回复: 何必难为自己呢，不讲了😄

    共 2 条评论
    3
  • 小乙哥
    2021-08-30
    http://ifeve.com/guava-ratelimiter/ RateLimiter的文档翻译，mark一下
    2
  • Happy
    2020-01-05
    老师，经过单元测试后，个人感觉 resync 方法有bug。resync 的功能仅仅是将时间转换为令牌的操作，并更新下一次产生令牌的时间。不消耗令牌。 resync 方法中 //新产生的令牌数 long newPermits = (now - next) / interval; 这一步中，假如 now - next 为 1.9 秒，interval 为1秒，那么除法后，会将 0.9 秒丢弃，长期这种操作，会导致错误越来越多。我这边做了一个补偿操作： long diff = (now - next) % interval; // 将下一个令牌发放时间重置为当前时间 next = now - diff; 单元测试在 https://github.com/1996fanrui/fanrui-learning/blob/755cb85bfc84981ba3a0309cc4fee91035e7ee25/module-juc/src/test/java/com/dream/juc/ratelimiter/RateLimiterTest.java 虽然课程早就结束了，但还是非常期待老师的反馈。
    展开
    共 1 条评论
    2
  • speedy9
    2019-06-11
    老师，前一个桶大小为1的代码是不是写错了，// 返回线程需要等待的时间 应该是return Math.max(at-now,0)吧
    共 2 条评论
    2
  • 密码123456
    2019-05-25
    桶容量为1的时候，我能理解。但是桶容量为多个的时候，就不理解了，比如 // 新产生的令牌数 long newPermits=(now-next)/interval; 这句，不应该1秒生成桶的总容量吗？假设now为2，next为1。interval也为1。那么一个周期也就产生一个令牌啊？
    2
  • 遇见阳光
    2019-05-25
    RateLimiter这个限流器和juc包的信号量有啥区别？
    2
  • SnowsonZ
    2021-07-15
    ”问题就出在定时器上，在高并发场景下，当系统压力已经临近极限的时候，定时器的精度误差会非常大，同时定时器本身会创建调度线程，也会对系统的性能产生影响“ 生产者消费者和定时器的关系是什么？
    1