Ở 10.000 kết nối, epoll nhanh gấp 1.540 lần poll — vì một cái là O(N), cái kia O(1)

Hình dung một lớp học 10.000 người và bạn cần biết ai đang cần giúp. Cách cũ: cứ vài phút, bạn đọc to cả danh sách 10.000 cái tên, gọi từng người "có cần gì không?", đánh dấu — làm lại từ đầu mỗi lần. Cách mới: ai cần giúp thì giơ tay, bạn chỉ liếc qua và thấy ngay mấy cánh tay đang giơ — số người trong lớp là 100 hay 100.000 chẳng ảnh hưởng gì. Cùng một mục tiêu "tìm ai cần giúp", nhưng một cách tốn công tỉ lệ với sĩ số, cách kia gần như không đổi. Đó chính xác là khác biệt giữa poll/select và epoll — và nó quyết định một server chịu được 100 hay 100.000 kết nối.

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 khả năng mở rộng. 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). Đúng cái đọc to cả danh sách 10.000 tên mỗi lầ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. Đúng chỉ liếc mấy cánh tay đang giơ.

Đ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ôi trường đo: container gcc:13 trên host ARM AArch64, N pipe với đúng một fd sẵn, một lần chờ không chặn, mỗi số lấy sau warmup. Con số tuyệt đối đổi theo máy; cái bền vững là hình dạng: poll/select dốc lên tuyến tính, epoll nằm phẳng.)

Hai niềm tin đối nghịch, cùng sai

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. 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.

Nhưng có một niềm tin ngược, sinh ra khi đã biết epoll thắng, cũng sai: "vậy epoll luôn tốt hơn, dùng nó cho mọi thứ, select/poll là đồ bỏ". Nhìn lại cột 100 fd: cả ba đều dưới 2 µs, khác biệt vô hình — và epoll đòi thêm bộ máy (tạo epoll fd, epoll_ctl đăng ký từng fd, quản lý vòng đời), lại chỉ có trên Linux. Với một client chờ vài fd, một công cụ nhỏ, hay code cần chạy đa nền tảng, poll đơn giản hơn và nhanh ngang epoll ở quy mô đó — kéo epoll vào là phức tạp hóa sớm mà chẳng lợi gì. Sự thật nằm ở giữa: O(N) vs O(1) chỉ tách bạch khi N lớn; chọn theo quy mô thật, đừng theo "cái nào nghe oách hơn". Đâ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 — nhưng cũng vô nghĩa nếu bạn không bao giờ chạm quy mô đó.

Về đến code hằng ngày

Điều đầ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 dựng trên. Đây là "vấn đề C10k" nổi tiếng — và epoll là câu trả lời.

Điều 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, select/poll đơn giản hơn và nhanh ngang epoll ở quy mô đó. epoll đáng cái phức tạp thêm chỉ khi số fd đủ lớn. Chọn theo quy mô thật của bạn.

Chỗ này gần như mọi thứ "nhiều kết nối" bạn dùng đều đứng trên đúng phép đo trên, thường ẩn kỹ. Selector của Java NIO là epoll dưới nền trên Linux; Netty còn có hẳn EpollEventLoop riêng (bỏ qua lớp NIO) để ép sát hiệu năng, và benchmark của họ cho thấy nó thắng NioEventLoop ở kết nối cao đúng vì lý do này. Node.js (libuv), nginx, Redis (event loop ae), HAProxy — tất cả chuyển sang epoll/kqueue chính là để giải C10k. Và cái giới hạn FD_SETSIZE 1024 của select là lý do lịch sử khiến nhiều phần mềm cũ "chết" ở đúng ~1000 kết nối cho tới khi viết lại bằng epoll. Không ai chọn epoll vì API đẹp — họ chọn vì O(1) thay O(N) là ranh giới mở-rộng-được. Cùng một bài học giơ-tay-thay-vì-điểm-danh, ở mọi tầng server.

Muốn tự thấy thì 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. Vài phút 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.