Mọi chương trình đa luồng đều dùng mutex (khóa) để bảo vệ dữ liệu chung. Có một niềm tin phổ biến rằng khóa "đắt" — rằng mỗi lock/unlock là một chuyến đi vào nhân. Nếu đúng vậy thì một vòng lặp khóa hàng triệu lần sẽ tốn hàng triệu lời gọi hệ thống. Tôi đo trong container để xem chi phí thật của một mutex, và strace cho tôi một con số làm sụp đổ mô hình tôi vẫn tin.
Mutex đứng trên cái gì
Trên Linux, pthread_mutex_t được xây trên một cơ chế của nhân tên là futex — viết tắt của fast userspace mutex, "mutex nhanh ở không gian người dùng". Cái tên đã nói hết ý tưởng: phần lớn công việc xảy ra trong user-space, không phải trong nhân.
Cụ thể, trạng thái của một mutex chỉ là một biến số nguyên nằm trong bộ nhớ tiến trình của bạn: một giá trị nghĩa là "đang rảnh", giá trị khác nghĩa là "đang bị giữ". Khi bạn lock một mutex đang rảnh, thư viện chỉ thực hiện một lệnh atomic — một phép so-sánh-và-đổi (compare-and-swap, CAS) trên biến đó, ngay trong user-space, đổi nó từ "rảnh" sang "bị giữ". Không có syscall nào cả. unlock cũng vậy: một lệnh atomic đổi lại về "rảnh".
Nhân chỉ vào cuộc trong một trường hợp: khi bạn muốn khóa mà nó đang bị luồng khác giữ. Lúc đó bạn không thể tiếp tục, phải ngủ chờ — và ngủ là việc chỉ nhân làm được. Thư viện gọi syscall futex(FUTEX_WAIT) để nhờ nhân cho luồng ngủ cho tới khi khóa được thả. Bên kia, khi luồng đang giữ khóa unlock và thấy có người đang chờ, nó gọi futex(FUTEX_WAKE) để nhân đánh thức người chờ dậy. Không tranh chấp thì không ai phải ngủ, và nhân không hề bị đụng tới.
Đo: rảnh thì gần như miễn phí, tranh chấp thì đắt
Tôi đo chi phí một cặp lock/unlock trong hai tình huống, ghim luồng vào lõi cụ thể:
| Trường hợp | Chi phí mỗi thao tác |
|---|---|
| Không tranh chấp (1 luồng) | 3,4 ns |
| Có tranh chấp (2 luồng, 2 lõi) | 46,0 ns |
Khóa không tranh chấp tốn 3,4 nano giây — cỡ vài lệnh CPU, đúng như một phép atomic đơn lẻ. Khi hai luồng trên hai lõi tranh nhau cùng một khóa, chi phí nhảy lên 46 nano giây, chậm hơn 13,5 lần. Nhưng con số thật sự làm tôi giật mình không phải hai số này, mà là bằng chứng strace đằng sau chúng.
Một lần tôi đo hớ: 2 triệu lần khóa, 0 lệnh futex
Tôi vào bài với niềm tin "mutex là đối tượng của nhân, mỗi lock/unlock là một syscall". Để chứng minh, tôi định strace một vòng lặp khóa nhiều lần và chỉ vào con số futex khổng lồ mà nói "đấy, mỗi lần khóa một syscall". Tôi chạy 2 triệu lần lock/unlock trên một luồng và đếm số lệnh futex:
strace -e trace=futex : 0 lệnh futex cho 2.000.000 lần khóa
Không một lệnh nào. Mô hình của tôi sai hoàn toàn. Hai triệu lần khóa mà nhân không hề được gọi tới, vì không có tranh chấp — mỗi lần khóa chỉ là một lệnh atomic trong user-space. Cái tên "futex = fast userspace mutex" nói đúng điều đó, mà tôi đã bỏ ngoài tai.
Rồi tôi đo trường hợp có tranh chấp — hai luồng cùng đập vào một khóa 2 triệu lần — và đếm lại:
strace -e trace=futex : 594 lệnh futex cho 2.000.000 lần khóa
Ngay cả khi tranh chấp, chỉ 594 lời gọi futex cho hai triệu lần khóa — tức khoảng 0,03%. Nghĩa là kể cả lúc tranh nhau, 99,97% số lần khóa vẫn được xử lý bằng lệnh atomic trong user-space; nhân chỉ bị gọi trong số ít lần một luồng thật sự phải ngủ hoặc phải đánh thức người khác. Chi phí 46 ns của trường hợp tranh chấp phần lớn không phải từ syscall, mà từ cache nảy qua nảy lại giữa hai lõi khi chúng giành cùng một dòng bộ nhớ chứa biến khóa.
Bài học đo lường: đừng đoán mô hình chi phí — hãy đo nó. Tôi đã tin chắc "khóa = syscall" và suýt viết cả một bài dựa trên niềm tin đó; một lệnh strace đếm syscall thật đã lật ngược nó. "Khóa đắt" chỉ đúng khi có tranh chấp thật; khóa không tranh chấp gần như miễn phí, và cái đắt khi tranh chấp cũng không nằm ở chỗ tôi tưởng (syscall) mà ở tương tranh cache giữa các lõi.
Vì sao chỉ 594 lần chứ không phải hàng nghìn
Con số 594 lệnh futex cho hai triệu lần khóa có tranh chấp đáng để dừng lại ngẫm. Nếu mỗi lần một luồng thấy khóa bận đều lập tức ngủ, ta đã thấy hàng trăm nghìn lệnh futex. Sở dĩ ít như vậy là vì thư viện pthread khôn hơn thế: khi gặp khóa bận, nó quay tại chỗ (spin) một lúc ngắn — thử lại lệnh atomic vài vòng — với hy vọng luồng kia thả khóa trong tích tắc. Rất thường là vậy (vùng găng ở đây chỉ là một phép shared++), nên luồng chờ giành được khóa mà không cần ngủ, không cần vào nhân. Chỉ khi quay một lúc mà vẫn không được, nó mới chịu gọi futex để ngủ. Đây là chiến lược hai pha — quay ngắn rồi mới ngủ — cân bằng giữa "ngủ ngay thì tốn syscall" và "quay mãi thì đốt CPU vô ích". Nó cũng giải thích vì sao vùng găng ngắn ít khi phải trả giá syscall dù bị tranh chấp: luồng chờ chỉ cần nhịn vài chục nano giây là tới lượt.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng sợ khóa tới mức né tránh nó một cách mù quáng. Vì khóa không tranh chấp chỉ tốn vài nano giây, việc bọc một đoạn code ngắn bằng mutex trong đường đi ít tranh chấp gần như không tốn gì. Những "tối ưu" phức tạp để bỏ khóa (lock-free) thường chỉ đáng khi khóa thật sự là điểm nóng có tranh chấp cao — mà điều đó phải đo mới biết, không phải đoán. Tối ưu một cái khóa 3,4 ns là phí công.
Hệ quả thứ hai: cái thật sự đắt là tranh chấp, và nó tệ đi theo số lõi. Khi nhiều luồng trên nhiều lõi cùng giành một khóa, bạn trả hai giá: cache nảy giữa các lõi (giá này có ngay cả khi chưa ai phải ngủ) và thỉnh thoảng một chuyến vào nhân để ngủ/đánh thức. Đây là lý do một khóa "nóng" bảo vệ một vùng găng lớn có thể giết chết khả năng mở rộng: thêm lõi không giúp gì vì tất cả xếp hàng sau một khóa, lại còn làm mỗi thao tác đắt hơn vì tranh chấp. Cách chữa là giảm tranh chấp — chia nhỏ khóa, thu hẹp vùng găng, hay dùng dữ liệu cục bộ theo luồng — chứ không phải bỏ khóa cho nhanh mà sai.
Hệ quả thứ ba là bài học đo lường bao trùm: strace là cách nhanh nhất để kiểm một mô hình chi phí trong đầu bạn. Khi bạn nghĩ "thao tác này chắc tốn syscall", hãy đếm thử — câu trả lời thường bất ngờ. Con số mang theo: một mutex không tranh chấp tốn ~3,4 ns và 0 syscall vì nó chỉ là một lệnh atomic trong user-space (futex = fast userspace mutex); nó chỉ gọi futex() vào nhân khi có tranh chấp thật, và ngay cả khi đó cũng chỉ ~0,03% số lần khóa — cái đắt của tranh chấp chủ yếu là cache nảy giữa các lõi, không phải syscall. Khóa không đắt; tranh chấp mới đắt.
Thử ba mươi giây
Viết một chương trình nhỏ khóa và mở một pthread_mutex vài triệu lần trên một luồng, rồi chạy strace -f -e trace=futex -c ./chương-trình. Bạn sẽ thấy bảng đếm syscall trống trơn cho futex — bằng chứng tận mắt rằng khóa không tranh chấp không hề vào nhân. Giờ thêm một luồng thứ hai cùng giành khóa đó và chạy lại: cột futex bắt đầu có số, và bạn thấy chính xác cái ngưỡng mà mutex chuyển từ "lệnh atomic thầm lặng" sang "phải nhờ nhân". Đó là ranh giới giữa khóa rẻ và khóa đắt, hiện ra thành con số ngay trước mắt.
