Một server phải phục vụ hàng nghìn kết nối cùng lúc bằng một (hay vài) luồng, nên nó cần chờ nhiều socket/pipe cùng một lúc và chỉ xử lý cái nào có dữ liệu. Có ba công cụ để làm việc đó: select, poll, và epoll. Nhìn qua chúng giống nhau — đều "chờ nhiều fd, trả về cái nào sẵn sàng" — nên dễ nghĩ chọn cái nào cũng vậy. Nhưng khác biệt giữa chúng là độ phức tạp thuật toán, và nó quyết định một server chịu được 100 hay 100.000 kết nối. Tôi đo trong container gcc:13 (ARM), tăng số fd từ 100 tới 10.000.
Vì sao select/poll là O(N) còn epoll là O(1)
select và poll hoạt động cùng một kiểu: mỗi lần gọi, bạn đưa cả danh sách N fd cho nhân; nhân quét hết N cái để xem cái nào sẵn sàng, rồi chép kết quả về cho bạn. Nghĩa là mỗi lần chờ tốn công tỉ lệ với N — O(N). Nếu bạn có 10.000 kết nối và chỉ một cái có dữ liệu, nhân vẫn phải kiểm tra cả 10.000 mỗi lần bạn gọi. (select còn tệ hơn: nó giới hạn cứng số fd ở FD_SETSIZE = 1024 — không chờ nổi 10.000.)
epoll tách việc làm hai. epoll_ctl đăng ký các fd bạn quan tâm một lần, và nhân giữ tập theo dõi đó bền qua các lần chờ. epoll_wait thì không cần đưa lại danh sách — nhân đã theo dõi các fd và biết cái nào sẵn, nên nó chỉ trả về những cái sẵn. Chi phí một lần chờ tỉ lệ với số fd sẵn (thường nhỏ), không phải tổng N — gần như O(1) bất kể bạn theo dõi bao nhiêu fd.
Đo: poll bung 100 lần, epoll phẳng
Tôi tạo N pipe, chỉ cho một fd có dữ liệu, đo thời gian một lần chờ (không chặn) qua ba cơ chế khi N tăng:
N fd | select | poll | epoll
100 | 1.814 ns | 1.919 ns | 132 ns
1000 | 23.174 ns | 22.263 ns | 125 ns
10000 | (>1024) | 203.307 ns | 132 ns
poll (và select) tăng tuyến tính theo N: từ ~1,9 µs ở 100 fd lên 203 µs ở 10.000 fd — tức mỗi lần tăng N gấp 10, thời gian cũng gấp ~10. Đúng O(N). Ở 10.000 fd, một lần poll mất 203 µs chỉ để phát hiện một fd sẵn. select thì thậm chí không chạy được với 10.000 fd vì giới hạn FD_SETSIZE 1024.
epoll thì phẳng — ~125-132 ns dù N là 100, 1000, hay 10.000. Số fd theo dõi không ảnh hưởng chi phí một lần chờ. Ở 10.000 fd, epoll (132 ns) nhanh hơn poll (203.307 ns) ~1.540 lần. Đây không phải chênh lệch vi mô — đó là ranh giới giữa một server sập dưới tải và một server chạy mượt. Và chú ý: chi phí O(N) đó trả mỗi vòng lặp sự kiện, tức mỗi khi server thức dậy xử lý — không phải một lần, mà hàng nghìn lần mỗi giây, nên 203µs nhân lên nhanh chóng thành phần lớn thời gian CPU của một server bận.
Một lần tôi đo hớ: không chỉ khác API
Tôi vào đo với ấn tượng mơ hồ: "select, poll, epoll về cơ bản như nhau — cùng chờ nhiều fd, chỉ khác cú pháp API, chọn cái nào quen thì dùng". Phép đo bác bỏ dứt khoát: chúng khác nhau ở độ phức tạp thuật toán, và với nhiều fd, khác biệt là bậc lớn — 1.540 lần ở 10.000 fd.
Bài học đo lường: hai API "làm cùng một việc" có thể có độ phức tạp khác nhau — và độ phức tạp mới quyết định khả năng mở rộng, không phải bề mặt API. select/poll và epoll trông tương đương ở giao diện ("cho tôi các fd sẵn"), nhưng bên dưới, select/poll làm lại O(N) công việc mỗi lần còn epoll amortize việc theo dõi vào một lần đăng ký. Ở quy mô nhỏ (ít fd) sự khác biệt vô hình — 100 fd thì cả ba đều nhanh; đó là lý do người ta dễ tưởng chúng như nhau. Chỉ khi N lớn, sự khác biệt O(N) vs O(1) mới bung ra. Đây là cùng bài học đo ở quy mô thật của sê-ri đồng thời: một khác biệt bị giấu ở quy mô nhỏ có thể là sinh tử ở quy mô lớn — và đó chính là quy mô mà một server thật gặp.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: với nhiều kết nối đồng thời, dùng epoll (hay cơ chế tương đương) — đừng select/poll. Nếu bạn viết một server chịu tải cao (nhiều nghìn kết nối), select/poll sẽ là nút thắt vì chi phí O(N) mỗi vòng lặp sự kiện. epoll (Linux), kqueue (BSD/macOS), IOCP (Windows) là các cơ chế O(1) mà mọi framework hiệu năng cao (nginx, Node.js, Redis, mọi async runtime) dựng trên. Đây là "vấn đề C10k" nổi tiếng — và epoll là câu trả lời.
Hệ quả thứ hai: nhưng với ít fd, select/poll hoàn toàn ổn — đừng phức tạp hóa sớm. Nếu bạn chỉ chờ vài fd (một client, một công cụ nhỏ), select/poll đơn giản hơn và nhanh ngang epoll ở quy mô đó — con số 100 fd cho thấy cả ba đều dưới 2 µs. epoll đáng cái phức tạp thêm (đăng ký, quản lý epoll fd) chỉ khi số fd đủ lớn. Chọn theo quy mô thật của bạn.
Hệ quả thứ ba là tinh thần đo lường: API giống nhau không nghĩa độ phức tạp giống nhau — đo ở quy mô lớn mới thấy. Con số mang theo: select và poll là O(N) — mỗi lần chờ đưa cả danh sách N fd cho nhân để quét, nên chi phí tăng tuyến tính (poll 1,9µs ở 100 fd bung lên 203µs ở 10000 fd), và select còn giới hạn cứng 1024 fd; epoll O(1) — nhân giữ tập theo dõi bền và chỉ trả fd sẵn, nên phẳng ~130ns bất kể N (100 hay 10000), nhanh gấp ~1540 lần poll ở 10000 fd. Ít fd thì cả ba như nhau; nhiều fd (server nhiều kết nối) epoll thắng bậc lớn. Độ phức tạp, không phải bề mặt API, quyết định khả năng mở rộng.
Thử ba mươi giây
Nếu bạn có (hay đọc) code dùng select hoặc poll trong một vòng lặp sự kiện, hỏi: nó chờ bao nhiêu fd? Nếu chỉ vài cái, không sao. Nhưng nếu là một server có thể lên hàng nghìn kết nối, mỗi vòng lặp sự kiện đang trả chi phí O(N) — và ở 10.000 fd đó là ~200 µs mỗi vòng chỉ để tìm fd sẵn, trước cả khi xử lý. Thử ước lượng: server của bạn gọi vòng lặp bao nhiêu lần mỗi giây, nhân với 200 µs — đó là CPU thuần đốt cho việc quét danh sách fd. Ba mươi giây tính đó cho bạn biết vì sao mọi server hiệu năng cao chuyển sang epoll/kqueue: không phải vì API đẹp hơn, mà vì O(1) thay O(N) là khác biệt giữa mở rộng được và không.
