Hàng đợi không khóa

"Lock-free" (không khóa) là một từ đầy hào quang trong lập trình đồng thời. Một cấu trúc dữ liệu lock-free đồng bộ bằng các thao tác atomic thay vì mutex — không luồng nào phải ngủ chờ, không có deadlock. Nghe như luôn nhanh hơn dùng khóa. Hàng đợi lock-free là ví dụ kinh điển, được ca ngợi và cũng bị sùng bái quá mức. Tôi đo hai loại hàng đợi lock-free so với hàng đợi có mutex, và phát hiện chữ "luôn" trong "luôn nhanh hơn" là sai.

SPSC: nơi lock-free thật sự tỏa sáng

Trường hợp đơn giản và đẹp nhất là SPSC — một producer, một consumer — dùng một ring buffer (bộ đệm vòng). Producer chỉ ghi vào chỉ số tail; consumer chỉ ghi vào chỉ số head. Điểm mấu chốt: hai bên ghi vào hai biến khác nhau, không ai ghi đè lên biến của ai. Không có ghi chung, nên không có tranh chấp thật — chỉ cần vài thao tác atomic nhẹ (acquire/release) để đảm bảo thứ tự nhìn thấy. Không khóa, không ngủ, không đợi.

Tôi đo trong container gcc:13: một producer đẩy 20 triệu phần tử, một consumer lấy hết, so ring buffer lock-free với một hàng đợi bảo vệ bằng mutex.

SPSC lock-free ring : 32,1 triệu op/giây
SPSC mutex queue    : 10,6 triệu op/giây   -> lock-free nhanh 3,0 lần

Lock-free nhanh gấp 3 lần. Đúng như hứa hẹn: vì không có ghi chung để tranh chấp, mỗi bên chạy gần như độc lập, còn phiên bản mutex phải khóa/mở khóa trên mỗi phần tử và hai luồng còn giành chính cái mutex đó. Đây là ca lock-free tỏa sáng thật sự.

Nhiều producer: lock-free đụng tường

Nhưng SPSC là trường hợp dễ — chỉ một người ghi mỗi chỉ số. Điều gì xảy ra khi nhiều producer cùng đẩy vào một hàng đợi? Giờ tất cả phải cùng cập nhật một chỉ số tail chung (bằng fetch_add hoặc một vòng CAS để giành chỗ), và ta quay lại đúng bài toán chia sẻ ghi. Tôi đo 1 đến 8 producer cùng đẩy vào một hàng đợi:

T=1 producer : lock-free 599 | mutex 246 | 2,43×
T=2 producer : lock-free 239 | mutex 94  | 2,55×
T=4 producer : lock-free 155 | mutex 47  | 3,26×
T=8 producer : lock-free 29  | mutex 36  | 0,82×

Ở ít producer (1-4), lock-free vẫn nhanh hơn mutex 2,4-3,3 lần. Nhưng ở 8 producer, lock-free tụt xuống 29 triệu op/giây — chậm hơn mutex (36). Tỉ lệ 0,82× nghĩa là lock-free đã thua. Vì cái chỉ số tail chung mà mọi producer cùng ghi trở thành một điểm nóng: dòng cache của nó nảy qua lại giữa 8 lõi, đúng cái cache-line bouncing của atomic tranh chấp ta đã đo. Lock-free không có phép màu nào để tránh vật lý cache coherence; nó chỉ đổi hình dạng của chi phí. Mutex thì xuống dốc duyên dáng hơn (kẻ thua ngủ), nên ở 8 producer nó vượt lên.

Một lần tôi đo hớ: lock-free không phải phép màu

Tôi vào đo với niềm tin phổ biến, gần như một tín điều: "lock-free luôn nhanh hơn có khóa; muốn nhanh thì bỏ mutex đi, dùng cấu trúc lock-free". Đo phá tan chữ "luôn". Lock-free chỉ nhanh khi không có ghi chung tranh chấp — như SPSC, nơi mỗi bên ghi chỉ số riêng. Khi có nhiều luồng cùng ghi một chỗ (nhiều producer vào một hàng đợi), lock-free đụng đúng bức tường cache coherence như mọi cơ chế khác, và ở tải cao còn thua mutex.

Và có một cái giá thứ hai, ẩn hơn nhưng quan trọng không kém: lock-free đổi tốc độ lấy độ phức tạp và rủi ro đúng đắn. Viết một hàng đợi MPMC lock-free đúng là một trong những thứ khó nhất trong lập trình hệ thống — bạn phải xử lý bài toán ABA (một giá trị đổi đi rồi đổi lại khiến CAS tưởng nhầm không có gì xảy ra), chọn đúng memory ordering cho từng thao tác, và giải quyết chuyện thu hồi bộ nhớ an toàn khi không có khóa. Một lỗi tinh vi ở đây tạo ra bug đua tranh chỉ hiện ra một lần trong triệu lần chạy. Một hàng đợi mutex thì đúng một cách hiển nhiên. Bài học đo lường: đừng bị hào quang của một kỹ thuật che mất việc đo cái giá thật của nó — cả giá hiệu năng (chỉ thắng ở đúng hình dạng tải) lẫn giá con người (code khó viết đúng).

Cùng một bức tường, một lần nữa

Điều đáng nhớ là hàng đợi nhiều producer thua ở 8 luồng không phải vì lock-free "kém", mà vì nó đụng đúng bức tường đã xuất hiện suốt sê-ri. Ở mutex bị giành, ở atomic tranh chấp, và ở contention và scaling, gốc rễ luôn là một: nhiều lõi cùng ghi vào một ô nhớ thì dòng cache phải nảy, và không cơ chế đồng bộ nào — khóa hay không khóa — tránh được vật lý đó. Lock-free chỉ dời chi phí từ "ngủ/đánh thức" sang "quay và nảy cache"; ở tải thấp cách dời đó có lời, ở tải cao thì không. Vì thế cách tăng tốc gốc rễ vẫn là giảm chia sẻ ghi (nhiều hàng đợi thay vì một, mỗi luồng một chỗ), chứ không phải đổi khóa sang lock-free. Và như mọi phần, chỉ đo đúng cách ở nhiều mức tải mới cho thấy bạn đang ở bên nào của điểm lật.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: dùng lock-free ở nơi nó thật sự thắng — SPSC và các mẫu không có ghi chung. Một ring buffer SPSC lock-free là công cụ tuyệt vời cho các đường ống một-producer-một-consumer (log, audio, mạng), nơi nó nhanh gấp mấy lần mutex một cách chắc chắn và an toàn (SPSC đủ đơn giản để viết đúng). Đó là chỗ ngọt ngào của lock-free.

Hệ quả thứ hai: với nhiều producer/consumer, đừng mặc định lock-free — đo trước. Một hàng đợi MPMC lock-free có thể nhanh hơn ở tải vừa, nhưng ở tải cao thường không hơn mutex (cùng đụng cache), lại khó viết đúng gấp bội. Thường một hàng đợi mutex đơn giản, hoặc chia thành nhiều hàng đợi (mỗi luồng/nhóm một hàng, giảm chia sẻ), là lựa chọn nhanh và đúng hơn.

Hệ quả thứ ba là tinh thần đo lường: đo cả hiệu năng lẫn độ phức tạp trước khi theo một xu hướng kỹ thuật. Con số mang theo: hàng đợi SPSC lock-free (mỗi bên ghi chỉ số riêng, không tranh chấp thật) nhanh hơn mutex 3 lần (32 so 11 triệu op/s) — lock-free tỏa sáng khi KHÔNG có ghi chung; nhưng nhiều producer cùng đẩy vào một hàng đợi (fetch_add chỉ số chung) thì đụng tường cache nảy, ở 8 producer lock-free lại THUA mutex (29 so 36 op/s); và lock-free đổi tốc độ lấy độ phức tạp cùng rủi ro đúng đắn (ABA, memory ordering). Lock-free không phải "luôn nhanh"; nó nhanh ở đúng hình dạng, và cái giá là code khó — đo cả hai.

Thử ba mươi giây

Nếu bạn có một đường ống một-producer-một-consumer đang dùng một hàng đợi có khóa, thử thay bằng một ring buffer SPSC lock-free (khoảng ba mươi dòng: một mảng, một atomic head, một atomic tail, producer chỉ chạm tail, consumer chỉ chạm head) và đo throughput — bạn rất có thể thấy nó nhanh gấp mấy lần, an toàn. Nhưng nếu bạn định viết một hàng đợi nhiều producer lock-free, hãy dừng lại: đo xem một mutex đơn giản có đủ nhanh cho tải thật của bạn không, vì ở nhiều producer lock-free thường không hơn mà lại mở ra cả một hố sâu ABA và memory ordering. Ba mươi giây đó phân định ranh giới giữa "lock-free là món quà" (SPSC) và "lock-free là cái bẫy" (MPMC dưới tải cao) — và đồng hồ cùng một cái nhìn tỉnh táo về độ phức tạp là thứ vẽ ra ranh giới đó.