java中常见的限流算法详细解析_java 固定窗口算法

前言

以下的文章参考了一些具体的资料加深了解
B站：Java限流算法，你知道该怎么做吗？

1. 验证限流以及容器限流

突发的流量请求，系统可能会造成奔溃。可以通过集群多个服务器，所以要加以限流
生活中的比如秒杀订单或者微博热搜条等

在某种容器或者验证上也可以加以限流，具体如下

• 合法性的验证限流：验证码、ip黑名单（防止无限次的调用）
• 容器限流：tomcat、nginx

tomcat的限流在配置文件配置如下：
通过限制线程数的参数个数maxThreads="150"

<Connector port="8080" prptpcpl="HTTP/1.1"
	connectionTimeout="20000"
	maxThreads="150"
	redirectPort="8443">
1
2
3
4

nginx的限流配置文件配置如下：

• 控制速率：(通过控制每秒2个并发数，队列存储4个，多了会拒绝)

limit_req_zone $binary_remote_addr zone mylimit:10m rate=2/s;
server{
	location /{
		limit_req zone=mylimit brust=4;
	}
}
1
2
3
4
5
6

• 控制并发数：（通过控制ip以及端口号）

limit_conn_zone $binary_remote_addr zone=perip:10m;
limit_conn_zone $binary_name zone=perserver:10m;
server{
	limit_conn perip 10;
	limit_conn perserver 100;
}
1
2
3
4
5
6

2. 服务端限流

服务端限流：固定时间窗口算法、滑动时间窗口算法、漏桶算法、令牌桶算法

2.1 固定时间窗口

通过固定窗口，对每个窗口在固定时间内加以流量限制。
通过计数器，如果有请求，计数器加1

但是这样会造成流量分布不均匀，某一时间刻可能就已经把该窗口的数据量用完，其他时间段已经不能使用或者该时间段已经访问不了，请求都会被拒绝，这种现象称为突刺现象
时间跨度越大，临界值不好设值

2.2 滑动时间窗口

为此可以将上面的算法加以处理
将其每个窗口细化成好几个窗口，时间范围缩小，时间粒度控制比较小，每个小窗口都有其计数器

该小窗口如果已经结束，往右滑动获取另外一个小窗口（该算法复杂度比较高，市面少部分也会有使用）

2.3 漏桶算法

上面的水流量可以存放（满了就会拒绝·），下面的水流量可以匀速访问，以恒定的速度进行访问（类似一秒钟只能访问多少个请求）。但是处理不了短时的高并发数据量

主要通过redis的命令，具体如下：c1.throttle mylimit 15(桶的容量) 30(流水量) 60(时间)

实现：用队列保存请求，用ScheduledThreadPoolExecutor（支持定时任务的线程池）来定时从队列获取

2.4 令牌桶算法

漏桶算法限制请求的速率，而令牌桶算法在限制请求速率的同时还允许一定程度的数据量突发调用

以恒定的速率生成令牌，即使遇到高并发的数据量，可以生成多个令牌数据。满了之后，会丢弃或者以一定的速率进行放入。
只有真正拿到令牌的数据才会执行其操作

可以处理瞬时的并发数据量

public class RateLimiterExample{
	public static void main(String[] args){
	//每秒产生10个令牌（每100ms产生一个）
		RateLimiter rt=RateLimiter.create(10);
		//11个线程逐一获取
		for(int i=0;i<11;i++){
			new Thread(()->{
				//获取1个令牌
					rt.acquire();
						System.out.println(" "+Instant.now());					
			}).start();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

RateLimiter的算法：

• token bucket
  非常易于出现
  最好设置的上线的限度是攻击的2倍

借两个窗口之间的请求进行攻击的话，可能会导致整个系统崩溃掉
为此有了如下算法

• sliding windows
  不仅记录的请求数量，还记录了所有请求的时间戳
  请求到达的时候，会移除距离这个当前节点相应单位窗口之外的所有旧请求，再来判断当前的请求与窗口请求数量（上限值是它的2倍），如果合适就接收请求。

具体算法的实现是某个ip或者用户等的限制，每个时间内的请求的上限，过期时间
这种设计模式可以通过redis很好的实现，通过设置key，设置时间限制的过期