大家好，我是君哥。

在日常开发工作中，环形队列的使用并不多，但其实环形队列是一个很有用的数据结构，而且有不少使用场景。今天来聊一聊环形队列的使用场景。

1.环形队列

队列这个数据结构最大的特点就是先进先出，它可以有两种实现方式，无界队列一般用链表来实现，有界队列可以用数组来实现。

但使用数组来实现队列，有新数据插入时，需要搬移元素，造成额外的性能开销。要解决数据搬移的问题，我们可以考虑使用环形队列。

下图是一个 8 个元素的环形队列：

环形队列的特点是写完最后一个元素后接着从头开始写，读元素也一样。初始状态，head 和 tail 都指向数据下标是 0 的位置。每写入一个元素，tail 往后移动一个指针，每读取一个元素，head 指针往后移动一个指针。如果写入的速度超过了读取速度一圈，未读取的元素就会被覆盖。

下图是用数组来表示的环形队列，尾节点指向头结点，实现首尾相连：

在上图中，head 所在数组位置元素值是 3，tail 所在数组位置元素值是 7。这时如果我们插入一个新元素 a，环形队列变成下图：

那环形队列代码怎么实现呢？这里给出一个示例代码：

public class CircleQueue {//实现环形队列的数组private String[] items;//数组大小private int size;//数组元素数量private int count = 0;private int head = 0;private int tail = 0;//申请一个指定容量的队列public CircleQueue(int size){items = new String[size];this.size = size;}public boolean enqueue(String item){if ((tail + 1) % size == head){//队列满return false;}items[tail] = item;tail = (tail + 1) % size;count++;return true;}public String dequeue(){String item = null;//队列空if(head == tail){return item;}item = items[head];head = (head + 1) % size;count--;return item;}
}

在上面的例子中，如果队列满了，就会写入消息失败。不过在实际使用场景中，有些场景如果队列满了，可以覆盖掉当前 tail 位置上的元素，tail 继续往下一个位置移动。这个适用于丢失数据影响较小的场景，比如记录日志。

2.使用场景

2.1 延时消息

在消息队列中，延时消息的使用场景很多，比如超过 30 分钟关闭未支付订单。主流消息队列实现延时关闭订单的方式是采用线程轮询的方式来判断订单是否超过 30 分钟，如果超过则关闭订单。

在 RocketMQ 5.0 之前，4.x 版本定义了 18 个延时级别：

private String messageDelayLevel = "1s 5s 10s 30s 1m 2m 3m 4m 5m 6m 7m 8m 9m 10m 20m 30m 1h 2h";

Broker 收到消息后，会根据延时级别把消息保存到同一个 Topic（SCHEDULE_TOPIC_XXXX）下的不同 queue。然后启动 18 个线程来对每个 queue 做轮询判断，如果时间到了，就把消息投递到原始队列，等待 Consumer 来拉取。

这样的设计存在一个问题，延时级别只有 18 个，不太灵活，对于大型的复杂业务系统，延时级别可能成千上万，这种设计无法满足。

为了解决这个设计问题，RocketMQ 5.0 基于时间轮算法引入了定时消息。如下图：

图中定义了一个 60s 的时间轮，时间轮上有一个指向当前时间的指针定时地移动到下一秒时间。

这样不用去轮询所有消息，每一个时间节点上的消息用链表串起来，当时间轮上的指针移动到当前的时间时，这个时间节点上符合条件的消息就交给异步线程来处理。

如果一个消息的延时时间超过 60s，比如 130s，该怎么设置呢？在每个时间轮节点增加一个 round 字段，记录时间轮转动的圈数，对于延时 130s 的消息，round 就是 2，放在第 10 个时间刻度的链表中。时间轮每转动一圈，round 值减一，这样当时间轮转到一个节点，处理节点上的消息时，首先判断 round 值是否等于 0，如果等于 0，则把这个消息从链表中移出交给异步线程执行，否则将 round 减 1 继续检查后面的任务。

2.2 Disruptor

Disruptor 是一款高性能的消息队列，它使用到了环形队列这个数据结构。那 Disruptor 使用环形队列是怎样做到高性能的呢？

2.2.1 内存预分配

Disruptor 使用循环队列，在队列初始化的时候，数组元素一次性初始化，这样可以不仅提升缓存命中率，还可以避免频繁 GC。

2.2.2 无锁并发

Disruptor 是一种生产者-消费者模式，当多个生产者在同一个位置写事件消息时，就会被覆盖。如下图，线程1 把位置 1 的元素更新成 b，线程 2 写入时本来应该在位置 2 写入 c，但是写入了位置 1，导致覆盖了线程 1 写入的值。消费者并发消费时也有类似的问题。

解决这个问题最好的方法就是给写入的代码加锁，只允许获取到锁的线程执行，但这样失去了并发优势，性能降低。

为了解决加锁带来的性能问题，Disruptor 在设计上进行了改造。当一个线程要写入循环队列时，先申请队列上连续的 n 个位置，申请成功这 n 个位置是线程独享的，这样线程在写入元素时就不用担心被覆盖。消费者进行并发消费时，也是先申请连续的 n 个位置独自消费，跟其他线程互相隔离。

2.2.3 解决伪共享

环形队列内部数组使用缓存行填充技术来避免伪共享问题，进一步提高了性能。

2.3 日志收集

dmesg 这个 Linux 命令我们应该了解过，主要用于查看系统启动时的日志信息、硬件信息。

dmesg 使用的日志就是存储在环形缓存区中，每当有新的日志写入时，如果环形队列已满，就会覆盖旧的日志，这样可以保证内核日志不会占用过多的内存空间，而且还能够不断记录新日志。

3.总结

环形队列作为一种有界循环队列，在消息中间件、高性能内存队列 Disruptor、日志收集等方面有广泛的应用。了解循环队列的原理，可以更好的理解它的使用场景。