epoll: The API that powers the modern internet (2022)
darkcoding.net
darkcoding.net
On Windows there's IOCP, on Mac and BSD-derivates there's kqueue, and Linux has epoll, but to a first approximation they all do basically the same thing; instead of giving you a full-sized array of "active or not" results that you have to iterate across to detect activity on each of your sockets (as you get from the standard berkeley sockets 'select' and 'poll' APIs), they only inform you about the sockets that are actually active, so you can spend less CPU time iterating through that big results array.
I can say from personal experience that when you've got a single server process that's monitoring 25,000 sockets on a Pentium Pro 200mhz box, it makes a huge difference!
I'm a little surprised (and maybe skeptical) that it'd make a noticeable difference for the much smaller number of sockets that your average web server would be using, but.. maybe?
epoll and kqueue really are just edge-triggered select/poll.
However IOCP and the new io_uring are different beasts, they are completion based APIs vs readiness based.
To quickly explain the difference:
readiness based: tell me all sockets that are ready to be read from
completion based: do this, tell me when you are done
The "tell me when you are done" part is usually handled in the form a message on a queue (or ring buffer, hence the name io_uring, with the u being for userspace). Which also generally means really high scalability of submitting tons of tasks and also processing tons of completions.
Completion based APIs are superior IMO and it was always sad to me that Windows had one and Linux didn't so it's awesome Jens Axboe got his hands dirty to implement it. It beats the pants off of libaio, eventfd, epoll and piles of hacks.
Edge-triggered is theoretically less work for the kernel than level-triggered, but requires that your application not be buggy. People tend to either assume "nobody uses edge-triggered" or "everybody uses edge-triggered".
Completion-based is far from trivial; since the memory traffic can happen at any time, the kernel has to consider "what if somebody changes the memory map between the start syscall and the end syscall". It complicates the application too, since now you have to keep ownership of a buffer but you aren't allowed to touch it.
AIX and Solaris apparently also support completion-based APIs, but I've never seen anyone actually run these OSes.
(aside, `poll` is the easiest API to use for just a few file descriptors, and `select` is more flexible than it appears if you ignore the value-based API assumptions and do your own allocation)
Even for reads, there exist plenty of scenarios where you will get short reads despite more data being available by the time you check. Though ... I wonder if deferring that and doing a second pass over all your FDs might be more efficient, since that gives more time for real data to arrive again?
Right, for reads, epoll will happily tell you if there is more data still there. If the read buffer size is reasonable, short reads should not be common. And if the buffer is huge, a trip around the event loop is probably better at that point to avoid starvation of the other events
Perhaps it's just that I cut my teeth on the classic Mac OS and absorbed its way of thinking, but after using its asynchronous, callback-driven IO API, the multithreaded polling/blocking approach dominant in the Unix world felt like a clunky step backward. I've been glad to see a steady shift toward asynchronous state machines as the preferred approach for IO.
I probably agree with that, but curious to know what your reasons are.
Well, that's half the story. The other half is that select/poll is stateless, meaning the application–kernel bridge is flooded with data about which events you are interested in, despite the fact that this set usually doesn't change much between calls.
kqueue and the like are stateful instead: you tell the kernel which events you are interested in and then it remembers that.
Very new to these APIs and their usages.
With the older select() and poll() interfaces, you have to pass the whole set every time you wait. The kernel has to construct individual wait queues for each fd. Epoll is just a more convenient and efficient API, allowing an efficient implementation on the side of the kernel.
And libevent if you want a portable front-end to all of them:
The article makes that clear.
Cool your wits.
> Aside: All of the above work on many operating systems and support API’s other than epoll, which is Linux specific. The Internet is mostly made of Linux, so epoll is the API that matters.
> without BSD’s kqueue (which preceded epoll by two years), we’d really be in trouble because the only alternatives were proprietary (/dev/poll in Solaris 8 and I/O Completion Ports in Windows NT 3.5).
Are you aware that Linux is used e.g. by Google, Microsoft or Amazon? Can there be occasions when they handle more than 5 simultaneous connections per box? Maybe epoll can make a difference for them, no?
Also this specific article is kinda hazy on pointing out epoll's improvements over previous APIs. One half is that event subscriptions are registered/submitted for a period longer than one syscall (which the article kinda-sorta says.) But the other half is that you also have an opaque field (mostly used as pointer) that the kernel returns back to you on event notifications, which removes an extra level of lookup in userspace.
And lastly, FreeBSD has in the meantime acquired epoll support, and Linux is moving to the next-yet-again replacement in io_uring (which calling an epoll/poll replacement is an insult, it does much more.)
Yes, at least this time they support true async disk IO, which epoll doesn't.
and `SO_REUSEPORT` is safe if you're using a fixed thread pool; it only fails if you use a variable-size thread pool or if you're using multiple processes and one dies (though frankly, if a process dies, you're going to lose something anyway).
The "but what if I `fork` and `close`" problem is purely theoretical I'm pretty sure.
It's an easy read and highly recommended! I think we can learn a lot by immersing ourselves in how good APIs are designed.
They allow you to handle heterogenous events inside that same loop, reducing the usage of threads.
For async disk IO, io_uring is the way to go.
As a lot of complication and issues seem to be around sequencing and the adhoc language, hopefully the community will eventually settle on using eBPF for all programming within io_uring [1].
https://github.com/tornadoweb/tornado/blob/branch4.5/tornado...
(Had to be in 4.5 because the newer versions 5.x and 6.x, it's switched to Python's stdlib asyncio)
Not to negate all the goodies that has given us
tldr: you create a bunch of processes, each of them creates its own socket (bound to the same local port) and processes requests. The kernel split incoming connections amongst the processes.
The issue: "short" and "long" requests are managed in the same way, so one process could be overloaded by "long" requests. There is no feedback loop, as far as I know.
Also, he does not speak about SCM_RIGHTS (https://man7.org/linux/man-pages/man7/unix.7.html), which may be replaced by the newer pidfd_getfd (https://man7.org/linux/man-pages/man2/pidfd_getfd.2.html)
tldr: you can pass a file descriptor between processes. So an overloaded process could pass some work to another worker.
Epoll is a great component, yet it will not give you billions of qps alone
They do. Look for "Correct Solution" further down.
Both APIs allow you to associate arbitrary data (a `void *` in kqueue, or a union of `int/uin32_t/uint65_/void *` in epoll) with the event that you're registering. So when you're notified of the event, you can access this data. In my case, it's a big Conn struct. It contains things like the # of requests on this connection (to enforce a configured max request per connection), a timestamp where it should timeout if there's no activity. The Conn is part of an intrusive linked list, so it has a next: *Conn and prev: *Conn. But, what you're probably most curious about, is that it has a Request.State. This has a static buffer ([]u8) that can grow as needed to hold all the received data up until that point (or if we're writing the data, then the buffered data that we have to write). It's important to have a max # of connections and a max request size so you can enforce an upper limit on the maximum memory the library might use. It acts as a state machine to track up to what point it's parsed the request. (since you don't want to have to re-parse the entire request as more bytes trickle in).
It's all half-baked. I can do receiving/sending asynchronously, but the application handler is called synchronously, and if that, for example, calls PG, that's probably also synchronous (since there's no async PG library in Zig). Makes me feel that any modern language needs a cohensive (as in standard library, or de facto standard) concurrency story.
I wasn't aware that you could store a reference when you register an fd with epoll. I have used select and poll in the past, and you'd need to maintain a mapping of fd->structure somehow, and you know C doesn't come with a handy data structure like a map to make this efficient and easy when scaling to say 100k+ fds. So being able to store and retrieve a reference is incredibly useful.
How do you handle the application handler code, would you run that in a separate thread to not block handling of other fds?
I considered what you're suggesting: having a threadpool to dispatch application handlers on. It's obviously better. But you do have to synchronize a little more, especially if you don't trust the client. While dispatched, the client shouldn't be able to send another request, so you need to remove the READ notification for the socket and then once the response is written, re-add it. Seemed a bit tedious considering I'm hoping to throw it all out when async is re-added as a first class citizen to the language.
The main benefit of my half-baked solution is that a slow or misbehaving connection won't slow (or block!) other connections. Application latency is an issue (since the worker can't processed more requests while the application handler is executing), but at least that's not open to an attack.
There's plenty of map like things available; not in the language standard, but in libcs or os includes, but fds are ints, and kernel APIs that return 'new' fds are contracted to return you the least numerical fd that isn't currently in use... So you can set a max fds (the OS will tell you if you ask), and set an array of that size.
> Do you need to keep custom structures for each network socket that maintains a snapshot of the state of how things are progressing?
Yup.
Everything is a callback and you dispatch those from your event loop. You're managing/implementing your own closures by (manually/explicitly) throwing all necessary data into some data structure (essentially the "async" part). Then make appropriate callback registration calls and return from your code (equivalent to "await").
There is potential for bugs if you try to be "clever" with partially parsing the buffer before all the message's data is received, but this is still far simpler than the kind of bugs we get with async/await.
From there it's just choosing a function to dispatch to based upon epoll event and being exceptionally careful to always use non blocking IO on the underlying fd.
That's one way of doing it.
Ideally, you track state for every connection (you need to do this even with async/await, it's just you need to be explicit) and you dispatch even handling to a thread pool using a command queue. One thread is your demultiplexor calling epoll/kqueue/MsgReceive/waitflor and all your other threads are workers in a pool, and communication is through a synchronized queue.
It's not fancy. It's low overhead and fairly easy to reason about.
In C, yes.
It starts with a simple single-request-at-a-time HTTP server implemented in Rust, then progresses to examples with multi-threading, non-blocking, epoll-based multiplexing, futures and async/await, showing the limitations and advantages at each step.
Previous discussion: https://news.ycombinator.com/item?id=37176960
Linux is also somewhat unique, because most of the Internet, basically, you could say all of the Internet with a bit of hand-waving runs on Linux. So, even if other OSes have asynchronous I/O it doesn't affect the Internet.
In contrast io_uring is a completion notification API. You give it a buffer to read or write from/to, and it'll notify you when the IO has been completed.
Io_uring is also more flexible, and can for example be used for disk IO which epoll can't.