Bài trước ta gặp CompareAndSwap như "nền tảng lock-free". Bài này ta thực sự xây một cấu trúc lock-free — một stack — bằng vòng lặp CAS, kiểm tra nó đúng, và đo hiệu năng. Kết quả gây bất ngờ và là một trong những sự thật quan trọng nhất về lập trình đồng thời: lock-free không tự động nhanh hơn. Dưới tranh chấp cao, stack lock-free này còn chậm hơn một mutex thường tới 3,5 lần. Bài này chỉ cách xây, và giải thích trung thực khi nào lock-free thực sự đáng.
Xây stack lock-free bằng vòng lặp CAS
Ý tưởng: thay vì khóa, mỗi thao tác đọc trạng thái hiện tại, tính trạng thái mới, rồi dùng CAS để cập nhật chỉ nếu trạng thái chưa đổi. Nếu CAS thất bại (ai đó chen vào giữa), thử lại.
func (s *Stack) Push(v int) {
n := &node{val: v}
for {
old := s.head.Load() // đọc head hiện tại
n.next = old // node mới trỏ tới head cũ
if s.head.CompareAndSwap(old, n) {
return // đổi thành công
}
// CAS thất bại: ai đó đã đổi head → thử lại vòng mới
}
}
Pop theo cùng mẫu: đọc head, tính head mới (old.next), CAS. CompareAndSwap(old, moi) là một lệnh CPU nguyên tử: nếu head vẫn là old thì đặt thành moi và trả true; ngược lại trả false (báo có người chen vào).
Hình 1: Vòng lặp CAS cho Push/Pop. CAS là "kiểm rồi đổi" nguyên tử; lock-freedom đảm bảo luôn có goroutine tiến triển; và vấn đề ABA mà Go phần lớn tránh nhờ GC.
Đo thật: đúng đắn, nhưng chậm hơn mutex
Kiểm đúng đắn trước: 10 goroutine cùng push 1000 phần tử, rồi pop hết:
push 10 goroutine x 1000 = 10000; pop được: 10000
go run -race: SẠCH (không data race)
Đủ 10000 phần tử, không mất cái nào, và -race sạch — vòng lặp CAS đúng đắn. Nhưng hiệu năng dưới tranh chấp cao (push+pop song song 10 core) mới là phần bất ngờ:
Hình 2: Đúng đắn (10000/10000, -race sạch). Hiệu năng: lock-free ~373-423 ns so với mutex ~107-111 ns — mutex nhanh hơn ~3,5 lần dưới tranh chấp cao. Bảng "khi nào lock-free thắng".
- Lock-free (vòng CAS): 423 / 412 / 373 ns/op.
- Mutex: 111 / 111 / 107 ns/op.
Mutex nhanh hơn lock-free ~3,5 lần dưới tranh chấp cao. Vì sao? Khi 10 core cùng đập vào một con trỏ head, rất nhiều CAS thất bại — mỗi lần thất bại phải làm lại cả vòng lặp (đọc lại head, dựng lại, CAS lại). Đây là bão retry: công sức lãng phí tăng theo mức tranh chấp. Mutex thì tuần tự hóa, nhưng một khi giữ khóa, nó làm việc không có retry phí phạm, và mutex của Go rất hiệu quả (spin ngắn rồi park).
Vậy khi nào lock-free thực sự thắng?
Giá trị thật của lock-free không phải tốc độ thô mà là bảo đảm tiến triển (progress guarantee): luôn có ít nhất một goroutine tiến lên, không bao giờ deadlock, không bị block vô hạn, không priority inversion (goroutine ưu tiên thấp giữ khóa chặn goroutine ưu tiên cao). Lock-free thắng khi:
- Tranh chấp thấp tới vừa: ít CAS thất bại nên ít retry, và tránh được chi phí park/unpark của mutex.
- Cần đảm bảo tiến triển: hệ thống thời gian thực, hoặc nơi một goroutine bị treo không được phép chặn cả hệ thống.
- Tránh syscall của mutex: khi mutex phải park goroutine (chờ lâu), lock-free tránh được chi phí đó.
Lock-free thua khi có một hotspot duy nhất bị tranh chấp rất cao — đúng như benchmark này.
Ứng dụng thực tế
Đừng viết lock-free để "nhanh hơn". Nếu mục tiêu chỉ là tốc độ dưới tranh chấp, một mutex tốt (hoặc sharding để giảm tranh chấp) thường thắng và dễ đúng hơn nhiều. Chỉ chọn lock-free khi bạn cần thuộc tính tiến triển của nó, không phải vì nghe "không khóa thì nhanh".
Giảm tranh chấp quan trọng hơn bỏ khóa. Nếu một cấu trúc là điểm nóng, cách tốt nhất thường là chia nhỏ (sharding: nhiều stack/counter, mỗi core một cái) để giảm tranh chấp — rồi mỗi shard dùng mutex đơn giản. Điều này thắng cả lock-free lẫn mutex đơn lẻ vì loại bỏ hotspot.
Dùng thư viện chuẩn khi có. sync.Map, atomic, channel đã được tối ưu kỹ. Tự viết cấu trúc lock-free là việc dễ sai (ABA, memory ordering) và hiếm khi thắng. Chỉ tự viết khi profiler chứng minh cần và không có sẵn giải pháp.
Đánh đổi cần cân nhắc
Lock-free đúng rất khó, và Go giúp một phần. Vấn đề ABA (head đổi A→B→A, CAS tưởng không đổi nhưng cấu trúc đã đổi) là bẫy lớn trong C/C++ với quản lý bộ nhớ tay. Go nhờ GC giữ node bị pop sống chừng nào còn tham chiếu, nên phần lớn tránh được ABA cổ điển — nhưng bạn vẫn phải cẩn thận với con trỏ tái dùng thủ công và memory ordering. Đừng đánh giá thấp độ khó.
Bão retry làm hiệu năng khó dự đoán. Không như mutex (chi phí tương đối ổn định), lock-free dưới tranh chấp có hiệu năng phụ thuộc mạnh vào mức tranh chấp và may rủi lịch trình. Ở tải cao đột biến, retry có thể bùng nổ. Mutex cho hành vi dễ đoán hơn — quan trọng với hệ thống cần độ trễ ổn định.
Đo trên tải thật, không tin lý thuyết. "Lock-free nhanh hơn" là niềm tin phổ biến mà benchmark này bác bỏ cho trường hợp tranh chấp cao một hotspot. Luôn đo cấu trúc của bạn dưới mẫu tải thật — số goroutine, tỷ lệ đọc/ghi, mức tranh chấp — trước khi chọn lock-free.
Ba ý mang về
- Cấu trúc lock-free xây bằng vòng lặp CAS thử-lại: đọc trạng thái, tính mới,
CompareAndSwapchỉ đổi nếu chưa ai chen vào, thất bại thì thử lại — đo thật stack lock-free đúng đắn (10000/10000 phần tử không mất,-racesạch nhờ CAS nguyên tử). - Lock-free KHÔNG tự động nhanh hơn: đo thật dưới tranh chấp cao, stack lock-free chậm hơn mutex ~3,5 lần (373 so 107 ns) vì bão retry — mỗi CAS thất bại phải làm lại cả vòng, lãng phí tăng theo tranh chấp; mutex tuần tự hóa nhưng không retry phí phạm.
- Giá trị lock-free là bảo đảm tiến triển, không phải tốc độ: thắng khi tranh chấp thấp-vừa, cần progress guarantee (không deadlock/block/priority inversion), hoặc tránh park của mutex — nhưng để "nhanh hơn" thì giảm tranh chấp bằng sharding + mutex đơn giản thường tốt hơn; Go nhờ GC phần lớn tránh ABA nhưng lock-free đúng vẫn rất khó.
Phần sau ta xây một cấu trúc lock-free phức tạp hơn và hữu dụng hơn: Phần sau mổ xẻ hàng đợi lock-free (Michael-Scott queue) — vì sao queue khó hơn stack, cách xử lý cả head lẫn tail bằng CAS, và khi nào nó đáng so với channel.
