阅读 46

『超级架构师』图码实战限流算法(二)

Hello 大家好,我是l拉不拉米,在我的『超级架构师』专栏上一篇文章 《图码实战限流算法(一)》中,我们通过图解 + 代码的形式讲解了两种常用的限流算法:固定时间窗口和滑动时间窗口算法。

今天继续讲解另外两种限流算法:漏桶算法和令牌桶算法。

漏桶算法

漏桶算法面对限流,就更加的柔性,不存在直接的粗暴拒绝。

rateLimiter-4

算法分析

它的原理很简单,可以认为就是注水漏水的过程。往漏桶中以任意速率流入水,以固定的速率流出水。当水超过桶的容量时,会被溢出,也就是被丢弃。因为桶容量是不变的,保证了整体的速率。

  • 流入的水滴,可以看作是访问系统的请求,这个流入速率是不确定的。

  • 桶的容量一般表示系统所能处理的请求数。

  • 如果桶的容量满了,就达到限流的阀值,就会丢弃水滴(拒绝请求)

  • 流出的水滴,是恒定过滤的,对应服务按照固定的速率处理请求。

伪代码

    /**      * 限流工具初始化系统时间      */     private long currentTime = System.currentTimeMillis();          /**      * 漏桶当前水量      */     private long water = 0;     /**      * 漏桶流出速率      */     private long leakyRate = 1;     /**      * 漏桶容量      */     private long leakyCapacity = 100;     /**      * 限流-漏桶算法      * 以固定速度流出,以任意速度流入,达到最大值则触发限流      */     public boolean leakyBucketAlgorithm() {         long now = System.currentTimeMillis();         water = Math.max(0, water - (now - currentTime) * leakyRate);         currentTime = now;         if (water <= leakyCapacity) {             water++;             return true;         } else {             return false;         }     } 复制代码

优缺点

在正常流量的时候,系统按照固定的速率处理请求,是我们想要的。但是面对突发流量的时候,漏桶算法还是循规蹈矩地处理请求,这就不是我们想看到的啦。流量变突发时,我们肯定希望系统尽量快点处理请求,提升用户体验嘛。

令牌桶算法

面对突发流量的时候,我们可以使用令牌桶算法限流。

rateLimiter-5

算法分析

  • 有一个令牌管理员,根据限流大小,定速往令牌桶里放令牌。

  • 如果令牌数量满了,超过令牌桶容量的限制,那就丢弃。

  • 系统在接受到一个用户请求时,都会先去令牌桶要一个令牌。如果拿到令牌,那么就处理这个请求的业务逻辑;

  • 如果拿不到令牌,就直接拒绝这个请求。

伪代码

    /**      * 限流工具初始化系统时间      */     private long currentTime = System.currentTimeMillis();     /**      * 令牌生成速率      */     private long tokenRate = 1;     /**      * 令牌桶容量      */     private long tokenCapacity = 100;     /**      * 令牌桶当前令牌数      */     private long token = 0;     /**      * 限流-令牌桶算法      * 以固定速度往桶内放入令牌,以任意速度拿出令牌,令牌为空则触发限流      */     public boolean tokenBucketAlgorithm() {         long now = System.currentTimeMillis();         token = Math.min(tokenCapacity, token + (now - currentTime) * tokenRate);         currentTime = now;         if (token < 1) {             return false;         } else {             token--;             return true;         }     } 复制代码

优缺点

如果令牌发放的策略正确,这个系统即不会被拖垮,也能提高机器的利用率。Guava的RateLimiter限流组件,就是基于令牌桶算法实现的。


作者:l拉不拉米
链接:https://juejin.cn/post/7028778945390575653


文章分类
代码人生
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐