哈尔滨网站制作策划,石家庄企业网站建设公司,wordpress注册不跳转,百度网站关键词排名助手本章我们会对限流算法做个简单介绍#xff0c;包括常用的限流算法#xff08;计数器、漏桶算法、令牌桶案发、滑动窗口#xff09;的概述、实现方式、典型场景做个说明。
什么是限流算法
限流是对系统的一种保护措施。即限制流量请求的频率#xff08;每秒处理多少个请求…本章我们会对限流算法做个简单介绍包括常用的限流算法计数器、漏桶算法、令牌桶案发、滑动窗口的概述、实现方式、典型场景做个说明。
什么是限流算法
限流是对系统的一种保护措施。即限制流量请求的频率每秒处理多少个请求。一般来说当请求流量超过系统的瓶颈则丢弃掉多余的请求流量保证系统的可用性。即要么不放进来放进来的就保证提供服务。
计数器
概述
计数器采用简单的计数操作到一段时间节点后自动清零
实现
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() {Overridepublic void run() {semaphore.release(1);}},3000,3000,TimeUnit.MILLISECONDS);//模拟无限请求从天而降降临while (true) {try {//判断计数器semaphore.acquire();} catch (InterruptedException e) {e.printStackTrace();}//如果准许响应打印一个okDate 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进入全部流程系统可能依然会出现宕机的情况。
漏桶算法
概述
漏桶算法将请求缓存在桶中服务流程匀速处理。超出桶容量的部分丢弃。漏桶算法主要用于保护内部的处理业务保障其稳定有节奏的处理请求但是无法根据流量的波动弹性调整响应能力。现实中类似容纳人数有限的服务大厅开启了固定的服务窗口。
实现
可以基于队列进行实现。
package com.ls.cloud.sys.alg.limit;import java.util.concurrent.*;public class Barrel {public static void main(String[] args) {//桶用阻塞队列实现容量为3final LinkedBlockingQueueInteger que new LinkedBlockingQueue(3);//定时器相当于服务的窗口2s处理一个ScheduledExecutorService service Executors.newScheduledThreadPool(1);service.scheduleAtFixedRate(new Runnable() {Overridepublic void run() {// 删除队首元素int v que.poll();System.out.println(处理v);}},2000,2000,TimeUnit.MILLISECONDS);//无数个请求i 可以理解为请求的编号int i0;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:13put任务号按照顺序入桶执行任务匀速的2s一个被处理因为桶的容量只有3所以1-3完美执行4被溢出丢弃5正常执行
优缺点
优点有效的挡住了外部的请求保护了内部的服务不会过载内部服务匀速执行无法应对流量洪峰无法做到弹性处理突发任务任务超时溢出时被丢弃。现实中可能需要缓存队列辅助保持一段时间
典型场景
nginx中的限流是漏桶算法的典型应用配置案例如下
http { #$binary_remote_addr 表示通过remote_addr这个标识来做key也就是限制同一客户端ip地址。 #zoneone:10m 表示生成一个大小为10M名字为one的内存区域用来存储访问的频次信息。 #rate1r/s 表示允许相同标识的客户端每秒1次访问 limit_req_zone $binary_remote_addr zoneone:10m rate1r/s; server { location /limited/ { #zoneone 与上面limit_req_zone 里的name对应。 #burst5 缓冲区超过了访问频次限制的请求可以先放到这个缓冲区内类似代码中的队列长度。#nodelay 如果设置超过访问频次而且缓冲区也满了的时候就会直接返回503如果没有设置则所有请求会等待排队类似代码中的put还是offer。 limit_req zoneone burst5 nodelay; }} 令牌桶
概述
令牌桶算法可以认为是漏桶算法的一种升级它不但可以将流量做一步限制还可以解决漏桶中无法弹性伸缩处理请求的问题。体现在现实中类似服务大厅的门口设置门禁卡发放。发放是匀速的请求较少时令牌可以缓存起来供流量爆发时一次性批量获取使用。而内部服务窗口不设限。
实现
package com.ls.cloud.sys.alg.limit;import java.util.concurrent.*;public class Token {public static void main(String[] args) throws InterruptedException {//令牌桶信号量实现容量为3final Semaphore semaphore new Semaphore(3);//定时器1s一个匀速颁发令牌ScheduledExecutorService service Executors.newScheduledThreadPool(1);service.scheduleAtFixedRate(new Runnable() {Overridepublic 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洪峰0-2迅速被执行说明桶中暂存了3个令牌有效应对了洪峰洪峰34被间隔性执行得到了有效的限流日常请求被匀速执行间隔均匀第二波洪峰来临和第一次一样请求过去后令牌最终被均匀颁发积累到3个后不再上升
典型场景
springcloud中gateway可以配置令牌桶实现限流控制案例如下
cloud: gateway: routes: ‐ id: limit_route uri: http://localhost:8080/test filters: ‐ name: RequestRateLimiter args: #限流的keyipKeyResolver为spring中托管的Bean需要扩展KeyResolver接口 key‐resolver: #{ipResolver} #令牌桶每秒填充平均速率相当于代码中的发放频率 redis‐rate‐limiter.replenishRate: 1 #令牌桶总容量相当于代码中信号量的容量 redis‐rate‐limiter.burstCapacity: 3 滑动窗口
概述
滑动窗口可以理解为细分之后的计数器计数器粗暴的限定1分钟内的访问次数而滑动窗口限流将1分钟拆为多个段不但要求整个1分钟内请求数小于上限而且要求每个片段请求数也要小于上限。相当于将原来的计数周期做了多个片段拆分更为精细。
实现 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也就是总长度3sfinal LinkedListLong linkedList new LinkedList();//计数器每片一个key可以使用HashMap这里为了控制台保持有序性和可读性采用TreeMapMapLong,AtomicInteger map new TreeMap();//心跳每1s跳动1次滑动窗口向前滑动一步实际业务中可能需要手动控制滑动窗口的时机。ScheduledExecutorService service Executors.newScheduledThreadPool(1);//获取key值这里即是时间戳秒private Long getKey(){return System.currentTimeMillis()/1000;}public Window(){//初始化窗口当前时间指向的是最末端前两片其实是过去的2sLong 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() {Overridepublic 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通过:{17017667670, 17017667680, 17017667691}
1701766769通过:{17017667670, 17017667680, 17017667692}
1701766769通过:{17017667670, 17017667680, 17017667693}
1701766769通过:{17017667670, 17017667680, 17017667694}
step:1701766770:{17017667680, 17017667694, 17017667700}
1701766770通过:{17017667680, 17017667694, 17017667701}
1701766770拒绝:{17017667680, 17017667694, 17017667701}
1701766770拒绝:{17017667680, 17017667694, 17017667701}
1701766770拒绝:{17017667680, 17017667694, 17017667701}
1701766770拒绝:{17017667680, 17017667694, 17017667701}
step:1701766771:{17017667694, 17017667701, 17017667710}
1701766771拒绝:{17017667694, 17017667701, 17017667710}
step:1701766772:{17017667701, 17017667710, 17017667720}
step:1701766773:{17017667710, 17017667720, 17017667730}
step:1701766774:{17017667720, 17017667730, 17017667740}
---------------------------
1701766774通过:{17017667720, 17017667730, 17017667741}
1701766774通过:{17017667720, 17017667730, 17017667742}
1701766774通过:{17017667720, 17017667730, 17017667743}
1701766774通过:{17017667720, 17017667730, 17017667744}
1701766774通过:{17017667720, 17017667730, 17017667745}
1701766774拒绝:{17017667720, 17017667730, 17017667745}
1701766774拒绝:{17017667720, 17017667730, 17017667745}
1701766774拒绝:{17017667720, 17017667730, 17017667745}
1701766774拒绝:{17017667720, 17017667730, 17017667745}
1701766774拒绝:{17017667720, 17017667730, 17017667745}
step:1701766775:{17017667730, 17017667745, 17017667750}
step:1701766776:{17017667745, 17017667750, 17017667760}
step:1701766777:{17017667750, 17017667760, 17017667770}
step:1701766778:{17017667760, 17017667770, 17017667780}典型场景
滑动窗口算法在tcp协议发包过程中被使用。在web现实场景中可以将流量控制做更细化处理解决计数器模型控制力度太粗暴的问题。
