算法实战3 - 高性能队列的实现思路

本章关键词

高性能队列、并发、线程安全

Disruptor 是一个高性能的内存消息队列，用于不同线程之间的通信。为了实现这样的高性能，它在设计和实现上做了很多功夫，这一节，我们就看一看它在底层用了什么样的数据结构。

底层数据结构的选取

对于消息队列，我们当然会选择使用队列这种数据结构。队列有两种实现思路，链式队列（使用链表实现） 和 顺序队列（使用数组实现）：

• 链式队列适合在不知道数据量的情况下使用，但是这可能会出现队列持续添加，从而导致内存溢出。
• 顺序队列使用数组实现，当队列中的消息数量超出限制，就会触发等待。从这个意义上来说，使用顺序队列更加符合我们的需求。
• 单纯的顺序队列在使用中会涉及数据搬移操作，所以我们可以选择使用循环队列避免这样的消耗。

线程队列的访问冲突问题

线程间的消息队列，可以用生产者-消费者模型很好地表示，这个模型非常经典，在这里就不多介绍了，我们直接说在实际应用中会遇到的问题：

• 多个生产者写入的数据可能会互相覆盖
• 多个消费者可能会读取重复的数据

这两个问题实际上是同一类问题：由于线程直接不是同步执行的，所以可能会相互影响，造成公共资源之间的使用冲突。

为了后面讲述的方便，我们定义一下向队列添加时使用的代码：

public boolean add(Long element) {
  if ((tail + 1) % size == head) return false;
  data[tail] = element;
  tail = (tail + 1) % size;
  return true;
}

在冲突时，程序会这样执行： 两个生产者同时想要写入数据：线程1希望写入12，线程2希望写入5，他们都向队列提出的写入请求。
在线程1执行完数据写入后，还没来得及将指针后移，线程2就已经执行了数据写入，这时线程1写入的12就被覆盖了
之后，两个线程都将指针后移，这导致出现了一个数据“空洞”

最简单的解决办法就是在数据写入和指针移动时对队列加锁。但是这样等于将一个并行的队列强制转成串行执行，势必会降低性能。

Disruptor的解决办法

Disruptor 的解决办法非常简单：一次申请 n 个内存空间：

对于生产者来说，它往队列中添加数据之前，先申请可用空闲存储单元，并且是批量地申请连续的 n 个（n≥1）存储单元。当申请到这组连续的存储单元之后，后续往队列中添加元素，就可以不用加锁了，因为这组存储单元是这个线程独享的。不过，从刚刚的描述中，我们可以看出，申请存储单元的过程是需要加锁的。
对于消费者来说，处理的过程跟生产者是类似的。它先去申请一批连续可读的存储单元（这个申请的过程也是需要加锁的），当申请到这批存储单元之后，后续的读取操作就可以不用加锁了。

具体操作过程如下： 高性能操作.jpg

总结

在线程队列中，一个非常重要的问题就是线程安全。解决这个问题，最常见的思路就是对操作进行加锁，而加锁对性能的影响是非常大的。为了避免这种影响，我们可以通过“分配多个空间，减小加锁次数”来避免过多的性能下降。

---

以上就是本节的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间