DOS/V Power Report 2004 March/VPR0403.ISO/talks/057/paper.dkb

Extensible Markup Language | 2003-09-18 | 41.4 KB | 972 lines

<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN"
"http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd">

<article lang="de">
  <articleinfo>
    <title>Skalierbare High-Performance Netzwerkprogrammierung unter Linux</title>

    <author>
      <firstname>Felix</firstname>
      <surname>von Leitner</surname>
      <affiliation>
        <address><email>[e-mail]</email></address>
      </affiliation>
    </author>

    <abstract>
      <para>Hochperformanter, gut skalierender Netzwerk-Code ist heute
      eines der wichtigsten Verkaufsargumente fr
      Server-Betriebssysteme.  Die Standard-Interfaces von POSIX und der
      Open Group eignen sich nur bedingt fr hohe Skalierbarkeit.</para>
      <para>Daher haben alle Anbieter in diesem Marktsegment eigene
      Interfaces entwickelt.  Dieser Artikel beleuchtet die Unterschiede
      stellvertretend an der Evolution dieser Interfaces unter
      Linux.</para>
    </abstract>
  </articleinfo>

  <sect1>
    <title>Grundlagen der Netzwerk-Programmierung</title>

    <para>Unter Unix werden Ger舩e und IPC-Mechanismen wie Dateien
    angesprochen.  Man fnet eine Datei mit
    <computeroutput>open()</computeroutput>, liest mit
    <computeroutput>read()</computeroutput>, schreibt mit
    <computeroutput>write()</computeroutput> und schlieﾟt die Datei
    wieder mit <computeroutput>close()</computeroutput>.  Hier ist ein
    kurzer Beispiel-Code:</para>

    <programlisting>
    char buf[4096];
    int fd=open("index.html", O_RDONLY);
    int len=read(fd,buf,sizeof buf);
    write(outfd,buf,len);
    close(fd);
    </programlisting>

    <para>Man beachte, daﾟ <computeroutput>open()</computeroutput> einen
    Integer zurckliefert, d.h. eine Zahl.  Diese dient als Referenz auf
    ein Kernel-Objekt; man kann damit in seinem Programm nichts tun, als
    sie dem Kernel gegenber als Referenz zu benutzen.  Damit Rechnen
    ist sinnlos, und es gibt auch keine Mlichkeit, zu einem solchen
    File Deskriptor den Dateinamen zu erfragen.</para>

    <para>Fr jeden Prozeﾟ fangen die Deskriptoren bei 0 an, und 0 bis 2
    sind fr Eingabe, Ausgabe und Fehlermeldungen reserviert.  POSIX
    sagt, daﾟ der Kernel als neuen Deskriptor immer den kleinsten noch
    nicht vergebenen zuweist.  Mehrere Prozesse knen (verschiedene)
    Deskriptoren fr die selbe Datei haben.</para>

    <para>Das API ist offensichtlich:
    <computeroutput>read()</computeroutput> kehrt zurck, wenn es Daten
    gelesen hat.  <computeroutput>write()</computeroutput> kehrt zurck,
    wenn die Daten geschrieben wurden.  Danach kann man den Puffer
    anderweitig verwenden.</para>

    <para>Netzwerkprogrammierung funktioniert analog.  Die Deskriptoren
    verweisen nicht auf Dateien, sondern auf Sockets (Steckdose).  Einen
    Socket richtet man mit <computeroutput>socket()</computeroutput>
    ein.  Hier ist ein Code-Beispiel:</para>

    <programlisting>
    char buf[4096];
    int len;
    int fd=socket(PF_INET,SOCK_STREAM,IPPROTO_TCP);
    struct sockaddr_in si;

    si.sin_family=PF_INET;
    inet_aton("127.0.0.1",&si.sin_addr);
    si.sin_port=htons(80);
    connect(fd,(struct sockaddr*)si,sizeof si);
    write(fd,"GET / HTTP/1.0\r\n\r\n");
    len=read(fd,buf,sizeof buf);
    close(fd);
    </programlisting>

    <para>Dieser Code fnet eine TCP-Verbindung zum Rechner 127.0.0.1 auf
    Port 80 und fragt nach /.  Es handelt sich hier also um einen
    simplen HTTP-Client.</para>

    <para>Das Socket-API trennt das Erstellen des Sockets von dem
    Erstellen einer Verbindung.  Der Hintergrund sind Server, die sich
    nie mit einer Gegenstelle verbinden, sondern zu denen die
    Gegenstellen sich verbinden.  Hier ist ein Mini-Server:</para>

    <programlisting>
    int len,s,fd=socket(PF_INET,SOCK_STREAM,IPPROTO_TCP);
    struct sockaddr_in si;

    si.sin_family=PF_INET;
    inet_aton("127.0.0.1",&si.sin_addr);
    si.sin_port=htons(80);
    bind(fd,(struct sockaddr*)si,sizeof si);
    listen(fd,16);
    s=accept(fd,(struct sockaddr*)&si,&len);
    </programlisting>
  </sect1>
  <sect1>
   <title>Handhabung mehrerer paralleler Verbindungen</title>

   <para>Wie kann ein Server mehr als einen Client verwalten?
   Offensichtlich ist das Modell mit dem blockierenden
   <computeroutput>read()</computeroutput> und
   <computeroutput>write()</computeroutput> nicht geeignet, um in einem
   Prozeﾟ mehr als eine Verbindung zu halten — man knte immer
   nur Daten ber eine Verbindung zur Zeit schicken.  Schlimmer noch,
   sobald der erste Client mal nichts schickt, bleibt das
   <computeroutput>read()</computeroutput> und damit die anderen
   Clients h舅gen.</para>

   <para>Die traditionelle Lung dafr ist, pro Verbindung einen neuen
   Prozeﾟ zu starten.</para>

   <sect2>
    <title>Ein Prozeﾟ pro Verbindung</title>

    <para>Unter Unix ist das glcklicherweise sehr einfach;
    man kann den gerade laufenden Prozeﾟ einfach klonen, man muﾟ nicht
    ein weiteres Programm dafr von der Festplatte laden, und der neue
    Prozeﾟ bernimmt auch alle Variablen und offenen File
    Deskriptoren.</para>

    <para>Trotzdem hat dieses Modell Nachteile und Probleme,
    insbesondere bei der Skalierbarkeit.  Typische Betriebssysteme sind
    fr den Fall von ein paar Dutzend bis zu Hundert Prozessen
    optimiert.</para>

    <para>Dazu kommt, daﾟ pro Prozeﾟ normalerweise bedeutende Mengen
    Systemspeicher verbraucht werden, insbesondere bei dynamisch
    gelinkten Programmen.  10.000 Clients gleichzeitig bringen auch
    grere Server zum Swappen, selbst wenn die Clients gar keine Daten
    anfordern.  Manche Systeme (Solaris, Windows) brauchen auﾟerdem sehr
    lange fr die Prozeﾟerzeugung und eignen sich daher fr dieses
    Modell nicht.</para>

    <para>Auch stellt sich bei diesem Modell die Frage, wie man Timeouts
    realisieren soll.  Wenn ein Client nach dem Verbindungsaufbau fr 20
    Minuten nichts sagt, sollte der Server in der Lage sein, das zu
    erkennen und die Verbindung zu schlieﾟen.
    </para>

   </sect2>
   <sect2>
    <title>Skalierbares Scheduling</title>
    <para>
    Das Betriebssystem verwaltet eine Liste von Prozessen
    und unterbricht periodisch (blicher Wert: 100 Mal pro Sekunde) den
    laufenden Prozeﾟ, um andere laufen zu lassen.  Dieser Teil des
    Systems, der den neuen Prozeﾟ ausw臧lt, heiﾟt Scheduler.
    </para>

    <para>
    Wenn ein Prozeﾟ wegen eines <computeroutput>read()</computeroutput>
    oder <computeroutput>write()</computeroutput> blockiert, w臧lt der
    Scheduler auch einen neuen Prozeﾟ.  Wenn also hunderte von Prozessen
    konkurrierend lesen und schreiben und dabei st舅dig blocken, dann
    verbringt das System einen signifikanten Teil der CPU-Zeit im
    Scheduler.
    </para>

    <para>
    Typischerweise laufen auf einem System eine paar Dutzend Prozesse,
    von denen ein oder zwei tats臘hlich laufen wollen, w臧rend die
    anderen gerade auf eine Eingabe oder ein Signal warten.  Es ist
    also sinnvoll, wenn das System zwei Prozeﾟlisten hat — eine
    fr die laufen wollenden Prozesse und eine fr die auf Eingabe
    wartenden.  Die erste Liste wird dann sehr kurz sein und der
    Scheduler spart sich das Anschauen der groﾟen Gesamtliste.
    </para>

    <para>
    Unix hat einen Mechanismus, um interaktive Prozesse zu bevorzugen
    und Batch-Prozesse zu benachteiligen.  Dazu wird sekndlich fr alle
    Prozesse der <computeroutput>nice</computeroutput>-Wert neu
    berechnet.  Dafr schaut sich der Scheduler alle Prozesse an, und
    muﾟ dabei bei einer sehr groﾟen Prozeﾟanzahl sehr viele Daten lesen.
    Das fhrt besonders bei 舁teren oder Desktop-CPUs zum Cache
    Trashing.
    </para>

    <para>
    Ein weiteres typisches Problem ist auch, daﾟ die Prozeﾟtabelle mit
    einem Kernel Lock geschtzt wird.  Bei einem System mit mehr als
    einem Prozessor wird also kann also der zweite Prozessor w臧rend der
    Nice-Berechnung keinen Prozeﾟwechsel vornehmen.  Dieses Problem
    len kommerzielle Unix-Varianten gewnlich, indem sie die
    Datenstruktur auf die Prozessoren verteilen, so daﾟ jeder Prozessor
    eine eigene Run Queue hat.
    </para>

    <para>
    Es gibt noch weiteren Spielraum fr Optimierungen im Scheduler.  Man
    kann z.B. die Run Queue sortiert vorhalten, und hierfr bieten sich
    diverse schlaue Datenstrukturen wie Heaps an, die den Aufwand von
    O(n) auf O(log n)<footnote>Vereinfacht gesagt heiﾟt O(n), daﾟ der
    Aufwand linear mit der Gre der Datenstruktur w臘hst (10.000
    Prozesse: Aufwand 10.000), w臧rend bei O(log n) der Aufwand nur
    logarithmisch steigt (10.000 Prozesse: Aufwand 14).</footnote> senken
    knen.
    </para>

    <para>
    Der heilige Gral der Scheduler ist allerdings der O(1)<footnote>O(1)
    zeigt an, daﾟ der Aufwand fr den Scheduler konstant ist, unabh舅gig
    von der Anzahl der Prozesse im System</footnote>-Scheduler.  Im
    Gesamtsystem wird die Leistung nie vlig unabh舅gig von der Anzahl
    der Prozesse sein knen, weil die Leistung heutiger Prozessoren
    stark davon abh舅gig ist, daﾟ alle h舫fig benutzten Daten im
    Prozessor-Cache Platz finden.
    </para>

    <para>
    Der Linux 2.4 Scheduler hat eine einzelne unsortierte Run Queue mit
    allen lauff臧igen Prozessen ("runnable"), und eine Liste mit allen
    blockenden Prozessen und Zombies.  Alle Operationen auf der Run
    Queue sind hinter einem Spinlock geschtzt.  Der Scheduler bemht
    sich um CPU-Affinit舩<footnote>Damit ist gemeint, daﾟ bei einem
    SMP-System ein Prozeﾟ nicht st舅dig von einem Prozessor zum n臘hsten
    wechselt, weil jeder Prozessor seinen eigenen Cache mitbringt, der
    dann nicht optimal ausgenutzt wird.</footnote>
    </para>

    <para>
    Fr Linux gibt es diverse neue Scheduler, mit Heaps und multiplen
    Run Queues, aber der erstaunlichste Scheduler ist der O(1)-Scheduler
    von Ingo Molnar.  Dieser Scheduler ist in den 2.5 "Hacker-Kerneln"
    Standard.
    </para>

    <para>
    Der O(1)-Scheduler hat pro CPU zwei Arrays mit jeweils einer
    verketteten Liste.  Pro mlicher Prozeﾟ-Priorit舩 gibt es eine
    Liste in diesen Arrays.  Da alle Eintr臠e in diesen Listen die
    gleiche Priorit舩 haben, mssen die Listen nicht weiter sortiert
    werden.  Das eine Array pro CPU hat die lauff臧igen Prozesse, das
    andere ist leer.  Das Ein- und Austragen eines Prozesses in einer
    doppelt verkettete Liste ist O(1).  Der Scheduler nimmt sich also
    immer die volle Liste, l葹t jeden Prozeﾟ darin einmal laufen, tr臠t
    den Prozeﾟ dann in dieser Liste aus und in der anderen Liste ein,
    und wenn die Liste leer ist, tauscht er die Zeiger auf die Arrays
    aus.  Die <computeroutput>nice</computeroutput> Berechnung wird in
    diesem Scheduler umgekehrt: jetzt werden nicht mehr interaktive
    Prozesse belohnt, sondern Batch-Prozesse werden bestraft
    (interaktive Prozesse blocken, Batch-Prozesse werden vom Scheduler
    unterbrochen).
    </para>

    <para>
    Dieser geniale Scheduler skaliert praktisch unabh舅gig von der
    Anzahl der Prozesse.  In Tests hat man selbst bei 100.000
    gestarteten Threads keine Verlangsamung beobachtet.
    </para>
   </sect2>
   <sect2>
    <title>Kontextwechsel und Prozeﾟerzeugungskosten</title>
    <para>
    Der Kontextwechsel ist auf heutigen Prozessoren eine der langsamsten
    Operationen berhaupt.  Ein Kontextwechsel findet statt, wenn ein
    Prozeﾟ zu einem anderen gewechselt wird (der ﾜbergang von einem
    Prozeﾟ zum Betriebssystem ist auch sehr aufwendig, aber dafr gibt
    es h舫fig sehr effizienten Hardware-Support).
    </para>

    <para>
    Bei einem Kontextwechsel muﾟ das Betriebssystem die Register sichern
    und laden, den TLB flushen und bei manchen Architekturen muﾟ auch
    manuell die Pipeline geleert werden und die Caches geflusht werden.
    Auf einem blichen Desktop-System mit laufendem mp3-Player kommen
    10-70 Kontextwechsel pro Sekunde vor.  Wenn ein HTTP-Benchmark ber
    Loopback l舫ft, sind es 10.000, ber ein Ethernet-Interface sogar
    20.000.  Offensichtlich z臧lt hier jede Mikrosekunde.  Architekturen
    mit wenig Registern wie x86 haben hier einen Erbvorteil gegenber
    Architekturen mit vielen Registern oder komplizierten Anordnungen
    wie SPARC oder IA-64.
    </para>

    <para>
    Der Speicherbedarf eines leeren Prozesses ist bei aktuellen
    Linux-System in der Tat erschreckend groﾟ.  Schuld ist aber nicht
    Linux, sondern die libc unter Linux, die GNU libc.  Diese verbraucht
    mit groﾟem Abstand von allen libc-Implementationen den meisten
    Speicher und hat die hhsten Startup-Kosten.
    </para>

    <para>
    Ich habe daher eine eigene libc fr Embedded-Systeme und
    Server-Anwendungen wie CGI-Programme und Servlets geschrieben, und
    damit erreicht man ein statisches Hallo-Welt-Binary von unter 300
    Bytes.  Das Ausfhren dieses Programmes inklusive
    <computeroutput>fork()</computeroutput>,
    <computeroutput>exec()</computeroutput> und
    <computeroutput>wait</computeroutput> kostet auf einem Athlon ca.
    200.000 CPU-Zyklen.  Ein 2 GHz Athlon kann also rein rechnerisch pro
    Sekunde 10.000 Prozesse erzeugen.
    </para>
   </sect2>
   <sect2>
    <title>Timeout-Handling</title>
    <para>
    Die einfachste Methode zum Timeout-Handling ist
    <computeroutput>alarm()</computeroutput>.
    <computeroutput>alarm(10)</computeroutput> schickt dem aktuellen
    Prozeﾟ nach 10 Sekunden ein Signal; wenn man dieses nicht explizit
    abf舅gt, wird der Prozeﾟ dann vom System beendet.  Fr triviale
    Netzwerk-Servlets ist das wie geschaffen.
    </para>

    <para>
    Unix bietet aber auch andere Methoden, um einen Timeout zu
    implementieren.  Die bekannteste (und 舁teste — eingefhrt
    1983 mit 4.2BSD) ist
    <computeroutput>select()</computeroutput>:
    </para>

    <programlisting>
    fd_set rfd;
    struct timeval tv;
    FD_ZERO(&rfd); FD_SET(0,&rfd); /* fd 0 */
    tv.tv_sec=5; tv.tv_usec=0;     /* 5 Sekunden */
    if (select(1,&rfd,0,0,&tv)==0) /* read, write, error, timeout */
      handle_timeout();
    if (FD_ISSET(0, &rfd))
      can_read_on_fd_0();
    </programlisting>

    <para>
    Das erste Argument ist die Nummer des grten bergebenen
    Filedeskriptors plus 1 (das ist die eine Ausnahme, bei der Rechnen
    mit den File Deskriptoren doch sinnvoll ist).  Die n臘hsten drei
    Argumente sind Bitfelder; man setzt das 23. Bit im 1. Array
    (<computeroutput>readfds</computeroutput>, read file descriptors),
    wenn auf auf dem File Deskriptor 23 Daten lesen mhte.  Das 2.
    Array ist fr Schreiben, das 3. fr Fehlerbehandlung.  Als letztes
    Argument bergibt man noch, wie lange man hhstens warten mhte.
    </para>

    <para>
    Mit <computeroutput>select()</computeroutput> lassen sich
    offensichtlich nicht nur Timeouts implementieren, sondern man kann
    auch mehrere Deskriptoren auf einmal zum Lesen oder Schreiben
    benutzen, d.h. man kann einen Server schreiben, der mehr als eine
    Verbindung gleichzeitig behandeln kann.
    </para>

    <para>
    <computeroutput>select()</computeroutput> hat aber auch wichtige
    Nachteile:
    <itemizedlist>
    <listitem><para><computeroutput>select()</computeroutput> sagt
    nicht, wie lange es denn tats臘hlich gewartet hat.  Man muﾟ also
    noch mal <computeroutput>gettimeofday()</computeroutput> o..
    aufrufen.</para></listitem>
    <listitem><para><computeroutput>select()</computeroutput> arbeitet
    mit Bitfeldern.  Die Gre h舅gt vom Betriebssystem ab.  Wenn man
    Glck hat, kann man so 1024 Deskriptoren ansprechen, h舫fig noch
    weniger.</para></listitem>
    </itemizedlist>
    </para>

    <para>
    Unter Linux gibt <computeroutput>select()</computeroutput> doch
    zurck, wie lange es gewartet hat, indem es den Timeout-Wert um den
    Betrag senkt, den es gewartet hat.  Das ist nicht nur unportabel, es
    besch臈igt auch portable Software, die sich darauf verl葹t, daﾟ der
    Timeout-Wert konstant bleibt.  Die Bitfeld-Gre ist unter Linux
    1024, bei NetBSD 256.
    </para>

    <para>
    Das Problem mit <computeroutput>select()</computeroutput> ist
    schlimmer als es aussieht, weil es manchmal von irgendwelchen
    Unter-Bibliotheken benutzt wird.  Apache hat an dieser Stelle z.B.
    Probleme mit den DNS-Bibliotheken bekommen und h舁t sich daher
    von Hand die Filedeskriptoren bis 15 frei, indem neue Deskriptoren
    nach oben verschoben werden (das kann man mit
    <computeroutput>dup2</computeroutput> machen).  DNS ht sonst
    einfach zu funktionieren auf, sobald man mal alle Deskriptoren bis
    1024 belegt hat.
    </para>

    <para>
    Eine Variation auf <computeroutput>select()</computeroutput> ist
    <computeroutput>poll()</computeroutput>, eingefhrt 1986 mit System V
    Release 3.  Man benutzt es ziemlich 臧nlich wie
    <computeroutput>select()</computeroutput>:
    </para>

    <programlisting>
    struct pollfd pfd[2];
    pfd[0].fd=0; pfd[0].events=POLLIN;
    pfd[1].fd=1; pfd[1].events=POLLOUT|POLLERR;
    if (poll(pfd,2,1000)==0) /* 2 records, 1000 milliseconds timeout */
      handle_timeout();
    if (pfd[0].revents&POLLIN) can_read_on_fd_0();
    if (pfd[1].revents&POLLOUT) can_write_on_fd_1();
    </programlisting>

    <para>
    <computeroutput>poll()</computeroutput> hat kein Limit auf die
    Anzahl oder Gre der Deskriptoren, dafr wird es auf manchen
    Museumsexponaten nicht untersttzt.  Es gibt sogar ein aktuelles
    Unix-Derivat, das kein <computeroutput>poll()</computeroutput>
    untersttzt, und das es damit unmlich macht, auf ihm portabel
    skalierbare Serversoftware laufen zu lassen: MacOS X.  Von der
    Benutzung von MacOS X kann daher nur abgeraten werden, bis jemand
    dem Hersteller fundamentales Unix-Wissen vermitteln konnte.
    </para>

    <para>
    W臧rend man mit <computeroutput>poll()</computeroutput> berhaupt
    erst mal in die Lage versetzt wird, Programme mit 10.000 offenen
    Client-Verbindungen zu schreiben, kann ein solches Programm mit
    <computeroutput>poll()</computeroutput> nicht effizient laufen.  Der
    Kernel muﾟ das gesamte Array aus dem User-Space lesen, die
    zugehigen Socket-Objekte aus seinen Datenstrukturen heraussuchen,
    auf neuen Daten oder Schreibbarkeit prfen, und dann im User-Space
    das entsprechende Bit setzen.  Heutige Prozessoren sind weitgehend
    von der Speicherbandbreite limitiert; das langwierige Durchgehen von
    groﾟen Arrays im User-Space ist daher sehr ineffizient, insbesondere
    wenn sich an dem Inhalt des Arrays seit dem letzten Aufruf von
    <computeroutput>poll()</computeroutput> gar nichts ge舅dert hat.
    </para>

    <para>
    Das klingt auf den ersten Blick unvermeidlich, aber wenn man sich
    typische Server-Lasten mit 10.000 Verbindungen ansieht, dann sind
    nur wenige Verbindungen davon aktiv, die meisten sind sehr langsam
    oder gar ganz inaktiv.  Ein viel effizienteres Schema w舐e daher,
    wenn man die Verwaltung der Liste der gewnschten Events dem Kernel
    berl葹t und ihm nur Ver舅derungen mitteilt.
    </para>

    <para>
    Es ist normalerweise nicht so kritisch, wenn
    <computeroutput>poll()</computeroutput> langsam ist, weil die Events
    ja nicht verloren gehen, sie kommen nur sp舩er an.  Der Durchsatz
    leidet daher nicht so stark wie die Latenz.  Ich habe mit
    <computeroutput>poll()</computeroutput> eine bis zu um den Faktor 20
    here Latenz als mit SIGIO oder epoll gemessen.
    </para>
   </sect2>
   <sect2>
    <title>Das Multithreading-Debakel</title>
    <part>
    In den letzten Jahren hat sich Multithreading als Lung fr alle
    Probleme in den Kfen etabliert, insbesondere fr Skalierbarkeit
    und Performance auch und vor allem bei Netzwerkprogrammierung.  Die
    Realit舩 sieht anders aus.  Die meisten Systeme haben ein hartes
    Limit fr die Anzahl der gleichzeitigen Threads.  Eine bliche
    Grenordnung ist 1024.  Von Skalierbarkeit kann unter solchen
    Umst舅den keine Rede sein.  Auch ansonsten kann man mit Thread
    bizarre Effekte erleben: pthread_create kann keine Threads anlegen,
    selbst wenn nur bereits 4 laufen, oder manchmal sogar wenn gar keine
    anderen Threads laufen, solange vorher viele Threads erzeugt wurden.
    Es ist mir unbegreiflich, wie Leute Threads fr
    Netzwerkprogrammierung verwenden knen.
    </part>
    <part>
    Das Multiprozeﾟ-Modell hat den Vorteil, daﾟ es fehlertolerant
    arbeitet.  Wenn ein Server-Prozeﾟ abstrzt, laufen die anderen
    weiter.  Es gibt auch keine Memory Leaks: wenn sich ein
    Server-Prozeﾟ beendet, gibt das System alle Resourcen automatisch
    frei.  Bei Threads ist beides nicht so.  Wenn ein Thread einen
    Absturz erzeugt, schieﾟt das System den ganzen Prozeﾟ mit allen
    anderen Threads mit ab.  Multithreading-Programme haben daher h舫fig
    die Eigenschaft, schrankenlos vor sich hin zu wachsen.  Manch
    kommerzielle Software kommt daher mit einem Shell Script, das sie
    nachts automatisch abschieﾟt und neu startet, um den Speicherlecks
    entgegen zu arbeiten.
    </part>

    <part>
    Man muﾟ sich natrlich auch bei
    <computeroutput>poll</computeroutput>-basierten Servern darum
    kmmern, daﾟ man keinen Speicher leckt, insofern ist das nicht den
    Threads alleine anzulasten, aber viele Multithread-Projekte sind aus
    Multiprozeﾟ-Projekten hervorgegangen und kriegen ihre Lecks nie
    wieder in den Griff.
    </part>
   </sect2>

   <sect2>
    <title>Asynchroner I/O</title>
    <part>
    <computeroutput>poll</computeroutput> und
    <computeroutput>select</computeroutput> funktionieren nicht auf
    Dateien, nur auf Sockets, Ger舩edateien und Pipes.  Das ist bei
    Festplatten normalerweise nicht so schlimm, aber wenn man einen
    Server schreibt, der per NFS gemountete Dateien frei geben soll,
    dann blockt bei einem NFS-Timeout der gesamte Server, selbst wenn
    die anderen Requests alle Dateien von der lokalen Festplatte
    betreffen.
    </part>

    <part>
    Die Unix-Standardisierungsgremien haben sich daher ein Modell fr
    asynchronen I/O ausgedacht, bei dem das
    <computeroutput>read</computeroutput>-ﾄquivalent sofort zurck kehrt
    und man sp舩er ein Signal kriegt, wenn die Operation fertig ist
    (analog natrlich fr <computeroutput>write</computeroutput>).  Das
    Problem ist, daﾟ dieses API fast niemand implementiert; Solaris hat
    die Funktionen, die liefern aber alle Fehler zurck (Solaris hat
    auch ein funktionierendes propriet舐es API).  Linux glibc
    implementiert diese Funktionen, indem pro Operation ein Thread
    aufgemacht wird.  Weil das so frchterlich ist, benutzt dieses API
    so gut wie niemand.
    </part>

    <part>
    Asynchroner I/O h舩te dabei durchaus Vorzge gegenber normalen
    Lesen.  Wenn man z.B. 1000 Blke aus einer Datenbank lesen will,
    und man liest sie alle sequentiell, dann muﾟ das System sie in der
    gew臧lten Reihenfolge lesen.  Da das User-Space Programm keine
    Ahnung haben kann, wie die Blke physikalisch auf der Platte
    verteilt sind, muﾟ das System unnig die Schreib-Lese-Kfe hin-
    und herbewegen.  Asynchroner I/O hingegen erlaubt dem System, die
    Blke in der effizientesten Reihenfolge zu lesen.  Es gibt Ans舩ze,
    asynchronen I/O auch in Linux anst舅dig zu implementieren.
    </part>
   </sect2>

   <sect2>
    <title>Linux 2.4: SIGIO</title>
    <part>Linux 2.4 kann poll-Events auch ber Signals mitteilen.  Die
    Idee ist, daﾟ man mit einem <computeroutput>fcntl</computeroutput>
    auf den File Deskriptor dem System mitteilt, daﾟ man an
    Status舅derungen interessiert ist, und dann kriegt man immer ein
    Signal, wenn sich an dem Deskriptor etwas tut.  Der Vorteil ist, daﾟ
    das im System mit O(1) implementierbar ist.  Hier ist Beispiel-Code:
    </part>

    <programlisting>
    int sigio_add_fd(int fd) {
      static const int signum=SIGRTMIN+1;
      static pid_t mypid=0;
      if (!mypid) mypid=getpid();
      fcntl(fd,F_SETOWN,mypid);
      fcntl(fd,F_SETSIG,signum);
      fcntl(fd,F_SETFL,fcntl(fd,F_GETFL)|O_NONBLOCK|O_ASYNC);
    }

    int sigio_rm_fd(struct sigio* s,int fd) {
      fcntl(fd,F_SETFL,fcntl(fd,F_GETFL)&(~O_ASYNC));
    }
    </programlisting>

    <part>
    Signal-Handler bekommen traditionell die Signal-Nummer bergeben.
    Bei Linux gibt es noch ein zweites Argument, eine struct, in der
    u.a. der File Deskriptor drin steht, so daﾟ man fr 1000
    Deskriptoren Signals ber den gleichen Handler bearbeiten lassen
    kann.
    </part>

    <part>
    Aus Performance-Grnden kann man auf die Zustellung der Signals auch
    verzichten und stattdessen das gew臧lte Signal blocken.  Es ist dann
    trotzdem noch mlich, dieses Signal zu empfangen, indem man in
    einer Schleife <computeroutput>sigtimedwait</computeroutput>
    aufruft.  Da kann brigens man auch noch einen Timeout angeben, was
    das Timeout-Handling vereinfacht.
    </part>

    <part>
    <acronym>SIGIO</acronym> ist ein sehr elegantes API, das allerdings ein Umdenken
    erfordert.  Da man nirgendwo sagt, an welchen Events man
    interessiert ist, kriegt man alle Events zugestellt.  Bei
    <computeroutput>select</computeroutput> und
    <computeroutput>poll</computeroutput> ist es so, daﾟ man auf ein
    Event auch einfach nicht reagieren kann.  Der n臘hste
    <computeroutput>poll</computeroutput>-Aufruf signalisiert dann das
    selbe Event noch einmal.  So kann man sehr sch fr Fairness
    sorgen und Rate Limiting implementieren.  <acronym>SIGIO</acronym> hingegen teilt nur
    das erste Event mit.  Wenn man darauf nicht reagiert, wird man nie
    wieder auf diesen Deskriptor hingewiesen werden.
    </part>

    <part>
    Die Angelegenheit ist sogar noch etwas schwieriger: Wenn man bei
    <computeroutput>poll</computeroutput> ein Lese-Event bekommt,
    <computeroutput>read</computeroutput> aufruft, 100 Bytes liest, und
    wieder <computeroutput>poll</computeroutput> aufruft, funktioniert
    das.  Bei <acronym>SIGIO</acronym> muﾟ man <computeroutput>read</computeroutput> so
    lange aufrufen, bis man explizit
    <computeroutput>EAGAIN</computeroutput> als Fehlermeldung kriegt
    ("sp舩er nochmal probieren").  Diese Fehlermeldung kann
    <computeroutput>read</computeroutput> nur erzeugen, wenn man
    <phrase>non-blocking I/O</phrase> fr diesen File Deskriptor
    aktiviert hat:
    </part>

    <programlisting>
    #include <fcntl.h>

    fcntl(fd,F_SETFL,fcntl(fd,F_GETFL,0) | O_NDELAY);
    </programlisting>

    <part>
    Das <computeroutput>poll</computeroutput>-Modell nennt man
    <phrase>level triggered</phrase>, das
    <acronym>SIGIO</acronym>-Modell heiﾟt <phrase>edge
    triggered</phrase>.  In der Praxis ist ersteres fr Programmierer
    einfacher zu verstehen.  Das <acronym>SIGIO</acronym>-Modell hat
    aber den Vorteil, daﾟ sich das Programm l舅ger am Stck mit der
    gleichen Verbindung besch臟tigt, so daﾟ die zugehigen Daten alle
    im Cache sind.  So ist es geringfgig effizienter.  Man kann
    auch mit <computeroutput>poll</computeroutput> arbeiten, als w舐e es
    edge triggered, aber nicht umgekehrt.
    </part>

    <programlisting>
    for (;;) {
      timeout.tv_sec=0;
      timeout.tv_nsec=10000;
      switch (r=sigtimedwait(&s.ss,&info,&timeout)) {
      case -1: if (errno!=EAGAIN) error("sigtimedwait");
      case SIGIO: puts("SIGIO!  overflow!"); return 1;
      }
      if (r==signum) handle_io(info.si_fd,info.si_band);
    }
    </programlisting>

    <para>
    Aber auch <acronym>SIGIO</acronym> hat Nachteile: der Kernel
    reserviert pro Prozeﾟ einen Speicherbereich fr die Liste der
    ausstehenden Events.  Wenn dieser Speicherbereich voll ist, wrden
    Events verloren gehen.  Der Kernel signalisiert daher dann mit SIGIO
    (mit dem Signal namens SIGIO, nicht dem Konzept), daﾟ die Queue
    vollgelaufen ist.  Das Programm muﾟ dann die Queue manuell leeren,
    indem fr den Signal Handler kurzzeitig
    <computeroutput>SIG_DFL</computeroutput> eingetragen wird, und sich
    die Events mit <computeroutput>poll</computeroutput> abholen.
    </para>

    <para>
    In der Praxis heiﾟt das, daﾟ man bei SIGIO eben doch noch ein Array
    mit <computeroutput>struct pollfd</computeroutput> verwalten muﾟ; das
    mhte man sich ja aber eigentlich gerade sparen, deshalb benutzt
    man ja SIGIO!  Das klingt vielleicht auf den ersten Blick nicht nach
    Arbeit, aber pollfds mssen kontinuierlich hintereinander liegen;
    man kann nicht in der Mitte des Arrays einen leeren Eintrag haben,
    sonst bricht <computeroutput>poll</computeroutput> mit
    <computeroutput>EBADFD</computeroutput> ab.  Wenn mein Server also
    viele Verbindungen offen hat, und in der Mitte wird eine
    geschlossen, muﾟ ich mein Array anpassen.  Das heiﾟt aber auch, daﾟ
    ich den zugehigen Eintrag im Array nicht einfach finden kann,
    indem ich den Deskriptor als Index nehme!  Daraus folgt, daﾟ man
    O(1)-Finden des zugehigen Eintrags nur ber eine Indirektion
    mit einem zweiten Array implementieren kann, und der Code wird dann
    entsprechend unbersichtlich.
    </para>

    <para>
    Es gibt noch einen Nachteil von SIGIO: man hat einen Syscall pro
    mitgeteiltem Event.  Bei poll ist zwar die Abarbeitung des Syscalls
    teuer, aber dafr hat man da nicht viele von.  Unter Linux ist der
    Aufruf eines Syscalls sehr effizient gelt, daher muﾟ man sich da
    nicht viel Sorgen machen; die kommerziellen Unixen haben da
    teilweise mehr als eine Grenordnung grere Latenzen.  Aber
    unabh舅gig davon, ob das jetzt sehr oder nur m葹ig viel
    verschwendete Leistung ist, man kann sich auch ein API vorstellen,
    bei dem man mehr als ein Event auf einmal gemeldet bekommen kann.
    </para>
   </sect2>
   <sect2>
    <title>Solaris: /dev/poll</title>
    <para>
    Bei Solaris kann man seit zwei-drei Jahren poll beschleunigen, indem
    man das Device <computeroutput>/dev/poll</computeroutput> fnet,
    dort sein <computeroutput>pollfd</computeroutput>-Array hinein
    schreibt, und dann mit einem <computeroutput>ioctl</computeroutput>
    auf Events wartet.
    </para>

    <para>
    Der <computeroutput>ioctl</computeroutput> sagt einem, wie viele
    Events anliegen, und so viele <computeroutput>struct
    pollfd</computeroutput> liest man dann von dem Device.  Man hat
    also nur fr die Deskriptoren Aufwand, bei denen auch tats臘hlich
    Events anliegen.  Das spart sowohl im Kernel als auch im User-Space
    gewaltig Aufwand und ist auch mit minimalem Aufwand auf bestehende
    Programme portierbar.
    </para>

    <para>
    Es gab Ans舩ze, ein solches Device auch unter Linux zu
    implementieren.  Keiner von ihnen hat es in den Standard-Kernel
    geschafft, und die Patches verhielten sich unter hoher Last
    teilweise undeterministisch, daher ist dieses API auf Solaris
    beschr舅kt.
    </para>
   </sect2>
   <sect2>
    <title>Linux: epoll</title>

    <para>
    Fr Linux 2.4 gibt es einen Patch, der
    <computeroutput>/dev/epoll</computeroutput> implementiert.  Die
    Anwendung entspricht weitgehend der Solaris-Variante:
    </para>

    <programlisting>
    int epollfd=open("/dev/misc/eventpoll",O_RDWR);
    char* map;
    ioctl(epollfd,EP_ALLOC,maxfds); /* Hint: Anzahl der Deskriptoren */
    map=mmap(0, EP_MAP_SIZE(maxfds), PROT_READ, MAP_PRIVATE, epollfd, 0);
    </programlisting>

    <para>
    Man fgt ein Event an, indem man auf das Device einen <computeroutput>pollfd</computeroutput> schreibt.
    Man lcht ein Event, indem man auf das Device einen
    <computeroutput>pollfd</computeroutput> mit
    <computeroutput>events==0</computeroutput> schreibt.  Wie bei Solaris holt man die Events mit einem
    <computeroutput>ioctl</computeroutput> ab:
    </para>

    <programlisting>
    struct evpoll evp;
    for (;;) {
      int n;
      evp.ep_timeout=1000;
      evp.ep_resoff=0;
      n=ioctl(e.fd,EP_POLL,&evp);
      pfds=(struct pollfd*)(e.map+evp.ep_resoff);
      /* jetzt hat man n pollfds mit Events in pfds */
    }
    </programlisting>

    <para>
    Dank <computeroutput>mmap</computeroutput> findet hier berhaupt
    kein Kopieren zwischen Kernel und User-Space statt.  Dieses API hat
    es nie in den Standard-Kernel geschafft, weil Linus
    <computeroutput>ioctl</computeroutput> nicht mag.  Seine Begrndung
    ist, daﾟ das ein Dispatcher sei, und man habe ber die
    Syscall-Nummer ja schon einen Dispatcher, und daher solle man doch
    bitte den benutzen.  Der Autor von epoll hat die Patches daraufhin
    noch einmal mit Syscalls implementiert, und diese API ist seit
    2.5.51 in der dokumentierten Form im Standard-Kernel enthalten.
    </para>

    <programlisting>
    int epollfd=epoll_create(maxfds);
    struct epoll_event x;
    x.events=EPOLLIN|EPOLLERR;
    x.data.ptr=whatever; /* hier tr臠t man sich einen Cookie ein */
    epoll_ctl(epollfd,EPOLL_CTL_ADD,fd,&x);
    /* 舅dern ist analog */
    epoll_ctl(epollfd,EPOLL_CTL_MOD,fd,&x);
    /* lchen ist analog, nur fd muﾟ eingetragen sein */
    epoll_ctl(epollfd,EPOLL_CTL_DEL,fd,&x);
    </programlisting>

    <para>
    Die EPOLLIN, ... Konstanten sind im Moment identisch mit POLLIN, aber
    der Autor wollte sich da alle Optionen offen halten.  Das epoll-API
    sagt einem nicht automatisch den Deskriptor zu dem Event.  Wenn man
    das mhte, muﾟ man den Deskriptor als Cookie eintragen.  Der Cookie
    ist ein 64-bit Wert, hier kann man also auch einen Zeiger auf eine
    Datenstruktur eintragen, in der dann neben anderen Daten auch der
    Deskriptor steht.  Seine Events holt man sich dann mit
    <computeroutput>epoll_wait</computeroutput> ab:
    </para>

    <programlisting>
    for (;;) {
      struct epoll_event x[100];
      int n=epoll_wait(epollfd,x,100,1000); /* 1000 Millisekunden */
      /* x[0] .. x[n-1] sind die Events */
    }
    </programlisting>
   </sect2>

   <sect2>
    <title>Windows: Completion Ports</title>

    <para>Auch Microsoft muﾟ skalierbare Netzwerk-Server anbieten
    knen.  Die Microsoft-Lung hierfr ist, daﾟ man einen Thread Pool
    aufmachen, und dann in jedem Thread mit einem SIGIO-臧nlichen
    Verfahren die Events benachrichtigt bekommt.
    </para>

    <para>
    Dieses Verfahren verbindet die Nachteile von Threads mit den
    Nachteilen von SIGIO.  Leider gibt es unter Windows keine
    Alternativen.  Fr die Neugierigen:
    <computeroutput>select()</computeroutput> wird unter Windows ber ein
    leeres Off-Screen Fenster implementiert, das dann ber den Fenster
    Input-Event Mechanismus die Netzwerk-Events mitgeteilt bekommt.
    </para>
   </sect2>

   <sect2>
    <title>FreeBSD: kqueue</title>

    <para>
    kqueue ist eine Kreuzung aus epoll und
    <computeroutput>/dev/poll</computeroutput>.  Man kann sich
    aussuchen, ob man nach level oder egde getriggert werden will.
    Auﾟerdem hat man noch eine Art SIGIO und File und Directory Status
    Notification eingebaut.  Dabei ist das API leider ziemlich
    unbersichtlich geworden.  Von der Performance her ist kqueue mit
    epoll vergleichbar.
    </para>
   </sect2>
  </sect1>
  <sect1>
   <title>Sonstige Tricks zur Performance-Steigerung</title>

   <sect2>
    <title>writev, TCP_CORK und TCP_NOPUSH</title>

    <para>
    Ein HTTP-Server schreibt erst einen (kleinen) Antwort-Header und
    dann die Datei in den Socket.  Wenn er fr beides einfach
    <computeroutput>write()</computeroutput> aufruft, erzeugt das ein
    kleines TCP-Paket fr den Header, und danach noch ein TCP-Paket fr
    die Daten.  Wenn man nur eine kleine Datei per HTTP bertragen will,
    h舩te beides vielleicht in ein Paket gepaﾟt.
    </para>

    <para>
    Offensichtlich kann man einen Puffer nehmen, und in diesen erst den
    Header und dann den Dateiinhalt hineinkopieren, und dann den Puffer
    schreiben.  Das ist aber Verschwendung von RAM-Bandbreite.  Es gibt
    drei andere Lungen: <computeroutput>writev()</computeroutput>,
    <computeroutput>TCP_CORK</computeroutput> (Linux) und
    <computeroutput>TCP_NOPUSH</computeroutput> (BSD).
    </para>

    <para>
    <computeroutput>writev()</computeroutput> ist wie ein
    Batch-<computeroutput>write()</computeroutput>.  Man bergibt ein
    Array mit Puffern, <computeroutput>writev()</computeroutput>
    schreibt sie alle hintereinander.  Der Unterschied ist normalerweise
    nicht meﾟbar, aber bei TCP-Servern macht er sich bemerktbar.
    </para>

    <programlisting>
    struct iovec x[2];
    x[0].iov_base=header; x[0].iov_len=strlen(header);
    x[1].iov_base=mapped_file; x[1].iov_len=file_size;
    writev(sock,x,2); /* returns bytes written */
    </programlisting>

    <para>
    <computeroutput>TCP_CORK</computeroutput> ist eine Socket-Option,
    die man mit <computeroutput>setsockopt</computeroutput> vor dem
    Schreiben setzt und nach dem letzten Schreiben wieder zurck setzt.
    Das sagt dem Kernel metaphorisch, daﾟ man die TCP-Flasche verkorkt
    h舁t, und erst am Ende lt man den Korken und alles sprudelt auf
    einmal ber das Netz hinaus.
    </para>

    <programlisting>
    int null=0, eins=1;

    /* Korken reinstecken */
    setsockopt(sock,IPPROTO_TCP,TCP_CORK,&eins,sizeof(eins));
    write(sock,header,strlen(header));
    write(sock,mapped_file,file_size);
    /* Korken ziehen */
    setsockopt(sock,IPPROTO_TCP,TCP_CORK,&null,sizeof(null));
    </programlisting>

    <para>
    <computeroutput>TCP_NOPUSH</computeroutput> ist das BSD-ﾄquivalent
    zu <computeroutput>TCP_CORK</computeroutput>.  Der einzige
    Unterschied ist, daﾟ man <computeroutput>TCP_NOPUSH</computeroutput>
    vor dem letzten Schreiben zurck setzen muﾟ, nicht danach.
    </para>
   </sect2>
   <sect2>
    <title>sendfile</title>

    <para>
    Typische hochskalierbare Server lesen immer Daten aus Dateien
    und schreiben sie ber das Netzwerk hinaus.  Dabei h舁t der
    Server-Prozeﾟ einen Puffer vor, in den er die Daten aus der Datei
    liest, und den er dann ber das Netz schreibt.  Hier werden also
    Daten unnig kopiert.  Es w舐e effizienter, wenn man die Datei
    direkt versenden knte.
    </para>

    <para>
    Das haben sich auch diverse Unix-Hersteller gedacht, und Microsoft
    hat einen solchen Syscall auch in Windows eingebaut.  Die meisten
    Server-Netzwerkkarten (alle Gigabit-Karten) beherrschen
    Scatter-Gather I/O, sozusagen
    <computeroutput>writev</computeroutput> in Hardware.  Das
    Betriebssystem kann dann die IP, TCP und Ethernet-Header in einem
    Puffer zusammenbauen, und die Netzwerkkarte holt sich den Inhalt des
    Pakets direkt aus dem Buffer Cache.  Dieses Zusammenspiel nennt man
    <phrase>zero copy TCP</phrase> und es ist sozusagen der heilige Gral
    der Netzwerkprogrammierung.
    </para>

    <para>
    Man kann die Daten aus dem Buffer Cache auch per
    <computeroutput>mmap</computeroutput> direkt in den User-Space
    Speicher einblenden, ohne daﾟ Daten kopiert werden mﾟten.  Leider
    kann Linux bei einem <computeroutput>write()</computeroutput> auf
    einen solchen Speicherbereich kein zero copy TCP initiieren, dazu
    muﾟ man <computeroutput>sendfile</computeroutput> benutzen.
    Trotzdem macht es Sinn, alle Daten wenn mlich mit
    <computeroutput>mmap</computeroutput> statt
    <computeroutput>read</computeroutput> zu lesen, weil man so im
    System Speicherplatz spart, den das System dann zum Cachen verwenden
    kann.
    </para>

    <para>
    Das groﾟe Problem bei <computeroutput>sendfile()</computeroutput> ist,
    daﾟ es jeder Anbieter mit einer anderen Semantik und anderen
    Argumenten implementiert hat.  Nicht einmal die freien Unixe haben
    sich an das gleiche Format gehalten.
    </para>
    </sect2>
    <sect2>
     <title>Sonstige Performance-Tweaks</title>

     <para>
     Auf heutiger Hardware ist <computeroutput>fork()</computeroutput>
     sehr effizient implementiert.  Die Datenbereiche der Prozesse
     werden nicht mehr kopiert, sondern es werden nur noch die
     Page-Mappings bernommen.  Das ist Grenordnungen effizienter als
     frher, aber bei einem Server-Prozeﾟ mit 20000 gemappten Dateien
     kann es sich schon um einen meﾟbaren Zeitraum handeln.  Es macht
     daher auch heute noch Sinn, in seinen Servern (z.B. fr den Aufruf
     von CGIs) <computeroutput>vfork()</computeroutput> vorzuziehen.
     </para>

     <para>
     Bei Servern mit sehr vielen offenen Deskriptoren kann
     <computeroutput>open()</computeroutput> plzlich meﾟbar langsamer
     werden.  Das liegt daran, daﾟ POSIX vorschreibt, daﾟ immer der
     kleinste unbelegte Deskriptor genommen werden muﾟ.  Das
     implementiert der Kernel, indem er Bitfelder linear durchgeht.  Es
     ist also theoretisch denkbar, daﾟ man ein paar Nanosekunden sparen
     kann, wenn man die untersten Dateideskriptoren mit
     <computeroutput>dup2</computeroutput> frei h舁t.  Diese Idee
     geistert seit Jahren ber diverse Mailinglisten; mir ist aber kein
     Fall bekannt, wo das tats臘hlich mal experimentell nachgewiesen
     worden ist.
     </para>

     <para>
     Auf neueren x86-Prozessoren gibt es neben dem
     Standard-Syscall-Mechanismus ber Software Interrupt 80 auch noch
     einen anderen Syscall-Mechanismus.  Der Linux Kernel hat relativ
     frischen Support dafr, indem er neben dem Programm im User Space
     noch eine weitere Code Page mit dem neuen Syscall einblendet.  Die
     Adresse der Page wird Programmen ber den ELF AUX Vektor bergeben
     (Daten auf dem Stack hinter <computeroutput>argv</computeroutput>
     und dem Environment).  Meinen Messungen zufolge reduziert sich
     damit die Syscall-Latenz auf die H舁fte.  In den HTTP-Benchmarks
     war die Auswirkung aber mit 2-5% nur knapp ber der statistischen
     Rauschgrenze.
     </para>
    </sect2>
  </sect1>
</article>