Mengapa Membutuhkan Lock-Free MPMC Queue?

Pada arsitektur worker backend dengan beban konkurensi tinggi, sinkronisasi berbasis mutex (sync.Mutex) sering menimbulkan overhead sistemik. Ketika puluhan producer dan ribuan worker berebut lock yang sama, kernel scheduler dipaksa melakukan ribuan context switch per detik. Hal ini memicu thread parking, lock contention, dan latensi ekor (tail latency) yang tinggi.

Alternatif yang lebih deterministik adalah bounded MPMC queue lock-free menggunakan array sirkular (ring-buffer) berukuran tetap ($2^n$). Struktur data ini memungkinkan multiple producer dan multiple consumer beroperasi secara simultan menggunakan operasi atomik tingkat hardware (CPU instructions seperti CMPXCHG) tanpa memblokir thread eksekusi.

Arsitektur Ring-Buffer Berbasis Sequence Number

Desain paling efisien untuk bounded lock-free MPMC ring-buffer pertama kali dipopulerkan oleh Dmitry Vyukov. Berbeda dengan implementasi single-variable lock-free yang rentan terhadap ABA problem, pendekatan ini menempatkan counter urutan (sequence) pada setiap slot di dalam buffer array.

Struktur Slot dan Reduksi Cache-Line Bouncing

Ketika banyak core CPU menulis ke memori yang saling berdekatan, performa turun drastis akibat fenomena false sharing (cache-line bouncing). Untuk menghindarinya, setiap node dan pointer indexing perlu diratakan ke batas ukuran cache line (umumnya 64 byte pada arsitektur x86-64 dan ARM64).

package queue

import (
	"sync/atomic"
	"unsafe"
)

type cell[T any] struct {
	sequence atomic.Uint64
	val      T
}

type MPMCQueue[T any] struct {
	_        [7]uint64      // Padding awal cache line
	buffer   []cell[T]
	mask     uint64
	_        [7]uint64      // Isolasi pointer buffer
	enqueuePos atomic.Uint64
	_        [7]uint64      // Isolasi atomic enqueue
	dequeuePos atomic.Uint64
	_        [7]uint64      // Isolasi atomic dequeue
}

Implementasi Kode: Enqueue dan Dequeue Berbasis CAS

Berikut implementasi lengkap buffer tanpa alokasi dinamis saat runtime, menggunakan sync/atomic di Go:

package queue

import (
	"runtime"
	"sync/atomic"
)

func NewMPMCQueue[T any](capacity uint64) *MPMCQueue[T] {
	// Kapasitas harus power of two untuk bitwise masking
	if capacity < 2 || (capacity&(capacity-1)) != 0 {
		panic("capacity must be a power of two")
	}

	q := &MPMCQueue[T]{
		buffer: make([]cell[T], capacity),
		mask:   capacity - 1,
	}

	for i := uint64(0); i < capacity; i++ {
		q.buffer[i].sequence.Store(i)
	}

	return q
}

func (q *MPMCQueue[T]) Enqueue(data T) bool {
	var pos uint64
	for {
		pos = q.enqueuePos.Load()
		c := &q.buffer[pos&q.mask]
		seq := c.sequence.Load()
		diff := int64(seq) - int64(pos)

		if diff == 0 {
			// Slot siap diisi, klaim tiket posisi enqueue
			if q.enqueuePos.CompareAndSwap(pos, pos+1) {
				c.val = data
				c.sequence.Store(pos + 1)
				return true
			}
		} else if diff < 0 {
			// Queue penuh (full buffer)
			return false
		}
		runtime.Gosched()
	}
}

func (q *MPMCQueue[T]) Dequeue() (T, bool) {
	var pos uint64
	var zero T
	for {
		pos = q.dequeuePos.Load()
		c := &q.buffer[pos&q.mask]
		seq := c.sequence.Load()
		diff := int64(seq) - int64(pos+1)

		if diff == 0 {
			// Item siap dibaca, klaim tiket posisi dequeue
			if q.dequeuePos.CompareAndSwap(pos, pos+1) {
				data := c.val
				c.val = zero // Cegah memory leak pada pointer reference
				c.sequence.Store(pos + q.mask + 1)
				return data, true
			}
		} else if diff < 0 {
			// Queue kosong (empty buffer)
			return zero, false
		}
		runtime.Gosched()
	}
}

Mitigasi ABA Problem dan Bounded Waiting

Pada struktur data single-pointer CAS seperti Treiber Stack, ABA problem terjadi saat alamat memori yang sama dialokasikan ulang sebelum verifikasi pointer selesai. Pada arsitektur Vyukov ini:

  • Pencegahan ABA Problem: Sequence number bertambah monotonik setiap siklus putaran buffer (sebesar capacity). Dua goroutine tidak akan mendapati nilai sequence identik untuk siklus traversal yang berbeda.
  • Bounded Waiting: Jika queue penuh, producer langsung mengembalikan flag false (non-blocking). Hal ini mencegah worker thread tertahan secara permanen (starvation). Untuk skenario wait-free bounded queue yang lebih ketat, rujukan model alokasi tiket deterministik dianalisis pada riset bounded wait-free queues oleh Nahla.

Analisis Performa: Lock-Free vs Mutex

Karakteristik performa antara MPMCQueue dan queue berbasis sync.Mutex memperlihatkan pola berikut saat diuji dengan benchmark beban paralel:

  • Throughput Rendah ke Sedang (< 4 Cores): sync.Mutex sering kali bersaing ketat dengan atomic CAS karena fast-path mutex di Go runtime sangat teroptimasi jika tanpa antrean thread.
  • High Contention (>= 8 Cores): Lock-free queue mempertahankan throughput linear tanpa degradasi akibat kernel descheduling. Mutex mengalami degradasi drastis karena overhead lock-waiter list dan sleeping thread wakeups.
  • Latency Spikes: Mutex menghasilkan P99 latency yang fluktuatif (jitter) di atas 10-50 milidetik saat heavy contention. Lock-free queue menjaga varians tail latency tetap di kisaran sub-mikrodetik.

Verifikasi Race Condition

Algoritma berbasis non-blocking synchronization wajib diverifikasi menggunakan race detector Go untuk mendeteksi memory ordering violation:

go test -race -cpu 4,8,16 -count=10 ./queue/...

Catatan: Jalankan selalu stress test dengan rasio producer-consumer asimetris (misal: 10 producer, 1 consumer dan sebaliknya) guna memastikan sequence diff logic menangani wrap-around dan buffer exhaustion secara konsisten tanpa data race.