the c10k problem.mht

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

implementation.=20
<P>In February 2006, a new attempt is being made to provide network AIO; =
see <A=20
href=3D"http://www.kegel.com/c10k.html#kevent">the note above about =
Evgeniy=20
Polyakov's kevent-based AIO</A>.=20
<P>In 1999, <B><A href=3D"http://oss.sgi.com/projects/kaio/">SGI =
implemented=20
high-speed AIO</A> for Linux</B>. As of version 1.1, it's said to work =
well with=20
both disk I/O and sockets. It seems to use kernel threads. It is still =
useful=20
for people who can't wait for Ben's AIO to support sockets.=20
<P>The O'Reilly book <A =
href=3D"http://www.oreilly.com/catalog/posix4/">POSIX.4:=20
Programming for the Real World</A> is said to include a good =
introduction to=20
aio.=20
<P>A tutorial for the earlier, nonstandard, aio implementation on =
Solaris is=20
online at <A=20
href=3D"http://sunsite.nstu.nsk.su/sunworldonline/swol-03-1996/swol-03-ai=
o.html">Sunsite</A>.=20
It's probably worth a look, but keep in mind you'll need to mentally =
convert=20
"aioread" to "aio_read", etc.=20
<P>Note that AIO doesn't provide a way to open files without blocking =
for disk=20
I/O; if you care about the sleep caused by opening a disk file, <A=20
href=3D"http://www.ussg.iu.edu/hypermail/linux/kernel/0102.1/0124.html">L=
inus=20
suggests</A> you should simply do the open() in a different thread =
rather than=20
wishing for an aio_open() system call.=20
<P>Under Windows, asynchronous I/O is associated with the terms =
"Overlapped I/O"=20
and IOCP or "I/O Completion Port". Microsoft's IOCP combines techniques =
from the=20
prior art like asynchronous I/O (like aio_write) and queued completion=20
notification (like when using the aio_sigevent field with aio_write) =
with a new=20
idea of holding back some requests to try to keep the number of running =
threads=20
associated with a single IOCP constant. For more information, see <A=20
href=3D"http://www.sysinternals.com/ntw2k/info/comport.shtml">Inside I/O =

Completion Ports</A> by Mark Russinovich at sysinternals.com, Jeffrey =
Richter's=20
book "Programming Server-Side Applications for Microsoft Windows 2000" =
(<A=20
href=3D"http://www.amazon.com/exec/obidos/ASIN/0735607532">Amazon</A>, =
<A=20
href=3D"http://www.microsoft.com/mspress/books/toc/3402.asp">MSPress</A>)=
, <A=20
href=3D"http://patft.uspto.gov/netacgi/nph-Parser?Sect1=3DPTO1&amp;Sect2=3D=
HITOFF&amp;d=3DPALL&amp;p=3D1&amp;u=3D/netahtml/srchnum.htm&amp;r=3D1&amp=
;f=3DG&amp;l=3D50&amp;s1=3D'6223207'.WKU.&amp;OS=3DPN/6223207&amp;RS=3DPN=
/6223207">U.S.=20
patent #06223207</A>, or <A=20
href=3D"http://msdn.microsoft.com/library/default.asp?url=3D/library/en-u=
s/fileio/filesio_4z1v.asp">MSDN</A>.=20

<H3><A name=3Dthreaded>4. Serve one client with each server =
thread</A></H3>
<P>... and let read() and write() block. Has the disadvantage of using a =
whole=20
stack frame for each client, which costs memory. Many OS's also have =
trouble=20
handling more than a few hundred threads. If each thread gets a 2MB =
stack (not=20
an uncommon default value), you run out of *virtual memory* at (2^30 / =
2^21) =3D=20
512 threads on a 32 bit machine with 1GB user-accessible VM (like, say, =
Linux as=20
normally shipped on x86). You can work around this by giving each thread =
a=20
smaller stack, but since most thread libraries don't allow growing =
thread stacks=20
once created, doing this means designing your program to minimize stack =
use. You=20
can also work around this by moving to a 64 bit processor.=20
<P>The thread support in Linux, FreeBSD, and Solaris is improving, and =
64 bit=20
processors are just around the corner even for mainstream users. Perhaps =
in the=20
not-too-distant future, those who prefer using one thread per client =
will be=20
able to use that paradigm even for 10000 clients. Nevertheless, at the =
current=20
time, if you actually want to support that many clients, you're probably =
better=20
off using some other paradigm.=20
<P>For an unabashedly pro-thread viewpoint, see <A=20
href=3D"http://www.usenix.org/events/hotos03/tech/vonbehren.html">Why =
Events Are A=20
Bad Idea (for High-concurrency Servers)</A> by von Behren, Condit, and =
Brewer,=20
UCB, presented at HotOS IX. Anyone from the anti-thread camp care to =
point out a=20
paper that rebuts this one? :-)=20
<H4><A name=3Dthreads.linuxthreads>LinuxThreads</A></H4><A=20
href=3D"http://pauillac.inria.fr/~xleroy/linuxthreads/">LinuxTheads</A> =
is the=20
name for the standard Linux thread library. It is integrated into glibc =
since=20
glibc2.0, and is mostly Posix-compliant, but with less than stellar =
performance=20
and signal support.=20
<H4><A name=3Dthreads.ngpt>NGPT: Next Generation Posix Threads for=20
Linux</A></H4><A href=3D"http://www-124.ibm.com/pthreads/">NGPT</A> is a =
project=20
started by IBM to bring good Posix-compliant thread support to Linux. =
It's at=20
stable version 2.2 now, and works well... but the NGPT team has <A=20
href=3D"http://www-124.ibm.com/pthreads/docs/announcement">announced</A> =
that they=20
are putting the NGPT codebase into support-only mode because they feel =
it's "the=20
best way to support the community for the long term". The NGPT team will =

continue working to improve Linux thread support, but now focused on =
improving=20
NPTL. (Kudos to the NGPT team for their good work and the graceful way =
they=20
conceded to NPTL.)=20
<H4><A name=3Dthreads.nptl>NPTL: Native Posix Thread Library for =
Linux</A></H4><A=20
href=3D"http://people.redhat.com/drepper/nptl/">NPTL</A> is a project by =
<A=20
href=3D"http://people.redhat.com/drepper/">Ulrich Drepper</A> (the =
benevolent=20
dict^H^H^H^Hmaintainer of <A =
href=3D"http://www.gnu.org/software/libc/">glibc</A>)=20
and <A href=3D"http://people.redhat.com/mingo/">Ingo Molnar</A> to bring =

world-class Posix threading support to Linux.=20
<P>As of 5 October 2003, NPTL is now merged into the glibc cvs tree as =
an add-on=20
directory (just like linuxthreads), so it will almost certainly be =
released=20
along with the next release of glibc.=20
<P>The first major distribution to include an early snapshot of NPTL was =
Red Hat=20
9. (This was a bit inconvenient for some users, but somebody had to =
break the=20
ice...)=20
<P>NPTL links:=20
<UL>
  <LI><A =
href=3D"https://listman.redhat.com/mailman/listinfo/phil-list">Mailing=20
  list for NPTL discussion</A>=20
  <LI><A href=3D"http://people.redhat.com/drepper/nptl/">NPTL source =
code</A>=20
  <LI><A href=3D"http://lwn.net/Articles/10465/">Initial announcement =
for NPTL</A>=20

  <LI><A =
href=3D"http://people.redhat.com/drepper/glibcthreads.html">Original=20
  whitepaper describing the goals for NPTL</A>=20
  <LI><A =
href=3D"http://people.redhat.com/drepper/nptl-design.pdf">Revised=20
  whitepaper describing the final design of NPTL</A>=20
  <LI><A=20
  =
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-kernel&amp;m=3D1032304390=
08204&amp;w=3D2">Ingo=20
  Molnar's</A> first benchmark showing it could handle 10^6 threads=20
  <LI><A=20
  =
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-kernel&amp;m=3D1032695980=
00900&amp;w=3D2">Ulrich's=20
  benchmark</A> comparing performance of LinuxThreads, NPTL, and IBM's =
<A=20
  href=3D"http://www.kegel.com/c10k.html#threads.ngpt">NGPT</A>. It =
seems to show=20
  NPTL is much faster than NGPT. </LI></UL>Here's my try at describing =
the history=20
of NPTL (see also <A=20
href=3D"http://www.onlamp.com/pub/a/onlamp/2002/11/07/linux_threads.html"=
>Jerry=20
Cooperstein's article</A>):=20
<P><A href=3D"http://people.redhat.com/drepper/glibcthreads.html">In =
March 2002,=20
Bill Abt of the NGPT team, the glibc maintainer Ulrich Drepper, and =
others=20
met</A> to figure out what to do about LinuxThreads. One idea that came =
out of=20
the meeting was to improve mutex performance; Rusty Russell <A=20
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-kernel&amp;m=3D1032848478=
15916&amp;w=3D2">et=20
al</A> subsequently implemented <A=20
href=3D"http://marc.theaimsgroup.com/?l=3Dlinux-kernel&amp;m=3D1021966259=
21110&amp;w=3D2">fast=20
userspace mutexes (futexes)</A>), which are now used by both NGPT and =
NPTL. Most=20
of the attendees figured NGPT should be merged into glibc.=20
<P>Ulrich Drepper, though, didn't like NGPT, and figured he could do =
better.=20
(For those who have ever tried to contribute a patch to glibc, this may =
not come=20
as a big surprise :-) Over the next few months, Ulrich Drepper, Ingo =
Molnar, and=20
others contributed glibc and kernel changes that make up something =
called the=20
Native Posix Threads Library (NPTL). NPTL uses all the kernel =
enhancements=20
designed for NGPT, and takes advantage of a few new ones. Ingo Molnar <A =

href=3D"https://listman.redhat.com/pipermail/phil-list/2002-September/000=
013.html">described</A>=20
the kernel enhancements as follows:=20
<BLOCKQUOTE><I>While NPTL uses the three kernel features introduced by =
NGPT:=20
  getpid() returns PID, CLONE_THREAD and futexes; NPTL also uses (and =
relies on)=20
  a much wider set of new kernel features, developed as part of this =
project.=20
  <P>Some of the items NGPT introduced into the kernel around 2.5.8 got=20
  modified, cleaned up and extended, such as thread group handling=20
  (CLONE_THREAD). [the CLONE_THREAD changes which impacted NGPT's =
compatibility=20
  got synced with the NGPT folks, to make sure NGPT does not break in =
any=20
  unacceptable way.]=20
  <P>The kernel features developed for and used by NPTL are described in =
the=20
  design whitepaper, http://people.redhat.com/drepper/nptl-design.pdf =
...=20
  <P>A short list: TLS support, various clone extensions (CLONE_SETTLS,=20
  CLONE_SETTID, CLONE_CLEARTID), POSIX thread-signal handling, =
sys_exit()=20
  extension (release TID futex upon VM-release), the sys_exit_group()=20
  system-call, sys_execve() enhancements and support for detached =
threads.=20
  <P>There was also work put into extending the PID space - eg. procfs =
crashed=20
  due to 64K PID assumptions, max_pid, and pid allocation scalability =
work. Plus=20
  a number of performance-only improvements were done as well.=20
  <P>In essence the new features are a no-compromises approach to 1:1 =
threading=20
  - the kernel now helps in everything where it can improve threading, =
and we=20
  precisely do the minimally necessary set of context switches and =
kernel calls=20
  for every basic threading primitive. </I></P></BLOCKQUOTE>One big =
difference=20
between the two is that NPTL is a 1:1 threading model, whereas NGPT is =
an M:N=20
threading model (see below). In spite of this, <A=20
href=3D"https://listman.redhat.com/pipermail/phil-list/2002-September/000=
009.html">Ulrich's=20
initial benchmarks</A> seem to show that NPTL is indeed much faster than =
NGPT.=20
(The NGPT team is looking forward to seeing Ulrich's benchmark code to =
verify=20
the result.)=20
<H4><A name=3Dthreads.freebsd>FreeBSD threading support</A></H4>FreeBSD =
supports=20
both LinuxThreads and a userspace threading library. Also, a M:N =
implementation=20
called KSE was introduced in FreeBSD 5.0. For one overview, see <A=20
href=3D"http://www.unobvious.com/bsd/freebsd-threads.html">www.unobvious.=
com/bsd/freebsd-threads.html</A>.=20

<P>On 25 Mar 2003, <A=20
href=3D"http://docs.freebsd.org/cgi/getmsg.cgi?fetch=3D121207+0+archive/2=
003/freebsd-arch/20030330.freebsd-arch">Jeff=20
Roberson posted on freebsd-arch</A>:=20
<BLOCKQUOTE><I>... Thanks to the foundation provided by Julian, David =
Xu,=20
  Mini, Dan Eischen, and everyone else who has participated with KSE and =

  libpthread development Mini and I have developed a 1:1 threading=20
  implementation. This code works in parallel with KSE and does not =
break it in=20
  any way. It actually helps bring M:N threading closer by testing out =
shared=20
  bits. ... </I></BLOCKQUOTE>And in July 2006, <A=20
href=3D"http://marc.theaimsgroup.com/?l=3Dfreebsd-threads&amp;m=3D1151919=
79412894&amp;w=3D2">Robert=20
Watson proposed that the 1:1 threading implementation become the default =
in=20
FreeBsd 7.x</A>:=20
<BLOCKQUOTE><I>I know this has been discussed in the past, but I figured =
with=20
  7.x trundling forward, it was time to think about it again. In =
benchmarks for=20
  many common applications and scenarios, libthr demonstrates =
significantly=20
  better performance over libpthread... libthr is also implemented =
across a=20
  larger number of our platforms, and is already libpthread on several. =
The=20
  first recommendation we make to MySQL and other heavy thread users is =
"Switch=20
  to libthr", which is suggestive, also! ... So the strawman proposal =
is: make=20
  libthr the default threading library on 7.x. </I></BLOCKQUOTE>
<H4><A name=3Dthreads.netbsd>NetBSD threading support</A></H4>According =
to a note=20
from Noriyuki Soda:=20
<BLOCKQUOTE><I>Kernel supported M:N thread library based on the =
Scheduler=20
  Activations model is merged into NetBSD-current on Jan 18 2003.=20
</I></BLOCKQUOTE>For details, see <A=20
href=3D"http://web.mit.edu/nathanw/www/usenix/freenix-sa/">An =
Implementation of=20
Scheduler Activations on the NetBSD Operating System</A> by Nathan J. =
Williams,=20
Wasabi Systems, Inc., presented at FREENIX '02.=20
<H4><A name=3Dthreads.solaris>Solaris threading support</A></H4>The =
thread support=20
in Solaris is evolving... from Solaris 2 to Solaris 8, the default =
threading=20
library used an M:N model, but Solaris 9 defaults to 1:1 model thread =
support.=20
See <A href=3D"http://docs.sun.com/db/doc/805-5080">Sun's multithreaded=20
programming guide</A> and <A=20
href=3D"http://java.sun.com/docs/hotspot/threads/threads.html">Sun's =
note about=20
Java and Solaris threading</A>.=20
<H4><A name=3Dthreads.java>Java threading support in JDK 1.3.x and=20
earlier</A></H4>As is well known, Java up to JDK1.3.x did not support =