1. Toy模板网首页
  2. > Toy博客

数据结构和算法专题---4、限流算法与应用

8月前 作者：斑马工 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构和算法专题---4、限流算法与应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本章我们会对限流算法做个简单介绍，包括常用的限流算法（计数器、漏桶算法、令牌桶案发、滑动窗口）的概述、实现方式、典型场景做个说明。

什么是限流算法

限流是对系统的一种保护措施。即限制流量请求的频率（每秒处理多少个请求）。一般来说，当请求流量超过系统的瓶颈，则丢弃掉多余的请求流量，保证系统的可用性。即要么不放进来，放进来的就保证提供服务。

计数器

概述

计数器采用简单的计数操作，到一段时间节点后自动清零

实现

package com.ls.cloud.sys.alg.limit;

import com.ls.cloud.common.core.util.DateUtil;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.concurrent.*;

public class Counter {

    public static void main(String[] args) {
        //计数器，这里用信号量实现
        final Semaphore semaphore = new Semaphore(1);
        //定时器，到点清零
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                semaphore.release(1);
            }
        },3000,3000,TimeUnit.MILLISECONDS);

        //模拟无限请求从天而降降临
        while (true) {
            try {
                //判断计数器
                semaphore.acquire();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //如果准许响应，打印一个ok
            Date date = new Date();
            SimpleDateFormat dateFormat= new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
            System.out.println("执行------------"+ dateFormat.format(date));
        }
    }
}

结果分析

执行------------2023-12-05 02:17:33
执行------------2023-12-05 02:17:36
执行------------2023-12-05 02:17:39
执行------------2023-12-05 02:17:42
执行------------2023-12-05 02:17:45

优缺点

  • 优点：实现起来非常简单。
  • 缺点：控制力度太过于简略，假如1s内限制3次，那么如果3次在前100ms内已经用完，后面的900ms将只能处于阻塞状态，白白浪费掉

典型场景

使用计数器限流的场景较少，因为它的处理逻辑不够灵活。最常见的是登录验证码倒计时，60秒接收一次，如果在限流场景使用计数器，可能导致前面100ms进入全部流程，系统可能依然会出现宕机的情况。

漏桶算法

概述

漏桶算法将请求缓存在桶中，服务流程匀速处理。超出桶容量的部分丢弃。漏桶算法主要用于保护内部的处理业务，保障其稳定有节奏的处理请求，但是无法根据流量的波动弹性调整响应能力。现实中，类似容纳人数有限的服务大厅开启了固定的服务窗口。
数据结构和算法专题---4、限流算法与应用,数据结构和算法专题,算法,计数器,漏桶算法,令牌桶,滑动窗口

实现

可以基于队列进行实现。

package com.ls.cloud.sys.alg.limit;

import java.util.concurrent.*;

public class Barrel {


    public static void main(String[] args) {
        //桶，用阻塞队列实现，容量为3
        final LinkedBlockingQueue<Integer> que = new LinkedBlockingQueue(3);

        //定时器，相当于服务的窗口，2s处理一个
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                // 删除队首元素
                int v = que.poll();
                System.out.println("处理："+v);
            }
        },2000,2000,TimeUnit.MILLISECONDS);


        //无数个请求，i 可以理解为请求的编号
        int i=0;
        while (true) {
            i++;
            try {
                System.out.println("put:"+i);
                //如果是put，会一直等待桶中有空闲位置，不会丢弃
//                que.put(i);
                //等待1s如果进不了桶，就溢出丢弃
                que.offer(i,1000,TimeUnit.MILLISECONDS);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

    }

}

结果

put:1
put:2
put:3
put:4
put:5
处理：1
put:6
put:7
处理：2
put:8
put:9
处理：3
put:10
put:11
处理：5
put:12
put:13
  • put任务号按照顺序入桶
  • 执行任务匀速的2s一个被处理
  • 因为桶的容量只有3，所以1-3完美执行，4被溢出丢弃，5正常执行

优缺点

  • 优点：有效的挡住了外部的请求，保护了内部的服务不会过载
  • 内部服务匀速执行，无法应对流量洪峰，无法做到弹性处理突发任务
  • 任务超时溢出时被丢弃。现实中可能需要缓存队列辅助保持一段时间

典型场景

nginx中的限流是漏桶算法的典型应用，配置案例如下：

http {    
	#$binary_remote_addr 表示通过remote_addr这个标识来做key，也就是限制同一客户端ip地址。       #zone=one:10m 表示生成一个大小为10M，名字为one的内存区域，用来存储访问的频次信息。    
	#rate=1r/s 表示允许相同标识的客户端每秒1次访问    
	limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;    
	server {        
	location /limited/ {        
	#zone=one 与上面limit_req_zone 里的name对应。        
	#burst=5 缓冲区，超过了访问频次限制的请求可以先放到这个缓冲区内，类似代码中的队列长度。
	#nodelay 如果设置，超过访问频次而且缓冲区也满了的时候就会直接返回503，如果没有设置，则所有请求会等待排队，类似代码中的put还是offer。                  
	 limit_req zone=one burst=5 nodelay;    
	 }
 }

令牌桶

概述

令牌桶算法可以认为是漏桶算法的一种升级，它不但可以将流量做一步限制，还可以解决漏桶中无法弹性伸缩处理请求的问题。体现在现实中，类似服务大厅的门口设置门禁卡发放。发放是匀速的，请求较少时，令牌可以缓存起来，供流量爆发时一次性批量获取使用。而内部服务窗口不设限。
数据结构和算法专题---4、限流算法与应用,数据结构和算法专题,算法,计数器,漏桶算法,令牌桶,滑动窗口

实现

package com.ls.cloud.sys.alg.limit;

import java.util.concurrent.*;

public class Token {
    public static void main(String[] args) throws InterruptedException {
        //令牌桶，信号量实现，容量为3
        final Semaphore semaphore = new Semaphore(3);

        //定时器，1s一个，匀速颁发令牌
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                if (semaphore.availablePermits() < 3){
                    semaphore.release();
                }
//                System.out.println("令牌数："+semaphore.availablePermits());
            }
        },1000,1000,TimeUnit.MILLISECONDS);


        //等待，等候令牌桶储存
        Thread.sleep(5);
        //模拟洪峰5个请求，前3个迅速响应，后两个排队
        for (int i = 0; i < 5; i++) {
            semaphore.acquire();
            System.out.println("洪峰："+i);
        }
        //模拟日常请求，2s一个
        for (int i = 0; i < 3; i++) {
            Thread.sleep(1000);
            semaphore.acquire();
            System.out.println("日常："+i);
            Thread.sleep(1000);
        }
        //再次洪峰
        for (int i = 0; i < 5; i++) {
            semaphore.acquire();
            System.out.println("洪峰："+i);
        }
        //检查令牌桶的数量
        for (int i = 0; i < 5; i++) {
            Thread.sleep(2000);
            System.out.println("令牌剩余："+semaphore.availablePermits());
        }
    }
}

结果

洪峰：0
洪峰：1
洪峰：2
洪峰：3
洪峰：4
日常：0
日常：1
日常：2
洪峰：0
洪峰：1
洪峰：2
洪峰：3
洪峰：4
令牌剩余：2
令牌剩余：3
令牌剩余：3
令牌剩余：3
令牌剩余：3
  1. 洪峰0-2迅速被执行，说明桶中暂存了3个令牌，有效应对了洪峰
  2. 洪峰3，4被间隔性执行，得到了有效的限流
  3. 日常请求被匀速执行，间隔均匀
  4. 第二波洪峰来临，和第一次一样
  5. 请求过去后，令牌最终被均匀颁发，积累到3个后不再上升

典型场景

springcloud中gateway可以配置令牌桶实现限流控制，案例如下：

cloud: 
	gateway: 
		routes: 
	  ‐ id:    limit_route 
		uri:    http://localhost:8080/test 
		filters: 
		‐   name:    RequestRateLimiter 
			args: 
			#限流的key，ipKeyResolver为spring中托管的Bean，需要扩展KeyResolver接口 key‐resolver:    '#{@ipResolver}' 
			#令牌桶每秒填充平均速率，相当于代码中的发放频率 
			redis‐rate‐limiter.replenishRate:    1 
			#令牌桶总容量，相当于代码中，信号量的容量 
			redis‐rate‐limiter.burstCapacity:    3

滑动窗口

概述

滑动窗口可以理解为细分之后的计数器，计数器粗暴的限定1分钟内的访问次数，而滑动窗口限流将1分钟拆为多个段，不但要求整个1分钟内请求数小于上限，而且要求每个片段请求数也要小于上限。相当于将原来的计数周期做了多个片段拆分，更为精细。

实现

数据结构和算法专题---4、限流算法与应用,数据结构和算法专题,算法,计数器,漏桶算法,令牌桶,滑动窗口

package com.ls.cloud.sys.alg.limit;

import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class Window {
    //整个窗口的流量上限，超出会被限流
    final int totalMax = 5;
    //每片的流量上限，超出同样会被拒绝，可以设置不同的值
    final int sliceMax = 5;
    //分多少片
    final int slice = 3;
    //窗口，分3段，每段1s，也就是总长度3s
    final LinkedList<Long> linkedList = new LinkedList<>();
    //计数器，每片一个key，可以使用HashMap，这里为了控制台保持有序性和可读性，采用TreeMap
    Map<Long,AtomicInteger> map = new TreeMap();
    //心跳，每1s跳动1次，滑动窗口向前滑动一步，实际业务中可能需要手动控制滑动窗口的时机。
    ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

    //获取key值，这里即是时间戳（秒）
    private Long getKey(){
        return System.currentTimeMillis()/1000;
    }

    public Window(){
        //初始化窗口，当前时间指向的是最末端，前两片其实是过去的2s
        Long key = getKey();
        for (int i = 0; i < slice; i++) {
            linkedList.addFirst(key-i);
            map.put(key-i,new AtomicInteger(0));
        }
        //启动心跳任务，窗口根据时间，自动向前滑动，每秒1步
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                Long key = getKey();
                //队尾添加最新的片
                linkedList.addLast(key);
                map.put(key,new AtomicInteger());

                //将最老的片移除
                map.remove(linkedList.getFirst());
                linkedList.removeFirst();

                System.out.println("step:"+key+":"+map);;
            }
        },1000,1000,TimeUnit.MILLISECONDS);
    }

    //检查当前时间所在的片是否达到上限
    public boolean checkCurrentSlice(){
        long key = getKey();
        AtomicInteger integer = map.get(key);
        if (integer != null){
            return integer.get() < totalMax;
        }
        //默认允许访问
        return true;
    }

    //检查整个窗口所有片的计数之和是否达到上限
    public boolean checkAllCount(){
        return map.values().stream().mapToInt(value -> value.get()).sum()  < sliceMax;
    }

    //请求来临....
    public void req(){
        Long key = getKey();
        //如果时间窗口未到达当前时间片，稍微等待一下
        //其实是一个保护措施，放置心跳对滑动窗口的推动滞后于当前请求
        while (linkedList.getLast()<key){
            try {
                Thread.sleep(200);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        //开始检查，如果未达到上限，返回ok，计数器增加1
        //如果任意一项达到上限，拒绝请求，达到限流的目的
        //这里是直接拒绝。现实中可能会设置缓冲池，将请求放入缓冲队列暂存
        if (checkCurrentSlice() && checkAllCount()){
            map.get(key).incrementAndGet();
            System.out.println(key+"=通过:"+map);
        }else {
            System.out.println(key+"=拒绝:"+map);
        }
    }


    public static void main(String[] args) throws InterruptedException {
        Window window = new Window();
        //模拟10个离散的请求，相对之间有200ms间隔。会造成总数达到上限而被限流
        for (int i = 0; i < 10; i++) {
            Thread.sleep(200);
            window.req();
        }
        //等待一下窗口滑动，让各个片的计数器都置零
        Thread.sleep(3000);
        //模拟突发请求，单个片的计数器达到上限而被限流
        System.out.println("---------------------------");
        for (int i = 0; i < 10; i++) {
            window.req();
        }

    }
}

结果

1701766769=通过:{1701766767=0, 1701766768=0, 1701766769=1}
1701766769=通过:{1701766767=0, 1701766768=0, 1701766769=2}
1701766769=通过:{1701766767=0, 1701766768=0, 1701766769=3}
1701766769=通过:{1701766767=0, 1701766768=0, 1701766769=4}
step:1701766770:{1701766768=0, 1701766769=4, 1701766770=0}
1701766770=通过:{1701766768=0, 1701766769=4, 1701766770=1}
1701766770=拒绝:{1701766768=0, 1701766769=4, 1701766770=1}
1701766770=拒绝:{1701766768=0, 1701766769=4, 1701766770=1}
1701766770=拒绝:{1701766768=0, 1701766769=4, 1701766770=1}
1701766770=拒绝:{1701766768=0, 1701766769=4, 1701766770=1}
step:1701766771:{1701766769=4, 1701766770=1, 1701766771=0}
1701766771=拒绝:{1701766769=4, 1701766770=1, 1701766771=0}
step:1701766772:{1701766770=1, 1701766771=0, 1701766772=0}
step:1701766773:{1701766771=0, 1701766772=0, 1701766773=0}
step:1701766774:{1701766772=0, 1701766773=0, 1701766774=0}
---------------------------
1701766774=通过:{1701766772=0, 1701766773=0, 1701766774=1}
1701766774=通过:{1701766772=0, 1701766773=0, 1701766774=2}
1701766774=通过:{1701766772=0, 1701766773=0, 1701766774=3}
1701766774=通过:{1701766772=0, 1701766773=0, 1701766774=4}
1701766774=通过:{1701766772=0, 1701766773=0, 1701766774=5}
1701766774=拒绝:{1701766772=0, 1701766773=0, 1701766774=5}
1701766774=拒绝:{1701766772=0, 1701766773=0, 1701766774=5}
1701766774=拒绝:{1701766772=0, 1701766773=0, 1701766774=5}
1701766774=拒绝:{1701766772=0, 1701766773=0, 1701766774=5}
1701766774=拒绝:{1701766772=0, 1701766773=0, 1701766774=5}
step:1701766775:{1701766773=0, 1701766774=5, 1701766775=0}
step:1701766776:{1701766774=5, 1701766775=0, 1701766776=0}
step:1701766777:{1701766775=0, 1701766776=0, 1701766777=0}
step:1701766778:{1701766776=0, 1701766777=0, 1701766778=0}

典型场景

滑动窗口算法，在tcp协议发包过程中被使用。在web现实场景中，可以将流量控制做更细化处理，解决计数器模型控制力度太粗暴的问题。文章来源地址https://www.toymoban.com/news/detail-756180.html

到了这里，关于数据结构和算法专题---4、限流算法与应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中，算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究，展示了算法在项目管理中的实际应用： 项目进度管理 ： 甘特图算法 ：甘特图是一种项目进度管理工具，它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(41)
  • 限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

    限流算法（计数器、滑动时间窗口、漏斗、令牌）原理以及代码实现

    本文会对这4个限流算法进行详细说明，并输出实现限流算法的代码示例。 代码是按照自己的理解写的，很简单的实现了功能，还请大佬们多多交流找bug。 下面还有投票，帮忙投个票👍 什么是限流？限流 限流 就是限制流量。在高并发、高流量的场景中我们需要把限流做好，

    2023年04月17日
    浏览(32)
  • 限流：计数器、漏桶、令牌桶 三大算法的原理与实战（史上最全）

    限流：计数器、漏桶、令牌桶 三大算法的原理与实战（史上最全）

    限流是面试中的常见的面试题（尤其是大厂面试、高P面试） 注：本文以 PDF 持续更新，最新尼恩 架构笔记、面试题 的PDF文件，请到文末《技术自由圈》公号获取 为什么要限流 简单来说： 限流在很多场景中用来限制并发和请求量，比如说秒杀抢购，保护自身系统和下游系统

    2023年04月17日
    浏览(27)

  • 数据结构与算法--哈夫曼树应用

    第1关：统计报文中各个字符出现的次数 任务描述 本关任务： 给定一串文本，统计其中各个字符出现的次数； 测试说明 平台会对你编写的代码进行测试： 测试输入：` abcdeabcdeabcdabcdabcdabcbccc 预期输出： a 6 b 7 c 9 d 5 e 2 代码： 第2关：对第一关报文中的各个字符进行哈夫曼编

    2024年02月06日
    浏览(36)
  • 【数据结构和算法】---二叉树（2）--堆的实现和应用

    【数据结构和算法】---二叉树（2）--堆的实现和应用

    如果有一个数字集合，并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ，且在逻辑结构（即二叉树）中，如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ；那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(33)
  • 数据结构与算法课程设计---最小生成树的应用

    数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题，有11个城市，城市之间有一些天然气管道，铺设天然气管道需要花费不同的金额，现在要你选择其中一些天然气管道，使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图，每个城市是一个顶点，城市与城市之间的管道是

    2024年02月08日
    浏览(37)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢，每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号，而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(51)

  • 数据结构专题2

    1. Cube - HDU 3584 三维的空间中有 n n n 个元素，初始时每个空间元素均为0。更新操作是0变1，1变0，是一个立方体型区域内的所有元素都更新。然后查询是问某个点的元素是0还是1. ( 1 = n = 100 , m = 10000 1=n=100, m =10000 1 = n = 100 , m = 10000 ) 三维树状数组，维护三维差分数组，所有加法

    2024年02月16日
    浏览(23)
  • 数据结构——顺序表专题

    数据结构——顺序表专题

    什么是数据结构 数据结构是由“数据”和“结构”两词组合而来的。 数据：常见的数值、网页中肉眼可见的信息，这些都是数据。 结构：当我们想要使用大量同一类型的数据时，通过手动定义大量的独立的遍历对于程序来说，可读性非常差，我们可以借助数组这样的数据结

    2024年02月21日
    浏览(22)
  • 数据结构 | 单链表专题【详解】

    数据结构 | 单链表专题【详解】

    顺序表遗留下来的问题 中间/头部的插⼊删除，时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后⾯没有数据插入了

    2024年02月06日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包