Bỏ cánh cửa quay ở lối vào tòa nhà và thay bằng một ô cửa trống, ai đi cũng nhanh hơn — khi vắng. Nhưng giờ tan tầm, tám trăm người vẫn phải chen qua đúng một ô cửa đó; bỏ cửa quay không tạo thêm lối đi, cái nghẽn không nằm ở cánh cửa mà ở chỗ ai cũng phải qua cùng một điểm. Thao tác atomic so với mutex đúng là chuyện cái cửa đó, và con số ở "lúc vắng" suýt khiến tôi kết luận sai cho "lúc đông". Ở bài về tranh chấp mutex tôi hứa sẽ đo thao tác nguyên tử (atomic) so với khóa. Đây là bài đó. Câu hỏi: một bộ đếm chung tăng bằng atomic_fetch_add (không khóa, "lock-free") so với tăng trong một mutex — cái nào nhanh hơn, và có scale không?

Nguyên tử là gì, khác khóa thế nào

Một thao tác nguyên tử thực hiện đọc-sửa-ghi như một bước không thể chia cắt của phần cứng. atomic_fetch_add(&x, 1) đọc x, cộng 1, ghi lại — và CPU đảm bảo không luồng nào chen được vào giữa. Trên ARM đời mới, nó biên dịch thành một lệnh phần cứng duy nhất ldadd (nhìn assembly xác nhận). Không mutex, không lời gọi hệ thống, không ngủ — nên gọi là lock-free.

Khác với mutex: mutex bảo vệ cả một vùng găng (đoạn code) và có thể khiến luồng ngủ khi tranh chấp (như bài futex đo); atomic chỉ làm nguyên tử một thao tác đơn trên một biến, không bao giờ ngủ. Nghe như atomic phải luôn nhanh hơn. Tôi đo thông lượng (triệu lần tăng mỗi giây) của một bộ đếm chung, tăng dần số luồng.

Đo: atomic thắng ở một luồng, thua ở tám luồng

Bộ đếm CHUNG, triệu ops/giây:
luồng |  mutex  | atomic
  1   |   239   |  626
  2   |    42   |  311
  4   |    53   |  154
  8   |    40   |   25   <-- atomic THUA mutex

Ở một luồng, atomic (626) nhanh hơn mutex (239) khoảng 2,6 lần — đúng như kỳ vọng, vì nó bỏ được toàn bộ chi phí khóa/mở khóa. Ở 2 và 4 luồng, atomic vẫn thắng rõ (311 so với 42, 154 so với 53). Nhìn ba dòng đầu, tôi đã định viết "atomic lock-free thì luôn nhanh hơn và scale tốt hơn khóa, cứ dùng nó".

Nhưng dòng cuối chặn tôi lại: ở tám luồng, atomic tụt xuống 25 triệu ops/giây — chậm hơn cả mutex (40). Con số này phá vỡ khái quát vội vàng của tôi.

Lock-free không phải contention-free — và tôi suýt khái quát nhầm

Lý do atomic sụp ở tám luồng nối thẳng với bài trước: dù không có khóa, tất cả tám lõi vẫn đập vào cùng một biến, tức cùng một dòng cache. Phần cứng chỉ cho một lõi sở hữu một dòng cache ở trạng thái ghi tại một thời điểm, nên dòng cache đó phải nảy qua nảy lại giữa các lõi mỗi lần một lõi muốn tăng — đúng cái trần cache-line đã đo ở bài tranh chấp mutex. Atomic bỏ được lời gọi khóa và nguy cơ ngủ, nhưng không bỏ được cái giá vật lý của nhiều lõi giành một dòng cache. Càng đông, càng nảy, càng chậm.

Và tôi đo một biến thể tệ hơn: vòng CAS tự viết. Thay vì fetch_add, ta đọc giá trị cũ rồi dùng compare-and-swap (so-sánh-và-đổi) để ghi giá trị mới, lặp lại nếu có ai chen vào giữa:

CAS loop, bộ đếm chung:
  1 luồng: 600 M ops/s | 0 lần thử lại
  2 luồng: 297 M ops/s | 13.392.590 lần CAS PHẢI thử lại
  4 luồng: 107 M ops/s | 14.454.761 lần thử lại
  8 luồng: 7,5 M ops/s | ~9.500.000 lần thử lại   <-- chậm nhất mọi cách

Ở một luồng, không ai chen nên 0 lần thử lại, siêu nhanh. Nhưng ở nhiều luồng, mỗi lần một luồng đọc giá trị rồi định CAS, một luồng khác đã kịp thay đổi giá trị đó → CAS thất bại, luồng phải đọc lại và làm lại từ đầu. Ở tám luồng, có mười triệu lần thử lại — hầu hết công sức đổ vào việc đọc-tính-rồi-vứt-bỏ. Thông lượng rơi xuống 7,5 triệu ops/giây, chậm nhất trong mọi cách, kể cả mutex.

Điều rút ra: "lock-free" không có nghĩa "contention-free" cũng không có nghĩa "scalable". Con số "atomic nhanh gấp 2,6 lần mutex" là thật — ở một luồng. Nhưng nó dụ tôi khái quát cho mọi mức luồng, và sai. Atomic thắng khi tranh chấp thấp; khi tranh chấp cao, nó sụp ngang hoặc tệ hơn khóa, còn CAS tự viết thì thảm họa. Cái bẫy là đo ở một điểm (một luồng) rồi ngoại suy cho cả đường cong. "Nhanh" vô nghĩa nếu chưa hỏi "ở mức tranh chấp nào".

Một cái bẫy nữa của CAS: bài toán ABA

Ngoài chuyện thử lại, CAS còn một cạm bẫy tinh vi mà đo tốc độ không thấy: bài toán ABA. CAS chỉ hỏi "giá trị hiện tại có bằng cái tôi đọc lúc nãy không?" — nó không biết giá trị đó có bị đổi rồi đổi lại trong lúc đó. Hình dung: luồng A đọc con trỏ đầu danh sách là X. Trong lúc A tạm dừng, luồng B lấy X ra, dùng, trả X về (địa chỉ tái sử dụng), rồi đầu danh sách lại là X. Khi A tỉnh dậy, CAS của nó thấy đầu vẫn là X nên thành công — dù cấu trúc bên dưới đã đổi hoàn toàn, dẫn tới hỏng dữ liệu. Với một bộ đếm long tăng đơn thuần thì ABA vô hại (giá trị cứ tăng, không quay lại), nhưng với con trỏ trong cấu trúc lock-free thì đây là lỗi kinh điển, phải chống bằng thẻ phiên bản (tagged pointer) hay con trỏ nguy hiểm (hazard pointer). Đây là lý do viết cấu trúc lock-free đúng khó hơn nhiều so với chỉ "dùng atomic cho nhanh".

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

Điều đầu tiên: dùng atomic cho bộ đếm/cờ tranh chấp thấp, không phải cho mọi thứ đồng thời. Một biến atomic thay cho mutex là lựa chọn tốt khi thao tác đơn giản (tăng một bộ đếm, đặt một cờ) và tranh chấp không quá gắt — nó nhanh và gọn. Nhưng đừng tưởng "lock-free" là phép màu cho khả năng mở rộng; dưới tranh chấp cao trên một biến, nó không cứu được bạn khỏi trần cache-line. Giải pháp scale thật vẫn là giảm chia sẻ: mỗi luồng một bộ đếm riêng (đệm ra dòng cache riêng), cộng lại khi cần — đúng cái đã đo ở bài trước.

Điều thứ hai: cẩn thận với vòng CAS tự viết. CAS là nền của mọi cấu trúc lock-free, nhưng một vòng CAS ngây thơ dưới tranh chấp cao biến thành một cơn bão thử-lại đốt CPU mà không tiến triển — chính là 7,5 triệu ops/giây với mười triệu lần thử lại. Nếu bạn thấy mình viết while (!compare_exchange(...)), hãy đo nó dưới tải thật; thường một fetch_add sẵn có (nếu đủ) hoặc giảm chia sẻ sẽ tốt hơn nhiều.

Và cái sự thật "lock-free không phải scalable, cái nghẽn là điểm chia sẻ chung chứ không phải cái khóa" này chính là thứ các thư viện đồng thời cấp cao đã học và né. LongAdder của Java ra đời đúng để thay AtomicLong dưới tranh chấp cao: nó tách bộ đếm ra nhiều ô (cell) trên các dòng cache riêng rồi cộng khi đọc — chính là "giảm chia sẻ" đóng gói sẵn, và nó thắng AtomicLong rõ rệt khi nhiều luồng cùng ghi. sync/atomic của Go cũng sụp y hệt trên một biến nóng, nên người ta dùng sharded counter hay sync.Pool. Ngay cả CSDL gặp đúng bài toán này ở dạng khác: một hàng "bộ đếm" bị mọi transaction cùng UPDATE (như tồn kho, số lượt xem) trở thành điểm nóng khóa hàng — giải pháp là tách thành nhiều hàng con cộng lại, đúng tinh thần giảm chia sẻ. Mẫu số chung: trên phần cứng nhiều lõi, khả năng mở rộng bị quyết định bởi bao nhiêu bên cùng ghi vào một điểm chung, không phải bởi bạn dùng khóa hay cơ chế lock-free — bỏ khóa mà giữ điểm chung thì vẫn nghẽn. Gói lại bằng số: atomic nhanh hơn mutex khi tranh chấp thấp (626 so với 239 ở một luồng, gấp 2,6 lần) nhưng cùng sụp vì trần cache-line khi tranh chấp cao (25 so với 40 ở tám luồng), và vòng CAS tự viết còn tệ nhất (7,5 triệu ops/giây, mười triệu lần thử lại); lock-free không phải scalable, cách scale thật là giảm chia sẻ. Với một bộ đếm thuần túy, relaxed memory ordering là đủ và rẻ hơn seq_cst mặc định trên nhiều kiến trúc (dù trên ARM đời mới đo được là gần bằng nhau).

Muốn tự thấy thì trong ngôn ngữ của bạn, tìm kiểu atomic: C11 _Atomic/stdatomic.h, C++ std::atomic, Java AtomicLong, Rust AtomicU64, Go sync/atomic. Thử viết một bộ đếm chung tăng bằng atomic từ 1, 2, 4, 8 luồng và đo ops/giây — bạn sẽ thấy đường cong đi lên rồi chững hoặc đi xuống, không phải tăng mãi. Rồi thử phiên bản "mỗi luồng một bộ đếm riêng, cộng ở cuối" (hay LongAdder trong Java) và so: nó sẽ scale gần tuyến tính. Khác biệt giữa hai đường cong đó chính là bài học của cả hai bài (tranh chấp mutex và bài này): trên phần cứng nhiều lõi, thứ quyết định khả năng mở rộng không phải bạn dùng khóa hay atomic, mà là có bao nhiêu lõi cùng giành một dòng cache.