前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >RateLimiter没有用到集合,核心是一个时间值

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

原创
作者头像
温安适
修改2021-03-01 14:31:34
2670
修改2021-03-01 14:31:34
举报
文章被收录于专栏:温安适的blog温安适的blog

前言

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

令牌桶算法

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

按图实现

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

代码语言:javascript
复制
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根本没有集合充当桶,核心是记录了下一令牌产生的时间与现存令牌数,并动态更新它们。

概要逻辑图如下:

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

代码语言:javascript
复制
@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 并没有详细看。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 令牌桶算法
  • 按图实现
  • RateLimiter概要实现
    • 概要逻辑图如下:
    • 总结
    • 不足
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档