首页 > 编程语言 >常见的限流算法

常见的限流算法

时间:2024-09-16 23:48:55浏览次数:11  
标签:请求 int 常见 计数器 private 算法 限流

限流算法是用于控制访问频率、保护系统免受过载攻击的重要手段。常见的限流算法有以下几种,每种算法都有不同的应用场景和优缺点。下面是几种常见的限流算法的详细介绍:

1. 计数器算法(Counter)

原理

计数器算法是最简单的限流算法。它在固定的时间窗口内记录请求的次数,一旦请求次数达到预设的上限,后续请求会被拒绝。

实现步骤
  • 设置一个时间窗口(例如 1 秒、1 分钟等)。
  • 使用一个计数器记录在当前时间窗口内的请求数量。
  • 如果计数器达到限制次数,则拒绝后续请求;否则增加计数器。
  • 当时间窗口结束时,重置计数器。
优点
  • 实现简单,适合处理短时间内的高并发请求。
缺点
  • 临界问题:在时间窗口的边界处可能出现"流量突发",例如在窗口末尾和下一个窗口的开始时连续发出大量请求。
使用场景

适用于简单的限流场景,比如 API 接口每秒最多允许多少次请求。

代码示例(伪代码)

java

复制代码

class CounterLimiter { private int maxRequests; private int currentCount; private long windowStart; private long windowDuration; public boolean allowRequest() { long now = System.currentTimeMillis(); if (now - windowStart > windowDuration) { windowStart = now; currentCount = 0; } if (currentCount < maxRequests) { currentCount++; return true; } else { return false; } } }

2. 滑动窗口算法(Sliding Window)

原理

滑动窗口算法是对计数器算法的一种优化,它将时间窗口进一步划分为多个小的时间片段,从而避免计数器算法的临界问题。每个小窗口内维护一个计数器,当请求到达时,滑动窗口根据当前时间计算跨越的时间片段,并更新计数器。

实现步骤
  • 将大时间窗口(如 1 分钟)分成多个小时间窗口(如 10 秒),并为每个小时间窗口维护请求计数。
  • 每次请求到达时,判断它属于哪个小窗口,并更新相应计数器。
  • 同时计算过去的所有小窗口总请求数,如果总数超过限流阈值,则拒绝请求。
优点
  • 缓解了计数器算法的临界问题,流量分布更加平滑。
缺点
  • 实现相对复杂,需要额外的存储空间维护多个小时间窗口。
使用场景

适合希望更加平滑限流的场景,尤其是对流量有一定均匀要求的服务。

代码示例(伪代码)

java

复制代码

class SlidingWindowLimiter { private int[] windows; private long windowSize; private int maxRequests; public boolean allowRequest() { long now = System.currentTimeMillis(); int currentWindowIndex = getWindowIndex(now); updateWindow(now); int totalRequests = getTotalRequests(); if (totalRequests < maxRequests) { windows[currentWindowIndex]++; return true; } else { return false; } } // 辅助方法省略 }

3. 漏桶算法(Leaky Bucket)

原理

漏桶算法可以看作是一个水桶模型,桶的容量代表系统能处理的最大请求数,请求是向桶中注水,水以固定速率流出。如果桶满了,则会丢弃新的请求。

实现步骤
  • 创建一个固定容量的桶。
  • 请求到达时将其放入桶中,桶以固定的速率处理请求。
  • 如果桶已满,拒绝新请求。
优点
  • 请求处理速率是固定的,能够很好地平滑突发流量。
缺点
  • 固定处理速率可能无法适应某些突发流量大的场景,可能导致部分请求被丢弃。
使用场景

适用于处理具有固定速率的请求处理场景,如网络流量控制等。

代码示例(伪代码)

java

复制代码

class LeakyBucketLimiter { private int bucketSize; private long lastLeakTime; private int currentWater; private int leakRate; public boolean allowRequest() { long now = System.currentTimeMillis(); leak(now); if (currentWater < bucketSize) { currentWater++; return true; } else { return false; } } private void leak(long now) { int leakedWater = (int) ((now - lastLeakTime) * leakRate); currentWater = Math.max(0, currentWater - leakedWater); lastLeakTime = now; } }

4. 令牌桶算法(Token Bucket)

原理

令牌桶算法类似于漏桶算法,但它允许一定程度的突发流量。系统以固定的速率生成令牌,令牌存放在桶中。每次请求需要从桶中获取令牌,如果桶中有足够的令牌,则允许请求通过,否则拒绝。

实现步骤
  • 设置一个容量为 bucketSize 的桶,用于存储令牌。
  • 系统以固定速率生成令牌,如果桶未满,令牌将被加入桶中。
  • 请求到达时,尝试从桶中获取令牌,如果有足够的令牌则允许请求,否则拒绝。
优点
  • 支持突发流量,同时保证了整体请求处理的速率。
缺点
  • 实现略微复杂,需要维护生成令牌的过程。
使用场景

适合处理偶发性高并发的场景,如 API 限流和保护下游服务。

代码示例(伪代码)

java

复制代码

class TokenBucketLimiter { private int bucketSize; private int tokens; private int refillRate; private long lastRefillTime; public boolean allowRequest() { refill(); if (tokens > 0) { tokens--; return true; } else { return false; } } private void refill() { long now = System.currentTimeMillis(); int newTokens = (int) ((now - lastRefillTime) * refillRate); tokens = Math.min(bucketSize, tokens + newTokens); lastRefillTime = now; } }

5. Redis 计数限流

原理

Redis 可以通过其 INCREXPIRE 命令实现简单高效的限流。每次请求到达时,使用 INCR 增加 Redis 中的计数器,如果计数器超过阈值,则拒绝请求。同时,使用 EXPIRE 为计数器设置过期时间。

实现步骤
  • 每个请求到来时对 Redis 中的计数器进行 INCR
  • 如果计数器在一个时间窗口内超过设定的阈值,则限流。
  • EXPIRE 命令设置计数器的过期时间,以实现限流的时间窗口控制。
优点
  • 分布式环境中非常适合,支持高并发请求的计数和过期时间管理。
缺点
  • Redis 需要额外的存储和网络开销。
使用场景

适用于分布式系统中的限流,尤其是在 API 网关和微服务架构中。

代码示例(伪代码)

java

复制代码

class RedisRateLimiter { private RedisClient redis; private String key; private int maxRequests; private int windowTime; public boolean allowRequest() { int count = redis.incr(key); if (count == 1) { redis.expire(key, windowTime); } return count <= maxRequests; } }

总结

算法优点缺点使用场景
计数器算法实现简单,适合小型项目临界点可能导致突发流量简单限流
滑动窗口算法平滑计数器算法的缺点,避免流量突发需要更多的存储空间和实现复杂度流量分布较平滑的场景
漏桶算法固定处理速率,流量控制稳定突发流量支持不佳,可能丢弃请求固定速率的服务
令牌桶算法支持突发流量,保证请求处理的平滑实现复杂,维护令牌生成支持突发流量的限流场景
Redis 限流分布式限流简单高效需要依赖 Redis,增加网络开销

标签:请求,int,常见,计数器,private,算法,限流
From: https://blog.csdn.net/m0_68570169/article/details/142309156

相关文章

  • 【智能算法应用】粒子群算法求解最小生成树问题
    目录1.最小生成树MST2.算法原理3.算法过程4.结果展示5.参考文献6.代码获取1.最小生成树MST最小生成树(MinimumSpanningTree,MST)是在给定的加权无向图中寻找一个边的子集,使得这些边构成的树包含图中的所有顶点,并且边的总权重尽可能小。如果图......
  • 【智能算法应用】海洋捕食者算法求解TSP问题
    目录1.算法原理2.TSP数学模型3.结果展示4.参考文献5.代码获取1.算法原理【智能算法】海洋捕食者算法(MPA)原理及实现2.TSP数学模型旅行商问题(TSP)是一种著名的组合优化问题,它涉及寻找给定一组城市及其之间的距离或成本,如何规划一条最短的路径,使得旅行商从起点出发,......
  • 【智能算法应用】飞蛾扑火算法求解TSP问题
    目录1.算法原理2.TSP数学模型3.结果展示4.参考文献5.代码获取1.算法原理【智能算法】飞蛾扑火算法(MFO)原理及实现2.TSP数学模型旅行商问题(TSP)是一种著名的组合优化问题,它涉及寻找给定一组城市及其之间的距离或成本,如何规划一条最短的路径,使得旅行商从起点出发,访......
  • 文心一言 VS 讯飞星火 VS chatgpt (348)-- 算法导论23.2 7题
    七、假定图G的一棵最小生成树已经被计算出来。如果在图中加入一个新结点及其相关的新边,我们需要多少时间来对最小生成树进行更新?如果要写代码,请用go语言。文心一言:在图中加入一个新节点及其相关边后,要更新最小生成树(MST),通常意味着需要重新计算包含新节点的最小生成树,因为新节点的加......
  • 【自动化测试】常见的自动化遍历工具以及如何选择合适的自动化遍历工具
    引言自动化遍历测试通常依赖于特定的工具来实现应用的自动操作和测试文章目录引言一、常见的自动化遍历工具1.1Appium1.2Selenium1.3Calabash1.4RobotFramework1.5Espresso1.6XCTest1.7Macaca1.8TestComplete1.9UiAutomator1.10总结二、如何选择合适的自......
  • 代码随想录算法 - 二叉树6
    题目1235.二叉搜索树的最近公共祖先给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个结点p、q,最近公共祖先表示为一个结点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。”例如......
  • 碰撞检测:详解矩形AABB与OBB碰撞检测算法(附ROS C++可视化)
    碰撞检测:详解矩形AABB与OBB碰撞检测算法(附ROSC++可视化)引言在机器人、游戏开发、计算机图形学等领域,碰撞检测是一个至关重要的任务。碰撞检测的目的是确定两个或多个物体是否发生了碰撞,以便采取相应的措施,如避免碰撞、触发事件等。在二维空间中,矩形是最常见的几何形状之一,而AABB(Ax......
  • 《黑神话:悟空》玩家常见的AkMatrixReverb.dll丢失的解决方法
    AkMatrixReverb.dll是一个与音效处理相关的动态链接库文件,通常用于游戏中的音频回声和混响效果。在《黑神话:悟空》这款游戏中,这个DLL文件是用于处理游戏内的各种音效,使玩家能够体验到更加真实和沉浸的音效体验。如果您在启动或者运行游戏时遇到了“缺少AkMatrixReverb.dll”的......
  • 贪心算法(算法详解+模板+例题)
    1.贪心是什么贪心算法(GreedyAlgorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好的策略。虽然这种策略并不保证一定能得到全局最优解,但在许多情况下,它能提供近似最优解,而且计算效率高。贪心算法通常适用于那些具有“最优......
  • 小林coding学习笔记(内存页面置换算法)
    缺页中断示意图1在CPU里执行一条查找某个页面A的指令,首先是虚拟内存,会到虚拟内存和物理内存的映射关系的页表中查询。2页表中不存在需要查找的页面A的有效信息。3则触发缺页中断信号给操作系统,操作系统收到缺页中断信号后,就会去磁盘里面查找该页面。4操作系统在磁盘中查......