8 ms·

As someone who ran IRC servers in the 90s the technical limitation was the number of file descriptors. I think Linux at the time was limited to 1024 and the big

As someone who ran IRC servers in the 90s the technical limitation was the number of file descriptors. I think Linux at the time was limited to 1024 and the biggest server on our network was a DEC Alpha with 4096. The entire network (DALnet at the time) was in the 20-30k user range so we absolutely needed multiple servers.

blibble 5y ago
there was also no efficient io multiplexing an ircd with a few thousand clients was cpu bound on poll()/select() /dev/poll and kqueue/epoll were game changing
- jlokier 5y ago
  It was actually possible to delegate subsets of descriptors to child processes doing the poll()/select(), making polling have the same time complexity as /dev/poll and kqueue/epoll, and avoid being CPU bound. Even better if you delegated cold subsets, and kept a hot subset in the main process. But few knew the trick so it didn't catch on.
  - blibble 5y ago
    mind explaining how? with poll()/select() I don't see how you can avoid checking every FD at least once (poll's fd counter aside), vs. epoll() only returning those in the desired state (and I don't think you could do tricks like epoll_wait() on an epoll fd)
    - jlokier 5y ago
      Sure. Fork some child processes, and keep an AF_UNIX socketpair() open to them so you can pass them file descriptiors with SCM_RIGHTS. Have the main process divide up the fds it is waiting on into a "hot" subset and cold subsets of size at most N, and for each cold subset pick a child process P. fds can be moved between hot and cold at any time, and generally you will move them to hot after they have woken and been used, and move them to cold after a few consecutive poll-cycles where they were not ready. Don't move fds to cold subsets belonging to child processes that you don't want to wake, though. When the main process is ready to "poll everything", have it iterate over each child process that is not already sleeping, and send a message over the socketpair(), containing a list of fd_set additions and removals to that child's wait-for subset, including the type of poll (read, write, etc). For each fd where the child doesn't have the real file descriptor yet, pass that over the socketpair() as part of the message. (If threads are usable instead of processes, there's no need to send the file descriptor. But on old systems, the system threads were often implemented by userspace multiplexing with poll/select anyway, so it wasn't a good idea to use threads with this technique.) As well as a list of changes, this message tells the child process to run poll/select on its subset, and then reply with the set of fds that are ready (and their readiness type). After issuing all the child process messages, the main process does its own poll/select, to wait for hot fds and replies from the child processes. The reason this has different scaling properties, despite the overheads, is that each child handles a limited size subset, messages scale with the amount of change activity not the size of sets, and ideally the "coldest" fds end up gathered together in child processes that continue to sleep between a large number of main process polls, so the number of active child processes and messages scales with the amount of change activity as well. Keep in mind, even active fds are removed from the wait-for subset if they've recently reported they are ready and the poll loop hasn't read/written them yet. So it has similar algorithmic properties to epoll. As a bonus in the case of select(), the fds in the child processes have smaller values than in the main process. So in addition to the number of fds polled per cycle scaling with the amount of activity instead of the total number of fds, the fd_set bitset size does not grow with the total number of fds either. In the main process the bitset size does grow, but it's possible to juggle fd values with dup2() to overcome that.
      - blibble 5y ago
        thank you for the detailed response that is indeed clever and I agree would practically improve the performance drastically for many (most?) workloads worst case scenario (say all your sockets have a approximately the same chance of waking up): the behaviour devolves into the same as for poll() though? as a broadcast medium: IRC has some annoying qualities in this regard (inline PINGs at regular intervals, events visible by nearly all that trigger socket avalanches, etc)
        jlokier 5y ago
        It does not devolve into poll() scaling behaviour, even in your uniform probability scenario. To picture it, maybe it helps to consider low and high uniform probabilities. If the uniform probability is a low enough per wait call, epoll/kqueue/etc have low cost per wait call, but so does this child-select method, because most child processes don't wake on each wait call. If the uniform probability is high enough, epoll/kqueue/etc return most of the fds, scaling just like the cost of select/poll, and child-select. So epoll/kqueue/etc and child-select match at the extremes, modulo constant factors. In general, with a constant-bounded subset size, you can say the cost of unnecessary fd polls is amortised over the necessary fd polls, because unnecessary fd polls only occur in child processes that wake due to a necessary fd poll. So the algorithmic big-O scaling of this method is still the same as epoll/kqueue/etc as the number of fds increases and the probability varies, whether it's uniform or non-uniform. No guarantees about the constant factors, though. You'd still want to tune parameters, to have enough and not too many in each subset. Constant-bounded subset size ensures scaling but not necessarily optimal performance. You can relax the constant bound and still keep the worst-case big-O scaling, if it's adaptive in the right sort of way, to better handle non-uniform probabilities with fewer processes.
        blibble 5y ago
        yes I see now, thanks
throwaway20371 5y ago
I'm pretty sure even back then you could edit the hard-coded limit in the source code and recompile. I remember us doing something like this as it was too expensive to just keep buying servers and our apps were connection-happy.
- wayoutthere 5y ago
  1024 was the max you could boost it to; 256 was the default as I recall. Linux 1.x was pretty bootstrappy.
- NovemberWhiskey 5y ago
  I recall going down this rabbit hole about fifteen years ago. It is, in principle, possible but you're going to be recompiling everything that could conceivably use an fd_set (so probably every single piece of code that links libc...) because it's a fixed size buffer that scales with FD_SETSIZE.
  - wayoutthere 5y ago
    This was actually less of a problem than it seems in hindsight — back at that time, package managers were relatively new and not often used as were dynamic libraries, so most things were just static binaries compiled from tarballs.
    - NovemberWhiskey 5y ago
      I know 15 years ago feels like it ought to be back in the dimly-veiled prehistory of Linux but actually we were on RHEL4, which was released in 2005.
      - wayoutthere 5y ago
        Really? Thought they bumped it in the late 90s. I was running IRC servers mostly in the 1995-2000 timeframe and I remember the connection limit going away at one point? It’s been ages, but I largely quit using IRC once I went to college so it had to be sometime around the late 90s :) Every network also seemed to have its own fork of ircd (and at least one rewrote it from scratch), so could have just been that the ones I used patched it in and others didn’t.

blibble 5y ago

there was also no efficient io multiplexing an ircd with a few thousand clients was cpu bound on poll()/select() /dev/poll and kqueue/epoll were game changing

jlokier 5y ago
It was actually possible to delegate subsets of descriptors to child processes doing the poll()/select(), making polling have the same time complexity as /dev/poll and kqueue/epoll, and avoid being CPU bound. Even better if you delegated cold subsets, and kept a hot subset in the main process. But few knew the trick so it didn't catch on.
- blibble 5y ago
  mind explaining how? with poll()/select() I don't see how you can avoid checking every FD at least once (poll's fd counter aside), vs. epoll() only returning those in the desired state (and I don't think you could do tricks like epoll_wait() on an epoll fd)
  - jlokier 5y ago
    Sure. Fork some child processes, and keep an AF_UNIX socketpair() open to them so you can pass them file descriptiors with SCM_RIGHTS. Have the main process divide up the fds it is waiting on into a "hot" subset and cold subsets of size at most N, and for each cold subset pick a child process P. fds can be moved between hot and cold at any time, and generally you will move them to hot after they have woken and been used, and move them to cold after a few consecutive poll-cycles where they were not ready. Don't move fds to cold subsets belonging to child processes that you don't want to wake, though. When the main process is ready to "poll everything", have it iterate over each child process that is not already sleeping, and send a message over the socketpair(), containing a list of fd_set additions and removals to that child's wait-for subset, including the type of poll (read, write, etc). For each fd where the child doesn't have the real file descriptor yet, pass that over the socketpair() as part of the message. (If threads are usable instead of processes, there's no need to send the file descriptor. But on old systems, the system threads were often implemented by userspace multiplexing with poll/select anyway, so it wasn't a good idea to use threads with this technique.) As well as a list of changes, this message tells the child process to run poll/select on its subset, and then reply with the set of fds that are ready (and their readiness type). After issuing all the child process messages, the main process does its own poll/select, to wait for hot fds and replies from the child processes. The reason this has different scaling properties, despite the overheads, is that each child handles a limited size subset, messages scale with the amount of change activity not the size of sets, and ideally the "coldest" fds end up gathered together in child processes that continue to sleep between a large number of main process polls, so the number of active child processes and messages scales with the amount of change activity as well. Keep in mind, even active fds are removed from the wait-for subset if they've recently reported they are ready and the poll loop hasn't read/written them yet. So it has similar algorithmic properties to epoll. As a bonus in the case of select(), the fds in the child processes have smaller values than in the main process. So in addition to the number of fds polled per cycle scaling with the amount of activity instead of the total number of fds, the fd_set bitset size does not grow with the total number of fds either. In the main process the bitset size does grow, but it's possible to juggle fd values with dup2() to overcome that.
    - blibble 5y ago
      thank you for the detailed response that is indeed clever and I agree would practically improve the performance drastically for many (most?) workloads worst case scenario (say all your sockets have a approximately the same chance of waking up): the behaviour devolves into the same as for poll() though? as a broadcast medium: IRC has some annoying qualities in this regard (inline PINGs at regular intervals, events visible by nearly all that trigger socket avalanches, etc)
      - jlokier 5y ago
        It does not devolve into poll() scaling behaviour, even in your uniform probability scenario. To picture it, maybe it helps to consider low and high uniform probabilities. If the uniform probability is a low enough per wait call, epoll/kqueue/etc have low cost per wait call, but so does this child-select method, because most child processes don't wake on each wait call. If the uniform probability is high enough, epoll/kqueue/etc return most of the fds, scaling just like the cost of select/poll, and child-select. So epoll/kqueue/etc and child-select match at the extremes, modulo constant factors. In general, with a constant-bounded subset size, you can say the cost of unnecessary fd polls is amortised over the necessary fd polls, because unnecessary fd polls only occur in child processes that wake due to a necessary fd poll. So the algorithmic big-O scaling of this method is still the same as epoll/kqueue/etc as the number of fds increases and the probability varies, whether it's uniform or non-uniform. No guarantees about the constant factors, though. You'd still want to tune parameters, to have enough and not too many in each subset. Constant-bounded subset size ensures scaling but not necessarily optimal performance. You can relax the constant bound and still keep the worst-case big-O scaling, if it's adaptive in the right sort of way, to better handle non-uniform probabilities with fewer processes.
        blibble 5y ago
        yes I see now, thanks

throwaway20371 5y ago

I'm pretty sure even back then you could edit the hard-coded limit in the source code and recompile. I remember us doing something like this as it was too expensive to just keep buying servers and our apps were connection-happy.

wayoutthere 5y ago
1024 was the max you could boost it to; 256 was the default as I recall. Linux 1.x was pretty bootstrappy.
NovemberWhiskey 5y ago
I recall going down this rabbit hole about fifteen years ago. It is, in principle, possible but you're going to be recompiling everything that could conceivably use an fd_set (so probably every single piece of code that links libc...) because it's a fixed size buffer that scales with FD_SETSIZE.
- wayoutthere 5y ago
  This was actually less of a problem than it seems in hindsight — back at that time, package managers were relatively new and not often used as were dynamic libraries, so most things were just static binaries compiled from tarballs.
  - NovemberWhiskey 5y ago
    I know 15 years ago feels like it ought to be back in the dimly-veiled prehistory of Linux but actually we were on RHEL4, which was released in 2005.
    - wayoutthere 5y ago
      Really? Thought they bumped it in the late 90s. I was running IRC servers mostly in the 1995-2000 timeframe and I remember the connection limit going away at one point? It’s been ages, but I largely quit using IRC once I went to college so it had to be sometime around the late 90s :) Every network also seemed to have its own fork of ircd (and at least one rewrote it from scratch), so could have just been that the ones I used patched it in and others didn’t.