登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

豆瓜网 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›令牌桶VS漏桶：谁才是流量控制的“最优解”？ ...

令牌桶VS漏桶：谁才是流量控制的“最优解”？

垢峒 前天 09:38
大家好，我是小富～
面试被问到限流算法，很多面试官会让直接手写令牌桶和漏桶的实现。虽然平时用过Redis、Guava等现成的限流工具，但真要手写还是有点慌。今天就来聊聊这两种经典限流算法的区别，并用Java手写实现。
很多的限流工具底层都应用了它们
一、令牌桶 vs 漏桶：核心区别

令牌桶

令牌桶的核心思想：固定容量的桶，以固定速率往桶里放令牌，请求来了就从桶拿令牌，没令牌就拒绝。
有点像买票进站，想去坐火车就先去售票窗口买票，买到票了就凭票进入，买不到等待，因为窗口会定时的放票，再去抢。
下图是用Ai生成的，大致能体现出这么个意思
1.png

令牌桶特点：
1、可以处理突发流量（桶里有令牌就能用），因为并不是一直请求都很多，但会一直以固定速率向桶里添加令牌，请求少时桶内令牌满了，请求激增可以满桶拿令牌顶一阵
2、原理和实现上相对简单
3、内存占用小
漏桶适用场景：

接口限流：保护业务系统或者敏感接口
防止恶意攻击：抵御Dos或DDos攻击
……
它的优势在于能够限制平均速率，同时允许一定的突发流量
漏桶

漏桶的核心思想比令牌桶早更简单：请求像水一样流入桶中，桶以固定速率“漏水”处理请求，超出桶容量的请求被丢弃或排队。
2.png

漏桶的特点：
1、输出非常平滑稳定
2、能有效保护下游系统（流量平滑）
3、❌ 无法处理突发流量
4、❌ 可能造成请求延迟
漏桶适用场景：

数据库连接池：保护数据库不被过载
消息队列消费：控制消费速率
支付系统：确保支付处理稳定性
二、手写实现

令牌桶实现
  1. public class TokenBucket {
  2.     // 桶容量（最大令牌数）
  3.     privatefinallong capacity;
  4.     // 令牌填充速率（令牌/秒）
  5.     privatefinallong refillRate;
  6.     // 当前令牌数量
  7.     private AtomicLong tokens;
  8.     // 上次填充时间戳（纳秒）
  9.     privatelong lastRefillTime;
  11.     public TokenBucket(long capacity, long refillRate) {
  12.         this.capacity = capacity;
  13.         this.refillRate = refillRate;
  14.         this.tokens = new AtomicLong(capacity);
  15.         this.lastRefillTime = System.nanoTime();
  16.     }
  18.     // 示例使用
  19.     public static void main(String[] args) throws InterruptedException {
  20.         // 创建桶：容量10令牌，每秒填充5令牌
  21.         TokenBucket bucket = new TokenBucket(10, 2);
  23.         // 模拟请求
  24.         for (int i = 1; i <= 50; i++) {
  25.             if (bucket.tryAcquire()) {
  26.                 System.out.println("请求" + i + ": 通过");
  27.             } else {
  28.                 System.out.println("请求" + i + ": 限流");
  29.             }
  30.             Thread.sleep(100); // 100ms请求一次
  31.         }
  32.     }
  34.     /**
  35.      * 尝试获取令牌
  36.      *
  37.      * @return true-获取成功，false-被限流
  38.      */
  39.     public synchronized boolean tryAcquire() {
  40.         refillTokens();
  41.         if (tokens.get() > 0) {
  42.             tokens.decrementAndGet();
  43.             returntrue;
  44.         }
  45.         returnfalse;
  46.     }
  48.     /**
  49.      * 尝试获取多个令牌
  50.      *
  51.      * @param numTokens 请求令牌数
  52.      */
  53.     public synchronized boolean tryAcquire(int numTokens) {
  54.         refillTokens();
  55.         if (tokens.get() >= numTokens) {
  56.             tokens.addAndGet(-numTokens);
  57.             returntrue;
  58.         }
  59.         returnfalse;
  60.     }
  62.     // 根据时间差补充令牌
  63.     private void refillTokens() {
  64.         long now = System.nanoTime();
  65.         // 计算时间差（秒）
  66.         double elapsedSec = (now - lastRefillTime) * 1e-9;
  68.         // 计算应补充的令牌数
  69.         long tokensToAdd = (long) (elapsedSec * refillRate);
  70.         if (tokensToAdd > 0) {
  71.             tokens.set(Math.min(capacity, tokens.get() + tokensToAdd));
  72.             lastRefillTime = now;
  73.         }
  74.     }
  75. }
复制代码

  • 使用 AtomicLong 保证线程安全。
  • 通过时间差动态计算补充的令牌数。
  • 桶容量限制突发流量的最大值。
3.png

漏桶实现
  1. import java.util.concurrent.atomic.AtomicLong;
  3. publicclass LeakyBucket {
  4.     // 桶容量（最大请求数）
  5.     privatefinallong capacity;
  6.     // 漏水速率（请求/秒）
  7.     privatefinallong leakRate;
  8.     // 当前水量（待处理请求数）
  9.     private AtomicLong water;
  10.     // 上次漏水时间戳（毫秒）
  11.     privatelong lastLeakTime;
  13.     public LeakyBucket(long capacity, long leakRate) {
  14.         this.capacity = capacity;
  15.         this.leakRate = leakRate;
  16.         this.water = new AtomicLong(0);
  17.         this.lastLeakTime = System.currentTimeMillis();
  18.     }
  20.     // 示例使用
  21.     public static void main(String[] args) throws InterruptedException {
  22.         // 创建桶：容量5请求，每秒处理2请求
  23.         LeakyBucket bucket = new LeakyBucket(5, 1);
  25.         // 模拟请求
  26.         for (int i = 1; i <= 15; i++) {
  27.             if (bucket.tryPass()) {
  28.                 System.out.println("请求" + i + ": 通过 (当前水位: " + bucket.water.get() + ")");
  29.             } else {
  30.                 System.out.println("请求" + i + ": 限流 (水位溢出)");
  31.             }
  32.             Thread.sleep(200); // 200ms请求一次
  33.         }
  34.     }
  36.     /**
  37.      * 尝试通过漏桶
  38.      *
  39.      * @return true-允许通过，false-被限流
  40.      */
  41.     public synchronized boolean tryPass() {
  42.         leakWater();
  43.         if (water.get() < capacity) {
  44.             water.incrementAndGet();
  45.             returntrue;
  46.         }
  47.         returnfalse;
  48.     }
  50.     // 根据时间差漏水
  51.     private void leakWater() {
  52.         long now = System.currentTimeMillis();
  53.         // 计算时间差（秒）
  54.         long elapsedMs = now - lastLeakTime;
  55.         if (elapsedMs > 0) {
  56.             // 计算漏水量
  57.             long leaked = (long) (elapsedMs * leakRate / 1000.0);
  58.             if (leaked > 0) {
  59.                 water.updateAndGet(cur -> Math.max(0, cur - leaked));
  60.                 lastLeakTime = now;
  61.             }
  62.         }
  63.     }
  64. }
复制代码

  • 漏出速率固定，确保请求处理平滑。
  • 水量超过容量时直接拒绝请求。
4.png

三、测试对比
  1. public class RateLimiterTest {
  2.     public static void main(String[] args) throws InterruptedException {
  3.         // 测试令牌桶：容量10，每秒填充5个令牌
  4.         TokenBucket tokenBucket = new TokenBucket(10, 5);
  6.         // 测试漏桶：容量10，每秒漏出5个请求
  7.         LeakyBucket leakyBucket = new LeakyBucket(10, 5);
  9.         System.out.println("=== 令牌桶测试（支持突发） ===");
  10.         testTokenBucket(tokenBucket);
  12.         Thread.sleep(1000);
  14.         System.out.println("\n=== 漏桶测试（平滑输出） ===");
  15.         testLeakyBucket(leakyBucket);
  16.     }
  18.     private static void testTokenBucket(TokenBucket bucket) {
  19.         // 模拟突发请求
  20.         for (int i = 0; i < 15; i++) {
  21.             boolean success = bucket.tryConsume(1);
  22.             System.out.printf("请求%d: %s (当前令牌: %.1f)%n",
  23.                 i + 1, success ? "通过" : "拒绝", bucket.getCurrentTokens());
  24.         }
  25.     }
  27.     private static void testLeakyBucket(LeakyBucket bucket) {
  28.         // 模拟突发请求
  29.         for (int i = 0; i < 15; i++) {
  30.             boolean success = bucket.tryConsume();
  31.             System.out.printf("请求%d: %s (当前水量: %.1f)%n",
  32.                 i + 1, success ? "通过" : "拒绝", bucket.getCurrentWater());
  33.         }
  34.     }
  35. }
复制代码
四、面试要点总结

面试官可能会问的问题：
Q: 两种算法的核心区别是什么？
A: 令牌桶允许突发，漏桶强制平滑输出
Q: 什么场景用令牌桶，什么场景用漏桶？
A: 需要处理突发用令牌桶，需要保护下游用漏桶
Q: 如何选择桶的容量和速率？
A: 根据业务峰值、系统承载能力、用户体验综合考虑
Q: 分布式环境下如何实现？
A: 可以用Redis实现，或者用一致性哈希分片
说在后边

手写限流算法是一般在高级别的面试中不太会出现，但它们的基础概念要掌握，在考场景题时它们都是不错的方案。
简单记：令牌桶像ATM机，有钱就能取；漏桶像水龙头，固定流速出水。
完活！

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
令牌桶VS漏桶才是流量

使用道具 举报

相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
垢峒
前天 09:38

0

粉丝关注

21

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫