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

简介: 【令牌桶算法与漏桶算法】

🐳令牌桶算法与漏桶算法

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


🌊令牌桶算法(Token Bucket Algorithm)

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

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

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

💧算法的基本工作流程如下:

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

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

🌊代码实现(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):表示漏桶以多快的速率处理请求。

💧算法的基本工作流程如下:

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

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

🌊代码实现(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; // 漏桶已满,请求被拒绝
        }
    }
}

测试:


🌊总结

令牌桶算法和漏桶算法都是有用的限流工具,可用于保护系统免受过多请求的冲击。通过使用这些算法,我们可以更好地管理和控制流量,确保系统的稳定性和可用性。

  • 令牌桶算法:以恒定速率生成令牌,用于限制请求的平均速率,并可以应对瞬时流量峰值。
  • 漏桶算法:以恒定速率处理请求,用于平滑流量,不管请求的到达速率如何。

这两种算法都有自己的应用场景,选择哪种算法取决于需求。如果需要平滑流量并确保恒定的处理速率,可以选择漏桶算法;如果需要允许瞬时的流量峰值,可以选择令牌桶算法。

相关文章
|
2月前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
|
6月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
327 1
|
6月前
|
存储 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
|
6月前
|
算法 Java 调度
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
|
6月前
|
缓存 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
|
6月前
|
监控 算法 Java
详解 Java 限流接口实现问题之避免令牌桶限流算法可能导致的过载问题如何解决
详解 Java 限流接口实现问题之避免令牌桶限流算法可能导致的过载问题如何解决
|
6月前
|
算法 Java
详解 Java 限流接口实现问题之漏桶限流算法的缺点问题如何解决
详解 Java 限流接口实现问题之漏桶限流算法的缺点问题如何解决
|
8月前
|
算法 Java Spring
用 Spring Boot 实现秒杀系统的流量控制:计数器算法与令牌桶算法
用 Spring Boot 实现秒杀系统的流量控制:计数器算法与令牌桶算法
160 0
|
9天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
139 80
|
2天前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。

热门文章

最新文章