限流算法(令牌通漏桶计数器)

news/2024/11/14 16:30:11/

限流算法(令牌桶&漏桶&计数器 )

什么是限流?

限流是为保护自身系统和下游系统不被高并发流量冲垮,导致系统雪崩等问题

限流在很多场景中用来限制并发请求量,比如说秒杀抢购、双11高并发流量等

在保证系统可用的情况下尽可能多增加进入的请求,其余的请求在排队等待,或者返回友好提示,保证里面的进入系统的用户可以正常使用,防止系统雪崩。

限流算法

令牌桶

**令牌桶(Token Bucket)**算法以一个设定的速率产生令牌(Token)并放入令牌桶,每次用户请求都得申请令牌,如果令牌不足,则拒绝请求。

令牌桶算法中新请求到来时会从桶里拿走一个令牌,如果桶内没有令牌可拿,就拒绝服务。当然,令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关,时间流逝的时间越长,会不断往桶里加入越多的令牌,如果令牌发放的速度比申请速度快,令牌桶会放满令牌,直到令牌占满整个令牌桶

在这里插入图片描述

令牌桶限流大致的规则如下:
(1)进水口按照某个速度,向桶中放入令牌。
(2)令牌的容量是固定的,但是放行的速度不是固定的,只要桶中还有剩余令牌,一旦请求过来就能申请成功,然后放行。
(3)如果令牌的发放速度,慢于请求到来速度,桶内就无令牌可领,请求就会被拒绝

总之,令牌的发送速率可以设置,从而可以对突发的出口流量进行有效的应对。

代码实现
import java.util.concurrent.*.
import java.util.concurrent.atomic.Atomiclnteger,
// 令牌桶限流算法
public class TokenBucketLimiter {
private static final int capacity= 10;//桶的容量
private static final int rate=5; //令牌生成速度 rate/s
private volatile static Atomiclnteger tokens = new Atomiclnteger(0); // 当前令牌数量// 开启一个线程放入令牌:rate/s
private static void productToken() {
//创建ScheduledThreadPool,参数为线程池的大小
ScheduledExecutorService scheduledThreadPool = Executors,newScheduledThreadPool(1)
//定时调度
scheduledThreadPool.scheduleAtFixedRate(0->{
int allTokens=tokens.get0)+rate; //计算牌数
tokens.set(Math.min(capacity, allTokens)); // 设置当前令牌数},1,1,TimeUnit.SECONDS);//延迟1秒后执行任务,并且每隔1秒执行一次
}   
特点:
  • 令牌桶的好处之一就是可以方便地应对突发出口流量。比如,可以改变令牌的发放速度(需后端系统能力的提升),算法能按照新的发送速率调大令牌的发放数量,使得出口突发流量能被处理。
  • 令牌生产速度固定,消费速度不固定。

漏桶

**漏桶(Leak Bucket)**算法限流的基本原理为:水(对应请求)从进水口进入到漏桶里,漏桶以一定的速度出水(请求放行),当水流入速度过大,桶内的总水量大于桶容量会直接溢出,请求被拒绝。

在这里插入图片描述

大致的漏桶限流规则如下:
(1)进水口(对应客户端请求)以任意速率流入进入漏桶,
(2)漏桶的容量是固定的,出水(放行)速率也是固定的,
(3)漏桶容量是不变的,如果处理速度太慢,桶内水量会超出了桶的容量,则后面流入的水滴会溢出表示请求拒绝。

水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会超过桶可接纳的容量时直接溢出。

可以看出漏桶算法能强行限制数据的传输速率。

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

代码实现
import java.util.concurrent.*,
import java.util.concurrent.atomic.Atomicinteger;
//漏桶限流算法
public class LeakyBucketLimiter {
// 计算的起始时间
private static long lastOutTime = System.currentTimeMillis(),
// 流出速率 每秒 2 次
private static int leakRate = 5
// 桶的容量
private static final int capacity = 100;
//剩余的水量
private static Atomiclnteger water = new Atomiclnteger(0);
/**
* 开启一个线程固定频率漏水:rate/s
*/
private static void waterLeaked() {
// 创建ScheduledThreadPool,参数为线程池的大小
ScheduledExecutorService scheduledThreadPool = Executors.newScheduledThreadPool(1);//定时调度
scheduledThreadPool.scheduleAtFixedRate(0->{
//剩余水量
int waterLeft = water.get0) -leakRate;
// 设置当前水量
water.set(Math.max(0, waterLeft));
}.1.1,TimeUnit.SECONDS); // 延迟1秒后执行任务,并且每隔1秒执行一次   
}    
特点
  • 削峰:有大量流量进入时,会发生溢出,从而限流保护服务可用性
  • 缓冲:不至于直接请求到服务器,缓冲压力
  • 请求速度不固定,漏桶出口的速度固定,因为计算性能固定,不能灵活的应对后端能力提升。比如通过动态扩容,后端流量从1000QPS提升到10000QPS,漏桶没有办法。

令牌桶&漏桶算法区别

令牌桶:按照固定速率往桶中添加令牌
漏桶:按照常量固定速率流出请求

这两种算法的主要区别在于漏桶算法能够强行限制数据的传输速率

而令牌桶算法在能够限制数据的平均传输数据外,还允许某种程度的突发传输

在令牌桶算法中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的限制,因此它适合于具有突发特性的流量。

计数器

**计数器(Counter)**算法是在一段时间间隔内(时间窗/时间区间),处理请求的最大数量固定,超过部分不做处理。计数器算法是限流算法里最简单也是最容易实现的一种算法

举个例子,比如我们规定对于A接口,我们1分钟的访问次数不能超过100个 ,可以这么做:
1.在一开 始的时候,可以设置一个计数器counter,每当一个请求过来的时候,counter就加1,如果counter的值大于100并日该请求与第一个请求的间隔时间还在1分钟之内,那么说明请求数过多,拒绝访问;
2.如果该请求与第一个请求的间隔时间大于1分钟,且counter的值还在限流范围内,那么就重置counter,就是这么简单粗暴。

代码实现
import java.util.concurrent.ExecutorService.
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.Atomiclnteger
import java.util.concurrent.atomic.AtomicLong;
/**
*计数器限流算法
*/
public class CounterLimiter {
/ 起始时间
private volatile static AtomicLong startTime = new AtomicLong(System.currentTimeMillis();
// 时间区间的时间间隔 ms
private static final long interval = 1000:
// 每秒限制数量
private static final long maxLimitCount = 10,
//累加器
private volatile static AtomicLong accumulator = new AtomicLong();
// 计数判断,是否超出限制
private static boolean isLimited(int reguestCount)long nowTime =System.currentTimeMillis0
//在时间区间之内
if (nowTime < startTime.get0 + interva)
long count=accumulator.addAndGet(reguestCount,
if (count <= maxLimitCount){
return false.
} else (
return true,
} else {
//在时间区间之外
System.out.println("新时间区到了.");
accumulator.set(0);//将计数器重新初始化为0
startTime.set(nowTime);
return false;
}}    
临界问题

计数器限流的严重问题:这个算法虽然简单,但是有一个十分致命的问题,那就是临界问题。

在这里插入图片描述

从上图中我们可以看到,假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么其实这个用户在1秒里面,瞬间发送了200个请求

我们刚才规定的是1分钟最多100个请求(规划的吞吐量),也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求,可以瞬间超过我们的速率限制。

lB2m-1731502464494)]

从上图中我们可以看到,假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么其实这个用户在1秒里面,瞬间发送了200个请求

我们刚才规定的是1分钟最多100个请求(规划的吞吐量),也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求,可以瞬间超过我们的速率限制。

用户有可能通过算法的这个漏洞,瞬间压垮我们的应用。


http://www.ppmy.cn/news/1546972.html

相关文章

Wi-Fi背后的工作原理与技术发展历程介绍【无线通信小百科】

1个视频说清楚WIFI&#xff1a;频段/历程/技术参数/常用模块 智能手机拥有率越来越高的今天&#xff0c;大家已经习惯了通过无线网络上网的方式。除了在外面需要用手机流量&#xff0c;我们通常在家里或者机场&#xff0c;商场都可以通过Wi-Fi连接上网。本期文章将为大家介绍Wi…

软件工程概论项目(二),node.js的配置,npm的使用与vue的安装

上一章我们配置了git仓库&#xff0c;这一章我们来配置项目需要用的一些其他的环境。 放一个思维导图在这里&#xff0c;可以参考一下&#xff0c;很不全面&#xff0c;没有参考价值,反正我先这样写吧。 参考了这个nodejs的配置&#xff0c;写的很好&#xff1a;https://blog.c…

从0开始学docker (每日更新 24-11-11)

Docker存储驱动及其选择 概述 理想情况下&#xff0c;只有很少的数据需要写入容器的可写层&#xff0c;更多的情形是用 Docker卷来写入数据。但是&#xff0c;有些工作负荷要求写入容器的可写层&#xff0c;这就需要使用存储驱动。存储驱动控制镜像和容器在 Docker主机上的存…

喜报|超维机器人荣获昇腾AI创新大赛铜奖

近日&#xff0c;在备受瞩目的昇腾AI创新大赛中&#xff0c;超维机器人凭借扎实的技术实力和创新产品&#xff0c;荣获大赛铜奖。这一荣誉不仅展现了超维机器人在智能巡检领域的技术创新与突破&#xff0c;也标志着超维机器人的智能巡检解决方案在人工智能领域获得了广泛认可&a…

★ C++进阶篇 ★ 异常

Ciallo&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;我将和大家一起学习C中的异常 ~ ​❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页&#xff1a;椎名澄嵐-CSDN博客 C基础篇专栏&#xff1a;★ C基础篇 ★_椎名澄嵐的博客-CSDN博客 C进阶篇专栏&am…

【保姆级教程】ChatOpenAI真香!LangChian中使用ChatOpenAI玩转多家大模型(附API-KEY)

1.[方式1]API站获取API-Key 获取API-Key看教程 【保姆级教程】手把手教你玩转多种OneAPI平台&#xff0c;白嫖GPT3.5 这里送两个模型的API-Key[限额限时]&#xff0c;给大家试用 支持模型gpt-3.5-turbo sk-aTU1v09zvzfZLJ6oCzhIxilgri7sFYZ0Xf1lItmqKCGgI2Mt支持模型glm-4-f…

中文分词模拟器

题目描述 给定一个连续不包含空格的字符串&#xff0c;该字符串仅包含英文小写字母及英文标点符号&#xff08;逗号、分号、句号&#xff09;&#xff0c;同时给定词库&#xff0c;对该字符串进行精确分词。 说明&#xff1a; 精确分词&#xff1a;字符串分词后&#xff0c;不…

AndroidStudio-文本显示

一、设置文本的内容 1.方式&#xff1a; &#xff08;1&#xff09;在XML文件中通过属性&#xff1a;android:text设置文本 例如&#xff1a; <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.andr…