当前位置：首页 > news >正文

常见限流算法详细解析

news 来源：原创 2025/7/14 21:45:30

常见限流算法详细解析

分布式系统中，由于接口API无法控制上游调用方的行为，因此当瞬时请求量突增时，会导致服务器占用过多资源，发生响应速度降低、超时、乃至宕机，甚至引发雪崩造成整个系统不可用。
限流，Rate Limiter，就是对API的请求量进行限制，对于超出限制部分的请求作出快速拒绝、快速失败、丢弃处理，以保证本服务以及下游资源系统的稳定。

常见的限流算法有：固定时间窗、滑动时间窗算法、漏桶算法、令牌桶算法，以下分别详解介绍。

固定时间窗口算法

生活示例

一个游戏规则：

每小时只能玩5次游戏
时间一到整点，计数器就会重置

举个例子：

上午9:55，你已经玩了3次游戏
上午10:05，你又可以玩完整的5次

这就像是一个"准点重置"的游戏规则。优点是简单直接！

算法原理

将时间划分为固定的窗口大小，例如10s
在窗口时间段内，每来一个请求，对计数器加1。
当计数器达到设定限制后，该窗口时间内的之后的请求都被丢弃处理。
该窗口时间结束后，计数器清零，从新开始计数。如上图所示，10s内限制100个请求，在第11s的时候计数器会从0重新开始计数。

如下图所示：

在这里插入图片描述

代码示例

public class FixedWindowRateLimiter {// 窗口最大请求数private final int maxRequests;// 窗口时间大小（毫秒）private final long windowSizeMillis;// 当前窗口的请求计数private int currentRequests = 0;// 窗口开始时间private long windowStartTime;public FixedWindowRateLimiter(int maxRequests, long windowSizeMillis) {this.maxRequests = maxRequests;this.windowSizeMillis = windowSizeMillis;this.windowStartTime = System.currentTimeMillis();}public synchronized boolean tryAcquire() {long currentTime = System.currentTimeMillis();// 如果当前时间已超过窗口，重置窗口if (currentTime - windowStartTime >= windowSizeMillis) {currentRequests = 0;windowStartTime = currentTime;}// 判断是否允许新请求if (currentRequests < maxRequests) {currentRequests++;return true;}return false;}
}// 短信发送限制器：每小时最多发送5条短信
FixedWindowRateLimiter smsSender = new FixedWindowRateLimiter(5, 60 * 60 * 1000);public boolean sendSMS(String phoneNumber, String message) {if (smsSender.tryAcquire()) {// 执行短信发送逻辑return true;} else {System.out.println("超过短信发送限制");return false;}
}

存在问题

边界问题

在窗口切换时可能会出现流量突发
例如，在一个小时的最后一秒和下一秒分别允许100个请求，实际上可能瞬间允许200个请求，所谓的2N问题，如下图所示：

不够平滑

流量控制不够精细
容易在窗口边界产生流量不均匀的情况

跨两个固定时间窗统计不准确：比如6t到16t之间也是10t大小的一个时间窗，但跨了两个固定的时间窗，问题是请求总数为110，超过阈值，这种固定时间窗无法处理这部分超出的请求，所以解决办法就是使用滑动时间窗。

滑动时间窗算法

生活示例

计数器滑动时间窗口算法是计数器固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点。TCP协议中数据包的传输，同样也是采用滑动窗口来进行流量控制。

想象你有一个会"移动"的时间窗口。

不再是整点重置
而是始终保持最近1小时内只能玩5次游戏
举个栗子：
- 9:30玩了2次
- 9:45玩了2次
- 10:15想玩，系统会检查9:15到10:15的记录

再举个例子：

再想象你是一个售票员，需要控制游乐场的人流量。你的规则是"任意10分钟内最多允许50人进入"。如果你每2分钟清点一次人数（这就是滑动步长），就比每1秒钟都清点要轻松得多，而且准确性也足够。

原理

滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器。

当请求的时间大于当前窗口的最大时间时，则将计时窗口向前平移一个小窗口。平移时，将第一个小窗口的数据丢弃，然后将第二个小窗口设置为第一个小窗口，同时在最后面新增一个小窗口，将新的请求放在新增的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之后不能超过设定的阈值。

滑动时间窗限流算法解决了固定时间窗限流算法的问题。其没有划分固定的时间窗起点与终点，而是将每一次请求的到来时间点作为统计时间窗的终点，起点则是终点向前推时间窗长度的时间点。这种时间窗称为“滑动时间窗”

在这里插入图片描述

图解

假设: 
- 时间窗口 = 10秒
- 滑动步长 = 2秒
- 最大请求 = 5个时间轴划分：
0s    2s    4s    6s    8s    10s   12s   14s
|-----|-----|-----|-----|-----|-----|-----|↑     ↑     ↑     ↑     ↑     ↑     ↑
小窗口1 窗口2  窗口3  窗口4  窗口5  窗口6  窗口7完整时间窗口（10秒）：
|----------------------------------|包含5个小窗口滑动过程：
第0秒:  [窗口1|窗口2|窗口3|窗口4|窗口5]
第2秒:    [窗口2|窗口3|窗口4|窗口5|窗口6]
第4秒:      [窗口3|窗口4|窗口5|窗口6|窗口7]

代码示例

public class SlidingWindowLimiter {private final int maxRequestsAllowed;     // 允许的最大请求数private final int windowSizeInSeconds;    // 时间窗口大小(秒)private final int slideTimeInSeconds;     // 滑动步长(秒)，最小时间窗格// 使用TreeMap记录每个小窗口中的请求数// Key: 窗口的开始时间戳（毫秒）// Value: 该窗口内的请求数private final TreeMap<Long, Integer> windowCounts = new TreeMap<>();public SlidingWindowLimiter(int maxRequests, int windowSize, int slideTime) {this.maxRequestsAllowed = maxRequests;this.windowSizeInSeconds = windowSize;this.slideTimeInSeconds = slideTime;}public synchronized boolean isAllowed() {long currentTime = System.currentTimeMillis();long windowStart = currentTime - (windowSizeInSeconds * 1000L);// 计算当前请求所属的小窗口的开始时间long currentSlideStart = currentTime - (currentTime % (slideTimeInSeconds * 1000L));// 清理过期的小窗口windowCounts.headMap(windowStart).clear();// 统计当前时间窗口内的总请求数int totalRequests = windowCounts.values().stream().mapToInt(Integer::intValue).sum();if (totalRequests < maxRequestsAllowed) {// 更新当前小窗口的计数windowCounts.merge(currentSlideStart, 1, Integer::sum);return true;}return false;}// 用于展示当前所有小窗口的状态public void printWindowStatus() {System.out.println("当前时间窗口状态：");windowCounts.forEach((timestamp, count) -> {String time = new SimpleDateFormat("HH:mm:ss.SSS").format(new Date(timestamp));System.out.printf("窗口开始时间：%s, 请求数：%d\n", time, count);});}
}public class Example {public static void main(String[] args) {// 创建限流器：// - 10秒的时间窗口// - 每个窗口最多允许5个请求// - 每2秒滑动一次SlidingWindowLimiter limiter = new SlidingWindowLimiter(5, 10, 2);// 模拟请求for (int i = 0; i < 8; i++) {boolean allowed = limiter.isAllowed();System.out.printf("请求 %d: %s\n", i + 1, allowed ? "通过" : "拒绝");limiter.printWindowStatus();try {Thread.sleep(1000); // 等待1秒} catch (InterruptedException e) {e.printStackTrace();}}}
}

漏桶算法

生活示例

想象你在一个水桶（桶装水、净水机）底部有个小洞的水龙头下，这个小洞代表了水流出的恒定速率，无论上面的水有多少，出水速度都是固定的。即使你快速地往桶里倒水，水也只会以固定的速度从底部的小洞流出。这就是漏桶算法的生活化比喻。

算法原理

![在这里插入图片描述![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/21ea20c5462d455aaeeee1a67eb82054.png)
漏桶算法的核心思想是：

请求（水）进入一个固定容量的"桶"
桶内请求以恒定速率被处理
如果桶已满，新的请求将被拒绝，桶的容量代表系统能够处理的最大并发请求数

代码示例

public class LeakyBucketRateLimiter {private final int capacity;private final int rate;private int currentWaterLevel = 0;private long lastRequestTime;// 添加拒绝策略枚举public enum LimitPolicy {REJECT,       // 直接拒绝WAIT,         // 等待DEGRADE       // 降级服务}public synchronized LimitResult tryAcquire(LimitPolicy policy) {long currentTime = System.currentTimeMillis();long timePassed = currentTime - lastRequestTime;// 计算流出的请求数int outflow = (int) (timePassed / (1000 / rate));currentWaterLevel = Math.max(0, currentWaterLevel - outflow);lastRequestTime = currentTime;// 根据不同策略处理限流 当桶已满时，拒绝新请求if (currentWaterLevel < capacity) {currentWaterLevel++;return new LimitResult(true, "请求通过");}// 根据不同策略返回结果switch (policy) {case REJECT:return new LimitResult(false, "请求被拒绝");case WAIT:// 模拟等待逻辑return new LimitResult(false, "请求需要等待");case DEGRADE:// 降级服务逻辑return new LimitResult(false, "服务降级");default:return new LimitResult(false, "未知策略");}}// 结果封装类public static class LimitResult {public final boolean allowed;public final String message;public LimitResult(boolean allowed, String message) {this.allowed = allowed;this.message = message;}}public static void main(String[] args) throws InterruptedException {LeakyBucketRateLimiter limiter = new LeakyBucketRateLimiter(10, 2);// 模拟请求for (int i = 0; i < 15; i++) {if (limiter.tryAcquire()) {System.out.println("请求" + i + ": 通过");} else {System.out.println("请求" + i + ": 被限流");}TimeUnit.MILLISECONDS.sleep(200);}}
}

优点：

算法简单，实现容易
可以平滑处理突发流量
能够有效防止系统过载

缺点：

不能充分利用系统资源
处理速率固定，不够灵活
无法应对短时间的高并发请求

令牌桶算法

生活示例

取号看演出或办理业务，取到号以后才能进场，取不到号就要等待

想象你有一个自动售货机，它每隔一段时间就会往机器里放入一定数量的"通行令牌"。只有拿到令牌的人才能购买商品。如果令牌被用完，就必须等待新的令牌生成。

算法原理

在这里插入图片描述

令牌桶算法的核心思想是：

有一个固定大小的令牌桶
系统以恒定速率向桶中添加令牌
每个请求需要获取一个令牌才能执行
如果桶中没有令牌，请求被拒绝或等待

代码示例

import java.util.concurrent.TimeUnit;public class TokenBucketRateLimiter {// 令牌桶最大容量private final int maxTokens;// 每秒生成的令牌数private final int tokenGenerateRate;// 当前令牌数private int currentTokens;// 上次令牌生成时间private long lastTokenTime;public TokenBucketRateLimiter(int maxTokens, int tokenGenerateRate) {this.maxTokens = maxTokens;this.tokenGenerateRate = tokenGenerateRate;this.currentTokens = maxTokens;this.lastTokenTime = System.currentTimeMillis();}public synchronized boolean tryAcquire() {long currentTime = System.currentTimeMillis();long timePassed = currentTime - lastTokenTime;// 计算这段时间内生成的令牌数int generatedTokens = (int) (timePassed * tokenGenerateRate / 1000);// 更新当前令牌数，不超过最大容量currentTokens = Math.min(maxTokens, currentTokens + generatedTokens);lastTokenTime = currentTime;// 判断是否有令牌if (currentTokens > 0) {currentTokens--;return true;}return false;}public static void main(String[] args) throws InterruptedException {TokenBucketRateLimiter limiter = new TokenBucketRateLimiter(10, 5);// 模拟请求for (int i = 0; i < 15; i++) {if (limiter.tryAcquire()) {System.out.println("请求" + i + ": 通过");} else {System.out.println("请求" + i + ": 被限流");}TimeUnit.MILLISECONDS.sleep(100);}}
}

优点：

可以处理突发流量
能更好地利用系统资源
灵活控制流量
支持预热和动态调整

缺点：

实现相对复杂
需要额外维护令牌生成和分配逻辑
可能会有一定的计算开销

总结：

介绍实现限流的几种方式，主要是窗口算法和桶算法，两者各有优势。

窗口算法实现简单，逻辑清晰，可以很直观的得到当前的 QPS 情况，但是会有时间窗口的临界突变问题，而且不像桶一样有队列可以缓冲。
桶算法虽然稍微复杂，不好统计 QPS 情况，但是桶算法也有优势所在。
- 漏桶模式消费速率恒定，可以很好的保护自身系统，可以对流量进行整形，但是面对突发流量不能快速响应。
- 令牌桶模式可以面对突发流量，但是启动时会有缓慢加速的过程，不过常见的开源工具中已经对此优化。

常见限流算法详细解析

常见限流算法详细解析分布式系统中，由于接口API无法控制上游调用方的行为，因此当瞬时请求量突增时，会导致服务器占用过多资源，发生响应速度降低、超时、乃至宕机，甚至引发雪崩造成整个系统不可用。限流，…...

编程日记 2025/7/14 21:45:30

第四十一天 ASP应用 HTTP.sys 漏洞 iis6文件解析漏洞和短文件漏洞 access数据库泄露漏洞

前言随着时代的发展现在呀，这个ASp已经淡出大众的视线了 ，ASP之前的火爆程度无异于现在的PHP 大家的童年 4399 什么的网站都是这个搭建的ASP 简介 | 菜鸟教程那大家想问为什么你妹的这个这么火的网站搭建语言被淘汰了呢其实多半是以为它的不开…...

编程日记 2025/7/14 14:54:37

LLM输出评估标准

LLM输出评估标准 LLM评估方法响应的完整性和简洁性：确定大模型的响应是否完全解决用户查询，简洁性则评估生成响应的相关性。文本相似性指标：将生成的文本与参考文本进行比较，评估它们的相似度，并给出得分以理解大模…...

编程日记 2025/7/14 21:04:18

ansible学习笔记之02command模块与shell模块

目录 1、概述 2、模块介绍 2.1 command模块 2.2 shell模块 2.3 小结 3、实验 3.1 测试ls命令 3.2 测试环境变量 3.3 测试操作符">" 1、概述本文介绍ansible的command模块与shell模块，并通过实验比对两个模块的异同。 2、模块介绍 2.1…...

编程日记 2025/7/14 10:26:30

Python 在同一/或不同PPT文档之间复制幻灯片

复制幻灯片可以帮助我们更高效地完成工作，节省大量的制作时间。通过复制现有的幻灯片，可以快速创建新的演示文稿，而无需重新设计板式样式等。此外，复制幻灯片还可以帮助我们保持内容的一致性，使整个PPT演示文稿看起来更…...

编程日记 2025/7/14 21:43:58

4. React 性能优化技巧：如何让你的应用更快

在构建大型应用时，性能优化是一个非常重要的话题。React 提供了许多优化工具，帮助我们提高应用的渲染速度和响应能力。本文将分享一些常见的 React 性能优化技巧。 4.1. 使用 React.memo 缓存组件当组件的 props 没有变化时，React 默认不会…...

编程日记 2025/7/14 21:33:49

云标准：云计算标准

目录云计算标准的定义和分类云计算标准的内容云计算标准的重要性云计算标准化组织 5.云计算标准的具体实例云计算标准是确保云计算技术、服务和应用发展的重要规范，它们对于提高云计算系统的互操作性、可靠性和安全性至关重要。以下是对云计算标准的详细解…...

编程日记 2025/7/9 1:04:07

Redis【2】- SDS源码分析

1 简介&基础用法 Redis 中用得最多的就是字符串，在 C 语言中其实可以直接使用 char* 字符数组来实现字符串，也有很多可以直接使用得函数。但是 Redis 并没有使用 C 语言原生的字符串，而是自己实现了一个 SDS（简单动态字符串&…...

编程日记 2025/7/14 19:04:40

力扣打卡8：最长上升子序列

链接：300. 最长递增子序列 - 力扣（LeetCode） 本题我开始想到的是dp，复杂度为O(n^2)，这也是很经典的解法。看到进阶解法可以O(nlogn)，想到可能是要用到二分，但是，我想到的是和map排…...

编程日记 2025/7/12 11:19:48

记录一次老平台改造通知用户刷新页面，纯前端实现

记录一次老平台改造通知用户刷新页面，纯前端实现方案概述背景现状问题本质方案设计前提设计实现其他补充写在最后的话抛出一个问题方案概述背景前端构建完上线，用户还停留还在老页面，用户不知道网页重新部署了，跳转页面的时…...

编程日记 2025/7/14 1:25:46

默认的是不行的不管pull啥镜像仍然会出现这个错误 Error response form daemon:Get "https://registry-1.docker.io/v2": net/http: request canceled while waiting for connection (Client.Timeout exceeded while await) 操作方法是如果在目录没有/etc/docker…...

编程日记 2025/7/14 21:27:26

Chrome扩展程序开发示例

项目文件夹内文件如下： manifest.json文件内容： {"manifest_version": 3,"name": "我的法宝","description": "我的有魔法的宝贝","version": "1.0","icons": {"…...

编程日记 2025/7/14 21:02:58

Linux 下使用飞鸽传书实现与Windows飞秋的通信

最近把单位的办公电脑换成Linux系统，但是其他同事们都使用飞秋2013进行局域网通信和文件传输，经过一番尝试，发现飞鸽传书For Linux 2014能够实现两者的互相通信。飞鸽传书ForLINUXLinux版下载_飞鸽传书ForLINUX免费下载_飞鸽传书ForLINUX1.2…...

编程日记 2025/7/13 1:51:40

docker批量创建cloudstack虚拟主机脚本

批量创建cloudstack脚本 #!/bin/bash # 配置变量 container_prefix"cloudworker-" base_ip"192.168.1." start_ip2 #开始ip start_container2 #上同 end_container4 #结束ip 包括 network_name"my_macvlan_network" image_name"dockedahi:…...

编程日记 2025/7/6 12:20:09

SpringBoot项目集成MinIO

最近在学习MinIO，所以想让自己的SpringBoot项目集成MinIO,在网上查阅资料，并进行操作的过程中遇到一些问题，所以想把自己遇到的坑和完成步骤记录下来供自己和各位查阅。一. MinIO的下载安装以及基本使用 1. 下载地址：https://d…...

编程日记 2025/7/12 5:57:32

【Flutter】常用样式、方法、组件（长期更新中）

一、样式设置设置颜色透明度：color: Color(0xff4B9E32).withOpacity(0.08) 二、常用方法数组排序：list.sort(); **升序**：(obj1, obj2) > obj1.compareTo(obj2) **降序**：(obj1, obj2) > obj2.compareTo(obj1)obj1.co…...

编程日记 2025/7/14 10:49:30

dbus接口方法的variant类型传参详解

python实现c++中so库调用及dbus服务开发-CSDN博客之前写的这篇博文介绍了如何创建一个dbus服务，但是注册的接口方法的入参还是比较简单的，实际上dbus的参数类型有很多种，调用方式也有多种，我们来逐一介绍下。其实基础数据类型，如字符串、整型、浮点型、布尔型等大多数…...

编程日记 2025/7/13 22:24:44

【时时三省】（NIT计算机考试）Word的使用方法

山不在高，有仙则名。水不在深，有龙则灵。 ----CSDN 时时三省一、软件简介 Microsoft Word，简称Word，是微软公司开发的一款文字处理软件，广泛应用于文档编辑、排版、打印等领域。无论是撰写论文、报告、简历&#xf…...

编程日记 2025/7/14 21:22:07

spring技术点

引入对象 Autowired 和 Resource的区别 Autowired 和 Resource的区别 valid 参数校验 jarkata进行SpringMVC校验常规当前进行校验的配置操作，参考文档如下进行操作。 SpringMVC校验注解不生效 List类型参数校验由于list类型默认不能进行标注校验实现&#x…...

编程日记 2025/7/4 5:54:12

工业—使用Flink处理Kafka中的数据_ChangeRecord1

使用 Flink 消费 Kafka 中 ChangeRecord 主题的数据，当某设备 30 秒状态连续为 “ 预警 ” ，输出预警信息。当前预警信息输出后，最近30...

编程日记 2025/7/3 13:45:03

实验日志——DETR

DETR训练日志 1. 代码来源代码源自作者的Github: https://github.com/facebookresearch/detr?tabreadme-ov-file 2. 数据来源在DETR中只使用了COCO2017数据集，其中训练集有118288张图像，验证集有5001张数据，测试集有40671张数据&#…...

编程日记 2025/7/14 21:43:58

前端常用缓存技术深度剖析

🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

编程日记 2025/6/28 19:59:17

汽车IVI中控开发入门及进阶（三十七）：基于HFP协议的蓝牙电话

概述： HFP全称Hands-free Profile，是一款让蓝牙设备控制电话的软件，多用于汽车上。此类设备最常见的例子是车载免提装置与蜂窝电话或可穿戴无线耳机一起使用。该配置文件定义了支持免提配置文件的两个设备如何在点对点的基础上相互交互。免提模式的实现通常使耳机或嵌入式免…...

编程日记 2025/7/12 6:24:14

分布式系统架构1：共识算法Paxos

1.背景今天开始更新分布式的文章，工作几年后还没系统的学习分布式的内容，趁着还有时间学习沉淀的时候多输出些文章 2.为什么需要分布式共识算法思考：现在你有一份随时变动的数据，需要确保它正确存储在网络的几台不同机器上&a…...

编程日记 2025/7/13 22:17:11

大语言模型应用Text2SQL本地部署实践初探

自从两年前OpenAI公司发布ChatGPT后，大模型(Large Language Model，简称LLM)相关技术在国内外可谓百家争鸣，遍地开花，在传统数据挖掘、机器学习和深度学习的基础上，正式宣告进入快速发展的人工智能(Artificial Intellig…...

编程日记 2025/7/14 11:52:21

C# WPF抽奖程序

C# WPF抽奖程序 using Microsoft.Win32; using System; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Windows; using System.…...

编程日记 2025/7/14 5:43:54

常见限流算法详细解析

固定时间窗口算法

生活示例

算法原理

代码示例

存在问题

滑动时间窗算法

生活示例

原理

图解

代码示例

漏桶算法

生活示例

算法原理

代码示例

优点：

缺点：

令牌桶算法

生活示例

算法原理

代码示例

优点：

缺点：

总结：

相关文章：