关于后端:12张图一次性搞懂高性能并发容器ConcurrentLinkedQueue

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 的后继节点

在入队时候三种状况：

1. 当 p 的后继节点为空时（p 为真正尾节点），尝试 CAS 减少新节点，胜利后尝试更新尾节点 tail
2. 当 p 等于 p 的后继节点时（p 的 next 指向本人，阐明构建成哨兵节点，出队 poll 时可能结构哨兵节点）；此时判断尾节点是否被批改过，如果尾节点被批改过就定位到尾节点，如果未被批改过（应用 next 无奈持续遍历），只能定位到头节点
3. 其余状况时，阐明此时的 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 的后继节点

出队的状况分为四种

1. 当 p 为真正头节点时，CAS 将数据设置为空，而后判断 head 是否为真正头节点，不是则更新头节点，而后将原来的头节点 next 指向它本人构建成哨兵节点
2. 当 p 的后继节点为空时，阐明队列为空，尝试 CAS 将头节点批改成 p
3. 如果 p 的后继节点是它本人，阐明其余线程 poll 出队构建成哨兵节点，跳过本次循环
4. 其余状况则向后遍历

     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 公布！