ming

不做不说

0%

令牌桶算法笔记

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

前言

令牌桶。。。用到是用到过 不过不是限流 是业务功能中使用的 不过跟限流类似 只不过生成令牌含义变成了某种业务的前置条件了
也记录一下 方便后续查询

算法原理

参考文档: https://baike.baidu.com/item/令牌桶算法/6597000

搞个放令牌的桶 每次请求都获取一个令牌进行访问 通过控制令牌生成的速度来控制请求速率

照例 意思意思 

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

--------
       ·生成令牌 
       ·
  ----------
  \        /
   \  桶  /
    \    /
     ----
       ·分发令牌
       ·
输入流量-------尝试获取令牌----> 有合法令牌继续访问、没有令牌或者不合法拒绝访问------>  输出流量
标记器

如果只是做流量控制 令牌桶算法本身就够用了
但是如果要做流量标记分析处理 那么就需要对流量进行标记 通过不同的方案去计算流量的特性
我也不明白 看起来就是通过做标记 来对流量进行分析
这里只作为记录

  • IN/OUT 公平标记器(FM)
  • 单速率三色标记器(srTCM)
  • 双速率标记器(trTCM)

实例

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
package com.ming;

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 令牌桶算法测试用例
 * 令牌桶算算法
 *
 * @author ming
 * @date 2019-09-17 13:55:47
 */
@Slf4j
public class TokenBucketTest {

    /**
     * 测试令牌桶模式 限流
     * <p>
     * 按照下面参数
     * 当桶满的情况下  5s内最大请求数为100  并且后续每5s 能够允许10次访问
     *
     * @author ming
     * @date 2019-09-17 13:57:12
     */
    @Test
    public void test() throws InterruptedException {
        //桶深
        int maxSize = 100;
        //生成令牌 休眠时间
        int generateSleepTime = 5;
        //一次生成多少令牌
        int generateTokenNumber = 30;

        //输出流量休眠时间
        int outputSleepTime = 1;


        //用 blockQueue模拟桶
        Queue<String> tokenBucket = new ArrayBlockingQueue<>(maxSize);

        //新启动一个线程 作为 token 生成 每5s生成10个
        new Thread(() -> {
            while (true) {
                for (int i = 0; i < generateTokenNumber; i++) {
                    try {
                        tokenBucket.add("生成令牌:" + System.currentTimeMillis() + "::" + i + "当前令牌桶容量:" + tokenBucket.size());
                    } catch (Exception e) {
                        //e.printStackTrace();
                        log.error("生成令牌失败 令牌桶当前容量:" + tokenBucket.size());
                        //不再继续添加令牌
                        continue;
                    }
                }

                try {
                    Thread.sleep(generateSleepTime * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        //新启动一个线程 作为请求流量并且处理
        new Thread(() -> {
            while (true) {
                //模拟获取令牌
                String token = System.currentTimeMillis() + "获取令牌" + tokenBucket.poll();
                if (StringUtils.isEmpty(token)) {
                    //令牌为null 拒绝访问
                    log.warn("无令牌 禁止访问~");
                } else {
                    //存在令牌 允许访问 此处直接打印令牌
                    log.info(tokenBucket.size()+"::允许访问:::" + token);
                }


                try {
                    Thread.sleep(outputSleepTime * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        Thread.sleep(1000000L);

    }


}

总结

令牌桶 通过控制令牌数量 来达到控制请求频率 之前没咋用过
不过 我看到更多的是在流量标记分析上用令牌桶的多 例如qos
在一些特定业务中 也有类似令牌桶算法的套路