【令牌桶算法与漏桶算法】

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

在这里插入图片描述

$\color{#FF1493}{令牌桶算法与漏桶算法}$

仰望天空妳我亦是行人.✨
个人主页——微风撞见云的博客
 《数据结构与算法》专栏的文章图文并茂生动形象简单易学欢迎大家来踩踩~
《Java学习笔记》专栏的文章是本人在Java学习中总结的一些知识点~
《每天一点小知识》专栏的文章可以丰富你的知识库滴水成河~
《Redis》专栏的文章是在学习Redis时整理的笔记与记录的思考~
《RabbitMQ》专栏的文章是在学习尚硅谷课程时整理的笔记方便复习巩固~
希望本文能够给读者带来一定的帮助~文章粗浅敬请批评指正

令牌桶算法与漏桶算法

令牌桶算法和漏桶算法都是用于限制请求速率的流量控制算法通常用于网络、服务器和API等场景中以防止突发的流量超出系统的处理能力。它们的主要区别在于如何处理流量超出限制的情况以及在限制流量时的行为。

令牌桶算法Token Bucket Algorithm

令牌桶算法的核心思想是系统维护一个固定容量的令牌桶这个桶以恒定的速率往里面添加令牌每个令牌代表一个请求的许可。当一个请求到达时它需要从令牌桶中获取一个令牌只有当令牌桶中有足够的令牌时请求才会被允许通过否则请求会被拒绝或等待。

令牌桶算法的关键参数包括

桶容量Bucket Capacity表示令牌桶可以存储的最大令牌数量。
令牌生成速率Token Generation Rate表示每秒钟系统向令牌桶中添加的令牌数量。

算法的基本工作流程如下

令牌桶初始化时设定桶容量和令牌生成速率。
每隔一定时间例如每秒往桶中添加一个令牌但不会超过桶的容量。
当请求到达时如果令牌桶中有足够的令牌就允许请求通过并从令牌桶中消耗一个令牌否则请求被限制或等待直到有足够的令牌。

令牌桶算法的优点是可以处理瞬时的流量峰值如果桶中有足够的令牌请求才可以被立即处理。同时令牌桶算法也可以平滑地控制请求速率。

代码实现Java

import java.util.concurrent.Semaphore;

class TokenBucket {
    private final int capacity; // 令牌桶容量
    private final long generationInterval; // 令牌生成间隔时间毫秒
    private long lastGenerationTime; // 上次生成令牌的时间
    private int tokens; // 当前令牌数量
    private final Semaphore semaphore; // 信号量用于控制请求

    public TokenBucket(int capacity, int tokensPerSecond) {
        this.capacity = capacity;
        this.generationInterval = 1000 / tokensPerSecond;
        this.tokens = capacity;
        this.semaphore = new Semaphore(1);
        this.lastGenerationTime = System.currentTimeMillis();
    }

    public boolean tryAcquire() {
        // 获取信号量确保令牌桶更新的线程独占执行
        try {
            semaphore.acquire();
            long currentTime = System.currentTimeMillis();
            long elapsedTime = currentTime - lastGenerationTime;

            // 计算新生成的令牌数量
            int newTokens = (int) (elapsedTime / generationInterval);
            if (newTokens > 0) {
                tokens = Math.min(capacity, tokens + newTokens);
                lastGenerationTime = currentTime;
            }

            // 尝试获取令牌
            if (tokens > 0) {
                tokens--;
                return true;
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            semaphore.release();
        }

        return false;
    }
}

测试

在这里插入图片描述

漏桶算法Leaky Bucket Algorithm

漏桶算法的思想是系统维护一个固定容量的漏桶当请求到达时漏桶以固定速率处理请求不管请求的到达速率如何。如果漏桶已满多余的请求将会被丢弃或排队等待。

漏桶算法的关键参数包括

桶容量Bucket Capacity表示漏桶的最大容量即漏桶可以保存的最多请求数。
漏水速率Leak Rate表示漏桶以多快的速率处理请求。

算法的基本工作流程如下

当请求到达时将请求放入漏桶中。
漏桶以恒定的速率处理请求如果漏桶不为空就从漏桶中移除一个请求并处理它。
如果漏桶为空新的请求将被丢弃或等待直到有空闲的容量。

漏桶算法的特点是无论请求的到达速率如何处理请求的速率都是恒定的因此可以用来平滑流量并限制突发请求。

代码实现Java

import java.util.concurrent.TimeUnit;

class LeakyBucket {
    private final int capacity; // 漏桶容量
    private final int rate; // 漏水速率 (请求/秒)
    private int water; // 当前水量
    private long lastLeakTime; // 上次漏水时间

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = 0;
        this.lastLeakTime = System.nanoTime();
    }

    public synchronized boolean tryConsume() {
        long now = System.nanoTime();
        long elapsedNanos = now - lastLeakTime;
        int leaked = (int) TimeUnit.NANOSECONDS.toSeconds(elapsedNanos) * rate;

        if (leaked > 0) {
            water = Math.max(0, water - leaked);
            lastLeakTime = now;
        }

        if (water < capacity) {
            water++;
            return true;
        } else {
            return false; // 漏桶已满请求被拒绝
        }
    }
}