Mit langsamen Geraeten sprechen: Blockieren, Interrupts und Warteschlangen

Ein Prozessor fuehrt einen Befehl in einem Bruchteil einer Nanosekunde aus. Eine Platte antwortet in einer Zehntelmillisekunde. Das ist eine Luecke von sechs Groessenordnungen zwischen dem Geraet, das das Betriebssystem verwaltet, und dem, was verwaltet, und praktisch jede Entwurfsentscheidung bei der Ein- und Ausgabe existiert, um diese Luecke zu verbergen.

CPU register: ~0.3 ns
L1 cache:     ~1 ns
RAM:          ~30 ns
SSD:          ~100 000 ns
HDD:          ~8 000 000 ns

SSD / RAM = 3000xDie Luecke, zu deren Verbergung die Ein- und Ausgabeuntersystem existiert.

Das einfachste Modell ist blockierende Ein- und Ausgabe. Der Prozess ruft read(), der Kernel reicht die Anforderung an das Geraet weiter, und der aufrufende Thread wird aus der Laufwarteschlange genommen und schlaeft. Er dreht sich nicht in einer Schleife und bekommt keinen Prozessor: er kostet nichts, bis das Geraet fertig ist. Dann loest das Geraet einen Interrupt aus, der Kernel weckt den Thread, und read() liefert die Daten. Aus der Sicht des Programms ist ein blockierendes Lesen eine Zeile Code. Aus der Sicht des Systems ist es ein Kontextwechsel hinaus und ein weiterer zurueck, plus die Zeit, die das Geraet gebraucht hat.

Die Alternative zum Interrupt ist Polling: der Prozessor fragt das Geraet wiederholt, ob es fertig ist. Das klingt offensichtlich schlechter und ist es meistens auch, aber nicht immer. Ein Interrupt ist nicht kostenlos - der Prozessor muss anhalten, seinen Zustand sichern, den Handler ausfuehren, und der Handler zerstoert die Nutzlichkeit des Befehlscaches und der Sprungvorhersage. Schliesst ein Geraet alle paar Mikrosekunden eine Anforderung ab, wird die Interruptrate zum Engpass und die Maschine verbringt ihre Zeit damit, Handler zu betreten und zu verlassen. Deshalb entscheidet die Zeitskala: Interrupts fuer langsame, unvorhersehbare Geraete wie Platten und Tastaturen, Polling fuer schnelle, bei denen die Wartezeit kurz und bekannt ist. Netzwerkkarten unter hoher Last sind der klassische Fall, weshalb sie bei steigender Paketrate automatisch von Interrupts auf Polling umschalten.

polling:    10 000 000 spins/s, 1 core busy
interrupt:  no cost while the device is idle

slow device, 0.1 ms  -> interrupts win
fast device, 40 000 iops -> interrupts cost 4 ms/sDer Kompromiss in Zahlen. Keine der beiden Antworten ist generell richtig; die Zeitskala entscheidet.

Nun die Kosten, die ueberraschen. Ein Aufruf von read() ist kein Funktionsaufruf. Es ist ein kontrollierter Uebergang in den Kernel: der Prozessor schaltet in den Kernelmodus, Register werden gesichert, Argumente geprueft, Rechte geprueft, und bei der Rueckkehr wird nach anstehenden Signalen gesehen und moeglicherweise neu geplant. All das geschieht, bevor der Kernel auch nur ein Byte von irgendwo gelesen hat. Auf einem modernen Prozessor kostet ein leerer Systemaufruf zwischen 100 und 300 Nanosekunden, gegen etwa 2 Nanosekunden fuer einen Aufruf innerhalb desselben Prozesses. Das ist die Zahl, die einen guten Teil echter Leistungsprobleme erklaert.

size_t n = read(fd, buf, 4096);

call: ~2 ns
read(4096): ~200 ns
read(1): ~1000 ns

4096 calls instead of 1 -> 4000xDieselben Bytes, geliefert in einem Aufruf und in viertausend Aufrufen.

Setzt man diese beiden Zahlen zusammen, hoert ein bekannter Rat auf, eine Stilfrage zu sein. Ein Programm, das eine 1-MiB-Datei Byte fuer Byte liest, macht 1048576 Systemaufrufe. Bei 200 Nanosekunden each sind das etwa 0,21 Sekunden reiner Aufrufaufwand, bevor ueberhaupt ein Datenbyte beruehrt wurde - und das ist der optimistische Fall, in dem jedes Byte schon im Seitencache liegt. Dieselbe Datei in 4-KiB-Bloecken gelesen braucht 256 Aufrufe und etwa 51 Mikrosekunden Aufwand. Lesen in 64-KiB-Bloecken braucht 16 Aufrufe. Das Verhaeltnis zwischen der Byte-fuer-Byte-Fassung und der Blockfassung liegt in den Tausenden, und nichts davon hat damit zu tun, wie schnell die Platte ist.

Wenn ein Thread auf viele Geraete gleichzeitig warten muss, funktioniert blockierendes Lesen nicht: der erste Aufruf blockiert, und die anderen zehn Sockets sieht niemand mehr an. Die alte Antwort waren select() und poll(), die dem Kernel eine Liste von Deskriptoren geben und fragen, welche Daten haben. Beide sind linear in der Anzahl der Deskriptoren, bei zehntausend Verbindungen laeuft also jeder Aufruf die ganze Liste ab. epoll war die Abhilfe: die Deskriptoren werden einmal registriert, und der Kernel haelt die interessanten auf einer Bereitschaftsliste. Das Programm blockiert einmal in epoll_wait und bekommt nur die Sockets zurueck, bei denen wirklich etwas vorliegt.

io_uring wurde gebaut, um genau diesen Schritt zu entfernen. Statt Interesse zu registrieren und dann pro Operation einen Systemaufruf abzusetzen, schreibt das Programm eine Anforderung in eine Uebermittlungswarteschlange im gemeinsamen Speicher, und der Kernel schreibt das Ergebnis in eine Abschlusswarteschlange. Ein Systemaufruf kann einen Stapel von Dutzenden Lesevorgaengen uebermitteln, oder mit aktiviertem Polling-Modus gar keinen. Das ist ein Abschlussmodell: ein Ergebnis erscheint in der Abschlusswarteschlange, wenn das Lesen bereits geschehen ist. Der Unterschied zaehlt am meisten bei vielen kleinen Operationen, weil er N Systemaufrufe in ungefaehr einen verwandelt.

/* readiness model */
for (;;) {
  n = epoll_wait(ep, evs, 128, -1);
  for (i = 0; i < n; i++) read(evs[i].data.fd, buf, 4096);
}

/* completion model */
for (;;) {
  sqe = io_uring_get_sqe(&ring);
  io_uring_prep_read(sqe, fd, buf, 4096, 0);
  io_uring_submit(&ring);
}Zwei Modelle nebeneinander. Das erste fragt, ob es lesen darf; das zweite bestellt das Lesen und holt die Antwort ab.

Der praktische Unterschied zwischen beiden ist nicht philosophisch. Im Bereitschaftsmodell kostet jedes Ereignis einen Systemaufruf fuer das Warten plus einen fuer das Lesen. Im Abschlussmodell wird das Lesen im Speicher eingereiht und kostet gar keinen Uebergang. Fuer einen Server mit zehntausenden kleinen Operationen pro Sekunde ist das der Unterschied zwischen fast der ganzen Zeit im Kernel und fast der ganzen Zeit bei echter Arbeit. Es erklaert auch, warum die Zahlen so stark mit der Warteschlangentiefe schwanken: eine Operation im Flug kann ein schnelles Geraet niemals auslasten.

epoll: 1 submit per batch
io_uring: 1 submit for N reads

queue depth 1: 1 000 000 iops
queue depth 32: 3 000 000 iopsDieselbe Schnittstelle bei verschiedenen Warteschlangentiefen. Tiefe Warteschlangen machen schnelle Geraete nutzbar.

Pufferung ist der Sammelbegriff fuer alle Stellen, an denen Daten kopiert werden. Der Kernel haelt einen Seitencache, ein zweites Lesen derselben Datei erreicht die Platte also nie. Die C-Bibliothek haelt einen Puffer im Benutzerraum fuer stdio, fgetc() ruft den Kernel also meist gar nicht auf. Beides ist dieselbe Idee: die langsame Operation buendeln und ihre Kosten verteilen. Beides hat auch dieselben Kosten: was du geschrieben hast, liegt noch nicht zwingend auf dem Geraet.

Die praktischen Regeln, die daraus folgen. Setze nie eine kleine Operation ab, wo eine grosse genuegt: die Blockgroesse ist der groesste Hebel, und groessere Bloecke gewinnen, bis sie nicht mehr in den Cache passen. Rufe fsync nicht bei jedem Schreibvorgang auf, wenn Korrektheit es nicht wirklich verlangt, und dann buendle. Wenn ein Thread auf viele Geraete warten muss, nutze Bereitschafts- oder Abschlussbenachrichtigung statt eines Threads pro Verbindung, denn ein Thread kostet einen Stapel und einen Kontextwechsel. Und miss die Systemzeit getrennt von der Benutzerzeit: ein Programm, dessen Systemzeit die Benutzerzeit uebersteigt, spricht viel zu oft mit dem Kernel.