Ở thread pool ta cho các worker lấy việc từ một hàng đợi chung. Nhưng khi có nhiều worker và việc rất ngắn, cái hàng đợi chung đó — cụ thể là một cái khóa bảo vệ nó — trở thành điểm nóng: mọi worker tranh nhau chính cái khóa ấy để lấy việc. Có một kiến trúc khác giải quyết chuyện này: work stealing (trộm việc), nền tảng của mọi runtime song song hiện đại (Go, Rust, Java ForkJoinPool, Intel TBB). Tôi đo nó so với hàng đợi chung, và phát hiện nó thắng ở hai mặt — nhưng không phải bùa vạn năng.
Hàng đợi chung so với deque riêng
Hàng đợi chung: một hàng đợi, một khóa; N worker cùng lấy việc từ đó. Đơn giản, nhưng cái khóa là điểm nghẽn — mỗi lần lấy một việc phải giành khóa với N-1 worker khác. Work stealing: mỗi worker có một deque (hàng đợi hai đầu) riêng, với khóa riêng. Worker đẩy và lấy việc ở đầu của mình — hầu như không đụng ai. Chỉ khi deque riêng cạn, nó mới đi trộm một việc từ đuôi deque của một worker khác. Phần lớn thời gian, mỗi worker làm việc trên deque riêng không tranh chấp; việc trộm (có tranh chấp) chỉ xảy ra khi một worker rảnh.
Tôi đo trong container gcc:13 (10 lõi), kiểm checksum để chắc mọi việc chạy đủ.
Đo: scale 4,5 lần, cân bằng 5 lần — nhưng có bẫy
Đầu tiên, throughput với nhiều việc rất ngắn, chia đều, tăng số worker:
NW | hàng đợi chung | work-stealing (triệu việc/giây)
2 | 10,8 | 10,9
4 | 10,1 | 17,0
8 | 5,2 | 13,2
16 | 3,2 | 14,3
Hàng đợi chung sụt khi thêm worker (10,8 → 3,2) — đúng cái scale âm ta đã đo: mọi worker tranh một khóa, khóa đó thành nút cổ chai. Work-stealing thì giữ và tăng (10,9 → 14,3), vì mỗi worker chủ yếu chạm deque riêng. Ở 16 worker, work-stealing đạt throughput gấp 4,5 lần hàng đợi chung.
Tiếp theo, cân bằng tải lệch: dồn toàn bộ việc (mỗi việc ~10 µs) vào deque của một worker, 8 worker:
chia tĩnh (không trộm) : 1363 ms (7 worker ngồi không)
work-stealing (tự san) : 274 ms -> nhanh 5 lần
Chia tĩnh mà việc dồn hết vào một worker thì 7 worker kia ngồi không, worker 0 làm tất cả — 1363 ms. Work-stealing để các worker rảnh đi trộm từ deque của worker 0, tự san đều tải — 274 ms, nhanh 5 lần. Đây là sức mạnh thật của work-stealing: nó không cần biết trước việc phân bố thế nào, kẻ rảnh tự đi tìm việc.
Một lần tôi đo hớ: trộm cũng tốn, không phải bùa
Tôi vào đo với hai niềm tin. Thứ nhất: "một hàng đợi chung là đủ". Sai — nó tranh khóa và sụt throughput khi đông worker. Thứ hai: "chia việc tĩnh đều là tối ưu". Cũng sai khi tải lệch — worker rảnh ngồi không. Cả hai đều được work-stealing giải quyết.
Nhưng đây là chỗ đo hớ thứ ba, tôi vấp trong chính lúc đo: tôi tưởng "work-stealing luôn thắng khi tải lệch". Lần đầu tôi đo với việc tí xíu (sub-µs) dồn hết vào một deque, và work-stealing lại chậm hơn để một worker làm một mình (0,8 lần)! Vì khi việc quá ngắn và dồn hết một chỗ, tất cả worker rảnh cùng lao vào trộm từ đúng một deque — chúng tranh nhau cái khóa của deque nạn nhân, và chi phí tranh chấp đó lớn hơn cả lợi ích song song. Chỉ khi tôi làm việc chunky hơn (~10 µs mỗi việc), lợi ích song song (8 worker cùng làm) mới lấn át chi phí trộm, và work-stealing thắng 5 lần.
Bài học đo lường: không có cấu trúc song song nào là bùa; mỗi cái có chi phí riêng, và cái đó chỉ đáng khi hạt việc đủ lớn để bù. Work-stealing giảm tranh chấp ở trường hợp thường (deque riêng) và tự cân bằng, nhưng bản thân việc trộm là một thao tác có khóa/atomic; nếu hạt việc quá nhỏ, chi phí trộm nuốt hết lợi. Nếu tôi chỉ đo một kích thước việc rồi khái quát, tôi đã kết luận sai theo chiều này hay chiều kia.
Deque của tôi còn có thể tốt hơn
Cần thành thật: bản work-stealing tôi đo dùng một khóa nhỏ cho mỗi deque — đơn giản để viết đúng, và đủ để chứng minh điểm chính (deque riêng giảm tranh chấp so với một hàng đợi chung). Các runtime thật thường dùng một deque lock-free tinh vi hơn (thuật toán Chase-Lev), nơi chủ deque đẩy/lấy bằng thao tác không khóa và chỉ kẻ trộm mới cần một CAS. Điều đó cắt thêm chi phí ở đường thường (chủ deque không cần khóa gì), nhưng cũng chính là loại code lock-free khó viết đúng mà bài hàng đợi không khóa đã cảnh báo. Nên con số 4,5 lần của tôi là cận dưới — một cài đặt tốt hơn còn nới rộng khoảng cách. Bài học phụ, đúng tinh thần đo lường: con số bạn đo phụ thuộc chất lượng cài đặt, nên hãy so sánh công bằng (cùng mức tối ưu) và hiểu rằng một kết quả cụ thể là của cài đặt này, không phải của ý tưởng nói chung.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi có nhiều worker và việc ngắn, tránh một hàng đợi chung duy nhất. Cái khóa của nó thành điểm nóng, và throughput sụt theo số worker thay vì tăng. Chia thành nhiều hàng đợi (mỗi worker/nhóm một hàng) hoặc dùng work-stealing để phần lớn thao tác không tranh chấp — đây là cùng nguyên tắc "giảm chia sẻ ghi" xuyên suốt sê-ri, áp cho hàng đợi việc.
Hệ quả thứ hai: work-stealing là câu trả lời cho tải không biết trước và lệch. Khi bạn không thể chia việc đều từ đầu (việc sinh động, thời lượng mỗi việc khác nhau nhiều), chia tĩnh sẽ để worker rảnh ngồi không. Work-stealing tự cân bằng mà không cần biết trước — lý do các runtime song song (Go scheduler, ForkJoinPool) đều dùng nó. Nhưng nhớ: nó đáng khi hạt việc đủ lớn; với việc siêu nhỏ, cân nhắc gộp việc thành lô lớn hơn trước.
Hệ quả thứ ba là tinh thần đo lường: đo với kích thước việc thật của bạn, đừng khái quát từ một điểm. Con số mang theo: hàng đợi chung tranh một khóa nên sụt khi đông worker (16 worker 3,2 so 10,8 triệu việc/s), work-stealing (deque riêng) scale hơn (4,5 lần ở 16) và tự cân bằng tải lệch (dồn 1 worker: 274 so 1363 ms, nhanh 5 lần); NHƯNG trộm có chi phí — việc tí xíu dồn một chỗ thì mọi kẻ trộm tranh nhau một deque, chậm hơn cả một worker làm (0,8 lần). Work-stealing scale và cân bằng tốt, nhưng chỉ đáng khi hạt việc đủ to.
Thử ba mươi giây
Nghĩ về một tác vụ song song bạn có mà việc phân bố không đều — ví dụ duyệt một cây lệch, hay xử lý các file kích thước rất khác nhau. Nếu bạn chia tĩnh (worker i lấy 1/N việc từ đầu), điều gì xảy ra khi phần của một worker nặng gấp mười lần phần của worker khác? Worker nhẹ xong sớm rồi ngồi không chờ worker nặng — bạn lãng phí phần lớn số lõi ở cuối. Đó chính là chỗ work-stealing (hay đơn giản là một hàng đợi việc chung với hạt đủ to) cứu bạn: kẻ rảnh tự đi tìm việc. Ba mươi giây hình dung kịch bản tải lệch đó cho bạn biết khi nào cân bằng tải động là cần — và nhắc rằng "chia đều từ đầu" chỉ tối ưu khi bạn biết việc đều, điều hiếm khi đúng.
