首页 > 编程语言 >基于令牌桶算法实现一个限流器

基于令牌桶算法实现一个限流器

时间：2024-10-26 21:10:00浏览次数：7  
标签：令牌 int rate 算法 限流 maxPermit permit new

序言：本文章基于令牌桶算法实现了简单的一个限流器

1 令牌桶算法

实现原理

  • 令牌生成：在固定的时间间隔内，算法会向一个桶中放入一定数量的令牌。令牌的生成速率是固定的，通常以每秒钟生成的令牌数来表示。
    • 桶的容量：桶有一个最大容量，如果桶满了，新的令牌将被丢弃。这意味着即使在高流量情况下，系统也不会无限制地增加请求。
  • 请求处理：每当一个请求到达时，它需要从桶中获取一个令牌。如果桶中有令牌，请求就可以被处理，桶中的令牌数量减一。如果没有令牌，请求将被拒绝或被延迟，具体取决于实现。
  • 流量控制：通过调整令牌的生成速率和桶的容量，可以控制流量的平稳性和最大流量。

算法优点：

  • 可以承载一定的突发流量情况。
  • 限流窗口的变化相对平稳。

coding

根据令牌桶算法原理，可以先定义出三个变量。桶容量、令牌产生速率和当前桶中的令牌数量。同时定义一个rateLimiter类和对应的构造方法：

public class RateLimiter {
    // 自己写的日志打印工具(在线程池的文章中有贴)
    static Logger log = new Logger(Logger.LogLevel.DEBUG, RateLimiter.class);
    // 桶容量
    private final int maxPermit;
    // 令牌产生速率 / 秒
    private final int rate;
    // 当前桶中的令牌数量(考虑到这个变量会多线程使用, 使用原子类来实现)
    private final AtomicInteger holdPermits;
    
    public RateLimiter(int maxPermit, int rate, int initPermits) {
        if (rate < 1) throw new IllegalArgumentException("the rate must be greater than 1");
        if (initPermits < 0) throw new IllegalArgumentException("the initPermits must be greater than 0");
        if (maxPermit < 1) throw new IllegalArgumentException("the maxPermit must be greater than 1");
        this.maxPermit = maxPermit;
        this.rate = rate;
        this.holdPermits = new AtomicInteger(initPermits);
    }
}

然后我们需要给这个类添加一个 boolean tryAcquire(int permit) 方法。表示获取permit数量个令牌。如果获取成功返回true，获取失败则返回false。
可以写出这个方法：

/**
 * 尝试获取 permit 数量的令牌
 *
 * @param permit 令牌数量
 * @return 获取到 permit 数量的令牌则返回 true, 否则返回 false
 */
public boolean tryAcquire(int permit) {
    if (permit > maxPermit) throw new IllegalArgumentException("the permit must be smaller than maxPermit:" + maxPermit);
    if (permit < 1) throw new IllegalArgumentException("the permit must be greater than 1");
    int currentPermits;
    do {
        currentPermits = holdPermits.get();
        if (currentPermits < permit) {
            return false;
        }
    } while (!holdPermits.compareAndSet(currentPermits, currentPermits - permit));
    // 日志打印
    log.debug("原令牌数：" + currentPermits + ", 减少：" + permit + ", 当前总数：" + (currentPermits - permit));
    return true;
}

这个方法中借助了原子类的compareAndSet操作和自旋来实现令牌的扣减。当当前桶中的令牌数量大于等于请求获取的令牌数时，使用compareAndSet来实现令牌的扣减。
但是这个方法可能由于其他线程的并发执行(提前扣减了令牌)而失败。所以需要自旋操作保证令牌数量足够时可以正确获得令牌许可。只有当桶中的令牌数小于请求要求的令牌数量时才会返回失败。

至此，令牌桶的构造方法和获取令牌的方法已经实现完成。但是何时且如何向桶中放入令牌呢？
如果使用定时任务的话，那么就需要创建额外的线程对象来完成。

这里借鉴前人的智慧，在每一次获取令牌时顺便计算和更新令牌数量，这样的话，我们还需要一个变量记住上一次计算令牌的时间。
所以在类中加一个变量 lastFreshTime 记录上一次计算更新令牌的时间，同时由于这个变量可能被多个线程更改，使用原子类对象保证线程安全。

// 上次计算更新令牌的时间
private final AtomicLong lastFreshTime;

然后，我们还需要一个方法，用于每次获取令牌前计算更新桶中的令牌数量，这个方法中首先根据过去时间的纳秒数量计算出应该产生的令牌数量，使用int向下取整,
然后使用令牌数量反向计算产生这些令牌所需的准确时间(因为令牌数量使用int取整了)，加上当前lastFreshTime的值即可以得到新的lastFreshTime的值。
这里为了保证线程安全，lastFreshTime 的更新使用compareAndSet保证只有一个线程可以获取更新权限。这个线程在成功更新lastFreshTime后，需要继续更新令牌的数量，
由于在tryAcquire中还可能出现其他线程扣减令牌数量的行为，所以这里还需要保证更新操作的原子性。

/**
 * 刷新令牌数量
 */
private void freshPermit() {
    long now = System.nanoTime();
    long lastTime = lastFreshTime.get();
    if (now <= lastTime) return;
    int increment = (int) ((now - lastTime) * rate / 1_000_000_000);
    long thisTime = lastTime + increment * 1_000_000_000L / rate;
    if (increment > 0 && lastFreshTime.compareAndSet(lastTime, thisTime)) {
        int current;
        int next;
        do {
            current = holdPermits.get();
            next = Math.min(maxPermit, current + increment);
        } while (!holdPermits.compareAndSet(current, next));
        log.debug("原令牌数：" + current + ", 增加：" + increment + ", 当前总数：" + holdPermits.get());
    }
}

至此，我们就实现了一个简单的令牌桶实现代码，只要每次tryAcquire时先使用freshPermit更新一下令牌数量就可以了。

但通常来说，令牌桶还会有一个带超时时间的boolean tryAcquire(int permit, long timeOut)方法。这里我们做一个简单的实现，使用定期的sleep操作而不是锁机制来完成。

假设要获取的令牌数量为 p，超时时间为 t，那么在tryAcquire(p, t)方法中，如果当前令牌不足p的话，那么线程将会sleep一定时间会再次尝试获取令牌，直到使用时间超过t仍未获取成功才会返回失败。

这里有一个问题就是睡眠时间sleepDuration的确定，在这个代码中，sleepDuration的值为 (p / rate) / 10，且最小为10，最大为100。
实现代码：

/**
 * 在 timeout 时间内尝试获取 permit 数量的令牌
 *
 * @param permit  令牌数量
 * @param timeOut 超时时间 单位 秒
 * @return 如果在 timout 时间内获取到 permit 数量的令牌则返回 true, 否则返回 false
 */
public boolean tryAcquire(int permit, long timeOut) {
    if (permit < 1) throw new IllegalArgumentException("the permit must be greater than 1");
    if (timeOut < 0) throw new IllegalArgumentException("the timeOut must be greater than 0");
    timeOut = timeOut * 1_000_000_000 + System.nanoTime();
    long sleepDuration = (long) (1.0 * permit / rate);
    sleepDuration = Math.min(sleepDuration, 100);
    sleepDuration = Math.max(sleepDuration, 10);
    while (System.nanoTime() < timeOut) {
        if (tryAcquire(permit)) return true;
        else {
            try {
                Thread.sleep(sleepDuration);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return false;
            }
        }
    }
    return false;
}

至此，我们就实现了一个简单的使用令牌桶算法的限流器类。
完整代码：

public class RateLimiter {

    static Logger log = new Logger(Logger.LogLevel.DEBUG, RateLimiter.class);
    /**
     * 最大令牌数量
     */
    private final int maxPermit;
    /**
     * 令牌产生速率 / 每秒
     */
    private final int rate;

    /**
     * 当前可用令牌数量
     */
    private final AtomicInteger holdPermits;
    /**
     * 上次计算令牌的时间
     */
    private final AtomicLong lastFreshTime;


    public RateLimiter(int maxPermit, int rate, int initPermits) {
        if (rate < 1) throw new IllegalArgumentException("the rate must be greater than 1");
        if (initPermits < 0) throw new IllegalArgumentException("the initPermits must be greater than 0");
        if (maxPermit < 1) throw new IllegalArgumentException("the maxPermit must be greater than 1");
        if (maxPermit < rate) throw new IllegalArgumentException("the maxPermit must be greater than rate");
        this.maxPermit = maxPermit;
        this.rate = rate;
        this.holdPermits = new AtomicInteger(initPermits);
        this.lastFreshTime = new AtomicLong(System.nanoTime());
    }

    /**
     * 尝试获取 permit 数量的令牌
     *
     * @param permit 令牌数量
     * @return 获取到 permit 数量的令牌则返回 true, 否则返回 false
     */
    public boolean tryAcquire(int permit) {
        if (permit > maxPermit)
            throw new IllegalArgumentException("the permit must be smaller than maxPermit:" + maxPermit);
        if (permit < 1) throw new IllegalArgumentException("the permit must be greater than 1");
        freshPermit();

        int currentPermits;
        do {
            currentPermits = holdPermits.get();
            if (currentPermits < permit) {
                return false;
            }
        } while (!holdPermits.compareAndSet(currentPermits, currentPermits - permit));

        log.debug("原令牌数：" + currentPermits + ", 减少：" + permit + ", 当前总数：" + (currentPermits - permit));
        return true;
    }

    /**
     * 刷新令牌数量
     */
    private void freshPermit() {
        long now = System.nanoTime();
        long lastTime = lastFreshTime.get();
        if (now <= lastTime) return;
        int increment = (int) ((now - lastTime) * rate / 1_000_000_000);
        long thisTime = lastTime + increment * 1_000_000_000L / rate;
        if (increment > 0 && lastFreshTime.compareAndSet(lastTime, thisTime)) {
            int current;
            int next;
            do {
                current = holdPermits.get();
                next = Math.min(maxPermit, current + increment);
            } while (!holdPermits.compareAndSet(current, next));
            log.debug("原令牌数：" + current + ", 增加：" + increment + ", 当前总数：" + holdPermits.get());
        }
    }

    /**
     * 在 timeout 时间内尝试获取 permit 数量的令牌
     *
     * @param permit  令牌数量
     * @param timeOut 超时时间 单位 秒
     * @return 如果在 timout 时间内获取到 permit 数量的令牌则返回 true, 否则返回 false
     */
    public boolean tryAcquire(int permit, long timeOut) {
        if (permit < 1) throw new IllegalArgumentException("the permit must be greater than 1");
        if (timeOut < 0) throw new IllegalArgumentException("the timeOut must be greater than 0");
        timeOut = timeOut * 1_000_000_000 + System.nanoTime();
        long sleepDuration = (long) (1.0 * permit / rate);
        sleepDuration = Math.min(sleepDuration, 100);
        sleepDuration = Math.max(sleepDuration, 10);
        while (System.nanoTime() < timeOut) {
            if (tryAcquire(permit)) return true;
            else {
                try {
                    Thread.sleep(sleepDuration);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    return false;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        RateLimiter rateLimiter = new RateLimiter(100, 50, 0);
        log.info("开始");
        for (int i = 0; i < 3; i++) {
            int j = i;
            new Thread(() -> {
                int k = 0;
                while (true) {
                    if (rateLimiter.tryAcquire(20, 1)) {
                        log.info("第" + k++ + "轮, 线程 " + j + " 获取令牌成功");
                    } else log.error("第" + k++ + "轮, 线程 " + j + " 获取令牌失败");
                    try {
                        Thread.sleep(888);
                    } catch (InterruptedException e) {
                        throw new RuntimeException(e);
                    }
                }
            }).start();
        }
    }
}

总结

这个案例中其实还是可以学习到不少关于如何线程安全的实现功能的问题。

标签：令牌,int,rate,算法,限流,maxPermit,permit,new
From： https://www.cnblogs.com/ZGByoyo/p/18504532

相关文章

  • 高级java每日一道面试题-2024年10月23日-JVM篇-说一下JVM有哪些垃圾回收算法?
    如果有遗漏,评论区告诉我进行补充面试官:说一下JVM有哪些垃圾回收算法?我回答:在Java虚拟机(JVM)中，垃圾回收(GarbageCollection,GC)是一项非常重要的功能，用于自动管理应用程序的内存。JVM采用多种垃圾回收算法来决定何时以及如何回收不再使用的对象所占用的内......
  • 代码随想录算法训练营day26|455.分发饼干 376. 摆动序列 53. 最大子序和
    学习资料：https://programmercarl.com/贪心算法理论基础.html#算法公开课贪心算法Part1求局部最优解，最终达到全局最优455.分发饼干（大胃口吃大饼干）点击查看代码classSolution(object):deffindContentChildren(self,g,s):""":typeg:List[int]......
  • 二分算法
    1.二分查找个人习惯使用左闭右闭的方法，不管用来求位置、求最大还是最小，都是同一个写法intfindborder(vector<int>&nums,inttgt){ intleft=0,right=nums.size();while(left<=right){intmid=left+(right-left)/2; //防溢出写法......
  • 马拉车算法（回文子串长度）
    #include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintMax=100000;chars[Max*2+5];charstr[Max*2+5];intdp[Max*2+5];voidmc(){intn=strlen(s+1);str[0]='s';intj=1;for(inti=1;i<=n;i++){str[j++]='#&#......
  • 【信奥赛·算法基础】CSP-J 枚举算法
    序言解决问题，并不是一开始就要找到最优解，而是在不断的调试中优化，将求解过程中耗时的部分、占用空间的部分尽可能的缩小，使得程序运行起来更高效一、定义与概念枚举算法，也叫穷举算法，是一种简单而直接的问题求解策略。它的核心思想是逐一列举问题的所有可能解，并逐一检验每个......
  • 【信奥赛·算法基础】CSP-J C++ 贪心算法示例汇总
    序言为了更清晰的了解贪心算法，我把常见的贪心算法示例做了一个总结，把问题和策略，以及代码示例放到了一起，方便学习和分析，这里示例仅以C++为例，其他语言可根据示例调整即可一、钱币找零问题问题描述：给定不同面额的钱币以及每种面额的数量，用最少的钱币张数凑齐给定的总金额。......
  • 刷题总结——回溯算法
    总论增量构造答案关注边界条件的逻辑当前操作？（选/不选，枚举选哪一个）子问题？下一个子问题？用什么数据结构保存搜索路径？时间复杂度计算：搜索树节点数*生成答案需要的时间题目分类可以分成子集型、排列型和组合型三种：回溯问题时间复杂度O()解法子集LC78nx2^n......
  • 算法之树状数组详解
    树状数组树状数组（BinaryIndexedTree，简称BIT），也被称为Fenwick树，是一种用于处理数组问题的高效数据结构。它特别适合解决涉及区间查询和更新的问题，尤其是当需要频繁地计算数组的前缀和时。树状数组的核心思想是利用二进制表示法(lowbit函数)来快速定位数组中的区间，并在O(lo......
  • 【路径规划】基于蚁群算法的二维机器人路径规划，二维珊格地图路径规划
    摘要本文研究了基于蚁群算法的二维机器人路径规划问题，利用蚁群算法优化机器人在二维栅格地图中的最优路径。蚁群算法通过仿生学模拟蚂蚁寻找食物的过程，在障碍物密集的栅格地图中寻找出最短、最优的路径。实验结果表明，该算法能够有效地避开障碍物，并通过多次迭代逐步优化路径，......
  • 【无人机设计与控制】基于Astar算法无人机路径规划，优化路径平滑
    摘要本文提出了一种基于A算法的无人机路径规划方法，并通过路径平滑优化提升路径的可行性和安全性。传统A算法在生成路径时，常因路径节点分布不规则导致路径不平滑，影响无人机的飞行效率和安全性。本文通过引入贝塞尔曲线对A*算法生成的路径进行优化，使其更加平滑和符合无人机的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99