您当前的位置:首页 > 电脑百科 > 程序开发 > 框架

Spring Boot 的接口限流算法优缺点深度分析

时间:2020-12-15 11:50:11  来源:  作者:

前言

在一个高并发系统中对流量的把控是非常重要的,当巨大的流量直接请求到我们的服务器上没多久就可能造成接口不可用,不处理的话甚至会造成整个应用不可用。

那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了就没了。通过限流,我们可以很好地控制系统的qps,从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。

算法介绍

计数器法

计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定,对于A接口来说,我们1分钟的访问次数不能超过100个。那么我们可以这么做:在一开始的时候,我们可以设置一个计数器counter,每当一个请求过来的时候,counter就加1,如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内,那么说明请求数过多;如果该请求与第一个请求的间隔时间大于1分钟,且counter的值还在限流范围内,那么就重置counter,具体算法的示意图如下:

Spring Boot 的接口限流算法优缺点深度分析

 

具体的伪代码如下:

public class CounterDemo {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 60000; // 时间窗口ms
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

这个算法虽然简单,但是有一个十分致命的问题,那就是临界问题,我们看下图:

Spring Boot 的接口限流算法优缺点深度分析

 

从上图中我们可以看到,假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么其实这个用户在1秒里面,瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求,也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求,可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞,瞬间压垮我们的应用。

聪明的朋友可能已经看出来了,刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢?或者说,如何将临界问题的影响降低呢?我们可以看下面的滑动窗口算法。

滑动窗口

滑动窗口,又称rolling window。为了解决这个问题,我们引入了滑动窗口算法。如果学过TCP网络协议的话,那么一定对滑动窗口这个名词不会陌生。下面这张图,很好地解释了滑动窗口算法:

Spring Boot 的接口限流算法优缺点深度分析

 

在上图中,整个红色的矩形框表示一个时间窗口,在我们的例子中,一个时间窗口就是一分钟。然后我们将时间窗口进行划分,比如图中,我们就将滑动窗口划成了6格,所以每格代表的是10秒钟。每过10秒钟,我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter,比如当一个请求在0:35秒的时候到达,那么0:30~0:39对应的counter就会加1。

那么滑动窗口怎么解决刚才的临界问题的呢?我们可以看上图,0:59到达的100个请求会落在灰色的格子中,而1:00到达的请求会落在橘黄色的格子中。当时间到达1:00时,我们的窗口会往右移动一格,那么此时时间窗口内的总请求数量一共是200个,超过了限定的100个,所以此时能够检测出来触发了限流。

我再来回顾一下刚才的计数器算法,我们可以发现,计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分,为60s。

由此可见,当滑动窗口的格子划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

public class CounterDemo {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 6000; // 时间窗口6ms,6格
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

漏桶算法

漏桶算法,又称leaky bucket。为了理解漏桶算法,我们看一下对于该算法的示意图:

Spring Boot 的接口限流算法优缺点深度分析

 

从图中我们可以看到,整个算法其实十分简单。首先,我们有一个固定容量的桶,有水流进来,也有水流出去。对于流进来的水来说,我们无法预计一共有多少水会流进来,也无法预计水流的速度。但是对于流出去的水来说,这个桶可以固定水流出的速率。而且,当桶满了之后,多余的水将会溢出。

我们将算法中的水换成实际应用中的请求,我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法,我们可以保证接口会以一个常速速率来处理请求。所以漏桶算法天生不会出现临界问题。具体的伪代码实现如下:

public class LeakyDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public Long water; // 当前水量(当前累积请求数)
    public boolean grant() {
        long now = getNowTime();
        water = Math.max(0L, water - (now - timeStamp) * rate); // 先执行漏水,计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        }
        else {
            // 水满,拒绝加水
            return false;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

令牌桶算法

令牌桶算法,又称token bucket。为了理解该算法,我们再来看一下算法的示意图:

Spring Boot 的接口限流算法优缺点深度分析

 

从图中我们可以看到,令牌桶算法比漏桶算法稍显复杂。首先,我们有一个固定容量的桶,桶里存放着令牌(token)。桶一开始是空的,token以一个固定的速率r往桶里填充,直到达到桶的容量,多余的令牌将会被丢弃。每当一个请求过来时,就会尝试从桶里移除一个令牌,如果没有令牌的话,请求无法通过。

具体的伪代码实现如下:

public class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public Long tokens; // 当前令牌数量
    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = Math.min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若不到1个令牌,则拒绝
            return false;
        }
        else {
            // 还有令牌,领取令牌
            tokens -= 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

RateLimiter实现

对于令牌桶的代码实现,可以直接使用Guava包中的RateLimiter。

@Slf4j
public class RateLimiterExample1 {

    // 代表每秒最多2个
    // guava限流采用的是令牌桶的方式
    private static RateLimiter rateLimiter = RateLimiter.create(2);

    public static void main(String[] args) {
        for (int index = 0; index < 100; index++) {
            // 单位时间内获取令牌
            if (rateLimiter.tryAcquire(190, TimeUnit.MILLISECONDS)) {
                handle(index);
            }
        }
    }
    private static void handle(int i) {
        log.info("{}", i);
    }

相关变种

若仔细研究算法,我们会发现我们默认从桶里移除令牌是不需要耗费时间的。如果给移除令牌设置一个延时时间,那么实际上又采用了漏桶算法的思路。google的guava库下的SmoothWarmingUp类就采用了这个思路。

临界问题

我们再来考虑一下临界问题的场景。在0:59秒的时候,由于桶内积满了100个token,所以这100个请求可以瞬间通过。但是由于token是以较低的速率填充的,所以在1:00的时候,桶内的token数量不可能达到100个,那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问题。下图比较了计数器(左)和令牌桶算法(右)在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率,但是下一个突发速率必须要等桶内有足够的token后才能发生:

Spring Boot 的接口限流算法优缺点深度分析

 

总结

计数器 VS 滑动窗口

计数器算法是最简单的算法,可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器(每一个格子存一份),所以滑动窗口在实现上需要更多的存储空间。也就是说,如果滑动窗口的精度越高,需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法,取走token是不需要耗费时间的,也就是说,假设桶内有100个token时,那么可以瞬间允许100个请求通过。

令牌桶算法由于实现简单,且允许某些流量的突发,对用户友好,所以被业界采用地较多。当然我们需要具体情况具体分析,只有最合适的算法,没有最优的算法。

 

原文:《Spring Boot的接口限流应用》

https://my.oschina.net/loubobooo/blog/1796752



Tags:Spring Boot   点击:()  评论:()
声明:本站部分内容来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
前言在一个高并发系统中对流量的把控是非常重要的,当巨大的流量直接请求到我们的服务器上没多久就可能造成接口不可用,不处理的话甚至会造成整个应用不可用。那么何为限流呢?顾...【详细内容】
2020-12-15   Spring Boot  点击:(0)  评论:(0)  加入收藏
对于高性能的 RPC 框架,Netty 作为异步通信框架,几乎成为必备品。例如,Dubbo 框架中通信组件,还有 RocketMQ 中生产者和消费者的通信,都使用了 Netty。今天,我们来看看 Netty 的基...【详细内容】
2020-12-14   Spring Boot  点击:(3)  评论:(0)  加入收藏
可以先释放容器分配给请求的线程与相关资源,减轻系统负担,释放了容器所分配线程的请求,其响应将被延后,可以在耗时处理完成(例如长时间的运算)时再对客户端进行响应。...【详细内容】
2020-12-11   Spring Boot  点击:(4)  评论:(0)  加入收藏
今天继续为大家分享在工作中如何优雅的校验接口的参数的合法性以及如何统一处理接口返回的json格式。每个字都是干货,原创不易,分享不易。 validation主要是校验用户提交的数...【详细内容】
2020-11-19   Spring Boot  点击:(17)  评论:(0)  加入收藏
最近发现 Spring Boot 本地不能 Debug 调试了,原来 Spring Boot 升级后,对应插件的命令参数都变了,故本文做一个升级。背景:Spring Boot 项目在使用 Spring Boot Maven 插件执行...【详细内容】
2020-11-11   Spring Boot  点击:(5)  评论:(0)  加入收藏
Kafka集群安装、配置和启动Kafka需要依赖zookeeper,并且自身集成了zookeeper,zookeeper至少需要3个节点保证集群高可用,下面是在单机linux下创建kafka3个节点伪集群模式。1、下...【详细内容】
2020-11-10   Spring Boot  点击:(3)  评论:(0)  加入收藏
建立多语言网站,可以获得更多用户流量。多语言网站被称为国际化(i18n),与本地化相反。你比如京东、淘宝这类电商网站就是国际化的电商网站,它支持多国语言。注意: 国际化是一个由...【详细内容】
2020-09-03   Spring Boot  点击:(6)  评论:(0)  加入收藏
松哥最近在研究 Spring Security 源码,发现了很多好玩的代码,抽空写几篇文章和小伙伴们分享一下。很多人吐槽 Spring Security 比 Shiro 重量级,这个重量级不是凭空来的,重量有...【详细内容】
2020-09-02   Spring Boot  点击:(6)  评论:(0)  加入收藏
SpringBoot 有两个关键元素:@SpringBootApplicationSpringApplication 以及 run() 方法 SpringApplication 这个类应该算是 Spring Boot 框架的“创新”产物了,原始的 Spring...【详细内容】
2020-08-12   Spring Boot  点击:(4)  评论:(0)  加入收藏
只要你用Springboot,一定会用到各种spring-boot-starter。其实写一个spring-boot-starter...【详细内容】
2020-08-10   Spring Boot  点击:(8)  评论:(0)  加入收藏
我们学会了如何使用Spring Boot使用进程内缓存在加速数据访问。可能大家会问,那我们在Spring Boot中到底使用了什么缓存呢?在Spring Boot中通过@EnableCaching注解自动化配置...【详细内容】
2020-07-16   Spring Boot  点击:(12)  评论:(0)  加入收藏
Spring Boot 配置文件加解密原理就这么简单背景接上文《失踪人口回归,mybatis-plus 3.3.2 发布》[1] ,提供了一个非常实用的功能 「数据安全保护」 功能,不仅支持数据源的配置...【详细内容】
2020-06-02   Spring Boot  点击:(9)  评论:(0)  加入收藏
找不到配置?配置不对?配置被覆盖?Spring Boot 配置加载过程解析:1、Spring Boot 配置的加载有着约定俗成的步骤: 从 resources 目录下加载 application.properties/applicatio...【详细内容】
2020-05-25   Spring Boot  点击:(25)  评论:(0)  加入收藏
前后端分离已经在慢慢走进各公司的技术栈,根据松哥了解到的消息,不少公司都已经切换到这个技术栈上面了。即使贵司目前没有切换到这个技术栈上面,松哥也非常建议大家学习一下前...【详细内容】
2020-03-31   Spring Boot  点击:(7)  评论:(0)  加入收藏
Spring Boot 算是目前 Java 领域最火的技术栈了,除了书呢?当然就是开源项目了,今天整理15个开源领域非常不错的Spring Boot项目供大家学习,参考。高富帅的路上只能帮你到这里了,...【详细内容】
2020-03-31   Spring Boot  点击:(7)  评论:(0)  加入收藏
在我们实际工作中,总会遇到这样需求,在项目启动的时候需要做一些初始化的操作,比如初始化线程池,提前加载好加密证书等。今天就给大家介绍一个 Spring Boot 神器,专门帮助大家解...【详细内容】
2019-12-26   Spring Boot  点击:(40)  评论:(0)  加入收藏
如果这两天登录 https://start.spring.io/ 就会发现,Spring Boot 默认版本已经升到了 2.1.0。这是因为 Spring Boot 刚刚发布了 2.1.0 版本,我们来看下 Spring Boot 2 发布以...【详细内容】
2019-12-26   Spring Boot  点击:(26)  评论:(0)  加入收藏
这篇文章介绍如何使用 Jpa 和 Thymeleaf 做一个增删改查的示例。先和大家聊聊我为什么喜欢写这种脚手架的项目,在我学习一门新技术的时候,总是想快速的搭建起一个 Demo 来试试...【详细内容】
2019-12-25   Spring Boot  点击:(37)  评论:(0)  加入收藏
使用了注解的方式进行对接口防刷的功能,非常高大上,本文章仅供参考 一,技术要点:springboot的基本知识,redis基本操作,...【详细内容】
2019-12-25   Spring Boot  点击:(29)  评论:(0)  加入收藏
1.环境目前开发的项目使用的spring boot(2.1.4.RELEASE)+ssm2. 需求现在有一个数据处理任务的接口,在spring boot项目启动后,可以手动的去启动任务,但是这样比较麻烦,每次项...【详细内容】
2019-10-10   Spring Boot  点击:(47)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条