epoll so với poll

Ở bài cạn file descriptor ta thấy một server có thể theo dõi hàng vạn kết nối cùng lúc. Nhưng theo dõi kiểu gì? Với hàng nghìn socket, server phải liên tục hỏi nhân "cái nào có dữ liệu để đọc?" — và cách hỏi quyết định server đó phục vụ được 100 hay 100.000 kết nối. Bài này đo hai cách hỏi kinh điển, poll và epoll, khi số fd tăng dần — và phát hiện lời giải thích quen thuộc "epoll là O(1)" đúng một nửa, che mất biến số thật.

Hai cách theo dõi nhiều fd

Bài toán gọi là I/O multiplexing: một tiến trình muốn chờ nhiều file descriptor cùng lúc, và được đánh thức khi bất kỳ cái nào sẵn sàng (có dữ liệu để đọc, hay chỗ trống để ghi). Có hai họ cơ chế.

poll (và select) làm theo cách thẳng thắn: mỗi lần gọi, bạn truyền cả danh sách N fd cho nhân; nhân quét qua tất cả N để xem cái nào sẵn sàng rồi trả kết quả. Nghĩa là mỗi lần gọi tốn O(n) — tỉ lệ với tổng số fd theo dõi, dù chỉ một cái có việc. Với 10.000 kết nối, mỗi lần hỏi nhân phải rà 10.000 mục.

epoll đảo cách làm: bạn đăng ký mỗi fd một lần bằng epoll_ctl, và nhân ghi nhớ chúng. Sau đó mỗi lần epoll_wait, nhân chỉ trả về những fd đã sẵn sàng — nó duy trì một danh sách sẵn sàng qua cơ chế callback, không quét lại toàn bộ. Đây là lời giải cho bài toán C10K (phục vụ chục nghìn kết nối đồng thời), và là nền của mọi server hiệu năng cao. Tôi muốn đo chính xác khác biệt này khi N lớn dần.

Đo: poll O(n), epoll gần như phẳng

Tôi tạo N pipe, cho đúng một đầu đọc sẵn sàng (có dữ liệu), rồi đo thời gian mỗi lần gọi poll và epoll_wait khi N tăng:

Con số nói thẳng. poll tăng tuyến tính: gấp 10 lần số fd thì gấp gần 10 lần thời gian — 10.000 fd tốn 247.670 ns (~248 micro giây) mỗi lần gọi. epoll thì gần như phẳng lì: ~130–175 ns bất kể N là 10 hay 10.000. Ở mốc 10.000 fd, epoll nhanh hơn poll khoảng 1.860 lần. Đây chính là lý do các server đời cũ dùng select/poll sập dưới vài nghìn kết nối, còn nginx hay Node dùng epoll gánh được hàng trăm nghìn: poll trả giá cho mọi kết nối mỗi vòng lặp, epoll thì không.

Một lần tôi đo hớ: epoll không phải O(1), mà là O(số sẵn sàng)

Nhìn cột epoll phẳng lì ~130 ns dù N tăng nghìn lần, tôi kết luận gọn gàng như sách vẫn viết: "epoll là O(1) — chi phí hằng số, không phụ thuộc số fd". Rồi định chốt bài ở đó. Nhưng có một biến tôi đã cố định mà không để ý: trong phép đo trên, luôn chỉ có 1 fd sẵn sàng. Điều gì xảy ra nếu nhiều fd cùng sẵn sàng?

Tôi cố định N = 10.000 và tăng dần số fd sẵn sàng:

1 sẵn sàng     ->    140 ns
100 sẵn sàng   ->    718 ns
1.000 sẵn sàng ->  8.316 ns
10.000 sẵn sàng -> 98.008 ns

Đây là cú lật. epoll_wait trả về danh sách các fd đã sẵn sàng, nên chi phí của nó tỉ lệ với số fd sẵn sàng, không phải hằng số tuyệt đối. Khi chỉ 1 sẵn sàng, nó ~140 ns (trông như O(1)); khi cả 10.000 cùng sẵn sàng, nó tốn 98.008 ns — gấp 700 lần, và tiến gần tới poll (~250.000 ns). Vậy epoll không phải O(1), mà là O(số fd sẵn sàng). Cái tôi tưởng là "chi phí hằng số" thực ra là "chỉ trả tiền cho những fd đang có việc".

Bài học đo lường: tôi đã đo một điều kiện (đúng 1 fd sẵn sàng) rồi vội khái quát thành quy luật, giấu mất biến số thật (số fd sẵn sàng). Lợi thế khủng khiếp của epoll không phải phép màu toán học O(1), mà đến từ một giả định về tải: server điển hình theo dõi rất nhiều kết nối nhưng chỉ ít hoạt động tại mỗi thời điểm (phần lớn là keep-alive đang rảnh chờ). Trong ca đó, poll phí công rà mọi kết nối rảnh, còn epoll chỉ chạm những cái thức dậy — thắng ngoạn mục. Nhưng nếu mọi kết nối cùng bận, ưu thế thu hẹp lại. Đo một ca rồi vội dán nhãn "O(1)" là cái bẫy quen thuộc — phải hỏi "hằng số theo biến nào, và mình đã cố định biến nào".

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

Hệ quả đầu tiên là với server nhiều kết nối, dùng epoll (hay cơ chế tương đương) là bắt buộc, không phải tùy chọn. Nếu bạn viết một server phải giữ hàng nghìn kết nối đồng thời (đa phần rảnh — WebSocket, long-polling, keep-alive), poll/select sẽ giết hiệu năng vì mỗi vòng lặp trả giá O(n) cho cả những kết nối im lìm. May là hầu hết runtime hiện đại đã dùng epoll dưới nắp (libuv của Node, netpoller của Go, asyncio của Python, Netty của Java), nên bạn hưởng lợi mà không phải gọi epoll_ctl trực tiếp — nhưng hiểu vì sao chúng nhanh giúp bạn không vô tình phá vỡ nó.

Hệ quả thứ hai là epoll không phải luôn thắng — với ít fd, poll/select đơn giản hơn và ngang ngửa. Phép đo cho thấy ở N nhỏ (10 fd), epoll chỉ nhỉnh hơn poll một chút, và epoll còn tốn thêm chi phí đăng ký mỗi fd (epoll_ctl) cùng một fd riêng cho chính epoll. Nếu bạn chỉ chờ dăm ba fd, hoặc mở-đóng liên tục các fd khác nhau mỗi vòng (khiến phải đăng ký lại), poll gọn gàng hơn và không thua kém. Chọn công cụ theo quy mô, đừng mặc định "epoll vì nghe nói nhanh".

Hệ quả thứ ba, về đo lường: một chi phí "hằng số" luôn hằng số theo một biến cụ thể — phải biết mình đã cố định biến nào. Con số mang theo: theo dõi N fd, poll tốn O(n) (10.000 fd = ~248 micro giây mỗi lần gọi) còn epoll gần như phẳng (~130 ns) khi ít fd sẵn sàng — nhanh gấp ~1860 lần; nhưng epoll thực chất là O(số fd SẴN SÀNG), không phải O(1), nên khi mọi fd cùng bận thì chi phí epoll cũng tăng và tiến gần poll. Ưu thế của epoll là "chỉ trả tiền cho cái đang có việc", một giả định đúng với server điển hình nhưng không phải luật toán học vô điều kiện.

Thử ba mươi giây

Xem một server đang dùng cơ chế nào: strace -c -e trace=epoll_wait,poll,select -p <pid> trong lúc nó xử lý tải — nếu thấy epoll_wait, nó đang dùng cách co giãn tốt; nếu thấy poll/select với số fd lớn, đó có thể là nút thắt ở quy mô cao. Đếm số fd một tiến trình đang theo dõi: ls /proc/<pid>/fd | wc -l. Muốn cảm nhận khác biệt, hình dung một vòng lặp server: với poll, mỗi vòng nhân rà tất cả kết nối kể cả đứa đang ngủ; với epoll, nhân đưa thẳng danh sách đứa vừa thức. Ở 10 kết nối, khác biệt không đáng kể; ở 10.000 với 9.999 đang rảnh, đó là khác biệt giữa 248 micro giây và 130 nano giây mỗi vòng — đúng cái bài này đo.