三种常见的限流算法(漏桶、令牌桶、滑动窗口)_fedorafrog的博客-程序员秘密_限流算法之漏桶算法、令牌桶算法

技术标签: 架构设计  

在开发高并发系统时,有三把利器用来保护系统:缓存、降级和限流。那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了就没了。通过限流,我们可以很好地控制系统的qps,从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。

1. 令牌桶算法

令牌桶算法是比较常见的限流算法之一,大概描述如下:

  1. 所有的请求在处理之前都需要拿到一个可用的令牌才会被处理;
  2. 根据限流大小,设置按照一定的速率往桶里添加令牌;
  3. 桶设置最大的放置令牌限制,当桶满时、新添加的令牌就被丢弃或者拒绝;
  4. 请求达到后首先要获取令牌桶中的令牌,拿着令牌才可以进行其他的业务逻辑,处理完业务逻辑之后,将令牌直接删除;
  5. 令牌桶有最低限额,当桶中的令牌达到最低限额的时候,请求处理完之后将不会删除令牌,以此保证足够的限流;

实现思路:可以准备一个队列,用来保存令牌,另外通过一个线程池定期生成令牌放到队列中,每来一个请求,就从队列中获取一个令牌,并继续执行。

幸运的是,通过Google开源的guava包,我们可以很轻松的创建一个令牌桶算法的限流器。

<dependency>
 
   <groupId>com.google.guava</groupId>
 
   <artifactId>guava</artifactId>
 
   <version>18.0</version>
 
</dependency>

通过RateLimiter类的create方法,创建限流器。

public class RateLimiterMain {
 
   public static void main(String[] args) {
 
       RateLimiter rateLimiter = RateLimiter.create(10);
 
       for (int i = 0; i < 10; i++) {
 
           new Thread(new Runnable() {
 
               @Override
 
               public void run() {
 
                   rateLimiter.acquire()
 
                   System.out.println("pass");
 
               }
 
           }).start();
 
       }
 
   }
 
}

其实Guava提供了多种create方法,方便创建适合各种需求的限流器。在上述例子中,创建了一个每秒生成10个令牌的限流器,即100ms生成一个,并最多保存10个令牌,多余的会被丢弃。

rateLimiter提供了acquire()和tryAcquire()接口 :

  1. 使用acquire()方法,如果没有可用令牌,会一直阻塞直到有足够的令牌。
  2. 使用tryAcquire()方法,如果没有可用令牌,就直接返回false。
  3. 使用tryAcquire()带超时时间的方法,如果没有可用令牌,就会判断在超时时间内是否可以等到令牌,如果不能,就返回false,如果可以,就阻塞等待。

2. 漏桶算法

漏桶算法其实很简单,可以粗略的认为就是注水漏水过程,往桶中以一定速率流出水,以任意速率流入水,当水超过桶流量则丢弃,因为桶容量是不变的,保证了整体的速率。

在算法实现方面,可以准备一个队列,用来保存请求,另外通过一个线程池定期从队列中获取请求并执行,可以一次性获取多个并发执行。

这种算法,在使用过后也存在弊端:无法应对短时间的突发流量

3. 滑动窗口

3.1 计数器算法

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

具体的伪代码如下:

public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }

    public long getNowTime() {
        return System.currentTimeMillis();
    }
}

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

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

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

3.2 滑动窗口算法

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

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

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

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

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fedorafrog/article/details/114846084

智能推荐

Qt学习 之 音乐播放器(加载本地视频、播放、暂停、移动滑块)_dlut_yan的博客-程序员秘密

.pro文件:#-------------------------------------------------## Project created by QtCreator 2018-07-21T15:46:29##-------------------------------------------------QT += core guigreaterThan(...

CondaHTTPError: HTTP 000 CONNECTION FAILED for url <https://repo.anaconda.com/pkgs/main/linux-64/cur_顾文繁的博客-程序员秘密

以前的贴子真的是不能太相信,太坑爹了,搞了一下午,在linux上配置conda环境时,直接贴了,不注意后面对应的平台(linux-32/linux-64/linux- armv6l/l inux-a rmv7l /linux -ppc64le/noarch/osx-32/OSX- 64/OSX- arm64/win-32/win-64/)查看自己的平台,在清华源后面加上就行了。CondaHTTPError: HTTP 000 CONNECTION FAILED for url

kettle表更新、插入更新、裁剪表_weixin_49708329的博客-程序员秘密_kettle裁剪表什么意思

定义表更新:就是把数据库已经存在的记录与数据流里面的记录进行对比,如果不同就进行更新。插入更新:就是把数据库已经存在的记录与数据流里面的记录进行对比,如果不同就进行更新,如果记录不存在,则会插入数据。裁剪表:就是将数据表中的信息全部清除,保留表的基本结构。实操:插入更新...

谈谈Processing 3D世界 一_小羽是个二狗子的博客-程序员秘密

Processing起初给人的映像是处理2D的一款优秀的软件。但其实抛开引用OpenGL不说,它也有一套完备的处理3D的方法。有兴趣的朋友可以一起来研究研究。好,前言少叙。我们直接开始正题:3D编程世界的hello world,先来一发!

ruby 语法的总结_sanshi0815的博客-程序员秘密

没有函数,用了半天的时间弄环境,用了半天的时间熟悉语法,函数可以自己去查手册函数查的网页在http://www.rubycentral.com/ref/index.html 函数库官方站在http://www.ruby-lang.org/编写工具在 win下使用http://homepage2.nifty.com/sakazuki/rde_e.htmlclass A  def initialize

Android JNI 删除文件和遍历文件夹并删除文件夹下的文件_安卓兼职framework应用工程师的博客-程序员秘密

对操作文件也是在开发中常用的事情,下面对删除文件和文件夹下的文件做个笔记1.删除文件extern "C" JNIEXPORT int JNICALLJava_com_xinrui_ndkapp_MainActivity_deletefile(JNIEnv *env, jobject instance, jstring str) { const char *str_path = env-&gt;GetStringUTFChars(str, JNI_FALSE);//本地代码绝不能修改字符串的内容

随便推点

嵌入式ARM交叉编译器安装_justloong的博客-程序员秘密_arm内核编译器

1、开发平台虚拟机:VirtualBox操作系统:Ubuntu 16.04 64bit2、准备ARM交叉编译工具包    编译uboot和linux kernel都需要ARM交叉工具链支持,这里使用Linaro提供的交叉编译工具。下载地址为:https://releases.linaro.org注意:如果主机是64bit,请选择64位的交叉编译器工具链,32bit的主机选择32

ART深入浅出5--了解Dex文件格式(2)_漂流的代码的博客-程序员秘密

本节介绍ClassDef的格式。ClassDef是Dex文件内部表示一个类的结构。包含了类的基本数据,如类的名称,访问级别,Field列表,Method列表等信息。

5G消息如何变现?商业模式到底是怎样?_uxuepai5g的博客-程序员秘密

导语:5G消息生态能有机的运转,关键源动力在于参与的每一方均“有利可图”,作为这个游戏圈的主导者——运营商,其商业模式(收费模式)的制定对行业发展息息相关。5G消息究竟采取什么样的收费模式...

零基础入门NLP赛事-新闻文本分类记录 task1_qq_24854953的博客-程序员秘密

赛题描述数据为:匿名处理后的新闻数据。数据为新闻文本,并按照字符级别进行匿名处理。整合划分出14个候选分类类别:财经、彩票、房产、股票、家居、教育、科技、社会、时尚、时政、体育、星座、游戏、娱乐的文本数据。赛题数据由以下几个部分构成:训练集20w条样本,测试集A包括5w条样本,测试集B包括5w条样本。赛题训练数据如下:评价标准为:f1-score,显然越大越好提交结果:输出每一条test’数据所属的类别思路本质上是一个分类问题,要根据文本每一句的字符进行分类。但是赛题数据是匿名的,不能直..

记录一次IDEA2020.3中Maven导入依赖失败的问题_吃饼干の小海豚的博客-程序员秘密

IDEA2020.3中Maven导入依赖失败的问题  pom.xml已导入坐标,maven本地仓库也下载了相对应的jar包,但是在项目的libraries中却报红了,找不到对应的jar包。

halcon与QT联合:(5.2)瓶盖检测以及QT界面搭建_Upupup6的博客-程序员秘密

在上一个博客5.1中只是做了一个简单的界面,下面我们将在界面上添加按钮、添加资源、画图(包括画圆、画矩形)、管理参数(参数的自动加载与保存)1、添加按钮、添加资源(类似于软件界面上方菜单栏的设置)1.1添加那妞PS:输入后要回车(不然添加不上)顺便把右边对应的属性下:QObject下的objectName改一下:分别改为drawCircle、drawRectangle、drawRectangle2。下面操作下边对应的Action Editor:还可以右键转到槽:...