the c10k problem.mht

It s time for web servers to handle ten thousand clients simultaneously, don t you think? After all,

  you are listening for, or to get the list of current events, you call =
kevent()=20
  on the descriptor returned by kqueue(). It can listen not just for =
socket=20
  readiness, but also for plain file readiness, signals, and even for =
I/O=20
  completion.=20
  <P><B>Note:</B> as of October 2000, the threading library on FreeBSD =
does not=20
  interact well with kqueue(); evidently, when kqueue() blocks, the =
entire=20
  process blocks, not just the calling thread.=20
  <P>See <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/doc/Poller_kqueue.html">Poller_kq=
ueue</A>=20
  (<A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_kqueue.cc"=
>cc</A>,=20
  <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_kqueue.h">=
h</A>,=20
  <A =
href=3D"http://www.kegel.com/dkftpbench/Poller_bench.html">benchmarks</A>=
)=20
  for an example of how to use kqueue() interchangeably with many other=20
  readiness notification schemes.=20
  <P>Examples and libraries using kqueue():=20
  <UL>
    <LI><A =
href=3D"http://people.freebsd.org/~dwhite/PyKQueue/">PyKQueue</A> -- a=20
    Python binding for kqueue()=20
    <LI><A href=3D"http://www.monkeys.com/kqueue/echo.c">Ronald F. =
Guilmette's=20
    example echo server</A>; see also <A=20
    =
href=3D"http://groups.yahoo.com/group/freebsd-questions/message/223580">h=
is 28=20
    Sept 2000 post on freebsd.questions</A>. </LI></UL>
  <P></P>
  <LI><A name=3Dnb.epoll><B>epoll</B></A><BR>This is the recommended=20
  edge-triggered poll replacement for the 2.6 Linux kernel.=20
  <P>On 11 July 2001, Davide Libenzi proposed an alternative to realtime =

  signals; his patch provides what he now calls <A=20
  =
href=3D"http://www.xmailserver.org/linux-patches/nio-improve.html">/dev/e=
poll=20
  www.xmailserver.org/linux-patches/nio-improve.html</A>. This is just =
like the=20
  realtime signal readiness notification, but it coalesces redundant =
events, and=20
  has a more efficient scheme for bulk event retrieval.=20
  <P>Epoll was merged into the 2.5 kernel tree as of 2.5.46 after its =
interface=20
  was changed from a special file in /dev to a system call, sys_epoll. A =
patch=20
  for the older version of epoll is available for the 2.4 kernel.=20
  <P>There was a lengthy debate about <A=20
  =
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-kernel&amp;m=3D1036079250=
20720&amp;w=3D2">unifying=20
  epoll, aio, and other event sources</A> on the linux-kernel mailing =
list=20
  around Halloween 2002. It may yet happen, but Davide is concentrating =
on=20
  firming up epoll in general first.=20
  <P></P>
  <LI><A name=3Dnb.kevent>Polyakov's kevent</A> (Linux 2.6+) <A =
name=3Dkevent>News=20
  flash: On 9 Feb 2006, and again on 9 July 2006, Evgeniy Polyakov =
posted=20
  patches which seem to unify epoll and aio; his goal is to support =
network=20
  AIO.</A> See:=20
  <UL>
    <LI><A href=3D"http://lwn.net/Articles/172844/">the LWN article =
about=20
    kevent</A>=20
    <LI><A href=3D"http://lkml.org/lkml/2006/7/9/82">his July =
announcement</A>=20
    <LI><A=20
    =
href=3D"http://tservice.net.ru/~s0mbre/old/?section=3Dprojects&amp;item=3D=
kevent">his=20
    kevent page</A>=20
    <LI><A=20
    =
href=3D"http://tservice.net.ru/~s0mbre/old/?section=3Dprojects&amp;item=3D=
naio">his=20
    naio page</A>=20
    <LI><A=20
    =
href=3D"http://thread.gmane.org/gmane.linux.network/37595/focus=3D37673">=
some=20
    recent discussion</A> </LI></UL>
  <P></P>
  <LI><A name=3Dnb.newni>Drepper's New Network Interface</A> (proposal =
for Linux=20
  2.6+)<BR>At OLS 2006, Ulrich Drepper proposed a new high-speed =
asynchronous=20
  networking API. See:=20
  <UL>
    <LI>his paper, "<A =
href=3D"http://people.redhat.com/drepper/newni.pdf">The=20
    Need for Asynchronous, Zero-Copy Network I/O</A>"=20
    <LI><A =
href=3D"http://people.redhat.com/drepper/newni-slides.pdf">his=20
    slides</A>=20
    <LI><A href=3D"http://lwn.net/Articles/192410/">LWN article from =
July 22</A>=20
    </LI></UL>
  <P></P>
  <LI><A name=3Dnb.sigio><B>Realtime Signals</B></A><BR>This is the =
recommended=20
  edge-triggered poll replacement for the 2.4 Linux kernel.=20
  <P>The 2.4 linux kernel can deliver socket readiness events via a =
particular=20
  realtime signal. Here's how to turn this behavior on: <PRE>/* Mask off =
SIGIO and the signal you want to use. */
sigemptyset(&amp;sigset);
sigaddset(&amp;sigset, signum);
sigaddset(&amp;sigset, SIGIO);
sigprocmask(SIG_BLOCK, &amp;m_sigset, NULL);
/* For each file descriptor, invoke F_SETOWN, F_SETSIG, and set O_ASYNC. =
*/
fcntl(fd, F_SETOWN, (int) getpid());
fcntl(fd, F_SETSIG, signum);
flags =3D fcntl(fd, F_GETFL);
flags |=3D O_NONBLOCK|O_ASYNC;
fcntl(fd, F_SETFL, flags);
</PRE>This sends that signal when a normal I/O function like read() or =
write()=20
  completes. To use this, write a normal poll() outer loop, and inside =
it, after=20
  you've handled all the fd's noticed by poll(), you loop calling <A=20
  =
href=3D"http://www.opengroup.org/onlinepubs/007908799/xsh/sigwaitinfo.htm=
l">sigwaitinfo()</A>.<BR>If=20
  sigwaitinfo or sigtimedwait returns your realtime signal, =
siginfo.si_fd and=20
  siginfo.si_band give almost the same information as pollfd.fd and=20
  pollfd.revents would after a call to poll(), so you handle the i/o, =
and=20
  continue calling sigwaitinfo().<BR>If sigwaitinfo returns a =
traditional SIGIO,=20
  the signal queue overflowed, so you <A=20
  =
href=3D"http://www.cs.helsinki.fi/linux/linux-kernel/Year-1999/1999-41/06=
44.html">flush=20
  the signal queue by temporarily changing the signal handler to =
SIG_DFL</A>,=20
  and break back to the outer poll() loop. <BR>
  <P>See <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/doc/Poller_sigio.html">Poller_sig=
io</A>=20
  (<A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_sigio.cc">=
cc</A>,=20
  <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_sigio.h">h=
</A>)=20
  for an example of how to use rtsignals interchangeably with many other =

  readiness notification schemes.=20
  <P>See <A href=3D"http://www.kegel.com/c10k.html#phhttpd">Zach Brown's =

  phhttpd</A> for example code that uses this feature directly. (Or =
don't;=20
  phhttpd is a bit hard to figure out...)=20
  <P>[<A=20
  =
href=3D"http://www.citi.umich.edu/techreports/reports/citi-tr-00-7.ps.gz"=
>Provos,=20
  Lever, and Tweedie 2000</A>] describes a recent benchmark of phhttpd =
using a=20
  variant of sigtimedwait(), sigtimedwait4(), that lets you retrieve =
multiple=20
  signals with one call. Interestingly, the chief benefit of =
sigtimedwait4() for=20
  them seemed to be it allowed the app to gauge system overload (so it =
could <A=20
  href=3D"http://www.kegel.com/c10k.html#overload">behave =
appropriately</A>).=20
  (Note that poll() provides the same measure of system overload.)=20
  <P></P>
  <LI><A name=3Dnb.sigfd><B>Signal-per-fd</B></A><BR>Chandra and =
Mosberger=20
  proposed a modification to the realtime signal approach called =
"signal-per-fd"=20
  which reduces or eliminates realtime signal queue overflow by =
coalescing=20
  redundant events. It doesn't outperform epoll, though. Their paper ( =
<A=20
  =
href=3D"http://www.hpl.hp.com/techreports/2000/HPL-2000-174.html">www.hpl=
.hp.com/techreports/2000/HPL-2000-174.html</A>)=20
  compares performance of this scheme with select() and /dev/poll.<BR>
  <P><A=20
  =
href=3D"http://boudicca.tux.org/hypermail/linux-kernel/2001week20/1353.ht=
ml">Vitaly=20
  Luban announced a patch implementing this scheme on 18 May 2001</A>; =
his patch=20
  lives at <A=20
  =
href=3D"http://www.luban.org/GPL/gpl.html">www.luban.org/GPL/gpl.html</A>=
.=20
  (Note: as of Sept 2001, there may still be stability problems with =
this patch=20
  under heavy load. <A =
href=3D"http://www.kegel.com/dkftpbench">dkftpbench</A> at=20
  about 4500 users may be able to trigger an oops.)=20
  <P>See <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/doc/Poller_sigfd.html">Poller_sig=
fd</A>=20
  (<A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_sigfd.cc">=
cc</A>,=20
  <A=20
  =
href=3D"http://www.kegel.com/dkftpbench/dkftpbench-0.44/Poller_sigfd.h">h=
</A>)=20
  for an example of how to use signal-per-fd interchangeably with many =
other=20
  readiness notification schemes. </P></LI></UL>
<H3><A name=3Daio>3. Serve many clients with each server thread, and use =

asynchronous I/O</A></H3>
<P>This has not yet become popular in Unix, probably because few =
operating=20
systems support asynchronous I/O, also possibly because it (like =
nonblocking=20
I/O) requires rethinking your application. Under standard Unix, =
asynchronous I/O=20
is provided by <A=20
href=3D"http://www.opengroup.org/onlinepubs/007908799/xsh/realtime.html">=
the aio_=20
interface</A> (scroll down from that link to "Asynchronous input and =
output"),=20
which associates a signal and value with each I/O operation. Signals and =
their=20
values are queued and delivered efficiently to the user process. This is =
from=20
the POSIX 1003.1b realtime extensions, and is also in the Single Unix=20
Specification, version 2.=20
<P>AIO is normally used with edge-triggered completion notification, =
i.e. a=20
signal is queued when the operation is complete. (It can also be used =
with level=20
triggered completion notification by calling <A=20
href=3D"http://www.opengroup.org/onlinepubs/007908799/xsh/aio_suspend.htm=
l">aio_suspend()</A>,=20
though I suspect few people do this.)=20
<P>glibc 2.1 and later provide a generic implementation written for =
standards=20
compliance rather than performance.=20
<P>Ben LaHaise's implementation for Linux AIO was merged into the main =
Linux=20
kernel as of 2.5.32. It doesn't use kernel threads, and has a very =
efficient=20
underlying api, but (as of 2.6.0-test2) doesn't yet support sockets. =
(There is=20
also an AIO patch for the 2.4 kernels, but the 2.5/2.6 implementation is =

somewhat different.) More info:=20
<UL>
  <LI>The page "<A =
href=3D"http://lse.sourceforge.net/io/aio.html">Kernel=20
  Asynchronous I/O (AIO) Support for Linux</A>" which tries to tie =
together all=20
  info about the 2.6 kernel's implementation of AIO (posted 16 Sept =
2003)=20
  <LI><A=20
  =
href=3D"http://www.linuxsymposium.org/2002/view_txt.php?text=3Dabstract&a=
mp;talk=3D11">Round=20
  3: aio vs /dev/epoll</A> by Benjamin C.R. LaHaise (presented at 2002 =
OLS)=20
  <LI><A=20
  =
href=3D"http://archive.linuxsymposium.org/ols2003/Proceedings/All-Reprint=
s/Reprint-Pulavarty-OLS2003.pdf">Asynchronous=20
  I/O Suport in Linux 2.5</A>, by Bhattacharya, Pratt, Pulaverty, and =
Morgan,=20
  IBM; presented at OLS '2003=20
  <LI><A=20
  =
href=3D"http://sourceforge.net/docman/display_doc.php?docid=3D12548&amp;g=
roup_id=3D8875">Design=20
  Notes on Asynchronous I/O (aio) for Linux</A> by Suparna Bhattacharya =
--=20
  compares Ben's AIO with SGI's KAIO and a few other AIO projects=20
  <LI><A href=3D"http://www.kvack.org/~blah/aio/">Linux AIO home =
page</A> - Ben's=20
  preliminary patches, mailing list, etc.=20
  <LI><A href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-aio">linux-aio =
mailing list=20
  archives</A>=20
  <LI><A href=3D"http://www.ocfs.org/aio/">libaio-oracle</A> - library=20
  implementing standard Posix AIO on top of libaio. <A=20
  =
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-aio&amp;m=3D1050691584258=
22&amp;w=3D2">First=20
  mentioned by Joel Becker on 18 Apr 2003</A>. </LI></UL>Suparna also =
suggests=20
having a look at the <A=20
href=3D"http://www.dafscollaborative.org/tools/dafs_api.pdf">the DAFS =
API's=20
approach to AIO</A>.=20
<P><A =
href=3D"http://www.ussg.iu.edu/hypermail/linux/kernel/0209.0/0832.html">R=
ed=20
Hat AS</A> and Suse SLES both provide a high-performance implementation =
on the=20
2.4 kernel; it is related to, but not completely identical to, the 2.6 =
kernel=20