《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 my.oschina.net/floor/blog/4965200 「温安适」欢迎转载,保留摘要,谢谢!


🙂🙂🙂关注微信公众号:【芋道源码】有福利:

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言将得到认真回复。甚至不知道如何读源码也可以请教噢
  4. 新的源码解析文章实时收到通知。每周更新一篇左右
  5. 认真的源码交流微信群。

前言

本文不是一个RateLimiter的详细分析,仅仅是概要分析。

令牌桶算法

一说到RateLimiter,必然要是说的令牌桶,它的大致逻辑如下

按图实现

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

import java.util.concurrent.*;

public class MyRateLimiter {
//令牌桶
BlockingQueue<Integer>TOKEN_BUCKET=new LinkedBlockingDeque<>(5);

public static void main(String[] args) {
MyRateLimiter myRateLimiter=new MyRateLimiter();
myRateLimiter.addTokenFixedRate();
for(int i=0;i<10;i++){
myRateLimiter.acqurie();
System.out.println("第几次执行i:" + i + ",执行时间为:" + System.currentTimeMillis());
}
}
/**
* 定时添加令牌
*/
public void addTokenFixedRate(){
ScheduledExecutorService scheduledExecutorService= Executors.newSingleThreadScheduledExecutor();
scheduledExecutorService.scheduleAtFixedRate(()->{
boolean suc=TOKEN_BUCKET.offer(1);
if(!suc){
System.out.println("令牌桶满了丢弃");
}
},0,200,TimeUnit.MILLISECONDS);
}

public void acqurie(){
while (TOKEN_BUCKET.poll()==null){};
}

}

测试结果如下,基本满足要求

RateLimiter概要实现

我一开始是按照自己实现的逻辑,去查看Guava的RateLimiter的源码的,结果发现\RateLimiter根本没有集合充当桶,核心是记录了下一令牌产生的时间与现存令牌数,并动态更新它们。**

概要逻辑图如下:

按照这个图看核心代码就比较容易了,摘录核心代码如下:

@CanIgnoreReturnValue
public double acquire(int permits) {
long microsToWait = reserve(permits);
stopwatch.sleepMicrosUninterruptibly(microsToWait);
return 1.0 * microsToWait / SECONDS.toMicros(1L);
}
//Reserve 一路向下能查到如下代码 reserveEarliestAvailable

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
resync(nowMicros);
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;
}

总结

RateLimiter根本没有集合充当桶,核心是记录了下一令牌产生的时间与现存令牌数,并动态更新它们

不足

SmoothWarmingUp 与SmoothBursty 并没有详细看。

文章目录
  1. 1. 前言
  2. 2. 令牌桶算法
  3. 3. 按图实现
  4. 4. RateLimiter概要实现
    1. 4.1. 概要逻辑图如下:
  5. 5. 总结
  6. 6. 不足