3分钟视频看懂令牌桶算法

novo 发布于2019-07-01 10:17 / 3211人阅读

摘要：视频介绍令牌桶，分析令牌桶原理和代码实现你好，我是好刚，这一讲我们来了解令牌桶。总结下令牌桶算法的特点，令牌桶即可以控制进入系统的请求请求量，同时允许突发流量。

视频介绍令牌桶，分析令牌桶原理和代码实现

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;
}

参考资料

Token bucket wiki

PHP Rate Limiting Library With Token Bucket Algorithm

云服务器 GPU云服务器令牌桶桶排序算法 webrtc漏桶算法 php给时间加3分钟

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28997.html

8分钟视频看懂限流算法

摘要：视频介绍限流算法，分析漏桶算法和令牌算法的应用场景，算法原理和算法实现方法视频在这里分钟看懂限流算法你好，我是好刚，这一讲我们来了解限流算法。这里限流的常用算法有漏桶算法和令牌桶算法。所以令牌桶算法的特点是允许突发流量。视频介绍限流算法，分析漏桶算法和令牌算法的应用场景，算法原理和算法实现方法【视频在这里】 8分钟看懂限流算法你好，我是好刚，这一讲我们来了解限流算法 (Rate ...

MAX_zuo 2019-07-01 10:16 评论0 收藏0
接口限流的常用算法汇总

摘要：接口限流的常用算法计数器法计数器法是限流算法里最简单也是最容易实现的一种算法。由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。漏桶算法漏桶算法，又称。接口限流什么是接口限流那么什么是限流呢？顾名思义，限流就是限制流量，包括并发的流量和一定时间内的总流量，就像你宽带包了1个G的流量，用完了就没了，所以控制你的使用频率和单次使用的总消耗。通过限...

gyl_coder 2019-06-27 15:37 评论0 收藏0
分布式系统关注点——想通关「限流」？只要这一篇

摘要：之前有了解到哥的一部分读者们没有充分搞清楚限流和熔断的关系。后者表示系统在同一时刻能处理的最大请求数量，比如次的并发。后续限流策略需要设定的具体标准数值就是从这些指标中来的。限流阈值不继续处理请求。如果这是第二次看到我的文章，欢迎扫描文末二维码订阅我哟~本文长度为2869字，建议阅读8分钟。可能你在网上看过不少「限流」相关的文章，但是z哥的这篇可能是最全面，最深入浅出的一篇了（容我...

CollinPeng 2019-08-16 13:57 评论0 收藏0
服务限流(自定义注解令牌桶算法)

摘要：自定义注解实现基于接口限流仔细看会发现上面的简单实现会造成我每个接口都要写一次限流方法代码很冗余所以采用来使用自定义注解来实现。服务限流 -- 自定义注解基于RateLimiter实现接口限流令牌桶限流算法showImg(https://segmentfault.com/img/bVbgTi6?w=2420&h=1547);图片来自网上令牌桶会以一个恒定的速率向固定容量大小桶...

microcosm1994 2019-08-19 11:09 评论0 收藏0
[登录那些事] 邮件发送，限流，漏桶与令牌桶

摘要：关于如何限速，有两个比较出名的算法，漏桶算法与令牌桶算法，这里对其简单介绍一下，最后再实践在我发邮件的中以下是发送邮件的，已限制为一分钟两次，你可以通过修改进行试验。前段时间，我使用了 jwt 来实现邮箱验证码的校验与用户认证与登录，还特别写了一篇文章作为总结。在那篇文章中，提到了一个点，如何限速。在短信验证码和邮箱验证码，如果不限速，被恶意攻击造成大量的 QPS，不仅拖垮了服务...

wpw 2019-08-23 17:18 评论0 收藏0