3分钟视频看懂令牌桶算法
视频介绍令牌桶,分析令牌桶原理和代码实现
https://www.bilibili.com/vide...
你好,我是好刚,这一讲我们来了解令牌桶(Token Bucket)。
先想象有一个木桶,系统按照固定速率,例如10ms 每次,往桶里加入Token,如果桶已经满了就不再添加。新请求来临时,会各自拿走一个Token,如果没有Token 就拒绝服务。这里如果一段时间没有请求时,桶内就会积累一些token,下次一旦有突发流量,只要token 足够,也能一次处理。
总结下令牌桶算法的特点,令牌桶即可以控制进入系统的请求请求量,同时允许突发流量。
在秒杀活动中,用户的请求速率是不固定的,这里我们假定为10r/s,令牌按照5个每秒的速率放入令牌桶,桶中最多存放20个令牌,那系统就只会允许持续的每秒处理5 个请求,或者每隔4 秒,等桶中20 个令牌攒满后,一次处理20个请求的突发情况,保证系统稳定性。
伪代码实现:
rate = 5.0; // unit: messages per = 8.0; // unit: seconds allowance = rate; // unit: messages last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds when (message_received): current = now(); time_passed = current - last_check; last_check = current; allowance += time_passed * (rate / per); if (allowance > rate): allowance = rate; // throttle if (allowance < 1.0): discard_message(); else: forward_message(); allowance -= 1.0;
令牌通算法PHP 实现
//速度 桶大小 / 时间段 $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; }
参考资料
相关推荐
cyhbrilliant 2020-10-16
campwin 2020-08-16
清溪算法 2020-02-12
Happyunlimited 2019-11-16
yingrenzhe 2019-11-08
闫新宇 2017-05-10
dushine00 2019-07-01
wuxiaosi0 2019-07-01
wuxiaosi0 2019-06-29
Broadview 2019-06-28
WindChaser 2019-06-27
bamboocqh 2019-04-27
sdwylry 2018-12-12
张小染 2019-04-17
yhguo00 2018-03-21
StrongHYQ 2019-03-05
纬纬 2018-05-17