Bài trước ta xây stack lock-free và thấy nó chậm hơn mutex. Bài này ta thử một cấu trúc khó hơn nhiều: hàng đợi lock-free. Stack chỉ có một điểm truy cập (đỉnh); hàng đợi có hai — lấy ở đầu (head), thêm ở cuối (tail) — nên phải phối hợp hai con trỏ nhất quán. Thuật toán chuẩn là Michael-Scott queue, một trong những cấu trúc lock-free nổi tiếng nhất. Ta sẽ xây nó, kiểm đúng, và đo — rồi thấy vì sao channel của Go vẫn là câu trả lời cho gần như mọi trường hợp.

Vì sao hàng đợi khó hơn stack

Stack lock-free chỉ cần CAS một con trỏ head. Hàng đợi phức tạp hơn hẳn:

  • Hai điểm truy cập: Enqueue đụng tail, Dequeue đụng head — phải giữ hai con trỏ nhất quán với nhau.
  • Node giả (dummy): queue bắt đầu với một node rỗng để head và tail luôn trỏ tới một node hợp lệ, tránh trường hợp đặc biệt khi rỗng.
  • Cập nhật hai bước: thêm một phần tử cần hai thao tác (gắn node vào cuối, rồi đẩy tail) — mà giữa hai bước có thể bị goroutine khác chen vào.
type MSQueue struct {
	head atomic.Pointer[node]   // lấy ở đây
	tail atomic.Pointer[node]   // thêm ở đây
}

Ảnh chụp đoạn mã Go nền tối minh hoạ hàng đợi lock-free Michael-Scott khó hơn stack nhiều, queue có hai đầu head để lấy tail để thêm nên phải CAS hai chỗ dùng node giả và có cơ chế giúp đẩy tail, một vì sao queue khó hơn stack stack chỉ một điểm head một CAS queue hai điểm Enqueue đụng tail Dequeue đụng head phải phối hợp head tail nhất quán dùng node giả dummy type MSQueue struct head atomic.Pointer node lấy ở đây tail atomic.Pointer node thêm ở đây, hai Enqueue gắn node cộng đẩy tail hai CAS for tail bằng q.tail.Load next bằng tail.next.Load if tail bằng q.tail.Load if next bằng nil if tail.next.CompareAndSwap nil n gắn vào cuối q.tail.CompareAndSwap tail n đẩy tail ok nếu fail return else q.tail.CompareAndSwap tail next tail tụt hậu giúp đẩy, ba cơ chế giúp đỡ helping điểm tinh vi nhất Enqueue có 2 bước gắn node rồi đẩy tail nếu goroutine A gắn xong nhưng chưa kịp đẩy tail thì bị treo goroutine B thấy tail.next khác nil B giúp đẩy tail hộ A không goroutine nào bị chặn đảm bảo lock-free thật sự MS queue chuẩn vàng đảm bảo tiến triển ngay cả khi một goroutine dừng giữa chừng nhờ các goroutine khác giúp hoàn tất thao tác dở, bốn Dequeue dời head giúp tail nếu cần for head bằng q.head.Load tail bằng q.tail.Load next bằng head.next.Load if head bằng tail if next bằng nil return 0 false rỗng q.tail.CompareAndSwap tail next giúp đẩy tail else if q.head.CompareAndSwap head next return next.val true dời head lấy giá trị

Hình 1: Michael-Scott queue. head/tail riêng, node giả, Enqueue hai CAS, và cơ chế "giúp đỡ" — goroutine khác giúp hoàn tất thao tác dở của goroutine bị treo.

Cơ chế "giúp đỡ": điểm tinh vi nhất

Enqueue có hai bước: gắn node mới vào tail.next, rồi đẩy tail trỏ tới node mới. Nếu goroutine A làm xong bước 1 nhưng bị treo trước bước 2, tail sẽ tụt hậu (chưa trỏ node cuối cùng). Michael-Scott giải quyết bằng helping:

} else {
	q.tail.CompareAndSwap(tail, next)   // tail tụt hậu → GIÚP đẩy hộ
}

Bất kỳ goroutine nào thấy tail.next != nil (tức tail tụt hậu) sẽ giúp đẩy tail hộ goroutine đang treo, rồi mới làm việc của mình. Nhờ vậy không goroutine nào bị chặn bởi một goroutine khác dừng giữa chừng — đây chính là điều làm nó thật sự lock-free (đảm bảo tiến triển), và là lý do MS queue được coi là "chuẩn vàng".

Đo thật: đúng đắn, nhưng chậm hơn channel

Kiểm đúng: 8 goroutine cùng enqueue 1000 phần tử, rồi dequeue hết:

enqueue 8 goroutine x 1000 = 8000;  dequeue được: 8000
go run -race:  SẠCH

Đủ 8000, FIFO bảo toàn, -race sạch — kể cả khi goroutine dừng giữa hai bước enqueue (nhờ helping). Nhưng hiệu năng dưới tranh chấp:

Ảnh chụp bảng kết quả đo thật nền tối MS queue đúng nhưng channel nhanh hơn khoảng 3 lần go run trừ race cộng go test bench song song Go 1.23 arm64 10 core, đúng đắn 8 goroutine enqueue không mất phần tử enqueue 8 goroutine x 1000 bằng 8000 dequeue được 8000 go run trừ race sạch head tail phối hợp đúng qua CAS cộng helping Michael-Scott queue bảo toàn FIFO và mọi phần tử dưới 8 goroutine đồng thời kể cả khi goroutine dừng giữa 2 bước enqueue nhờ cơ chế giúp đỡ, hiệu năng dưới tranh chấp enqueue cộng dequeue song song 10 core cấu trúc MS queue lock-free 2 CAS thao tác 330,7 330,0 332,8 ns Channel có đệm chan buffered 114,8 103,8 114,9 ns channel nhanh hơn MS queue khoảng 3 lần queue lock-free đụng hai hotspot head cộng tail mỗi thao tác 2 CAS cộng bão retry channel của Go được tối ưu cực kỹ runtime hỗ trợ hàng đợi vòng đánh thức goroutine thông minh, chọn cái nào channel gần như luôn đúng cho producer-consumer FIFO nhanh đơn giản tích hợp select close range MS queue chỉ khi cần thứ channel không làm được unbounded không block peek ưu tiên phi-FIFO sự thật tự viết queue lock-free nhiều mã tinh vi cộng chậm hơn, cốt lõi MS queue head tail riêng node giả 2 CAS cơ chế giúp đỡ đúng đắn 8000 trên 8000 trừ race sạch FIFO bảo toàn hiệu năng chậm hơn channel 3x 330 vs 110 ns dưới tranh chấp giá trị học cơ chế thực tế dùng channel gần như luôn thắng khi tự viết chỉ khi channel không đủ hiếm và đo trước

Hình 2: Đúng đắn (8000/8000, FIFO, -race sạch). Hiệu năng: MS queue ~330 ns so với channel ~110 ns — channel nhanh hơn ~3 lần. Bảng chọn channel vs MS queue.

  • MS queue lock-free: 330,7 / 330,0 / 332,8 ns/op.
  • Channel có đệm: 114,8 / 103,8 / 114,9 ns/op.

Channel nhanh hơn MS queue ~3 lần dưới tranh chấp. Lý do tương tự stack nhưng nặng hơn: queue lock-free đụng hai hotspot (head và tail), mỗi thao tác cần 2 CAS cộng bão retry. Trong khi channel của Go được tối ưu cực kỹ ở tầng runtime — hàng đợi vòng (ring buffer), đánh thức goroutine thông minh, tích hợp scheduler.

Ứng dụng thực tế

Channel là câu trả lời cho gần như mọi producer-consumer FIFO. Nhanh, đơn giản, và tích hợp select, close, range. Trước khi nghĩ tới bất kỳ hàng đợi tự viết nào, hãy dùng channel — nó gần như luôn đúng và luôn đủ nhanh. "Đừng giao tiếp bằng chia sẻ bộ nhớ, hãy chia sẻ bộ nhớ bằng giao tiếp" — channel hiện thực triết lý này.

Chỉ tự viết queue lock-free khi channel không làm được. Vài trường hợp channel không phủ: hàng đợi unbounded không bao giờ block (channel có đệm cố định, đầy thì block/drop), hoặc cần peek (xem phần tử đầu không lấy ra), hoặc thứ tự phi-FIFO (ưu tiên). Đây là những lý do hiếm; nếu gặp, cân nhắc thư viện đã kiểm chứng trước khi tự viết.

MS queue là kiến thức nền quý, dù ít dùng trực tiếp. Hiểu cơ chế helping và cách phối hợp head/tail giúp bạn đọc được code lock-free của người khác (runtime Go, thư viện hiệu năng cao) và suy luận đúng về đồng thời. Học nó để hiểu, không nhất thiết để viết.

Đánh đổi cần cân nhắc

Độ phức tạp của queue lock-free rất cao so với lợi ích. MS queue có nhiều trường hợp tinh vi (node giả, helping, kiểm tra tail chưa đổi hai lần) mà một lỗi nhỏ gây bug đồng thời cực khó tìm. So với make(chan T, n) một dòng, chi phí bảo trì không đáng trừ khi có lý do rất cụ thể. Đơn giản là một tính năng.

Node-per-element gây áp lực cấp phát và GC. Mỗi Enqueue cấp một node mới; queue rỗng vẫn giữ node giả. Với throughput cao, đây là nguồn rác đáng kể (channel dùng ring buffer cấp phát một lần). Nếu tự viết, cân nhắc pool node — nhưng điều đó lại mở ra vấn đề ABA đã bàn ở bài trước.

Đo trên mẫu tải thật. Như cả stack lẫn queue cho thấy, "lock-free nhanh hơn" là niềm tin sai cho tranh chấp cao một hotspot. Nếu bạn đang cân nhắc lock-free vì hiệu năng, hãy đo channel/mutex trước — chúng thường thắng và đơn giản hơn nhiều. Chỉ khi đo chứng minh chúng là nút thắt và không có cách giảm tranh chấp (sharding), mới tính tới lock-free.

Ba ý mang về

  1. Hàng đợi lock-free khó hơn stack vì có hai điểm truy cập: Michael-Scott queue dùng head/tail riêng, node giả, và cập nhật hai bước (gắn node rồi đẩy tail) với cơ chế helping — goroutine khác giúp đẩy tail hộ goroutine treo giữa chừng, đảm bảo tiến triển thật sự; đo thật đúng đắn 8000/8000 phần tử, FIFO, -race sạch.
  2. Channel vẫn nhanh hơn MS queue lock-free ~3 lần dưới tranh chấp: đo thật 330 ns so với 110 ns — queue lock-free đụng hai hotspot (head + tail), mỗi thao tác 2 CAS + bão retry, trong khi channel được tối ưu cực kỹ ở tầng runtime (ring buffer, đánh thức thông minh).
  3. Dùng channel cho gần như mọi producer-consumer FIFO: nhanh, đơn giản, tích hợp select/close/range — chỉ tự viết queue lock-free khi cần thứ channel không làm được (unbounded không block, peek, ưu tiên phi-FIFO), và luôn đo trước; MS queue là kiến thức nền quý để hiểu code lock-free, không phải để viết hằng ngày.

Phần sau ta xem một cấu trúc đồng thời của thư viện chuẩn được tối ưu sẵn: Phần sau mổ xẻ sync.Map — cấu trúc read/dirty hai tầng bên trong, khi nào nó thắng map+mutex, và vì sao nó không phải "map nhanh hơn" cho mọi trường hợp.