Atomic 'lock-free' vẫn chậm 10 lần khi đông, và vòng CAS còn thua cả mutex

Hình dung cả đội cùng cập nhật một tấm bảng điểm chung. Có hai cách. Cách "fetch_add": một cái nút thần kỳ — ai bấm thì con số tự tăng đúng một đơn vị, không cần đọc, không cần tính, phần cứng lo hết trong một nhịp, và không ai phải làm lại. Cách "CAS": bạn nhìn con số (giả sử 5), nhẩm "mình sẽ đổi thành 6", rồi ghi — nhưng chỉ ghi được nếu bảng vẫn đang là 5; nếu ai đó đã đổi nó thành 6 trong lúc bạn nhẩm, thao tác của bạn bị từ chối, bạn phải nhìn lại và làm lại từ đầu. Khi đông người, ai cũng thấy số 5, ai cũng nhẩm, nhưng chỉ một người ghi được — số còn lại phí toàn bộ công vừa làm và thử lại. Và dù dùng cách nào, vẫn chỉ có một tấm bảng vật lý mà mỗi lúc một người mới chạm được — nên đông người thì vẫn giành giật nó. Đó là toàn bộ câu chuyện atomic mà tôi đo.

Ở bài mutex ta thấy khóa không tranh chấp rất rẻ. Nhưng có một cách khác để cập nhật dữ liệu chia sẻ mà không cần khóa chút nào: các biến atomic. Chúng cho phép đọc-sửa-ghi nguyên tử — không thể bị xen giữa — bằng chỉ thị phần cứng, nên được ca ngợi là "lock-free" và nhanh. Câu hỏi: atomic thật sự rẻ đến đâu, và "lock-free" có nghĩa là thoát khỏi cái giá của tranh chấp không? Tôi đo, và cả ba niềm tin phổ biến về atomic đều lệch.

Hai kiểu atomic: fetch_add và CAS

Có hai thao tác atomic hay dùng. atomic_fetch_add cộng một giá trị vào biến một cách nguyên tử — trên ARM hiện đại (LSE) đây là một lệnh phần cứng (ldadd) thực hiện đọc-cộng-ghi không thể bị chia cắt, và không thử lại (cái nút thần kỳ). CAS (compare_exchange — so sánh và đổi) đổi giá trị chỉ khi nó vẫn đúng như bạn kỳ vọng; nếu một luồng khác đã chen vào và đổi nó, CAS thất bại và bạn phải thử lại trong một vòng lặp (nhìn-nhẩm-ghi-lại). CAS mạnh hơn (cập nhật có điều kiện, nền tảng của mọi cấu trúc lock-free) nhưng mang theo chi phí thử lại.

Tôi đo trong container gcc:13 (AArch64, 10 lõi), so với mutex ở bài trước.

Không tranh chấp: rẻ, nhưng không miễn phí

atomic_fetch_add KHÔNG tranh chấp (1 luồng) : 1,59 ns/thao tác
(so với mutex không tranh chấp                : 3,3 ns)

atomic không tranh chấp là 1,59 ns — rẻ hơn mutex khoảng 2 lần. Đây là niềm tin thứ nhất bị điều chỉnh: atomic không miễn phí (nó vẫn là một phép đọc-sửa-ghi trên bộ nhớ, có rào ngầm), và nó chỉ nhanh hơn mutex khoảng 2 lần, cùng bậc độ lớn — không phải "trăm lần" như đồn. Với một biến không bị giành, cả hai đều là thao tác vài nano giây.

Có tranh chấp: lock-free không phải contention-free

Đây là chỗ niềm tin thứ hai sụp. Cho nhiều luồng cùng fetch_add vào một biến chung:

T=1 : 1,6 ns    T=2 : 5,3 ns    T=4 : 9,1 ns    T=8 : 16,6 ns

Chi phí mỗi thao tác tăng ~10 lần từ 1 lên 8 luồng. atomic "lock-free" vẫn chậm đi khi tranh chấp — vì dù không có khóa, biến vẫn nằm trên một dòng cache, và khi nhiều lõi cùng ghi vào nó, dòng cache đó phải nảy qua lại giữa các lõi (cache-line bouncing). Mỗi lõi muốn ghi phải giành quyền sở hữu độc quyền dòng cache, đẩy nó ra khỏi cache của lõi khác (vẫn chỉ một tấm bảng, phải chuyền tay). Lock-free không phải contention-free. Cái đắt của việc chia sẻ không đến từ cơ chế khóa, mà từ vật lý của cache coherence — và atomic không thoát khỏi nó.

Còn vòng CAS thì tệ hơn hẳn khi đông:

T=1 : 1,6 ns (0 thử lại)   T=4 : 8,0 ns (0,25 thử lại/op)
T=8 : 128,9 ns (3,76 thử lại/op)

Ở 8 luồng, mỗi thao tác CAS tốn 128,9 ns — và trung bình 3,76 lần thử lại cho mỗi lần thành công. Vì nhiều luồng cùng đọc giá trị cũ rồi cùng thử đổi; chỉ một thắng, những luồng còn lại thấy giá trị đã đổi, thất bại, phải đọc lại (dòng cache đang nảy) và thử lại. So với mutex ở bài trước — 27 ns ở 8 luồng cho vùng tới hạn ngắn — vòng CAS chậm hơn cả mutex.

(Môi trường đo: container gcc:13 trên host ARM AArch64 (LSE, ldadd), 10 lõi, so với mutex bài trước. Con số tuyệt đối đổi theo máy; điều bền vững là hình dạng: atomic không tranh chấp rẻ ngang bậc mutex, fetch_add tranh chấp chậm dần vì cache nảy, và vòng CAS phí công thử lại khi đông.)

Ba niềm tin phổ biến, cùng lệch

Tôi vào đo với ba niềm tin phổ biến về atomic, và cả ba đều bị đo lật. Một: "atomic miễn phí" — không, 1,6 ns, rẻ nhưng thật. Hai: "atomic lock-free nên không bị tranh chấp" — sai hẳn, fetch_add vẫn chậm 10 lần khi tranh chấp vì cache nảy; lock-free chỉ nghĩa là không có khóa/không thể deadlock, không nghĩa là không tốn khi giành. Ba: "atomic luôn nhanh hơn mutex nhiều lần" — fetch_add nhanh hơn mutex chút ít (cùng bậc), nhưng một vòng CAS dưới tranh chấp cao lại chậm hơn cả mutex (128,9 so 27 ns), vì công thử-lại bị phí.

Ba niềm tin gặp nhau ở một sự thật, và là bài học đo lường của bài: cái đắt không nằm ở việc bạn dùng mutex hay atomic, mà ở chỗ nhiều lõi cùng GHI vào một ô nhớ. Chia sẻ một biến ghi giữa các lõi luôn tốn — vì dòng cache phải nảy — dù bạn bọc nó bằng khóa hay bằng lệnh atomic. Đổi mutex sang atomic không giải quyết được contention; nó chỉ đổi hình dạng của cái giá.

Vì sao fetch_add thắng vòng CAS

Chênh lệch giữa fetch_add (16,6 ns) và vòng CAS (128,9 ns) ở 8 luồng đáng để hiểu, vì nó dạy một điều tinh tế về phần cứng. fetch_add trên ARMv8.1+ là một lệnh atomic duy nhất (ldadd) mà con chip thực hiện không bao giờ thất bại: nó giành dòng cache, cộng, xong — mỗi lõi được phục vụ lần lượt, không ai phải "làm lại" (cái nút thần kỳ). Vòng CAS thì ngược lại: nó là mẫu "đọc giá trị cũ → tính giá trị mới → thử đổi, nếu ai chen vào thì lặp". Dưới tranh chấp cao, nhiều luồng cùng đọc một giá trị cũ, cùng tính, rồi chỉ một luồng đổi thành công; phần còn lại phí toàn bộ công vừa làm và phải đọc lại dòng cache đang nảy. Đó là lý do CAS đo ra 3,76 lần thử lại mỗi op và chậm gấp 8 lần fetch_add. Bài học, đúng như đo lường vi mô đúng cách nhấn mạnh: hai thao tác "cùng là atomic" có thể có hành vi tranh chấp khác hẳn — nên khi chọn giữa fetch_add và một vòng CAS, hãy đo ở đúng mức tranh chấp bạn sẽ gặp, đừng giả định "atomic là atomic".

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

Điều đầu tiên: đừng đổi mutex sang atomic với kỳ vọng "lock-free nên nhanh". Nếu điểm nóng là một biến bị nhiều luồng cùng ghi, atomic hóa nó vẫn để lại cache-line bouncing — và nếu bạn dùng vòng CAS, có thể còn chậm hơn. Cách đúng để tăng tốc là giảm chia sẻ, không phải đổi cơ chế đồng bộ.

Điều thứ hai: cho mỗi luồng một ô riêng, gộp cuối cùng. Thay vì tất cả cùng fetch_add vào một bộ đếm chung, cho mỗi luồng một bộ đếm cục bộ (không chia sẻ, không nảy cache), rồi cộng tất cả lại một lần khi xong. Đây là mẫu "reduction"; nó biến một điểm nóng tranh chấp thành các phép cộng cục bộ rẻ. Với fetch_add một biến chung ở 8 luồng là 16,6 ns/op; với bộ đếm cục bộ thì mỗi op quay về ~1 ns không tranh chấp.

Chỗ này đúng là bài toán mà thư viện các ngôn ngữ đã đóng gói sẵn, và biết cách chúng phân biệt fetch_add với CAS giúp bạn chọn đúng. Java AtomicLong.incrementAndGet() dịch ra LOCK XADD (x86) hay ldaddal (ARM) — một lệnh không thử lại, đúng fetch_add; nhưng AtomicReference.updateAndGet()/compareAndSet trong vòng lặp là CAS-retry, chậm dần khi đông đúng như tôi đo. Và câu trả lời của Java cho một bộ đếm nóng chính là LongAdder — nó không dùng một atomic chung mà giữ một mảng ô per-thread (Striped64), cộng vào ô riêng rồi sum() gộp: đúng "mỗi luồng một ô" tôi vừa nói, và nó bỏ xa AtomicLong khi nhiều luồng ghi. Go phân biệt rõ atomic.AddInt64 (fetch_add, không retry) với vòng atomic.CompareAndSwap bạn tự viết (retry). Ở tầng database, optimistic locking kiểu Hibernate @Version chính là một CAS ở mức dòng — "cập nhật nếu số phiên chưa đổi, nếu đổi thì retry transaction" — và một hot row mà mọi transaction cùng CAS sẽ retry tơi bời y như vòng CAS 8 luồng của tôi. Mẫu số chung: ưu tiên thao tác một-lệnh-không-retry (fetch_add) hơn vòng CAS khi chỉ cần cộng/tăng, và khi tranh chấp cao thì chia ô thay vì tối ưu cơ chế.

Muốn tự thấy thì cho 8 luồng cùng atomic_fetch_add vào một biến chung 10 triệu lần mỗi luồng, đo thời gian mỗi thao tác — bạn sẽ thấy nó chậm hơn nhiều so với một luồng, dù "không có khóa". Rồi đổi thành: mỗi luồng cộng vào một biến long cục bộ của riêng nó, rồi cộng 8 kết quả lại ở cuối — đo lại, mỗi phép cộng giờ quay về ~1 ns và tổng thời gian giảm mạnh. Vài phút đó dạy bạn điều cốt lõi về đồng thời hiệu năng: nút thắt không phải "khóa hay không khóa", mà là "có chia sẻ ô nhớ ghi hay không" — và cách nhanh nhất luôn là đừng chia sẻ khi không cần.