12张图一次性搞懂高性能并发容器ConcurrentLinkedQueue
前言
上篇文章聊到并发汇合CopyOnWeiteArrayList的实现与特点，其不足之处是不适宜写多的场景也不适宜并发量大的场景
本篇文章来聊聊并发场景下高性能的ConcurrentLinkedQueue
浏览本文大略须要10分钟
在浏览本文前，须要了解CAS、volatile等常识
如果不了解CAS能够查看这篇文章15000字、6个代码案例、5个原理图让你彻底搞懂Synchronized 的第二大节
如果不了解volatile能够查看这篇文章5个案例和流程图让你从0到1搞懂volatile关键字
数据结构
ConcurrentLinkedQueue从名称上来看就可能晓得，它反对并发、由链表实现的队列
通过源码，咱们能够看到ConcurrentLinkedQueue应用字段记录首尾节点、并且节点的实现是单向链表
并且这些关键字段都被volatile润饰，在读场景下应用volatile保障可见性，不必“加锁”
还有一些其余字段，比方应用CAS的Unsafe和一些偏移量信息等，这里就不一一列举
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E> implements Queue<E>, java.io.Serializable { private static class Node<E> { //记录数据 volatile E item; //后继节点 volatile Node<E> next; } //首节点 private transient volatile Node<E> head; //尾节点 private transient volatile Node<E> tail; } 在初始化时，首尾节点会同时指向一个存储数据为空的节点
public ConcurrentLinkedQueue() { head = tail = new Node<E>(null); }设计思维
提早更新首尾节点
在查看实现原理前，咱们先来说说ConcurrentLinkedQueue的设计思维，否则实现原理可能会看不懂
ConcurrentLinkedQueue写场景中采纳乐观锁的思维，应用CAS+失败重试来保障操作的原子性
为了防止CAS开销过大，ConcurrentLinkedQueue采纳提早更新首尾节点的思维，来缩小CAS次数
也就是说ConcurrentLinkedQueue中的首尾节点并不一定是最新的首尾节点
哨兵节点
ConcurrentLinkedQueue的设计中应用哨兵节点
什么是哨兵节点？
哨兵节点又称虚构节点，哨兵节点常应用在链表这种数据结构中
单向链表中如果要增加或者删除某个节点时，肯定要取得这个节点的前驱节点再去进行操作
当操作的是第一个节点时，如果在第一个节点后面加个虚构节点（哨兵节点），那么就不必非凡解决
换而言之应用哨兵节点能够缩小代码复杂度，置信刷过链表相干算法的同学深有体会
哨兵节点还可能在只有一个节点时缩小并发抵触
这一特点可能要看完后续实现和流程图能力了解
源码实现
ConcurrentLinkedQueue次要的操作是入队、出队，咱们应用offer和poll来对其进行剖析
offer
在剖析源码前，先来阐明一些简单变量的作用
t记录尾节点tail
p用于循环遍历的节点，当p节点为真正尾节点时才容许增加新节点
q 用于记录p的后继节点
在入队时候三种状况：
- 当p的后继节点为空时（p为真正尾节点），尝试CAS减少新节点，胜利后尝试更新尾节点tail
- 当p等于p的后继节点时（p的next指向本人，阐明构建成哨兵节点，出队poll时可能结构哨兵节点）；此时判断尾节点是否被批改过，如果尾节点被批改过就定位到尾节点，如果未被批改过（应用next无奈持续遍历），只能定位到头节点
- 其余状况时，阐明此时的p并不是真正的尾节点，须要定位到真正尾节点；此时如果p不是原来的尾节点并且尾节点被批改过，那就定位到尾节点，否则定位到后继节点持续遍历
第二、三种状况的代码观赏性很好然而可读性不好，能够将总结的状况与源码剖析一起观看，如果还是不了解后续有流程图不便了解
public boolean offer(E e) { //查看空指针 checkNotNull(e); //构建新节点 final Node<E> newNode = new Node<E>(e); //失败重试的循环 //t:以后记录的尾节点 //p:真正的尾节点 //q:p的后继节点 for (Node<E> t = tail, p = t;;) { Node<E> q = p.next; //状况1：p的后继节点为空，阐明以后p就是真正尾节点 if (q == null) { //尝试CAS批改p的后继节点为新节点 //如果p的next是null 则替换成新节点newNode //失败则阐明其余线程cas增加节点胜利，持续循环；胜利则判断是否更新尾节点tail if (p.casNext(null, newNode)) { //如果p不等于t 阐明此时的尾节点不是真正的尾节点 //尝试CAS：如果以后尾节点是t，那么就将新节点设置成尾节点 if (p != t) casTail(t, newNode); return true; } } //状况2:p等于p的后继节点（p指向本人） else if (p == q) //t：旧的尾节点 //(t = tail)：新的尾节点 //t != (t = tail): 阐明尾节点被批改过，p等于新的尾节点；未被批改过，p等于头节点 p = (t != (t = tail)) ? t : head; //状况3：此时p不是真正尾节点，须要去定位真正尾节点 else //p!=t:p不再是原来的尾节点 //t != (t = tail):尾节点被批改过 //p不再是原来的尾节点 并且 尾节点被批改过 就让p等于批改过的尾节点；否则让p等于它的后继节点q p = (p != t && t != (t = tail)) ? t : q; } }poll
如果了解入队offer中的变量，那么出队poll也好了解，其中p和q都是相似的
h记录头节点head
p用于循环遍历的节点，当p节点为真正头节点时才容许出队
q 用于记录p的后继节点
出队的状况分为四种
- 当p为真正头节点时，CAS将数据设置为空，而后判断head是否为真正头节点，不是则更新头节点，而后将原来的头节点next指向它本人构建成哨兵节点
- 当p的后继节点为空时，阐明队列为空，尝试CAS将头节点批改成p
- 如果p的后继节点是它本人，阐明其余线程poll出队构建成哨兵节点，跳过本次循环
- 其余状况则向后遍历
public E poll() { //不便退出双重循环 restartFromHead: for (;;) { //h记录头节点 //p真正头节点 //q为p的后继节点 for (Node<E> h = head, p = h, q;;) { //获取p节点的数据 E item = p.item; //状况1： //如果数据不为空 阐明p节点为真正头节点 //尝试CAS将数据设置为null,如果数据为item则替换为null，失败则阐明其余线程以及出队，持续循环 if (item != null && p.casItem(item, null)) { //如果以后头节点不是真正头节点则更新头节点 if (p != h) updateHead(h, ((q = p.next) != null) ? q : p); return item; } //状况2： //p的后继节点为空，阐明以后为空队列，尝试CAS将头节点批改为p（p此时可能是哨兵节点） else if ((q = p.next) == null) { updateHead(h, p); return null; } //状况3: //如果p的后继节点指向p本人，阐明其余线程poll出队时构建成哨兵节点，跳过本次循环 else if (p == q) continue restartFromHead; //状况4: //p定位为后继节点须要遍历 else p = q; } } }在更新头节点办法中，会进行判断
如果以后头节点不是真正头节点，则尝试CAS将头节点设置成p真正头节点
CAS胜利后将原来的头节点的next指向它本人，构建成哨兵节点
final void updateHead(Node<E> h, Node<E> p) { if (h != p && casHead(h, p)) h.lazySetNext(h);}流程图实现
想要跟着debug的同学，须要把idea中的这两个设置敞开，否则debug会有误
为了更容易的了解，咱们来看一段简略的代码，并附带其实现流程图
public void testConcurrentLinkedQueue() { ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>(); queue.offer("h1"); queue.offer("h2"); queue.offer("h3"); String p1 = queue.poll(); String p2 = queue.poll(); String p3 = queue.poll(); String p4 = queue.poll(); queue.offer("h4"); System.out.println(queue); }【申明：如果图中节点item没写数据，阐明存储的数据为空；如果节点next没画指向关系，也阐明为空】
执行结构时，会初始化首尾节点指向同一个数据为空的节点
在第一次入队时，一进入循环就满足第一种状况，此时的p就是真正尾节点，间接CAS设置next为新节点，但因为p与tail雷同，就不会更新尾节点tail
因而首尾节点还是哨兵节点，而哨兵节点的next指向新入队的节点
在第二次入队时，因为此时的p(tail)不是真正尾节点，会来到第三种状况，因为tail没被批改过，p会被改成它的后继节点，持续向后遍历
在第二次循环时，p就是真正尾节点，于是尝试CAS增加新节点，因为此时p和尾节点tail不同，于是会更新tail
在第三次入队时，状况与第一次入队雷同
此时队列中存在哨兵节点和h1、h2、h3四个节点
在第一次出队时，因为head指向的哨兵节点数据域为空，会来到第四种状况，行将p改为它的后继节点，持续向后遍历
在第二次循环时，p为h1节点，因为数据不为空，CAS将数据设置为空
p.casItem(item, null) 将原h1节点数据设置为空
此时head并不是真正头节点，于是会更新head
而后将原来的head指向它本人，构建成哨兵节点，不便两头两个不再应用的节点GC
在第二次出队时，满足第一种状况，间接CAS将h2节点数据设置为空，不会更新头节点
在第三次出队时，也相似与第一次出队，满足第四种状况
在第二次循环时，去CAS将数据设置为空，更新头节点，将原来的头节点设置成哨兵节点
在第四次出队时会满足第三种状况，但此时p就是首节点，因而不会更新首节点，而后返回Null
此时咱们能够发现尾节点tail在哨兵节点上，如果往后遍历是永远无奈达到队列的
再进行一次入队操作，发现它满足第二种状况，p的next指向本人，因为未被批改过，p等于头节点，又从新回到队列上
再进入一轮循环，会CAS增加h4再更新尾节点tail
至此，该简略示例笼罩大部分入队、出队的流程，再来聊聊哨兵节点
在此过程中，哨兵节点能够防止队列中只有一个节点而产生竞争
总结
ConcurrentLinkedQueue基于单向链表实现，应用volatile保障可见性，使得在读场景下不须要应用其余同步机制；应用乐观锁CAS+失败重试保障写场景下操作的原子性
ConcurrentLinkedQueue应用提早更新首尾节点的思维，大大减少CAS次数，晋升并发性能；应用哨兵节点，升高代码复杂度，防止一个节点时的竞争
在入队操作时，会在循环中找到真正的尾节点，应用CAS增加新节点，再判断是否CAS更新尾节点tail
在入队操作的循环期间个别状况下是向后遍历节点，因为出队操作会构建哨兵节点，当判断为哨兵节点（next指向本人）时，依据状况定位到尾节点或头节点（“跳出”）
在出队操作时，也是在循环中找到真正的头节点，应用CAS将真正头节点的数据设置为空，再判断是否CAS更新头节点，而后让旧的头节点next指向它本人构建成哨兵节点，不便GC
在出队操作的循环期间个别状况下也是向后遍历节点，因为出队会构建哨兵节点，当检测到以后是哨兵节点时，也要跳过本次循环
ConcurrentLinkedQueue基于哨兵节点、提早CAS更新首尾节点、volatile保障可见性等特点，领有十分高的性能，绝对于CopyOnWriteArrayList来说实用于数据量大、并发高、频繁读写、操作队头、队尾的场景
最初（不要白嫖，一键三连求求拉~）
本篇文章被支出专栏 由点到线，由线到面，深入浅出构建Java并发编程常识体系，感兴趣的同学能够继续关注喔
本篇文章笔记以及案例被支出 gitee-StudyJava、 github-StudyJava 感兴趣的同学能够stat下继续关注喔~
案例地址：
Gitee-JavaConcurrentProgramming/src/main/java/F_Collections
Github-JavaConcurrentProgramming/src/main/java/F_Collections
有什么问题能够在评论区交换，如果感觉菜菜写的不错，能够点赞、关注、珍藏反对一下~
关注菜菜，分享更多干货，公众号：菜菜的后端私房菜
本文由博客一文多发平台 OpenWrite 公布！