wordpress如何修改用户名密码,如何做seo网站,软件开发者选项,wordpress如何添加一级目录限流算法——时间滑动窗口
背景#xff1a;
在当今的微服务架构中#xff0c;会存在流量剧增的情况#xff0c;需要适当的限流才能保证我们服务不会被打崩#xff0c;因此一些限流组件就随之诞生#xff0c;主流的接口限流组件#xff0c;如 spring cloud alibaba sent…限流算法——时间滑动窗口
背景
在当今的微服务架构中会存在流量剧增的情况需要适当的限流才能保证我们服务不会被打崩因此一些限流组件就随之诞生主流的接口限流组件如 spring cloud alibaba sentinel等开源限流工具包如 guava 等。
本篇文章主要通过手撕代码对时间滑动窗口限流算法实现。
常见限流算法
限流算法是一种用于控制数据流速率的方法以防止系统过载或保证服务质量。常见的限流算法包括固定窗口算法、滑动窗口算法、漏桶算法、漏桶算法和令牌桶算法
固定窗口算法。这是一种简单的计数器算法它在固定的时间窗口内累加访问次数。当访问次数达到设定的阈值时触发限流策略。这种方法在每个新的时间窗口开始时进行计数器的清零。滑动窗口算法。滑动窗口算法是对固定窗口算法的改进它将时间窗口分为多个小周期每个小周期都有自己的计数器。随着时间的滑动过期的小周期数据被删除这样可以更精确地控制流量。漏桶算法。漏桶算法则是一种更加平滑的限流方式它以固定的速率处理请求就像漏桶以一定的速率释放水滴一样。如果请求速率超过漏桶的释放速率则超出部分的请求会被丢弃。令牌桶算法。令牌桶算法中系统以恒定的速率向桶中添加令牌每个请求在处理前都需要从桶中获取一个令牌。如果桶中没有足够的令牌则请求会被限流。
这些算法各有优缺点适用于不同的场景和需求。例如固定窗口和滑动窗口算法适合于QPS限流和统计总访问量而漏桶和令牌桶算法则更适合于保证请求处理的平滑性和速率限制。
业务场景
需求需要针对单个设备限制设备在固定时间内上报消息的频率所以需要在设备发送消息前判断当前设备是否超出了限流标准如果超过了标准就需要限制发送。
时间滑动窗口算法
例如需求是十秒钟限制请求数100
格子时间
我们可以将时间转为秒看作一个个格子将一秒钟看作一个格子当同一秒钟新来的请求就将当前格子中的计数加一随着时间的推移到下一秒钟就创建出新的格子这样我们就可以得到一个长链表里面是随着时间推移一个个记录请求数的格子。
窗口
我们需求是计算十秒钟的请求是否超限最新的十个格子也就是10秒钟就是我们当前的窗口大小。我们只需要计算当前窗口内的请求总数是否超过了限制即可。
滑动窗口
随之时间推移会不断的创建新的格式我们需要计算的窗口也会随着时间不断向后滑动只包含当前最新的十个格子。
如下图图示会建立一个长链表其中包括当前的时间窗口以及过期的时间格子。判断是否超限只需计算当前滑动窗口内的所有请求数之和即可。 缺陷
随着时间推移会不断创建新的格子此时链表就会越来越长并且过期的时间格子永远也用不到了所以需要将过期的时间格子进行清除并且最新的格子也需要一直创建此时就需要一个异步任务一直来创建和清除格子无论是在时间上还是空间上都是比较消耗性能。
有没有优化方法
答案是有的环形数组。
我们可以根据当前的窗口来创建一个环形的数组随着时间的推移新的格子会将原来个格子覆盖掉也不需要开启异步线程专门用来创建和清除格子。 环形数组
所谓环形数组我们可以使用数组 取余 的方式来实现。
可以通过对当前时间取余的方式确定当前时间格子的下标。
此时我们还需要维护一个变量上次请求时间lastTime需要与当前时间now进行比较来决定我们计数的策略。
会有以下三种情况
1情况一lastTime 和 now 在同一秒钟该情况只需要继续沿用上次请求创建的格子格子中请求数1即可。 2情况二当前时间和上次请求记录时间不在同一格子但是在同一个周期中没有超过一个周期。 该情况从当前时间now计算时间窗口保留在同一个周期内的格子 (now - lastTime] 之间的格子即绿色的格子里面存储的数据是同一个周期内的而从 (lastTime - now] 之间的格子已经是上一个周期已经淘汰需要将其重置为0并且将now 当前的格子数置为1重新开始计数当前格子。
3情况三当前时间和上次请求记录时间已经超过了一个周期中已经超过了环形数组中的一圈。 此时就需要将当前窗口内的所有格子进行清空重新开始计数。
4情况四异常情况时钟回拨可能是服务器时间被人修改往前修改了导致时间出错lastTime now需要重新统计。
java代码实现
package com.company.limit;import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicIntegerArray;
import java.util.concurrent.atomic.AtomicLong;/*** 时间滑动窗口算法* 限流算法*/
public class TimeSlidingWindow {/*** 限流上线次数*/private Integer limitMaxNum;/*** 滑动窗口格子数* 根据时间来60秒分成60格*/private Integer windowNum;/*** 上次统计时间单位秒*/private ConcurrentHashMapString, AtomicLong lastTimeMap;/*** 记录key值与时间窗口映射*/private ConcurrentHashMapString, AtomicIntegerArray timeWindowsMap;/*** 记录key值与窗口内请求总数映射*/private ConcurrentHashMapString, AtomicInteger timeCountMap;public TimeSlidingWindow(int limitMaxNum, int windowNum) {this.timeWindowsMap new ConcurrentHashMap();this.timeCountMap new ConcurrentHashMap();this.windowNum windowNum;this.limitMaxNum limitMaxNum;this.lastTimeMap new ConcurrentHashMap();}/*** 限流方法入口* param key* return*/public Boolean limit(String key) {// 获取当前窗口AtomicIntegerArray windows this.timeWindowsMap.computeIfAbsent(key, k - new AtomicIntegerArray(this.windowNum));// 获取当前窗口请求总和AtomicInteger count timeCountMap.computeIfAbsent(key, k - new AtomicInteger(0));AtomicLong lastTime lastTimeMap.computeIfAbsent(key, k - new AtomicLong(System.currentTimeMillis() / 1000));// 计算当前时间所处格子Long now System.currentTimeMillis() / 1000;int temp (int) (now % this.windowNum);// 计算当前时间与上次请求时间差用于刷新窗口Long diffTime now - lastTime.get();// System.out.println(now: now);
// System.out.println(lastTime: lastTime.get());// 将锁的粒度缩小单个value节点synchronized (windows) {if (diffTime 0 now.equals(lastTime.get())) {/*1当前时间所属格子与上次请求记录在同一个格子中该情况只需要继续沿用上次请求创建的格子格子中请求数*/windows.getAndAdd(temp, 1);count.addAndGet(1);} else if (diffTime 0 diffTime windowNum) {/*2当前时间和上次请求记录时间在同一个周期中环形数组的同一个周期中没有超过一个周期。该情况意味着从当前时间now计算时间窗口内请求数只需要保留并计算 (now - last) 之间的格子而从(last - now) 之间的格子已经淘汰需要将其重置为0并且将now 当前的格子数置为1重新开始计数当前格子。*/count clearExpireWindows(windows, (int) (lastTime.get() % this.windowNum), temp, count);windows.set(temp, 1);count.addAndGet(1);} else if (diffTime 0 diffTime this.windowNum) {/*3当前时间和上次请求记录时间不在同一个周期中已经超过了环形数组中的一圈。意味着之前统计的*/windows new AtomicIntegerArray(this.windowNum);windows.set(temp, 1);count.set(1);} else {/*4异常情况时钟回拨可能是服务器时间被人修改往前修改了导致时间出错需要重新统计*/System.out.println(时钟回拨时间异常重新开启限流统计);this.timeWindowsMap new ConcurrentHashMap();this.timeCountMap new ConcurrentHashMap();return true;}lastTime.set(now);// 如果限流了这次计数需要回退if (count.get() this.limitMaxNum) {windows.getAndAdd(temp, -1);count.addAndGet(-1);return false;}}return true;}/*** 清除过期数据* param windows 需要清除的窗口* param from 开始位置* param to 结束位置* param count 当前周期计算总和* return*/private AtomicInteger clearExpireWindows(AtomicIntegerArray windows, int from, int to, AtomicInteger count) {if (to from) {count.addAndGet(1);return count;}// 调整下标值若结束位置小于开始位置则说明当前格子位于下一个周期中。if (to from) {to this.windowNum to;}while (from to) {int window windows.get(from % this.windowNum);count.addAndGet(-window);windows.set(from % this.windowNum, 0);}return count;}public static void main(String[] args) {TimeSlidingWindow timeSlidingWindow new TimeSlidingWindow(5, 10);new Thread(() - {int i 0;while (i 600) {Boolean limit timeSlidingWindow.limit(/hello);System.out.println(/hello i : limit , 时间: (i * 300.0) / 1000.0);try {Thread.sleep(300);} catch (InterruptedException e) {e.printStackTrace();}i;}}).start();new Thread(() - {int i 0;while (i 600) {Boolean limit1 timeSlidingWindow.limit(/world);System.out.println(/world i : limit1 , 时间: (i * 500.0) / 1000.0);try {Thread.sleep(500);} catch (InterruptedException e) {e.printStackTrace();}i;}}).start();}
}
