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: 输入&…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...

6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...

高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...