Ở ABA ta chạm một câu hỏi chưa trả lời: trong code lock-free, khi nào an toàn để giải phóng (free) một node? Một luồng khác có thể vừa đọc con trỏ tới node đó và sắp truy cập nó — nếu bạn free ngay, luồng kia đọc phải bộ nhớ đã chết (use-after-free), hoặc node được cấp phát lại gây ABA. Đây là bài toán thu hồi bộ nhớ của lock-free, và nó khó hơn viết chính giải thuật. Hai lời giải nổi tiếng là hazard pointer và RCU (Read-Copy-Update). Tôi đo chúng, và phát hiện điều khiến RCU đặc biệt: nó làm việc đọc gần như miễn phí — nhưng "miễn phí" đó được trả ở chỗ khác.
Hai cách biết "còn ai đang đọc"
Cốt lõi của cả hai kỹ thuật: trước khi free một node, phải biết chắc không luồng nào còn đang đọc nó. Chúng trả lời câu đó theo hai cách, nhưng chung một nguyên tắc — mỗi luồng tự khai báo vào một ô riêng, không đụng vào bộ nhớ chung.
Hazard pointer: mỗi luồng, trước khi truy cập một node, công bố con trỏ tới node đó vào một ô "hazard" riêng của mình. Writer muốn free một node thì quét mọi ô hazard; nếu node đang được ai đó công bố, hoãn free. RCU: reader vào một "vùng đọc" (read-side critical section) không khóa — chỉ đánh dấu một ô riêng rằng "tôi đang đọc". Writer thay đổi dữ liệu bằng cách tạo bản sao mới, đổi con trỏ, rồi chờ một grace period — khoảng thời gian đủ để mọi reader đang đọc bản cũ thoát ra — trước khi free bản cũ.
Điểm chung quyết định hiệu năng: đường đọc chỉ ghi vào ô riêng của luồng, không cập nhật bộ nhớ dùng chung. Đó là lý do đọc rẻ. Tôi đo trong container gcc:13 (10 lõi, dòng cache 64B), so đường đọc kiểu RCU với đường đọc dùng read-write lock.
Đo (a): đọc RCU scale, đọc rwlock sụp
Cho N luồng liên tục đọc một dữ liệu chung, hai cách vào vùng đọc: RCU (ghi epoch vào ô riêng, căn lề 64 byte) và rwlock (pthread_rwlock_rdlock/unlock, cập nhật bộ đếm reader chung). Đo throughput đọc theo N:
N | RCU (ô riêng) | rwlock (đếm chung) | RCU/rwlock
1 | 488 triệu/s | 158 triệu/s | 3×
2 | 969 | 72 | 13×
4 | 1.814 | 11 | 164×
8 | 2.888 | 7,7 | 374×
Hai đường cong đi ngược nhau hoàn toàn. RCU scale gần tuyến tính: 488 triệu đọc/giây ở 1 luồng lên 2.888 triệu ở 8 luồng (~5,9×). Vì mỗi reader chỉ ghi vào ô epoch riêng của nó — không luồng nào đụng chung một dòng cache, nên không có tranh chấp coherence. rwlock thì SỤP: 158 triệu ở 1 luồng rơi xuống 7,7 triệu ở 8 luồng — scale âm. Vì mỗi rdlock/unlock phải cập nhật một bộ đếm reader chung, và cái bộ đếm đó nảy qua nảy lại giữa các lõi — đúng cái ghi-chung đắt hơn đọc-chung 721 lần ta đã đo, và đúng lý do rwlock chậm cho đọc ngắn.
Kết quả: ở 8 luồng, đọc kiểu RCU nhanh hơn đọc rwlock 374 lần. Đây là lý do RCU thống trị các đường đọc nóng trong nhân Linux — hàng triệu lần đọc mỗi giây, và RCU khiến chúng gần như miễn phí và scale hoàn hảo.
Đo (b): grace period — cái giá của writer
Nhưng "gần như miễn phí" ở đường đọc phải được trả ở đâu đó — và chỗ đó là writer. Trong RCU, writer không được free ngay; nó phải chờ grace period — chờ mọi reader đang đọc bản cũ thoát ra. Để biết điều đó, writer quét các ô epoch của mọi luồng. Tôi đo chi phí một lần quét N ô:
quét 1 ô : 0,25 ns/lần
quét 8 ô : 2,07 ns/lần (~0,25 ns mỗi ô)
Bản thân việc quét rẻ (0,25 ns/ô). Nhưng đó không phải toàn bộ cái giá — cái giá thật là writer phải chờ cho tới khi tất cả reader cũ ra khỏi vùng đọc trước khi free, và bộ nhớ bị giữ lại lâu hơn (node cũ không được thu hồi ngay mà nằm chờ hết grace period). Với workload đọc-nhiều-ghi-ít, đây là đổi chác tuyệt vời: đường đọc (chạy hàng triệu lần) gần như miễn phí, còn đường ghi (chạy hiếm) gánh thêm việc chờ và thu hồi trễ. Nhưng nếu ghi thường xuyên, việc thu hồi trễ khiến bộ nhớ tồn đọng, và writer chờ nhiều — RCU mất lợi.
Một lần tôi đo hớ: thu hồi lock-free không miễn phí, chỉ dời chỗ
Tôi vào đo với hai niềm tin. Thứ nhất: "đọc trong cấu trúc đồng thời thì cũng phải đồng bộ như nhau — rwlock hay RCU cũng vậy". Sai — đo cho thấy đọc RCU nhanh hơn đọc rwlock 374 lần ở 8 luồng, vì RCU không đụng bộ nhớ chung ở đường đọc còn rwlock thì đụng (bộ đếm reader). Thứ hai, nguy hiểm hơn: "thu hồi bộ nhớ trong lock-free chắc cũng miễn phí như bản thân giải thuật lock-free". Sai — thu hồi an toàn đòi một cơ chế (hazard pointer hay grace period), và cơ chế đó có giá.
Bài học đo lường, và là ý sâu nhất của phần này: hiệu năng không bao giờ tự nhiên biến mất — nó chỉ dời chỗ. RCU không xóa chi phí đồng bộ; nó chuyển chi phí từ reader (đông, nóng) sang writer (ít, nguội) cộng một khoản trễ (bộ nhớ giữ tới hết grace period). Đó là một sự đổi chác thông minh khi đọc nhiều hơn ghi hàng nghìn lần — bạn tối ưu đúng cái chạy thường xuyên. Nhưng gọi nó "miễn phí" là hiểu sai: bạn không bỏ chi phí, bạn chuyển nó tới nơi ít đau nhất. Đúng tinh thần đo lường: mọi tối ưu đồng thời đều là một sự dời chỗ chi phí, và chỉ đo mới cho biết bạn dời nó đi đâu và có đáng không cho workload của mình.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với dữ liệu đọc-rất-nhiều-ghi-ít dùng chung, cân nhắc RCU (hoặc bản đọc không khóa tương tự). Bảng định tuyến, cấu hình, danh sách theo dõi — thứ đọc hàng triệu lần và cập nhật hiếm — là ứng viên hoàn hảo. RCU cho đường đọc gần như miễn phí và scale tuyến tính, đổi lấy đường ghi phức tạp hơn (copy + chờ grace period). Nhiều ngôn ngữ/thư viện có sẵn (userspace RCU, arc-swap của Rust, AtomicReference + copy-on-write của Java).
Hệ quả thứ hai: đừng dùng rwlock cho đọc ngắn, đông luồng. Như đo được, rwlock cập nhật bộ đếm reader chung mỗi lần đọc, và cái bộ đếm đó thành điểm nóng coherence — đọc sụp thay vì scale. Nếu đường đọc của bạn ngắn và nhiều luồng, một cơ chế đọc không-ghi-chung (RCU, epoch-based, seqlock cho một số ca) sẽ nhanh hơn nhiều lần.
Hệ quả thứ ba là tinh thần đo lường: tối ưu là dời chi phí, không phải xóa — đo xem nó dời đi đâu. Con số mang theo: thu hồi bộ nhớ lock-free (hazard pointer/RCU) làm ĐỌC gần miễn phí bằng cách cho mỗi reader ghi ô RIÊNG (không đụng bộ nhớ chung) -> đọc RCU scale gần tuyến tính (488->2888 triệu/s từ 1->8 luồng), nhanh 374× rwlock ở 8 luồng (rwlock SỤP 158->7,7 vì bộ đếm reader chung nảy coherence); NHƯNG không miễn phí — đổi lại WRITER phải chờ grace period (quét ô reader, chờ reader cũ ra) mới free, thu hồi TRỄ, bộ nhớ giữ lâu hơn. Lock-free chỉ DỜI chi phí từ reader sang writer + trễ, không xóa. Đọc-nhiều-ghi-ít -> RCU.
Thử ba mươi giây
Nghĩ về một cấu trúc dữ liệu dùng chung trong hệ của bạn mà đọc nhiều hơn ghi rất nhiều — một bảng tra, một cấu hình, một danh sách hiếm khi đổi nhưng đọc liên tục. Hỏi: đường đọc hiện có đồng bộ gì không? Nếu nó lấy một khóa (kể cả rwlock) mỗi lần đọc, thì mỗi lần đọc đang cập nhật trạng thái chung (bộ đếm khóa) — và với nhiều luồng, cái đó thành điểm nóng làm đọc chậm đi khi thêm luồng. Thử hình dung một đường đọc không ghi gì chung (đọc con trỏ hiện tại, dùng, xong — writer lo việc thay và thu hồi): đọc sẽ scale tuyến tính. Đó là ý tưởng RCU. Rồi hỏi câu thứ hai để không bị lừa: cái giá writer trả là gì? — writer phải chờ mọi reader cũ ra trước khi giải phóng bản cũ, nên bộ nhớ giữ lâu hơn và ghi phức tạp hơn. Ba mươi giây cân "đọc rẻ đi" với "ghi đắt lên và thu hồi trễ" đó cho bạn biết RCU có hợp workload của mình không — và nhắc rằng trong đồng thời, không có bữa trưa miễn phí, chỉ có chuyển chi phí tới nơi nó ít đau nhất.
