Java高并发系统限流算法的实现（Java高并发处理）

目录1 概述2 计数器限流2.1 概述2.2 实现2.3 结果分析2.4 优缺点2.5 应用3 漏桶算法3.1 概述3.2 实现3.3 结果分析3.4 优缺点4 令牌桶算法4.1 概述4.2 实现4.3 结果分析4.4 应用5 滑动窗口5.1 概述5.2 实现5.3 结果分析5.4 应用

1 概述

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。限流可以认为服务降级的一种，限流是对系统的一种保护措施。即限制流量请求的频率（每秒处理多少个请求）。一般来说，当请求流量超过系统的瓶颈，则丢弃掉多余的请求流量，保证系统的可用性。即要么不放进来，放进来的就保证提供服务。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

2 计数器限流

2.1 概述

计数器采用简单的计数操作，到一段时间节点后自动清零

2.2 实现

package com.oldlu.limit;

import java.util.concurrent.*;

public class Counter {

public static void main(String[] args) {

//计数器，这里用信号量实现

final Semaphore semaphore = new Semaphore(3);

//定时器，到点清零

ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

service.scheduleAtFixedRate(new Runnable() {

@Override

public void run() {

semaphore.release(3);

}

},3000,3000,TimeUnit.MILLISECONDS);

//模拟无数个请求从天而降

while (true) {

try {

//判断计数器

semaphore.acquire();

} catch (InterruptedException e) {

e.printStackTrace();

}

//如果准许响应，打印一个ok

System.out.println("ok");

}

}

}

2.3 结果分析

3个ok一组呈现，到下一个计数周期之前被阻断

2.4 优缺点

实现起来非常简单。控制力度太过于简略，假如1s内限制3次，那么如果3次在前100ms内已经用完，后面的900ms将只能处于阻塞状态，白白浪费掉。

2.5 应用

使用计数器限流的场景较少，因为它的处理逻辑不够灵活。最常见的可能在web的登录密码验证，输入错误次数冻结一段时间的场景。如果网站请求使用计数器，那么恶意攻击者前100ms吃掉流量计数，使得后续正常的请求被全部阻断，整个服务很容易被搞垮。

3 漏桶算法

3.1 概述

漏桶算法将请求缓存在桶中，服务流程匀速处理。超出桶容量的部分丢弃。漏桶算法主要用于保护内部的处理业务，保障其稳定有节奏的处理请求，但是无法根据流量的波动弹性调整响应能力。现实中，类似容纳人数有限的服务大厅开启了固定的服务窗口。

3.2 实现

package com.oldlu.limit;

import java.util.concurrent.*;

public class Barrel {

public static void main(String[] args) {

//桶，用阻塞队列实现，容量为3

final LinkedBlockingQueue que = new LinkedBlockingQueue(3);

//定时器，相当于服务的窗口，2s处理一个

ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

service.scheduleAtFixedRate(new Runnable() {

@Override

public void run() {

int v = que.poll();

System.out.println("处理："+v);

}

},2000,2000,TimeUnit.MILLISECONDS);

//无数个请求，i 可以理解为请求的编号

int i=0;

while (true) {

i++;

try {

System.out.println("put:"+i);

//如果是put，会一直等待桶中有空闲位置，不会丢弃

// que.put(i);

//等待1s如果进不了桶，就溢出丢弃

que.offer(i,1000,TimeUnit.MILLISECONDS);

} catch (Exception e) {

e.printStackTrace();

}

}

}

}

3.3 结果分析

put任务号按照顺序入桶执行任务匀速的1s一个被处理因为桶的容量只有3，所以1-3完美执行，4被溢出丢弃，5正常执行

3.4 优缺点

有效的挡住了外部的请求，保护了内部的服务不会过载内部服务匀速执行，无法应对流量洪峰，无法做到弹性处理突发任务任务超时溢出时被丢弃。现实中可能需要缓存队列辅助保持一段时间5）应用nginx中的限流是漏桶算法的典型应用，配置案例如下：

http {

#$binary_remote_addr 表示通过remote_addr这个标识来做key，也就是限制同一客户端ip地址。

#zone=one:10m 表示生成一个大小为10M，名字为one的内存区域，用来存储访问的频次信息。

#rate=1r/s 表示允许相同标识的客户端每秒1次访问

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {

location /limited/ {

#zone=one 与上面limit_req_zone 里的name对应。

#burst=5 缓冲区，超过了访问频次限制的请求可以先放到这个缓冲区内，类似代码中的队列长度。

#nodelay 如果设置，超过访问频次而且缓冲区也满了的时候就会直接返回503，如果没有设置，则所有请求

会等待排队，类似代码中的put还是offer。

limit_req zone=one burst=5 nodelay;

}

}

4 令牌桶算法

4.1 概述

令牌桶算法可以认为是漏桶算法的一种升级，它不但可以将流量做一步限制，还可以解决漏桶中无法弹性伸缩处理请求的问题。体现在现实中，类似服务大厅的门口设置门禁卡发放。发放是匀速的，请求较少时，令牌可以缓存起来，供流量爆发时一次性批量获取使用。而内部服务窗口不设限。

4.2 实现

package com.oldlu.limit;

import java.util.concurrent.*;

public class Token {

public static void main(String[] args) throws InterruptedException {

//令牌桶，信号量实现，容量为3

final Semaphore semaphore = new Semaphore(3);

//定时器，1s一个，匀速颁发令牌

ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

service.scheduleAtFixedRate(new Runnable() {

@Override

public void run() {

if (semaphore.availablePermits() < 3){

semaphore.release();

}

// System.out.println("令牌数："+semaphore.availablePermits());

}

},1000,1000,TimeUnit.MILLhttp://ISECONDS);

//等待，等候令牌桶储存

Thread.sleep(5);

//模拟洪峰5个请求，前3个迅速响应，后两个排队

for (int i = 0; i < 5; i++) {

semaphore.acquire();

System.out.println("洪峰："+i);

}

//模拟日常请求，2s一个

for (int i = 0; i < 3; i++) {

Thread.sleep(1000);

semaphore.acquire();

System.out.println("日常："+i);

Thread.sleep(1000);

}

//再次洪峰

for (int i = 0; i < 5; i++) {

semaphore.acquire();

System.out.println("洪峰："+i);

}

//检查令牌桶的数量

for (int i = 0; i < 5; i++) {

Thread.sleep(2000);

System.out.println("令牌剩余："+semaphore.availablePermits());

}

}

}

4.3 结果分析

注意结果出现的节奏！洪峰0-2迅速被执行，说明桶中暂存了3个令牌，有效应对了洪峰洪峰3，4被间隔性执行，得到了有效的限流日常请求被匀速执行，间隔均匀第二波洪峰来临，和第一次一样请求过去后，令牌最终被均匀颁发，积累到3个后不再上升

4.4 应用

springcloud中gateway可以配置令牌桶实现限流控制，案例如下：

cloud:

gateway:

routes:

‐ id: limit_route

uri: http://localhost:8080/test

filters:

‐ name: RequestRateLimiter

args:

#限流的key，ipKeyResolver为spring中托管的Bean，需要扩展KeyResolver接口

key‐resolver: '#{@ipResolver}'

#令牌桶每秒填充平均速率，相当于代码中的发放频率

redis‐rate‐limiter.replenishRate: 1

#令牌桶总容量，相当于代码中，信号量的容量

redis‐rate‐limiter.burstCapacity: 3

5 滑动窗口

5.1 概述

滑动窗口可以理解为细分之后的计数器，计数器粗暴的限定1分钟内的访问次数，而滑动窗口限流将1分钟拆为多个段，不但要求整个1分钟内请求数小于上限，而且要求每个片段请求数也要小于上限。相当于将原来的计数周期做了多个片段拆分。更为精细。

5.2 实现

package com.oldlu.limit;

import java.util.LinkedList;

import java.util.Map;

import java.util.TreeMap;

import java.util.concurrent.Executors;

import java.util.concurrent.ScheduledExecutorService;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.atomic.AtomicInteger;

public class Window {

//整个窗口的流量上限，超出会被限流

final int totalMax = 5;

//每片的流量上限，超出同样会被拒绝，可以设置不同的值

final int sliceMax = 5;

//分多少片

final int slice = 3;

//窗口，分3段，每段1s，也就是总长度3s

final LinkedList linkedList = new LinkedList<>();

//计数器，每片一个key，可以使用HashMap，这里为了控制台保持有序性和可读性，采用TreeMap

Map map = new TreeMap();

//心跳，每1s跳动1次，滑动窗口向前滑动一步，实际业务中可能需要手动控制滑动窗口的时机。

ScheduledExecutorService service = Executors.newScheduledThreadPool(1);

//获取key值，这里即是时间戳（秒）

private Long getKey(){

return System.currentTimeMillis()/1000;

}

public Window(){

//初始化窗口，当前时间指向的是最末端，前两片其实是过去的2s

Long key = getKey();

for (int i = 0; i < slice; i++) {

linkedList.addFirst(key‐i);

map.put(key‐i,new AtomicInteger(0));

}

//启动心跳任务，窗口根据时间，自动向前滑动，每秒1步

service.scheduleAtFixedRate(new Runnable() {

@Override

public void run() {

Long key = getKey();

//队尾添加最新的片

linkedList.addLast(key);

map.put(key,new AtomicInteger());

//将最老的片移除

map.remove(linkedList.getFirst());

linkedList.removeFirst();

System.out.println("step:"+key+":"+map);;

}

},1000,1000,TimeUnit.MILLISECONDS);

}

//检查当前时间所在的片是否达到上限

public boolean checkCurrentSlice(){

long key = getKey();

AtomicInteger integer = map.get(key);

if (integer != null){

return integer.get() < sliceMax ;

}

//默认允许访问

return true;

}

//检查整个窗口所有片的计数之和是否达到上限

public boolean checkAllCount(){

return map.values().stream().mapToInt(value ‐> value.get()).sum() < totalMax;

}

//请求来临....

public void req(){

Long key = getKey();

//如果时间窗口未到达当前时间片，稍微等待一下

//其实是一个保护措施，放置心跳对滑动窗口的推动滞后于当前请求

while (linkedList.getLast()

try {

Thread.sleep(200);

} catch (InterruptedException e) {

e.printStackTrace();

}

}

//开始检查，如果未达到上限，返回ok，计数器增加1

//如果任意一项达到上限，拒绝请求，达到限流的目的

//这里是直接拒绝。现实中可能会设置缓冲池，将请求放入缓冲队列暂存

if (checkCurrentSlice() && checkAllCount()){

map.get(key).incrementAndGet();

System.out.println(key+"=ok:"+map);

}else {

System.out.println(key+"=reject:"+map);

}

}

public static void main(String[] args) throws InterruptedException {

Window window = new Window();

//模拟10个离散的请求，相对之间有200ms间隔。会造成总数达到上限而被限流

for (int i = 0; i < 10; i++) {

Thread.sleep(200);

window.req();

}

//等待一下窗口滑动，让各个片的计数器都置零

Thread.sleep(3000);

//模拟突发请求，单个片的计数器达到上限而被限流

System.out.println("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐");

for (int i = 0; i < 10; i++) {

window.req();

}

}

}

5.3 结果分析

模拟零零散散的请求，会造成每个片里均有计数，总数达到上限后，不再响应，限流生效：

再模拟突发的流量请求，会造成单片流量计数达到上限，不再响应而被限流

5.4 应用

滑动窗口算法，在tcp协议发包过程中被使用。在web现实场景中，可以将流量控制做更细化处理，解决计数器模型控制力度太粗暴的问题。

try {

Thread.sleep(200);

} catch (InterruptedException e) {

e.printStackTrace();

}

}

//开始检查，如果未达到上限，返回ok，计数器增加1

//如果任意一项达到上限，拒绝请求，达到限流的目的

//这里是直接拒绝。现实中可能会设置缓冲池，将请求放入缓冲队列暂存

if (checkCurrentSlice() && checkAllCount()){

map.get(key).incrementAndGet();

System.out.println(key+"=ok:"+map);

}else {

System.out.println(key+"=reject:"+map);

}

}

public static void main(String[] args) throws InterruptedException {

Window window = new Window();

//模拟10个离散的请求，相对之间有200ms间隔。会造成总数达到上限而被限流

for (int i = 0; i < 10; i++) {

Thread.sleep(200);

window.req();

}

//等待一下窗口滑动，让各个片的计数器都置零

Thread.sleep(3000);

//模拟突发请求，单个片的计数器达到上限而被限流

System.out.println("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐");

for (int i = 0; i < 10; i++) {

window.req();

}

}

}

5.3 结果分析

模拟零零散散的请求，会造成每个片里均有计数，总数达到上限后，不再响应，限流生效：

再模拟突发的流量请求，会造成单片流量计数达到上限，不再响应而被限流

5.4 应用

滑动窗口算法，在tcp协议发包过程中被使用。在web现实场景中，可以将流量控制做更细化处理，解决计数器模型控制力度太粗暴的问题。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。