使用Go实现可用select监听的队列

1. 背景与选型

和《基于Redis Cluster的分布式锁实现以互斥方式操作共享资源》一文一样，今天要说的Go队列方案也是有一定项目背景的。

5G消息方兴未艾^[1]！前一段时间从事了一段时间5G消息网关的研发，但凡涉及类似消息业务的网关，我们一般都离不开队列这种数据结构的支持。这个5G消息网关项目采用的是Go技术栈开发，那么我们应该如何为它选择一个与业务模型匹配且性能不差的实现呢？

如今一提到消息队列，大家第一个想到的一定是kafka^[2]，kafka的确是一款优秀的分布式队列中间件，但对于我们这个系统来说，它有些“重”，部署和运维都有门槛，并且项目组里也没有能很好维护它的专家，毕竟“可控”是技术选择的一个重要因素。除此之外，我们更想在Go技术栈的生态中挑选，但kafka是Java实现的。

Go圈里在性能上能与kafka“掰掰手腕”的成熟选手不多，nats^[3]以及其主持持久化的子项目nats-streaming^[4]算是其中两个。不过nats的消息送达模型是：At-least-once-delivery，即至少送一次（而没有kafka的精确送一次的送达模型)。一旦消费者性能下降，给nats server返回的应答超时，nats就会做消息的重发处理：即将消息重新加入到队列中。这与我们的业务模型不符，即便nats提供了发送超时的设定，但我们还是无法给出适当的timeout时间。Go圈里的另一个高性能分布式消息队列nsq^[5]采用的也是“至少送一次”的消息送达模型^[6]，因此也无法满足我们的业务需求。

我们的业务决定了我们需要的队列要支持“多生产者多消费者”模型，Go语言内置的channel也是一个不错的候选。经过多个Go版本的打磨和优化，channel的send和recv操作性能在一定数量goroutine的情况下已经可以满足很多业务场景的需求了。但channel还是不完全满足我们的业务需求。我们的系统要求尽可能将来自客户端的消息接收下来并缓存在队列中。即便下游发送性能变慢，也要将客户消息先收下来，而不是拒收或延迟响应。而channel本质上是一个具有“静态大小”的队列并且Go的channel操作语义会在channel buffer满的情况下阻塞对channel的继续send，这就与我们的场景要求有背离，即便我们使用buffered channel，我们也很难选择一个合适的len值，并且一旦buffer满，它与unbuffered channel行为无异。

这样一来，我们便选择自己实现一个简单的、高性能的满足业务要求的队列，并且最好能像channel那样可以被select监听到数据ready，而不是给消费者带去“心智负担” ：消费者采用轮询的方式查看队列中是否有数据。

2. 设计与实现方案

要设计和实现这样一个队列结构，我们需要解决三个问题：

• 实现队列这个数据结构；
• 实现多goroutine并发访问队列时对消费者和生产者的协调；
• 解决消费者使用select监听队列的问题。

我们逐一来看！

1) 基础队列结构实现来自一个未被Go项目采纳的技术提案

队列是最基础的数据结构，实现一个“先进先出(FIFO)”的练手queue十分容易，但实现一份能加入标准库、资源占用小且性能良好的queue并不容易。Christian Petrin^[7]在2018年10月份曾发起一份关于Go标准库加入queue实现的技术提案^[8]，提案对基于array和链表的多种queue实现^[9]进行详细的比对，并最终给出结论：impl7^[10]是最为适宜和有竞争力的标准库queue的候选者。虽然该技术提案目前尚未得到accept，但impl7足可以作为我们的内存队列的基础实现。

2) 为impl7添加并发支持

在性能敏感的领域，我们可以直接使用sync包提供的诸多同步原语来实现goroutine并发安全访问，这里也不例外，一个最简单的让impl7队列实现支持并发的方法就是使用sync.Mutex实现对队列的互斥访问。由于impl7并未作为一个独立的repo存在，我们将其代码copy到我们的实现中(queueimpl7.go)，并将其包名由queueimpl7改名为queue：

// github.com/bigwhite/experiments/blob/master/queue-with-select/safe-queue1/queueimpl7.go

// Package queueimpl7 implements an unbounded, dynamically growing FIFO queue.
// Internally, queue store the values in fixed sized slices that are linked using
// a singly linked list.
// This implementation tests the queue performance when performing lazy creation of
// the internal slice as well as starting with a 1 sized slice, allowing it to grow
// up to 16 by using the builtin append function. Subsequent slices are created with
// 128 fixed size.
package queue

// Keeping below as var so it is possible to run the slice size bench tests with no coding changes.
var (
        // firstSliceSize holds the size of the first slice.
        firstSliceSize = 1

        // maxFirstSliceSize holds the maximum size of the first slice.
        maxFirstSliceSize = 16

        // maxInternalSliceSize holds the maximum size of each internal slice.
        maxInternalSliceSize = 128
)
... ...

下面我们就来为以queueimpl7为底层实现的queue增加并发访问支持：

// github.com/bigwhite/experiments/blob/master/queue-with-select/safe-queue1/safe-queue.go

package queue

import (
 "sync"
)

type SafeQueue struct {
 q *Queueimpl7
 sync.Mutex
}

func NewSafe() *SafeQueue {
 sq := &SafeQueue{
  q: New(),
 }

 return sq
}

func (s *SafeQueue) Len() int {
 s.Lock()
 n := s.q.Len()
 s.Unlock()
 return n
}

func (s *SafeQueue) Push(v interface{}) {
 s.Lock()
 defer s.Unlock()

 s.q.Push(v)
}

func (s *SafeQueue) Pop() (interface{}, bool) {
 s.Lock()
 defer s.Unlock()
 return s.q.Pop()
}

func (s *SafeQueue) Front() (interface{}, bool) {
 s.Lock()
 defer s.Unlock()
 return s.q.Front()
}

我们建立一个新结构体SafeQueue，用于表示支持并发访问的Queue，该结构只是在queueimpl7的Queue的基础上嵌入了sync.Mutex。

3) 支持select监听

到这里支持并发的queue虽然实现了，但在使用上还存在一些问题，尤其是对消费者而言，它只能通过轮询的方式来检查队列中是否有消息。而Go并发范式中，select扮演着重要角色，如果能让SafeQueue像普通channel那样能支持select监听，那么消费者在使用时的心智负担将大大降低。于是我们得到了下面第二版的SafeQueue实现：

// github.com/bigwhite/experiments/blob/master/queue-with-select/safe-queue2/safe-queue.go

package queue

import (
 "sync"
 "time"
)

const (
 signalInterval = 200
 signalChanSize = 10
)

type SafeQueue struct {
 q *Queueimpl7
 sync.Mutex
 C chan struct{}
}

func NewSafe() *SafeQueue {
 sq := &SafeQueue{
  q: New(),
  C: make(chan struct{}, signalChanSize),
 }

 go func() {
  ticker := time.NewTicker(time.Millisecond * signalInterval)
  defer ticker.Stop()
  for {
   select {
   case <-ticker.C:
    if sq.q.Len() > 0 {
     // send signal to indicate there are message waiting to be handled
     select {
     case sq.C <- struct{}{}:
      //signaled
     default:
      // not block this goroutine
     }
    }
   }
  }

 }()

 return sq
}

func (s *SafeQueue) Len() int {
 s.Lock()
 n := s.q.Len()
 s.Unlock()
 return n
}

func (s *SafeQueue) Push(v interface{}) {
 s.Lock()
 defer s.Unlock()

 s.q.Push(v)
}

func (s *SafeQueue) Pop() (interface{}, bool) {
 s.Lock()
 defer s.Unlock()
 return s.q.Pop()
}

func (s *SafeQueue) Front() (interface{}, bool) {
 s.Lock()
 defer s.Unlock()
 return s.q.Front()
}

从上面代码看到，每个SafeQueue的实例会伴随一个goroutine，该goroutine会定期(signalInterval)扫描其所绑定的队列实例中当前消息数，如果大于0，则会向SafeQueue结构中新增的channel发送一条数据，作为一个“事件”。SafeQueue的消费者则可以通过select来监听该channel，待收到“事件”后调用SafeQueue的Pop方法获取队列数据。下面是一个SafeQueue的简单使用示例：

// github.com/bigwhite/experiments/blob/master/queue-with-select/main.go
package main

import (
 "fmt"
 "sync"
 "time"

 queue "github.com/bigwhite/safe-queue/safe-queue2"
)

func main() {
 var q = queue.NewSafe()
 var wg sync.WaitGroup

 wg.Add(2)
 // 生产者
 go func() {
  for i := 0; i < 1000; i++ {
   time.Sleep(time.Second)
   q.Push(i + 1)

  }
  wg.Done()
 }()

 // 消费者
 go func() {
 LOOP:
  for {
   select {
   case <-q.C:
    for {
     i, ok := q.Pop()
     if !ok {
      // no msg available
      continue LOOP
     }

     fmt.Printf("%d\n", i.(int))
    }
   }

  }

 }()

 wg.Wait()
}

从支持SafeQueue的原理可以看到，当有多个消费者时，只有一个消费者能得到“事件”并开始消费。如果队列消息较少，只有一个消费者可以启动消费，这个机制也不会导致“惊群”；当队列中有源源不断的消费产生时，与SafeQueue绑定的goroutine可能会连续发送“事件”，多个消费者都会收到事件并启动消费行为。在这样的实现下，建议消费者在收到“事件”后持续消费，直到Pop的第二个返回值返回false(代表队列为空)，就像上面示例中的那样。

这个SafeQueue的性能“中规中矩”，比buffered channel略好(Go 1.16 darwin下跑的benchmark)：

$go test -bench .
goos: darwin
goarch: amd64
pkg: github.com/bigwhite/safe-queue/safe-queue2
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkParallelQueuePush-8              10687545        110.9 ns/op       32 B/op        1 allocs/op
BenchmarkParallelQueuePop-8               18185744         55.58 ns/op        0 B/op        0 allocs/op
BenchmarkParallelPushBufferredChan-8      10275184        127.1 ns/op       16 B/op        1 allocs/op
BenchmarkParallelPopBufferedChan-8        10168750        128.8 ns/op       16 B/op        1 allocs/op
BenchmarkParallelPushUnBufferredChan-8     3005150        414.9 ns/op       16 B/op        1 allocs/op
BenchmarkParallelPopUnBufferedChan-8       2987301        402.9 ns/op       16 B/op        1 allocs/op
PASS
ok   github.com/bigwhite/safe-queue/safe-queue2 11.209s

注：BenchmarkParallelQueuePop-8因为是读取空队列，所以没有分配内存，实际情况是会有内存分配的。另外并发goroutine的模拟差异可能导致有结果差异。

3. 扩展与问题

上面实现的SafeQueue是一个纯内存队列，一旦程序停止/重启，未处理的消息都将消失。一个传统的解决方法是采用wal(write ahead log)在推队列之前将消息持久化后写入文件，在消息出队列后将消息状态也写入wal文件中。这样重启程序时，从wal中恢复消息到各个队列即可。我们也可以将wal封装到SafeQueue的实现中，在SafeQueue的Push和Pop时自动操作wal，并对SafeQueue的使用者透明，不过这里有一个前提，那就是队列消息的可序列化（比如使用protobuf)。另外SafeQueue还需提供一个对外的wal消息恢复接口。大家可以考虑一下如何实现这些。

另外在上述的SafeQueue实现中，我们在给SafeQueue增加select监听时引入两个const：

const (
 signalInterval = 200
 signalChanSize = 10
)

对于SafeQueue的使用者而言，这两个默认值可能不满足需求，那么我们可以将SafeQueue的New方法做一些改造，采用“功能选项(functional option)”的模式^[11]为用户提供设置这两个值的可选接口，这个“作业”也留给大家了^_^。

本文所有示例代码可以在这里^[12]下载 - https://github.com/bigwhite/experiments/tree/master/queue-with-select。

参考资料