8分钟视频看懂限流算法

MAX_zuo 发布于2019-07-01 10:16 / 1435人阅读

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

视频介绍限流算法，分析漏桶算法和令牌算法的应用场景，算法原理和算法实现方法

【视频在这里】 8分钟看懂限流算法

你好，我是好刚，这一讲我们来了解限流算法 (Rate Limiting Throttling)。

1. 应用场景

首先我们看一个典型的应用场景，比如在商品抢购的场景里面，可能会有百万级别的用户请求我们的抢购接口。

这个时候如果不做任何保护措施，服务器就会承受很大的处理压力，请求量很高，服务器负载也很高，并且当请求超过服务器承载极限的时候，系统就会崩溃，导致所有人都不能访问。为了保证抢购服务的可用性，一个常用的办法是对秒杀请求进行限流，拦截掉大部分请求，只允许一部分请求真正进入后端服务器，这样就可以防止大量请求造成系统压力过大导致的系统崩溃，从而保护服务正常可用。这里限流的常用算法有漏桶算法和令牌桶算法。

2. 漏桶算法

我们先来看漏桶算法（Leaky Bucket），先想象有一个木桶，新请求就像水滴一样，不断地滴进来，水滴进来的速度是不确定的，有时会快一点，有时会慢一点，同时桶底下有个洞，可以按照固定的速度把水漏走，如果水进来的速度比漏走的快，桶就会满了，桶满了水就会漫出来，对应的就是拒绝请求。

漏桶算法的主要特点是可以平滑网络上的突发流量，请求可以被整形成稳定的流量。

算法伪代码如下：

C               // 水桶总容量
r               // 漏水速度
at              // 上一个请求时间
w               // 当前桶里面的水量

when (b):
      bt = now();
      wb = (bt - at) * r  // 已经流出的水
     w = max(w - wb, 0)  // 桶里面的水量减去流走的水量等于当前水量，最多流干等于0

    if w < C:           // 水桶还没满，可以继续添加
        w ++;
        return true
    else:
        return false

3. 令牌桶算法

我们再看下令牌桶算法（Token Bucket）。也是先有一个木桶，系统按照固定速度，往桶里加入Token，如果桶已经满了就不再添加。当有请求到来时，会各自拿走一个Token，取到Token 才能继续进行请求处理，没有Token 就拒绝服务。

这里如果一段时间没有请求时，桶内就会积累一些Token，下次一旦有突发流量，只要Token 足够，也能一次处理。所以令牌桶算法的特点是允许突发流量。

我们看一个例子，看看令牌桶如何允许突发流量，假如令牌则按照每秒5 个的速度放入令牌桶，桶中最多存放20 个令牌，那系统可以支持两种类型的请求流量，一种是允许持续的每秒处理5 个请求，第二种是每隔4 秒，等桶中20 个令牌攒满后，就可以处理一次有20 个请求的突发情况。

算法伪代码如下:

C   // 水桶总容量
r   // 添加令牌速度
at = // 上一个请求时间
w   // 当前令牌数

when (b):
    bt = now()
    wb = (bt - at) * r    // 两次请求期间新增的Token
    w = min(w + wb, C)    // 上一个请求剩余的Token 数加上新增的剩余数不能超过木桶的总容量

    if (w > 1.0):
        w --              // 令牌足够，可以处理请求并且将令牌数减一
        return true
    else:
        return false

4. 两种算法比较

最后我们对比下漏桶算法和令牌桶算法。其实在实现上，两种算法是效果一样但方向相反的算法。

漏桶算法是请求流入的速度不确定，有时快有时慢，是存在突发情况的；但是请求流出的速度是固定的，它是流入会有突发情况，但是流出速度固定。

令牌桶算法就是固定的Token 流入速度，一个Token 代表一个请求可以被处理的机会；当系统有一段空闲时间之后，桶内有足够的token，这样可以处理突发的请求流量，它是流入速度固定，但是流出不固定。

总结下特点：漏桶算法因为流出速度固定，可以用来整流，无论你流入速率多大，我都按照固定的速度去处理。令牌桶算法的特点则是，支持突发情况，两种算法在实际使用时，应该根据具体场景灵活选用。

限流算法就介绍到这，我是好刚，好刚用在刀刃上。如果讲解对你有帮助，那就请你帮忙转发吧。

5. 令牌通算法实现

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

https://en.wikipedia.org/wiki/Leaky_bucket

PHP Rate Limiting Library With Token Bucket Algorithm

Rate Limiter

https://www.cnblogs.com/haoxinyue/p/6792309.html

https://github.com/yangwenmai/ratelimit

https://blog.52itstyle.com/ar...

云服务器 GPU云服务器微信发10分钟以上视频微信怎么发10分钟视频电话视频通话多少钱一分钟微信怎么发10分钟视频给好友

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

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

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

摘要：视频介绍令牌桶，分析令牌桶原理和代码实现你好，我是好刚，这一讲我们来了解令牌桶。总结下令牌桶算法的特点，令牌桶即可以控制进入系统的请求请求量，同时允许突发流量。视频介绍令牌桶，分析令牌桶原理和代码实现 https://www.bilibili.com/vide... 你好，我是好刚，这一讲我们来了解令牌桶（Token Bucket）。先想象有一个木桶，系统按照固定速率，例如10ms...

novo 2019-07-01 10:17 评论0 收藏0
分布式系统关注点——想通关「限流」？只要这一篇

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

CollinPeng 2019-08-16 13:57 评论0 收藏0
大型网站限流算法的实现和改造

摘要：涉及变量接口时间单位允许访问多少次递增间隔时间递增步长当前可访问次数的访问时间当前时间参照漏桶算法需要注意的点条件一线程一存在不能访问添加，设置为线程二过去时间所有的条件二参考计算器算法条件二实现。算法升级参考漏桶算法升级实现。最近写了一个限流的插件，所以避免不了的接触到了一些限流算法。本篇文章就来分析一下这几种常见的限流算法分析之前依我个人的理解来说限流的话应该灵活到可以针对...

DC_er 2019-08-19 11:16 评论0 收藏0
接口限流的常用算法汇总

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

gyl_coder 2019-06-27 15:37 评论0 收藏0