ming

不做不说

0%

漏桶算法笔记

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

前言

之前也用到过 这个漏桶算法实现的限流 但是不是我写的 也没怎么关注
这次看到redis书中提到了 就顺便写一篇笔记记录一下 方便后续查询

算法原理

参考文档: https://baike.baidu.com/item/%E6%BC%8F%E6%A1%B6%E7%AE%97%E6%B3%95/8455361

总的来说 就是类似小学应用题中的 游泳池 边放水 边进水 当游泳池满了之后 不能再进水
漏桶算法 适合整理流量
但是对于突发特性的流量来说 适应性不是很强
很容易导致游泳池满了导致拒绝访问

懒的截图 手画个简略图 意思意思 

1
2
3
4
5
6
7
8
9
10
11
12
13

------                     
     ·输入流量                 
     ·                     
 ----------------          
 \          /    ·溢出流量      
  \   桶  /      ·          
   \      /                
    -------                
       ·                   
       ·输出流量               
       ·

实例

java编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package com.ming;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 漏桶算法测试用例
 * 漏桶算法
 *
 * @author ming
 * @date 2019-09-17 09:58:13
 */
@Slf4j
public class LeakyBucketTest {


    /**
     * 输入速率大于 输出速率
     * 桶未满之前 多余的流量存到桶中 延迟输出
     * 桶满之后 后续流量抛弃
     * <p>
     * 由于环境艰苦   此处使用两个线程模拟输入和输出流量
     * 输入每次请求休眠inputSleepTime时间 输出每次休眠outputSleepTime时间
     * sleepTime越短 输入速率或者输出速率越高    反之越低
     * 通过修改 输入输出速率进行不同情况的测试
     * 输入速率=输出速率 如果桶中没有之前的流量那么直接输出 如果有 那么会有一个稳定的延迟时间
     * 输入速率>输出速率  桶未满之前  会持续输出 无法处理的流量存入桶中 当桶满之后  抛弃流量
     * 输入速率<输出速率  如果桶中没有之前的流量 那么直接输入 如果有 那么延迟时间会越来越短直至没有延迟
     *
     * <p>
     * 使用 有界队列 非阻塞函数 来模拟
     *
     * @author ming
     * @date 2019-09-17 10:07:36
     */
    @Test
    public void test() throws InterruptedException {
        //桶最大容量
        int maxSize = 10;
        //输入流量速率 s
        int inputSleepTime = 1;
        //输出流量速率  s
        int outputSleepTime = 2;
        mockLeakyBucket(maxSize, inputSleepTime, outputSleepTime);
        Thread.sleep(100000000L);
    }


    /**
     * 模拟 漏桶
     *
     * @param maxSize         桶最大深度
     * @param inputSleepTime  输入速率参数
     * @param outputSleepTime 输出速率参数
     * @author ming
     * @date 2019-09-17 10:50:14
     */
    private void mockLeakyBucket(int maxSize, int inputSleepTime, int outputSleepTime) {
        //使用有界 队列 模拟桶   最大为maxSize
        Queue<String> bucket = new ArrayBlockingQueue<>(maxSize);

        //启动一条线程模拟输入流量
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(inputSleepTime * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                //由于是有界队列 add方法不会阻塞  如果超出边界直接报错
                try {
                    bucket.add("流量:" + LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
                } catch (Exception e) {
                    e.printStackTrace();
                    log.error("流量溢出" + bucket.size() + ";" + Thread.currentThread().getName());
                }
            }
        }).start();

        //启动另一个线程模拟输入流量处理
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(outputSleepTime * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                log.info("输出流量:" + bucket.poll() + ";" + Thread.currentThread().getName());
            }
        }).start();
    }
}

总结

漏桶算法 原理还是很简单的 就是一个输入输出速率和中间桶的处理
漏桶算法适合流量较为稳定的情况 用来整理流量 处理少量突发流量
如果有突发流量 只能就要取调整桶大小或者输出流量速率来达到适应突发流量
如果加桶大小 延迟就会高
不过企业项目中 很少会有大量突发流量 所以用漏桶算法一般也足够了