漏桶算法与令牌桶算法
https://www.cnblogs.com/xuwc/p/9123078.html
https://www.cnblogs.com/xuwc/p/9123078.html
http://www.seedblog.cn/article_details/488
漏桶算法
概念
漏桶算法，又称leaky bucket。为了理解漏桶算法，我们看一下对于该算法的示意图：
从图中我们可以看到，整个算法其实十分简单。首先，我们有一个固定容量的桶(请求数控制)，有水流进来(应用中的请求)，也有水流出去(处理请求)。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出(多余请求不处理)。
这样在并发多的情况下，会丢弃很多请求。
实现
php
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
|
/**
* [leaky php实现漏桶算法]
* @Author [NiuShao <camel_niu@163.com> <qq:370574131>]
* @DateTime 2020-06-26
* @param [type] $contain [int 桶的总容量]
* @param [type] $addNum [int 每次注入桶中的水量]
* @param [type] $leakRate [int 桶中漏水的速率,秒为单位。例如2/s,3/s]
* @param integer &$water [int 当前水量]
* @param integer &$preTime [int 时间戳,记录的上次漏水时间]
* @return [type] [bool,返回可否继续注入true/false]
*/
function leaky($contain,$addNum,$leakRate,&$water=0,&$preTime=0)
{
//参数赋值
//首次进入默认当前水量为0
$water = empty($water) ? 0 : $water;
//首次进入默认上次漏水时间为当前时间
$preTime = empty($water) ? time() : $preTime;
$curTime = time();
//上次结束到本次开始，流出去的水
$leakWater = ($curTime-$preTime)*$leakRate;
//上次结束时候的水量减去流出去的水，也就是本次初始水量
$water = $water-$leakWater;
//水量不可能为负，漏出大于进入则水量为0
$water = ( $water>=0 ) ? $water : 0 ;
//更新本次漏完水的时间
$preTime = $curTime;
//水小于总容量则可注入，否则不可注入
if( ($water+$addNum) <= $contain ){
$water += $addNum;
return true;
}else{
return false;
}
}
/**
* 测试
* @var integer
*/
for($i=0;$i<500;$i++){
$res = leaky(50,1,5,$water,$timeStamp);
var_dump($res);
usleep(50000);
}
#############实现2#######################
//速度 桶大小 / 时间段
$rate = $maxRequests / $period;
$t_key = $keyTime($id); //最后一次获取令牌时间
$a_key = $keyAllow($id); //已有令牌数
//判断是否有最后一次获取令牌记录
if ($cache->exists($t_key)) {
$c_time = time();
//计算上一次获取令牌到现在过去的时间
$time_passed = $c_time - $cache->get($t_key);
$cache->set($t_key, $c_time, $ttl);
//获取桶中令牌数
$allow = $cache->get($a_key);
$allow += $time_passed * $rate; //加上最后一次消费令牌到现在期间增长的令牌数
//令牌数不能超过最大数
if ($allow > $maxRequests) {
$allow = $maxRequests;
}
//使用的令牌数不能超过最大限制
if ($allow < $use) {
$cache->set($a_key, $allow, $ttl);
return 0;
} else {
//消费令牌
$cache->set($a_key, $allow - $use, $ttl);
return (int) ceil($allow);
}
} else {
//记录当前时间为最后一次处理时间，用于下次使用
$cache->set($t_key, time(), $ttl);
//没有令牌时按照最大令牌数处理
$cache->set($a_key, $maxRequests - $use, $ttl);
return $maxRequests;
}
|
令牌桶算法
概念
为了更形象了解该算法，我们看一下该算法的示意图：
\
令牌桶算法的原理是系统以恒定的速率产生令牌，然后把令牌放到令牌桶中，令牌桶有一个容量，当令牌桶满了的时候，再向其中放令牌，那么多余的令牌会被丢弃；当想要处理一个请求的时候，需要从令牌桶中取出一个令牌，如果此时令牌桶中没有令牌，那么则拒绝该请求。
实现
php实现
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
class TrafficShaperController extends Controller
{
/**
* 令牌桶总数量
* @var int
*/
private $totleNum = 25;
/**
* 令牌标识（可以根据需要加上关键ID，uid、orderid...）
* @var string
*/
private $quekueName ="TrafficShaper_queue";
/**
* redis缓存类
* @var object
*/
private $redis;
/**
* 初始化方法
*
* @author heyw<1051834593@qq.com>
* @since 2020/12/10
*/
public function _initialize()
{
$this->redis = Redis::getInstance();
}
/**
* 模拟用户消耗令牌
*
* @param int $num
* @author heyw<1051834593@qq.com>
* @since 2020/12/10
*/
public function run($num = 1)
{
// 初始化
$this->reset();
// 模拟1s请求10次
while (1) {
$this->getKey();
sleep(0.1);
}
}
/**
* 获取令牌
*
* @return bool
* @author heyw<1051834593@qq.com>
* @since 2020/12/11
*/
protected function getKey()
{
// 初始化
$redis = $this->redis;
$queueName = $this->quekueName;
// 获取一个令牌，如果没有直接返回
$res = $redis->rPop($queueName);
// 获得令牌，处理业务
var_dump($res ?'get it' : 'empty');
return true;
}
/**
* 重置
*
* @author heyw<1051834593@qq.com>
* @since 2020/12/11
*/
protected function reset()
{
$this->redis->delete($this->quekueName);
$this->add(25);
}
/**
* 定时加入令牌桶，1s执行1次
*
* @author heyw<1051834593@qq.com>
* @since 2020/12/10
*/
public function add($stepNum = 5)
{
// 初始化
$redis = $this->redis;
$queueName = $this->quekueName;
// 当前令牌书
$currNum = $redis->lSize($queueName) ?: 0;
$maxNum = $this->totleNum;
$addNum = $maxNum >= $currNum + $stepNum ? $stepNum : $maxNum - $currNum;
if ($addNum == 0) {
return true;
}
// 加入令牌
$token = array_fill(0, $addNum, 1);
$redis->lPush($queueName, $token);
return true;
}
}
|
go实现
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
|
package main
import (
"fmt"
"time"
)
var (
lastRequestTime int64 = time.Now().Unix()
tokenSurplus int64 = 0
qps int64 = 5
)
func getMin(a, b int64) int64 {
if a > b {
return b
}
return a
}
func getToken() bool {
now := time.Now().Unix()
temp := (now-lastRequestTime)*qps + tokenSurplus
tokenNow := getMin(temp, qps)
if tokenNow > 0 {
lastRequestTime = now
tokenSurplus--
return true
}
return false
}
func main() {
fmt.Println(time.Now().Unix())
}
|
https://blog.csdn.net/HapplyFox/article/details/115458867
对比
令牌桶和漏桶对比：
- 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
- 漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
- 令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
- 漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
- 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；
- 两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。
概述
在大量并发的环境下，为了防止由于请求暴涨，导致系统崩溃从而引起雪崩，一般会对流量做一定的限制操作。比如等待、排队、降级、拒绝服务、限流等
说明
主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量
