专栏首页Java技术栈RateLimiter 的底层实现是啥?

RateLimiter 的底层实现是啥?

作者:温安适 来源:https://my.oschina.net/floor/blog/4965200

前言

本文不是一个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根本没有集合充当桶,核心是记录了下一令牌产生的时间与现存令牌数,并动态更新它们。最后,关注公众号Java技术栈,在后台回复:面试,可以获取我整理的 Java 系列面试题和答案,非常齐全。

本文分享自微信公众号 - Java技术栈(javastack),作者:点击关注 ????

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

原始发表时间:2021-06-08

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • RateLimiter 的底层实现是啥?

    来源 | https://my.oschina.net/floor/blog/4965200

    程序猿DD
  • synchronized底层是怎么实现的?

    面试的时候有被问到,synchronized底层是怎么实现的,回答的比较浅,面试官也不是太满意,所以觉得要好好总结一下,啃啃这个硬骨头。

    纪莫
  • 基于 Redis 实现简单限流器及其在路由中间件中的应用

    所谓限流器,指的是限制访问指定服务/路由的流量,通俗点说,就是限制单位时间内访问指定服务/路由的次数(频率),从系统架构角度看,通过限流器可以有效避免短时间内的...

    学院君
  • 天天用Synchronized,底层原理是个啥?

    https://www.cnblogs.com/paddix/p/5367116.html

    Java技术栈
  • 天天用Synchronized,底层原理是个啥?

    接下来我就通过几个例子程序来说明一下这三种使用方式(为了便于比较,三段代码除了 Synchronized 的使用方式不同以外,其他基本保持一致)。

    哲洛不闹
  • servlet的底层实现原理是什么?

    1) 首先Sun公司编写了一系列Class,比如javax.servlet.http.HttpServlet,你编写的Servlet需要利用或继承它 们。这一系...

    马克java社区
  • libevent是怎么选择底层实现的

    libevent实际封装了很多IO复用模式,比如evport,select,poll,epoll,devpoll等等,这些都是不同操作系统下的I/O多路复用模式...

    cpp加油站
  • TCP/IP的底层队列是如何实现的?

    自从上次学习了TCP/IP的拥塞控制算法后,我越发想要更加深入的了解TCP/IP的一些底层原理,搜索了很多网络上的资料,看到了陶辉大神关于高性能网络编程的专栏,...

    用户5927304
  • ArrayList底层实现

    package java.util; public class ArrayList<E> extends AbstractList<E> im...

    用户1215919
  • # iOS中的KVO底层实现

    KVO是Key-Value-Observer的缩写,使用的是观察者模式。底层实现机制都是isa-swizzing,就是在底层调用object_setClass函...

    Haley_Wong
  • InnoDB引擎的底层实现

    InnoDB的存储文件有两个,后缀名分别是 .frm和 .idb;其中 .frm是表的定义文件, .idb是表的数据文件。

    AlbertZhang
  • 雪花算法到底是啥原理?附 Java 实现!

    其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳,基本上保持自增的,后面的...

    Java技术栈
  • 超详细的Guava RateLimiter限流原理解析

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

    程序员历小冰
  • 基于Redis实现分布式应用限流

    限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务。 前几天在DD的公众号,看了一篇关于使用 ...

    冷冷
  • spirng底层实现原理

    用户2146856
  • spirng底层实现原理

    用户2146856
  • 死磕Synchronized底层实现

    关于synchronized的底层实现,网上有很多文章了。但是很多文章要么作者根本没看代码,仅仅是根据网上其他文章总结、照搬而成,难免有些错误;要么很多点都是一...

    Java团长
  • 死磕Synchronized底层实现

    关于synchronized的底层实现,网上有很多文章了。但是很多文章要么作者根本没看代码,仅仅是根据网上其他文章总结、照搬而成,难免有些错误;要么很多点都是一...

    java思维导图
  • HashMap底层实现详解

      HashMap是基于哈希表的Map接口的非同步实现(Hashtable跟HashMap很像,唯一的区别是Hashtalbe中的方法是线程安全的,也就是同步的...

    IT小马哥

扫码关注云+社区

领取腾讯云代金券