Khi nhiều luồng cùng cập nhật một dữ liệu chung, cách quen thuộc là dùng mutex (khóa): luồng nào muốn sửa thì khóa lại, sửa, rồi mở khóa; luồng khác chờ. Nhưng có một hướng khác nghe rất hấp dẫn: lock-free — đồng bộ không cần khóa, dùng các lệnh nguyên tử (atomic) của CPU, chủ yếu là CAS (compare-and-swap: "nếu giá trị vẫn là X thì đặt thành Y").

Hình dung một cuốn sổ ghi chép chung mà nhiều người cần cập nhật. Kiểu mutex: ai muốn ghi thì cầm lấy sổ, người khác đứng đợi tới lượt — trật tự, không ai giẫm chân, nhưng phải xếp hàng. Kiểu lock-free: ai cũng cứ chép nội dung ra giấy nháp của mình, rồi khi định ghi vào sổ thì liếc xem sổ có bị ai đổi từ lúc mình đọc không — nếu có, xé nháp làm lại từ đầu. Không ai phải đợi, nhưng nếu đông người cùng giành ghi, số lần "làm lại" phình lên. Nhiều người tin "lock-free không khóa nên luôn nhanh hơn mutex". Tôi đo một biến đếm bị nhiều luồng cùng tăng, so mutex với atomic và CAS-loop trong container gcc:13, và con số cho thấy câu chuyện phụ thuộc mức tranh chấp — không có bên nào luôn thắng.

Khóa và chờ, so với thử-lại không khóa

Hai cách đồng bộ khác nhau ở chỗ xử lý xung đột thế nào:

  • Mutex (khóa): một luồng khóa, sửa, mở khóa; các luồng khác chờ. Đơn giản, dễ viết đúng. Nhược điểm: nếu luồng đang giữ khóa bị treo/chậm, cả hệ chờ theo (không đảm bảo tiến độ). Khóa không tranh chấp thì rẻ, nhưng tranh chấp cao thì tốn (chờ, đánh thức, chuyển ngữ cảnh).

  • Lock-free (atomic/CAS): không khóa. Luồng đọc giá trị, tính giá trị mới, rồi CAS ghi lại — nếu trong lúc đó ai đó chen vào (giá trị đã đổi), CAS thất bại và luồng thử lại (xé nháp làm lại). Ưu điểm lớn: một luồng chết/treo không kẹt luồng khác (đảm bảo tiến độ toàn hệ). std::atomic::fetch_add là một lệnh atomic sẵn của phần cứng; còn CAS-loop là bạn tự viết vòng lặp thử-lại.

Điểm mấu chốt đo lường: khi nhiều luồng cùng đụng một biến, cache line chứa biến đó phải nhảy qua lại giữa các lõi (phần 13) — và cả mutex lẫn atomic đều chịu chi phí này. Lock-free không xóa được chi phí đó; nó chỉ đổi cách trả.

Đo: atomic thắng khi ít luồng, ngang hoặc thua khi tranh gay gắt

Tôi cho nhiều luồng cùng tăng một biến đếm chung (tổng 40 triệu lần), đo ns mỗi thao tác theo số luồng, cho ba cách: mutex, atomic::fetch_add, và CAS-loop tự viết:

Biến đếm dùng chung, tổng 40 triệu lần tăng, g++ -O2 -pthread:

   luồng | mutex (khóa) | atomic fetch_add | CAS loop
   ------|--------------|------------------|----------
     1   |   4,1 ns     |    1,6 ns        |   1,6 ns
     2   |  31,2 ns     |    3,2 ns        |   2,5 ns
     4   |  18,9 ns     |    6,5 ns        |   8,0 ns
     8   |  22,1 ns     |   20,8 ns        | 141,5 ns

Nhìn dòng 1 luồng (không tranh chấp): mutex 4,1 ns, atomic 1,6 ns. Atomic nhanh hơn, nhưng mutex không đắt — một khóa không tranh chỉ tốn vài nano-giây. Điều này đã bác "mutex luôn chậm".

Nhìn 2–4 luồng (tranh vừa): atomic thắng rõ — 3,2 và 6,5 ns so với mutex 31,2 và 18,9 ns. Ở mức tranh chấp vừa, fetch_add không phải vào nhân, không chờ, nên nhanh hơn hẳn mutex. Đây là sân của lock-free.

Nhìn dòng 8 luồng (tranh gay gắt) — chỗ phá vỡ "lock-free luôn nhanh hơn": atomic fetch_add tụt xuống 20,8 ns, gần bằng mutex 22,1 ns. Vì cache line của biến đếm phải ping-pong liên tục giữa 8 lõi, throughput không còn scale — ns/op tăng theo số luồng thay vì giảm. Và CAS-loop tự viết thì tệ hẳn: 141,5 ns, chậm hơn mutex 6,8 lần. Vì mỗi lần một luồng CAS thất bại (giá trị đã đổi), nó phải thử lại từ đầu — càng đông luồng, càng nhiều lần xé-nháp-làm-lại phí công. fetch_add (một lệnh phần cứng) tránh vòng lặp thử-lại nên tốt hơn CAS-loop khi đông.

Chú ý dáng chung: không cách nào scale — ns/op ở 8 luồng đều tệ hơn ở 1 luồng, vì tất cả tranh một cache line. Lock-free không phải phép màu chống tranh chấp.

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin phổ biến: "lock-free không dùng khóa, không chờ, nên chắc chắn nhanh hơn mutex — cứ dùng atomic/CAS thay khóa là được". Con số bác ngay: ở tranh chấp gay gắt (8 luồng, một biến), atomic fetch_add chỉ ngang mutex (20,8 vs 22,1 ns), và CAS-loop tự viết còn tệ hơn mutex 6,8 lần (141,5 ns) vì thử-lại liên tục cộng cache line nhảy giữa các lõi. "Không khóa" không có nghĩa "không tranh chấp" — dữ liệu chung vẫn phải đồng bộ qua cache, và lock-free trả chi phí đó dưới dạng retry. Chưa kể lock-free cực khó viết đúng: các bẫy ABA, thứ tự bộ nhớ (memory ordering), khiến một cấu trúc lock-free tự viết dễ sai một cách tinh vi.

Nhưng nếu vì thế mà tin điều ngược lại — "mutex là khóa, khóa thì chậm, nên tránh mutex bằng mọi giá" — thì cũng sai. Mutex không tranh chấp chỉ tốn 4,1 ns (một luồng) — rất rẻ; và ngay ở 8 luồng, mutex (22,1 ns) còn tốt hơn CAS-loop tự viết (141,5 ns). Mutex đơn giản, dễ viết đúng, và ở phần lớn workload (tranh chấp thấp-vừa, hoặc vùng khóa ngắn) nó đủ nhanh. Né mutex để tự viết lock-free thường là đánh đổi đúng đắn và đơn giản lấy phức tạp và dễ sai mà không có lợi tốc độ tương xứng.

Về đến code hằng ngày

Việc đầu tiên: mặc định dùng mutex (hoặc atomic sẵn như fetch_add) — chỉ tự viết lock-free khi đo cho thấy thật sự cần. Với tranh chấp thấp-vừa và vùng khóa ngắn, mutex đủ nhanh và đúng. Nếu cần một biến đếm/cờ chia sẻ, dùng std::atomic với thao tác sẵn (fetch_add, exchange) — chúng là lock-free phần cứng, nhanh, và đúng mà không phải tự lo ordering. Đừng nhảy vào tự cài lock-free stack/queue trừ khi hồ sơ hiệu năng chỉ đúng chỗ đó.

Việc thứ hai: giảm tranh chấp quan trọng hơn chọn cơ chế đồng bộ. Cả mutex lẫn atomic đều tệ khi nhiều luồng đụng một điểm nóng. Cách thắng thật là đừng chia sẻ điểm nóng: đếm cục bộ mỗi luồng rồi cộng cuối (sharding), chia dữ liệu theo luồng, dùng cấu trúc per-thread. Một biến đếm sharded scale tuyến tính, trong khi một biến chung không cách nào scale dù mutex hay lock-free. Kiến trúc giảm chia sẻ đánh bại mọi tối ưu vi mô về khóa.

Cuộc tranh cãi "khóa hay không khóa" này lặp lại y hệt ở mọi tầng, và bài học cũng vậy. Java có synchronized/ReentrantLock (mutex) so với AtomicLong (lock-free) — và JDK sinh ra LongAdder chính vì AtomicLong bị nhiều luồng đập không scale, nên nó shard ra nhiều ô rồi cộng lại, đúng "đếm cục bộ rồi gộp". Go khuyên thẳng trong tài liệu: đừng vội thay sync.Mutex bằng sync/atomic cho tới khi đo, vì mutex Go rất nhẹ khi không tranh. Còn ở tầng database, đây là cả một triết lý: khóa bi quan (pessimistic lock, kiểu mutex) so với khóa lạc quan (optimistic concurrency control — đọc phiên bản, ghi kèm điều kiện "nếu chưa đổi", đúng CAS) — và optimistic thắng khi xung đột hiếm, nhưng thua khi tranh chấp cao vì transaction bị hủy và thử lại liên tục, y hệt CAS-loop 141,5 ns ở trên. Nguyên tắc xuyên suốt mọi tầng: chi phí đồng bộ nằm ở chia sẻ, không ở bản thân cái khóa — và cách nhanh nhất thường là đừng chia sẻ.

Muốn tự thấy thì viết một biến đếm bị nhiều luồng cùng tăng, theo ba cách: một dùng std::mutex bảo vệ một int, một dùng std::atomic<long>::fetch_add, một dùng vòng lặp compare_exchange_weak (CAS tự viết). Chạy tổng cùng số lần tăng, chia cho 1, 2, 4, 8 luồng, và bấm giờ thời gian thực (dùng steady_clock, không phải clock() — nó cộng CPU của mọi luồng). Bạn sẽ thấy ở một luồng atomic nhanh hơn mutex nhưng mutex vẫn rẻ; ở vài luồng atomic thắng rõ; ở tám luồng cả ba đều chậm lại (ns/op tăng theo số luồng), atomic gần bằng mutex, và CAS-loop tệ hẳn vì thử lại liên tục. Cuối cùng, thử phiên bản mỗi luồng đếm riêng rồi cộng cuối — nó scale, vì không tranh một cache line. Ba mươi giây đó cho thấy điều mà "lock-free không khóa nên nhanh hơn" giấu đi: chi phí đồng bộ nằm ở cache line chia sẻ, không ở bản thân cái khóa — và cách nhanh nhất thường là đừng chia sẻ, chứ không phải đổi khóa lấy CAS.