Compare-and-swap (CAS) là viên gạch nền của mọi cấu trúc lock-free: CAS(addr, expected, new) chỉ ghi new vào addr nếu giá trị hiện tại đúng bằng expected — nguyên tử, một lần. Mẫu dùng kinh điển: đọc giá trị hiện tại, tính giá trị mới, rồi CAS — nếu CAS thành công, "chưa ai đổi trong lúc mình tính". Nghe chắc nịch. Nhưng có một cái bẫy tinh vi mang tên ABA khiến "CAS thành công" không đảm bảo điều bạn tưởng. Tôi tái hiện nó có kiểm soát trong container, và đo cả liều thuốc.
CAS so giá trị, không so lịch sử
Cái mà CAS thực sự bảo đảm rất hẹp: tại thời điểm CAS chạy, giá trị bằng expected. Nó không bảo đảm "không ai đổi giá trị trong khoảng từ lúc bạn đọc tới lúc bạn CAS". Đó là hai điều rất khác nhau. Nếu giá trị đi từ A (bạn đọc) sang B rồi quay lại A (trước khi bạn CAS), thì CAS của bạn thấy A — đúng expected — và thành công, dù thế giới đã thay đổi và quay lại. Đây là bài toán ABA: cùng một giá trị A, nhưng lịch sử đã khác.
Với một biến đếm đơn thuần, ABA thường vô hại (A vẫn là A). Nhưng với con trỏ trong cấu trúc lock-free, nó chết người: con trỏ A có thể trỏ tới một node đã bị pop ra và tái sử dụng — cùng địa chỉ, nội dung khác. CAS thành công, nhưng bạn vừa nối lại một node đã chết. Tôi dựng đúng kịch bản đó và ép nó xảy ra một cách xác định (dùng một handshake hai cờ atomic để buộc thứ tự xen kẽ), trong container gcc:13.
Đo (a): CAS thường thành công sai
Ngăn xếp lock-free ban đầu: A -> B -> C (đỉnh là A). Luồng T1 muốn pop A: nó đọc đỉnh = A, đọc A.next = B, rồi tạm dừng (handshake). Trong lúc T1 dừng, luồng T2 làm ba việc: pop A (đỉnh = B), pop B (đỉnh = C), rồi push A trở lại (giờ A.next = C, đỉnh = A). Ngăn xếp giờ là A -> C, và B đã ra ngoài. T1 tỉnh dậy, chạy CAS(đỉnh, A, B) — ý nó là "pop A, đặt đỉnh thành cái sau A mà tôi đã đọc, tức B":
CAS plain: THÀNH CÔNG dù trạng thái đã đổi -> đỉnh = B
ABA XẢY RA: node B đã bị pop lại sống dậy làm đỉnh -> ngăn xếp HỎNG
CAS thành công — vì đỉnh đúng là A tại thời điểm đó (T2 đã đẩy A về). Nhưng T1 đặt đỉnh = B, cái mà nó đọc từ đầu. B đã bị pop ra rồi! Giờ ngăn xếp thành B -> C, node A biến mất và node B (đã bị loại) sống dậy làm đỉnh. Cấu trúc hỏng hoàn toàn — mất một phần tử, thêm lại một phần tử đã xóa — mà CAS báo thành công. Không có lỗi nào, không có ngoại lệ; chỉ dữ liệu sai lặng lẽ. Đây chính xác là vì sao ABA nguy hiểm: nó lách qua đúng cơ chế mà bạn tin để bảo vệ mình.
Đo (b): versioned CAS bắt được
Liều thuốc chuẩn: versioned CAS (còn gọi tagged pointer). Ý tưởng: đừng chỉ lưu giá trị, mà lưu (giá trị, bộ đếm phiên) trong cùng một ô nguyên tử; mỗi lần sửa, tăng bộ đếm phiên. Giờ "A ở phiên 0" và "A ở phiên 3" là hai giá trị khác nhau, dù cùng con trỏ A. Tôi đóng gói (chỉ số node, phiên) vào một số 64-bit và lặp lại đúng kịch bản:
CAS versioned: THẤT BẠI vì phiên đã đổi (đỉnh giờ là (v3, A))
BẮT ĐƯỢC ABA -> sẽ thử lại với trạng thái mới (đúng)
T1 đọc (v0, A). Ba thao tác của T2 mỗi lần tăng phiên: (v0,A) -> (v1,B) -> (v2,C) -> (v3,A). T1 chạy CAS((v0,A) -> (v1,B)), nhưng giá trị hiện tại là (v3,A) — khác (v0,A) vì phiên đã nhảy từ 0 lên 3. CAS thất bại. T1 phát hiện có người đã đụng vào, quay lại đọc trạng thái mới ((v3,A), với A.next giờ là C), và pop A một cách đúng đắn. ABA bị chặn tận gốc, vì bộ đếm phiên biến "A quay lại" thành "một A khác".
Đo (c): versioning gần như miễn phí
Có người ngại: đóng gói bộ đếm phiên có làm CAS chậm không? Tôi đo throughput một vòng CAS thường (trên một uint) so với vòng CAS versioned (trên một uint64 đóng gói giá trị + phiên), một luồng:
plain CAS (uint) : 3,69 ns/op (271 triệu/giây)
versioned CAS (u64) : 3,72 ns/op (268 triệu/giây)
Chênh lệch ~1% — gần như miễn phí. Cả hai đều là một thao tác CAS nguyên tử trên một word (32-bit hay 64-bit không khác biệt đáng kể trên CPU 64-bit); bộ đếm phiên chỉ là vài bit thừa trong cùng word đó. Nên chống ABA bằng versioning không đánh đổi hiệu năng — cái giá thật của lock-free không nằm ở đây mà ở độ khó viết đúng.
Một lần tôi đo hớ: CAS thành công không bằng "yên ổn"
Tôi vào đo với hai niềm tin phổ biến. Thứ nhất: "CAS thành công nghĩa là không ai đụng vào giá trị đó". Sai — CAS thành công chỉ nghĩa giá trị bằng expected tại thời điểm CAS; nó hoàn toàn không biết giá trị đã đi A→B→A trong lúc bạn tính toán. Thứ hai, hệ quả: "lock-free đơn giản mà, cứ CAS là an toàn". Cũng sai — ABA là một lớp bug mà CAS trần không chống được, và cấu trúc lock-free đúng đắn phải chủ động chống nó.
Điều làm tôi phải cẩn thận khi đo: ABA phụ thuộc timing. Tôi phải ép thứ tự xen kẽ bằng handshake mới thấy nó xảy ra một cách chắc chắn; trong thực tế, cửa sổ đua rất hẹp, nên một cấu trúc lock-free dính ABA có thể chạy đúng hàng triệu lần rồi hỏng một lần ở production. Đây đúng là bài học của deadlock: "chạy thử thấy ổn" không chứng minh code lock-free an toàn — tính đúng phải đến từ phân tích (giá trị có thể quay lại không? node có thể tái dùng không?), không phải từ việc chưa gặp lỗi. Bài học đo lường: một thao tác nguyên tử "thành công" chỉ bảo đảm đúng cái nó định nghĩa — bằng giá trị — chứ không bảo đảm cái bạn mong nó bảo đảm — không ai can thiệp. Đọc kỹ hợp đồng của nguyên hàm, đừng gán cho nó ý nghĩa mạnh hơn thực tế.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi viết lock-free với con trỏ tái dùng, luôn nghĩ tới ABA. Bất cứ khi nào bạn CAS một con trỏ mà node có thể bị pop ra rồi cấp phát lại (cùng địa chỉ), ABA rình rập. Dùng versioned/tagged pointer (đóng phiên vào con trỏ — nhiều CPU hỗ trợ CAS kép 128-bit cho đúng việc này), hoặc các kỹ thuật quản lý bộ nhớ trì hoãn như hazard pointer / RCU (sê-ri sẽ bàn sau) để bảo đảm node không bị tái dùng khi còn ai đang trỏ tới.
Hệ quả thứ hai: đừng gán cho "CAS thành công" ý nghĩa mạnh hơn nó có. CAS nói "giá trị bằng expected lúc này", không nói "không ai đổi từ lúc bạn đọc". Nếu logic của bạn dựa vào điều thứ hai (ví dụ giả định node bạn đọc vẫn còn nguyên trong cấu trúc), bạn cần thêm bảo vệ — phiên bản, hoặc đảm bảo an toàn bộ nhớ khác. Với biến đếm/cờ đơn thuần thì CAS trần đủ (ABA vô hại); với con trỏ và cấu trúc thì không.
Hệ quả thứ ba là tinh thần đo lường: hiểu chính xác nguyên hàm bảo đảm gì — và ABA phụ thuộc timing nên phải phân tích, đừng tin phép thử. Con số mang theo: CAS thành công CHỈ bảo đảm giá trị = expected TẠI THỜI ĐIỂM CAS, KHÔNG bảo đảm không ai đổi trong khoảng đọc->CAS — đó là ABA: ép A->B->A giữa lúc đọc và CAS thì CAS plain THÀNH CÔNG dù trạng thái đã hỏng (node bị pop sống dậy làm đỉnh, ngăn xếp hỏng lặng lẽ). Thuốc: versioned CAS (đóng gói bộ đếm phiên) -> A-phiên-0 khác A-phiên-3, CAS thất bại, bắt được ABA, gần MIỄN PHÍ (3,69 vs 3,72 ns/op). Lock-free KHÔNG đơn giản; ABA phụ thuộc timing nên 'chạy thử thấy ổn' không chứng minh an toàn.
Thử ba mươi giây
Nếu bạn có (hoặc định viết) một cấu trúc lock-free dùng CAS trên con trỏ, hỏi một câu: con trỏ này có thể trỏ tới một giá trị đã từng ra khỏi cấu trúc rồi quay lại không? Cụ thể: một node có thể bị pop ra, được cấp phát lại (hoặc push lại), rồi khi bạn CAS thì địa chỉ trùng nhưng "bản chất" đã khác? Nếu có, bạn có nguy cơ ABA — và nó sẽ không hiện ra trong test bình thường vì cửa sổ đua quá hẹp. Cách kiểm nhanh: giá trị bạn CAS có phải là con trỏ tới bộ nhớ có thể tái dùng không? Nếu đúng, thêm một bộ đếm phiên (versioned CAS) — nó gần như miễn phí và chặn ABA tận gốc. Ba mươi giây hỏi "giá trị này có thể quay lại không" đó phân biệt một CAS an toàn (biến đếm, cờ) với một CAS cần chống ABA (con trỏ) — và nhắc rằng trong lock-free, "CAS thành công" là một lời hứa hẹp hơn nhiều so với cảm giác an tâm nó mang lại.
