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

43次阅读

共计 5459 个字符,预计需要花费 14 分钟才能阅读完成。

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次要的操作是入队、出队,咱们应用 offerpoll来对其进行剖析

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

正文完
 0