Java 实现滑动时间窗口限流算法的代码

在网上搜滑动时间窗口限流算法,大多都太复杂了,本人实现了个简单的,先上代码:

package cn.dijia478.util;

import java.time.LocalTime;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 滑动时间窗口限流工具
 * 本限流工具只适用于单机版,如果想要做全局限流,可以按本程序的思想,用redis的List结构去实现
 *
 * @author dijia478
 * @date 2020-10-13 10:53
 */
public class SlideWindow {

  /** 队列id和队列的映射关系,队列里面存储的是每一次通过时候的时间戳,这样可以使得程序里有多个限流队列 */
  private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();

  private SlideWindow() {}

  public static void main(String[] args) throws InterruptedException {
    while (true) {
      // 任意10秒内,只允许2次通过
      System.out.println(LocalTime.now().toString() + SlideWindow.isGo("ListId", 2, 10000L));
      // 睡眠0-10秒
      Thread.sleep(1000 * new Random().nextInt(10));
    }
  }

  /**
   * 滑动时间窗口限流算法
   * 在指定时间窗口,指定限制次数内,是否允许通过
   *
   * @param listId   队列id
   * @param count   限制次数
   * @param timeWindow 时间窗口大小
   * @return 是否允许通过
   */
  public static synchronized boolean isGo(String listId, int count, long timeWindow) {
    // 获取当前时间
    long nowTime = System.currentTimeMillis();
    // 根据队列id,取出对应的限流队列,若没有则创建
    List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
    // 如果队列还没满,则允许通过,并添加当前时间戳到队列开始位置
    if (list.size() < count) {
      list.add(0, nowTime);
      return true;
    }

    // 队列已满(达到限制次数),则获取队列中最早添加的时间戳
    Long farTime = list.get(count - 1);
    // 用当前时间戳 减去 最早添加的时间戳
    if (nowTime - farTime <= timeWindow) {
      // 若结果小于等于timeWindow,则说明在timeWindow内,通过的次数大于count
      // 不允许通过
      return false;
    } else {
      // 若结果大于timeWindow,则说明在timeWindow内,通过的次数小于等于count
      // 允许通过,并删除最早添加的时间戳,将当前时间添加到队列开始位置
      list.remove(count - 1);
      list.add(0, nowTime);
      return true;
    }
  }

}

运行可以看到,任意10秒内,通过的次数不超过2次。或者按照实现原理来说,任意通过2次内的时间差,都不超过10秒:

这里画图做说明,为什么这样可以做到滑动窗口限流,假设10秒内允许通过5次

1.这条线就是队列list,当第一个事件进来,队列大小是0,时间是第1秒:

2.因为size=0,小于5,都没有到限制的次数,完全不用考虑时间窗口,直接把这次事件的时间戳放到0的位置:

3.第2.8秒的时候,第二个事件来了。因为此时size=1,还是小于5,把这次事件的时间戳放到0的位置,原来第1秒来的事件时间戳会往后移动一格:

4.陆续的又来了3个事件,队列大小变成了5,先来的时间戳依次向后移动。此时,第6个事件来了,时间是第8秒:

5.因为size=5,不小于5,此时已经达到限制次数,以后都需要考虑时间窗口了。所以取出位置4的时间(离现在最远的时间),和第6个事件的时间戳做比较:

6.得到的差是7秒,小于时间窗口10秒,说明在10秒内,来的事件个数大于5了,所以本次不允许通过:

7.接下来即便来上100个事件,只要时间差小于等于10秒,都同上,拒绝通过:

8.第11.1秒,第101次事件过来了。因为size=5,不小于5,所以取出位置4的时间(离现在最远的时间),和第101个事件的时间戳做比较:

9.得到的差是10.1秒,大于时间窗口10秒,说明在10秒内,来的事件个数小于等于5了,所以本次允许通过:

10.删除位置4的时间(离现在最远的时间),把这次事件的时间戳放到0的位置,后面的时间戳依次向后移动:

往后再来其他事件,就是重复4-10的步骤,即可实现,在任意滑动时间窗口内,限制通过的次数

其本质思想是转换概念,将原本问题的确定时间大小,进行次数限制。转换成确定次数大小,进行时间限制。

到此这篇关于Java 实现滑动时间窗口限流算法的代码的文章就介绍到这了,更多相关Java滑动时间窗口限流算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java实现仿淘宝滑动验证码研究代码详解

    通过下面一张图看下要实现的功能,具体详情如下所示: 现在我就来介绍些软件的其它功能.希望大家有所受益. 模拟人为搜索商品 在刷单的时候,不能直接拿到一个商品网址就进入购买页面吧,得模拟人为搜索. 在这一个过程中有两个难点: 1)商品列表的异步加载 ; 2)翻页并且截图; 在园子里,我就不在关公面前耍大刀了. 直接上关键代码: i:搜索商品,并且翻页 public bool? SearchProduct(TaskDetailModel taskDetailData) { bool? result

  • selenium+java破解极验滑动验证码的示例代码

    摘要 分析验证码素材图片混淆原理,并采用selenium模拟人拖动滑块过程,进而破解验证码. 人工验证的过程 1.打开威锋网注册页面 2.移动鼠标至小滑块,一张完整的图片会出现(如下图1) 3.点击鼠标左键,图片中间会出现一个缺块(如下图2) 4.移动小滑块正上方图案至缺块处 5.验证通过 selenium模拟验证的过程 加载威锋网注册页面 下载图片1和缺块图片2 根据两张图片的差异计算平移的距离x 模拟鼠标点击事件,点击小滑块向右移动x 验证通过 详细分析 1.打开chrome浏览器控制台,会

  • java实现菜单滑动效果

    菜单滑动效果的实现 public class MenuScrollerActivity extends BaseGameActivity implements IScrollDetectorListener, IOnSceneTouchListener, IClickDetectorListener { // =========================================================== // Constants // ==================

  • Java selenium处理极验滑动验证码示例

    要爬取一个网站遇到了极验的验证码,这周都在想着怎么破解这个,网上搜了好多知乎上看到有人问了这问题,我按照这思路去大概实现了一下. 1.使用htmlunit(这种方式我没成功,模拟鼠标拖拽后轨迹没生成,可以跳过) 我用的是java,我首先先想到了用直接用htmlunit,我做了点初始化 private void initWebClient() { if (webClient != null) { return; } webClient = new WebClient(BrowserVersion.

  • Javaweb应用使用限流处理大量的并发请求详解

    在web应用中,同一时间有大量的客户端请求同时发送到服务器,例如抢购.秒杀等.这个时候如何避免将大量的请求同时发送到业务系统. 第一种方法:在容器中配置最大请求数,如果大于改请求数,则客户端阻塞.该方法有效的阻止了大量的请求同时访问业务系统,但对用户不友好. 第二种方法:使用过滤器,保证一定数量的请求能够正常访问系统,多余的请求先跳转到排队页面,由排队页面定时发起请求.过滤器实现如下: public class ServiceFilter implements Filter { private

  • Java实现滑动验证码的示例代码

    最近滑动验证码在很多网站逐步流行起来,一方面对用户体验来说,比较新颖,操作简单,另一方面相对图形验证码来说,安全性并没有很大的降低.当然到目前为止,没有绝对的安全验证,只是不断增加攻击者的绕过成本. 接下来分析下滑动验证码的核心流程: 后端随机生成抠图和带有抠图阴影的背景图片,后台保存随机抠图位置坐标 前端实现滑动交互,将抠图拼在抠图阴影之上,获取到用户滑动距离值,比如以下示例 前端将用户滑动距离值传入后端,后端校验误差是否在容许范围内. 这里单纯校验用户滑动距离是最基本的校验,出于更高的安全考

  • Java 实现滑动时间窗口限流算法的代码

    在网上搜滑动时间窗口限流算法,大多都太复杂了,本人实现了个简单的,先上代码: package cn.dijia478.util; import java.time.LocalTime; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Random; import java.util.concurrent.ConcurrentHashMap; /** * 滑动时间窗

  • Java中4种经典限流算法讲解

    目录 限流是什么? 常见的限流算法 固定窗口限流算法 滑动窗口限流算法 漏桶算法 令牌桶算法 最近,我们的业务系统引入了Guava的RateLimiter限流组件,它是基于令牌桶算法实现的,而令牌桶是非常经典的限流算法.本文将跟大家一起学习几种经典的限流算法. 限流是什么? 维基百科的概念如下: In computer networks, rate limiting is used to control the rate of requests sent or received by a net

  • Golang实现常见的限流算法的示例代码

    目录 固定窗口 滑动窗口 漏桶算法 令牌桶 滑动日志 总结 限流是项目中经常需要使用到的一种工具,一般用于限制用户的请求的频率,也可以避免瞬间流量过大导致系统崩溃,或者稳定消息处理速率 这个文章主要是使用Go实现常见的限流算法,代码参考了文章面试官:来,年轻人!请手撸5种常见限流算法! 和面试必备:4种经典限流算法讲解如果需要Java实现或更详细的算法介绍可以看这两篇文章 固定窗口 每开启一个新的窗口,在窗口时间大小内,可以通过窗口请求上限个请求. 该算法主要是会存在临界问题,如果流量都集中在两

  • redis zset实现滑动窗口限流的代码

    目录 限流 rediszset特性 滑动窗口算法 java代码实现 补充:RediszSet实现滑动窗口对短信进行防刷限流 前言 示例代码 限流 需求背景:同一用户1分钟内登录失败次数超过3次,页面添加验证码登录验证,也即是限流的思想. 常见的限流算法:固定窗口计数器:滑动窗口计数器:漏桶:令牌桶.本篇选择的滑动窗口计数器 redis zset特性 Redis 有序集合(sorted set)和集合(set)一样也是 string 类型元素的集合,且不允许重复的成员.不同的是每个元素都会关联一个

  • Java实现5种限流算法及7种限流方式

    目录 前言 1. 限流 2. 固定窗口算法 2.1. 代码实现 3. 滑动窗口算法 3.1. 代码实现 4. 滑动日志算法 4.1. 代码实现 5. 漏桶算法 6. 令牌桶算法 6.1. 代码实现 6.2. 思考 7. Redis 分布式限流 7.1. 固定窗口限流 7.3. 滑动窗口限流 8. 总结 参考 前言 最近几年,随着微服务的流行,服务和服务之间的依赖越来越强,调用关系越来越复杂,服务和服务之间的稳定性越来越重要.在遇到突发的请求量激增,恶意的用户访问,亦或请求频率过高给下游服务带来较

  • 详解5种Java中常见限流算法

    目录 01固定窗口 02滑动窗口 03漏桶算法 04令牌桶 05滑动日志 06分布式限流 07总结 1.瞬时流量过高,服务被压垮? 2.恶意用户高频光顾,导致服务器宕机? 3.消息消费过快,导致数据库压力过大,性能下降甚至崩溃? ...... 在高并发系统中,出于系统保护角度考虑,通常会对流量进行限流:不但在工作中要频繁使用,而且也是面试中的高频考点. 今天我们将图文并茂地对常见的限流算法分别进行介绍,通过各个算法的特点,给出限流算法选型的一些建议,并给出Java语言实现的代码示例. 01固定窗

  • ASP.NET Core中使用滑动窗口限流的问题及场景分析

    目录 算法原理 漏检 太刚 算法实现 进程内即内存滑动窗口算法 基于Redis的滑动窗口算法 应用算法 1.安装Nuget包 2.使用中间件 滑动窗口算法用于应对请求在时间周期中分布不均匀的情况,能够更精确的应对流量变化,比较著名的应用场景就是TCP协议的流量控制,不过今天要说的是服务限流场景中的应用. 算法原理 这里假设业务需要每秒钟限流100次,先来看固定窗口算法的两个问题: 漏检 如下图所示,单看第1秒和第2秒,其请求次数都没有超过100,所以使用固定窗口算法时不会触发限流.但是第1秒的后

  • Java 常见的限流算法详细分析并实现

    目录 为什么要限流 限流算法 计数器限流 漏桶限流 令牌桶限流 为什么要限流 在保证可用的情况下尽可能多增加进入的人数,其余的人在排队等待,或者返回友好提示,保证里面的进行系统的用户可以正常使用,防止系统雪崩. 限流算法 限流算法很多,常见的有三类,分别是 计数器算法 .漏桶算法.令牌桶算法 . (1)计数器:           在一段时间间隔内,处理请求的最大数量固定,超过部分不做处理. (2)漏桶:           漏桶大小固定,处理速度固定,但请求进入速度不固定(在突发情况请求过多时

  • go redis实现滑动窗口限流的方式(redis版)

    之前给大家介绍过单机当前进程的滑动窗口限流 , 这一个是使用go redis list结构实现的滑动窗口限流 , 原理都一样 , 但是支持分布式 原理可以参考之前的文章介绍 func LimitFreqs(queueName string, count uint, timeWindow int64) bool { currTime := time.Now().Unix() length := uint(ListLen(queueName)) if length < count { ListPus

  • java限流算法详细

    目录 1.场景 2.算法详解 2.1 计数算法 2.1.1 说明 2.1.2 适用场景 2.1.3 代码 2.2 漏桶算法 2.2.1 说明 2.2.2 漏桶算法图示 2.2.3 适用场景 2.2.4 代码 2.3 令牌桶算法 2.3.1 说明 2.3.2 令牌桶算法图示 2.3.3 适用场景 2.3.4 代码 2.3.5 第三方工具类 1.场景 程序中经常需要对接口进行限流,防止访问量太大,导致程序崩溃. 常用的算法有:计数算法.漏桶算法.令牌桶算法,最常用的算法是后面两种. 2.算法详解 2

随机推荐