Java内置队列和高性能队列Disruptor
一、队列简介
队列是一种特殊的线性表,遵循先入先出、后入后出(FIFO)的基本原则,一般来说,它只允许在表的前端进行删除操作,而在表的后端进行插入操作,但是java的某些队列运行在任何地方插入删除;比如我们常用的 LinkedList 集合,它实现了Queue 接口,因此,我们可以理解为 LinkedList 就是一个队列;
二、Java队列分类
Java中队列主要分为阻塞和非阻塞,有界和无界、单向链表和双向链表之分;
2.1、阻塞和非阻塞
-
阻塞队列
入列(添加元素)时,如果元素数量超过队列总数,会进行等待(阻塞),待队列的中的元素出列后,元素数量未超过队列总数时,就会解除阻塞状态,进而可以继续入列;
出列(删除元素)时,如果队列为空的情况下,也会进行等待(阻塞),待队列有值的时候即会解除阻塞状态,进而继续出列;
阻塞队列的好处是可以防止队列容器溢出;只要满了就会进行阻塞等待;也就不存在溢出的情况;
只要是阻塞队列,都是线程安全的;;
-
非阻塞队列
不管出列还是入列,都不会进行阻塞
入列时,如果元素数量超过队列总数,则会抛出异常,
出列时,如果队列为空,则取出空值;
一般情况下,非阻塞式队列使用的比较少,一般都用阻塞式的对象比较多;阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法:
-
出队阻塞方法 : take()
-
入队阻塞方法 : put()
2.2、有界和无界
-
有界:有界限,大小长度受限制
-
无界:无限大小,其实说是无限大小,其实是有界限的,只不过超过界限时就会进行扩容,就行ArrayList 一样,在内部动态扩容
2.3、单向链表和双向链表
单向链表 : 每个元素中除了元素本身之外,还存储一个指针,这个指针指向下一个元素;
双向链表 :除了元素本身之外,还有两个指针,一个指针指向前一个元素的地址,另一个指针指向后一个元素的地址;
三、Java内置队列
3.1、Java 队列接口继承图
3.2、常见的Java线程安全的内置队列
队列 | 有界性 | 锁 | 数据结构 | 队列类型 |
---|---|---|---|---|
ArrayBlockingQueue | 有界 | 加锁(ReentrantLock,读写同一把锁) | arraylist(数组) | 阻塞 |
LinkedBlockingQueue | 可选 | 加锁(ReentrantLock,读写各自一把锁) | linkedlist(链表) | 阻塞 |
ConcurrentLinkedQueue | 无界 | 无锁(CAS) | linkedlist(链表) | 非阻塞 |
LinkedTransferQueue | 无界 | 无锁(CAS) | linkedlist(链表) | 阻塞 |
PriorityBlockingQueue | 无界 | 加锁(ReentrantLock,读写同一把锁) | heap(堆) | 阻塞 |
DelayQueue | 无界 | 加锁(ReentrantLock,读写同一把锁) | heap(堆) | 阻塞 |
-
ArrayBlockingQueue
一个用数组实现的有界阻塞队列,初始化时必须指定队列大小。此队列按照先进先出(FIFO)的原则对元素进行排序。默认情况下采用非公平锁的方式实现,可以通过构造器传参控制是采用公平锁还是非公平锁实现
-
LinkedBlockingQueue
一个由链表结构组成的有界阻塞队列,此队列按照先进先出(FIFO)的原则对元素进行排序
-
LinkedTransferQueue
一个由链表结构组成的无界阻塞队列 -
ConcurrentLinkedQueue
一个通过CAS实现的线程安全的无界非阻塞队列
-
PriorityBlockingQueue
一个带优先级的无界队列,而不是先进先出队列。元素按优先级顺序被移除,而且它也是无界的,也就是没有容量上限,虽然此队列逻辑上是无界的,但是由于资源被耗尽,所以试图执行添加操作可能会导致 OutOfMemoryError 错误; -
DelayQueue
一个通过PriorityBlockingQueue实现延迟获取元素的无界队列无界阻塞队列,其中添加进该队列的元素必须实现Delayed接口(指定延迟时间),而且只有在延迟期满后才能从中提取元素。
如果要 实现 一个 线程安全的队列,有两种方式:一种是使用阻塞算法,另一种是使用非阻塞算法。
使用阻塞算法的队列可以用一个 锁 (入队和出队用同一把锁,ArrayBlockingQueue )或两个锁 (入队和出队 用不同的锁 ,LinkedBlockingQueue)等方式来 实现 。
非阻塞的实现 方式则 可以使用循环CAS 的方式来实现(ConcurrentLinkedQueue 。
3.3、队列常用方法
-
add:增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
-
remove:移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
-
element:返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
-
offer:添加一个元素并返回true 如果队列已满,则返回false
-
poll:移除并返问队列头部的元素 如果队列为空,则返回null
-
peek:返回队列头部的元素 如果队列为空,则返回null
-
put:添加一个元素 如果队列满,则阻塞
-
take:移除并返回队列头部的元素 如果队列为空,则阻塞
-
drainTo(list):一次性取出队列所有元素
知识点: remove、element、offer 、poll、peek 其实是属于Queue接口。
四、高性能队列Disruptor
4.1、Disruptor简介
Disruptor是英国外汇交易公司LMAX开发的一个高性能队列,研发的初衷是解决内存队列的延迟问题。与Kafka、RabbitMQ用于服务间的消息队列不同,disruptor一般用于线程间消息的传递。基于Disruptor开发的系统单线程能支撑每秒600万订单。 disruptor适用于多个线程之间的消息队列,作用与ArrayBlockingQueue有相似之处
,但是disruptor从功能、性能都远好于ArrayBlockingQueue,当多个线程之间传递大量数据或对性能要求较高时,可以考虑使用disruptor作为ArrayBlockingQueue的替代者。 官方也对disruptor和ArrayBlockingQueue的性能在不同的应用场景下做了对比,目测性能只有有5~10倍左右的提升。
目前,包括Apache Storm、Camel、Log4j2等等知名的框架都在内部集成了Disruptor用来替代jdk的队列,以此来获得高性能。
Disruptor使用观察者模式, 主动将消息发送给消费者, 而不是等消费者从队列中取; 在无锁的情况下, 实现queue(环形, RingBuffer)的并发操作, 性能远高于BlockingQueue。
4.2、高性能原理
Disruptor为什么性能这么好呢,主要依赖于以下四个特性
无锁设计:CAS
采用CAS无锁方式,保证线程的安全性。多线程环境下,多个生产者通过do/while循环的条件CAS,来判断每次申请的空间是否已经被其他生产者占据。假如已经被占据,该函数会返回失败,While循环重新执行,申请写入空间。如果申请到之后,直接在该位置写入或者读取数据。
ArrayBlockingQueue用了重量级lock锁,在我们加锁过程中我们会把锁挂起,解锁后,又会把线程恢复,这一过程会有一定的开销,并且我们一旦没有获取锁,这个线程就只能一直等待,这个线程什么事也不能做。
CAS 更多知识见 Java 锁
RingBuffer : 环形数组
引入环形的数组结构:这种固定大小的环形队列的另外一个好处就是可以做到完全的内存复用。在系统的运行过程中,不会有新的空间需要分配或者老的空间需要回收,大大减少系统分配空间及回收空间的额外开销,避免频繁的GC;同时,数组对处理器的缓存机制更加友好。
[图片上传失败...(image-1650c4-1677132259413)]
-
元素位置的定位:
数组长度强制要求一定是 2^n ,这样可以通过位运算,加快定位的速度。通过sequence &(queueSize-1)就能立即定位到实际的元素位置index,这比取余(%)操作快得多(hashMap定位也是采用这种方式)。
下标采取递增的形式,不用担心index溢出的问题,index是long类型,即使100万QPS的处理速度,也需要30万年才能用完。
-
消除伪共享 : 通过添加额外的无用信息,避免伪共享问题
当CPU访问某一个变量时候,首先会去看CPU Cache内是否有该变量,如果有则直接从中获取,否者就去主内存里面获取该变量,然后把该变量所在内存区域的一个Cache行大小的内存拷贝到Cache(cache行是Cache与主内存进行数据交换的单位)。
由于存放到Cache行的的是内存块而不是单个变量,所以可能会把多个变量存放到了一个cache行。当多个线程同时修改一个缓存行里面的多个变量时候,由于同时只能有一个线程操作缓存行,所以相比每个变量放到一个缓存行性能会有所下降,这就是伪共享。
总之伪共享的产生是因为多个变量被放入了一个缓存行,并且多个线程同时去写入缓存行中不同变量,解决伪共享最直接的方法就是填充,通过添加额外的无用信息,避免伪共享问题。
如上图变量x,y同时被放到了CPU的一级和二级缓存,当线程1使用CPU1对变量x进行更新时候,首先会修改cpu1的一级缓存变量x所在缓存行,这时候缓存一致性协议会导致cpu2中变量x对应的缓存行失效,那么线程2写入变量x的时候就只能去二级缓存去查找,这就破坏了一级缓存,而一级缓存比二级缓存更快。更坏的情况下如果cpu只有一级缓存,那么会导致频繁的直接访问主内存。我们的缓存都是以缓存行作为一个单位来处理的,所以失效x的缓存的同时,也会把y失效,反之亦然。
4.3、Disruptor应用场景
参考使用到disruptor的一些框架.
- log4j2
Log4j 2相对于Log4j 1最大的优势在于多线程并发场景下性能更优。该特性源自于Log4j 2的异步模式采用了Disruptor来处理。
-
Jstorm 在流处理中不同线程中数据交换,数据计算可能蛮多内存中计算, 流计算快进快出,disruptor应该不错的选择。
-
百度uid-generator 部分使用ring buffer和去伪共享等思路缓存已生成的uid,也部分参考了disruptor
经过测试,Disruptor的速度比LinkedBlockingQueue提高了七倍。所以,当你在使用LinkedBlockingQueue出现性能瓶颈的时候,你就可以考虑采用Disruptor的代替。
相关文章:

Java内置队列和高性能队列Disruptor
一、队列简介 队列是一种特殊的线性表,遵循先入先出、后入后出(FIFO)的基本原则,一般来说,它只允许在表的前端进行删除操作,而在表的后端进行插入操作,但是java的某些队列运行在任何地方插入删…...

比特数据结构与算法(第四章_下)二叉树的遍历
本章将会详细讲解二叉树遍历的四种方式,分别为前序遍历、中序遍历、后续遍历和层序遍历。在学习遍历之前,会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作&#…...
chatGPT是什么
2022年11月,人工智能公司OpenAI推出了一款聊天机器人:ChatGPT。它能够通过学习和理解人类语言来进行对话,还能与聊天对象进行有逻辑的互动。除了聊天,ChatGPT还能够根据聊天对象提出的要求,进行文字翻译、文案撰写、代…...
jenkins漏洞集合
目录 CVE-2015-8103 反序列化远程代码执行 CVE-2016-0788 Jenkins CI和LTS 远程代码执行漏洞 CVE-2016-0792 低权限用户命令执行 CVE-2016-9299 代码执行 CVE-2017-1000353 Jenkins-CI 远程代码执行 CVE-2018-1000110 用户枚举 CVE-2018-1000861 远程命令执行 CVE-2018…...

用canvas画一个炫酷的粒子动画倒计时
前言 😆 这是一篇踩在活动尾声的文章,主要是之前在摸鱼社群里有人发了个粒子动画的特效视频,想着研究研究写一篇文章出来看看,结果这一下子就研究了半个多月。 😂 下面就把研究成果通过文字的形式展现出来吧…...
Java技术学习——Maven相关知识
一、什么是Maven? Maven是Apache软件基金会组织维护的一款专门为Java项目提供构建和依赖管理支持的工具。 1.1 构建 构建过程包含的主要环节如下: 清理:删除上一次构建的结果,为下一次构建做好准备编译:Java源程序…...

C++ 认识和了解C++
1.在使用C语言写代码的时候开头要用到的是: #include<iostream> using namespace std;不可以写成这样: #include iostream.h(1)iostream是输入输出流类, istream输入流类 cin >> ostream输出流类 cout &…...
u盘误删的文件怎么找回
u盘误删的文件怎么找回?u盘的特点之一就是极其便携,可以容纳各种格式的数据和文件,需要时可以直接使用。每次使用都会或多或少的存放一些文件,但有使用就会有删除,为了不影响使用性,清理存储空间是必要的。清理中如果…...

二分查找由浅入深--算法--java
二分查找写在开头算法前提:算法逻辑算法实现简单实现leftright可能超过int表示的最大限度代码分析和变换更多需求:求索引最小的值java二分API应用基础题思考难度方法写在开头 二分查找应该是算比较简单的这种算法了,我本以为还可以。但有时候…...

【学习】笔记本电脑重新安装系统win10
安装系统有很多方法: 软件安装制作启动u盘本文使用的方法就是启动盘安装: 1.首先下载iso镜像文件: msdn我告诉你:MSDN, 我告诉你 - 做一个安静的工具站 (itellyou.cn) 2.下载启动盘制作工具: 制作启动盘rufus:Rufus - 轻松创建 USB 启动盘 3.官网下载: https://do…...

RocketMQ的一些使用理解
1.RocketMQ的生产者生产负载策略(3种) (1)SelectMessageQueueByHash (一致性hash) (2)SelectMessageQueueByMachineRoom (机器随机) (3)SelectMessageQueueByRandom (随机) 第1种一…...

Java枚举详解
一.枚举 1.为什么有枚举? 如果我们的程序需要表示固定的几个值: 比如季节:spring (春),summer(夏),autumn(秋),winter(冬) 用常量表示: public static final int SEASON_SPRING 1;public st…...

虚拟机上安装openKylin详细步骤总结
一、创建虚拟机 首先获取操作系统安装镜像文件: 链接:https://pan.baidu.com/s/1tSuXmDk2ZILR4ieee6iImw?pwdcy47 提取码:cy47 (1-1)进入新虚拟机创建向导,选择“自定义”: (1-…...
夜天之书 #74 企业开源的软件协议模型实践(Part 2)
在上一篇文章中,我介绍了企业开源的完全开放源码策略及其风险。完全开放源码,即以符合开源定义的软件协议发布企业自研软件的情形。本文介绍应对完全开放源码后的风险的第一种策略:提高市场占有率与开放标准。与其说是策略,不如说…...

2.webpack实时打包
简介 上一章已经实现了使用 webpack 构建了一个简单的项目;但是我们发现,每次修改了 index.js 需要重新执行 cnpm run dev 命令重新构建 main.js;这在开发阶段是无法忍受的,因为这样调式将浪费大量的时间;还好 webpac…...

KingbaseES V8R3 表加密
前言 透明加密是指将数据库page加密后写入磁盘,当需要读取对应page时进行加密读取。此过程对于用户是透明, 用户无需干预。 该文档进行数据库V8R3版本测试透明加密功能,需要说明,该版本发布时间早于V8R6,所以只能进行表…...
2 为社么软件架构很重要?
2 为社么软件架构很重要? 啊,建造,建造! 这是所有艺术中最崇高的艺术。 — 亨利沃兹沃思朗费罗 如果架构是答案,那么问题是什么? 本章从技术角度重点介绍架构的重要性。我们将研究面包师的十几个最重要…...

Python 之 Pandas merge() 函数、set_index() 函数、drop_duplicates() 函数和 tolist() 函数
文章目录一、merge() 函数1. inner2. left 和 right3. outer二、set_index() 函数三、drop_duplicates() 函数四、tolist() 函数五、视频数据分析案例1. 问题要求2. 解决过程在最开始,我们先导入常规的 numpy 和 pandas 库。 import numpy as np import pandas as …...

MySQL实战之深入浅出索引(下)
1.前言 在上一篇文章中,我们介绍了InnoDB索引的数据结构模型,今天我们再继续聊一下跟MySQL索引有关的概念。 在介绍之前,我们先看一个问题: 表初始化语句 mysql> create table T ( ID int primary key, k int NOT NULL DEFA…...
(二分查找)leetcode1539. 第 k 个缺失的正整数
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识一、题目 1、题目描述 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数组里第 k 个缺失的正整数。 示例 1: 输入&…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...