Unix / Linux mit geringer Latenz

11

Die meisten Programmierjobs mit niedriger Latenz / hoher Frequenz (basierend auf Jobspezifikationen) scheinen auf Unix-Plattformen implementiert zu sein. In vielen Spezifikationen stellen sie besondere Anforderungen an Personen mit Linux-Erfahrung mit geringer Latenz.

Angenommen, dies bedeutet kein Echtzeit-Linux-Betriebssystem. Könnten mir die Leute helfen, worauf sich dies beziehen könnte? Ich weiß, dass Sie die CPU-Affinität für Threads festlegen können, aber ich gehe davon aus, dass sie viel mehr verlangen.

Kernel-Tuning? (obwohl ich gehört habe, dass Hersteller wie Solarflare sowieso Kernel-Bypass-Netzwerkkarten produzieren)?

Was ist mit DMA oder möglicherweise gemeinsam genutztem Speicher zwischen Prozessen? Wenn mir Leute kurze Ideen geben könnten, könnte ich auf Google recherchieren.

(Für diese Frage ist wahrscheinlich jemand erforderlich, der mit dem Hochfrequenzhandel vertraut ist.)

user997112
quelle
2
Kernel-Tuning ist der Weg, um ein Nicht-Echtzeit-Betriebssystem so Echtzeit wie möglich zu machen. Das Feststecken von Fäden ist ebenfalls obligatorisch. Sie können mehr darüber in diesem Artikel lesen: coralblocks.com/index.php/2014/04/…
rdalmeida
Auch verwandt: stackoverflow.com/q/15702601/632951
Pacerier

Antworten:

26

Ich habe eine Menge Arbeit geleistet, um HFT-Gruppen in IB- und Hedge-Fonds-Umgebungen zu unterstützen. Ich werde aus der Sysadmin-Ansicht antworten, aber einiges davon gilt auch für die Programmierung in solchen Umgebungen.

Es gibt einige Dinge, nach denen ein Arbeitgeber normalerweise sucht, wenn er sich auf die Unterstützung bei geringer Latenz bezieht. Einige davon sind "Rohgeschwindigkeits" -Fragen (wissen Sie, welche Art von 10-g-Karte Sie kaufen und in welchen Steckplatz Sie sie stecken müssen?), Aber in mehr geht es um die Art und Weise, in der sich eine Hochfrequenz-Handelsumgebung von einer herkömmlichen unterscheidet Unix-Umgebung. Einige Beispiele:

  • Unix ist traditionell so optimiert, dass es das Ausführen einer großen Anzahl von Prozessen unterstützt, ohne dass Ressourcen verloren gehen. In einer HFT-Umgebung möchten Sie jedoch wahrscheinlich eine Anwendung mit einem absoluten Minimum an Overhead für die Kontextumschaltung usw. ausführen . Als klassisches kleines Beispiel ermöglicht das Aktivieren von Hyperthreading auf einer Intel-CPU, dass mehrere Prozesse gleichzeitig ausgeführt werden. Dies hat jedoch erhebliche Auswirkungen auf die Leistung der Geschwindigkeit, mit der jeder einzelne Prozess ausgeführt wird. Als Programmierer müssen Sie sich ebenfalls die Kosten für Abstraktionen wie Threading und RPC ansehen und herausfinden, wo eine monolithischere Lösung - obwohl sie weniger sauber ist - Overhead vermeidet.

  • TCP / IP wird normalerweise optimiert, um Verbindungsabbrüche zu vermeiden und die verfügbare Bandbreite effizient zu nutzen. Wenn Ihr Ziel darin besteht, aus einer sehr schnellen Verbindung die geringstmögliche Latenz zu erzielen, anstatt aus einer eingeschränkteren Verbindung die höchstmögliche Bandbreite herauszuholen, sollten Sie die Optimierung des Netzwerkstapels anpassen. Von der Programmierseite aus sollten Sie sich ebenfalls die verfügbaren Socket-Optionen ansehen und herausfinden, welche Standardeinstellungen besser auf Bandbreite und Zuverlässigkeit abgestimmt sind als auf die Reduzierung der Latenz.

  • Wie beim Netzwerk, so auch beim Speicher - möchten Sie wissen, wie Sie ein Problem mit der Speicherleistung von einem Anwendungsproblem unterscheiden und welche E / A-Nutzungsmuster die Leistung Ihres Programms am wenigsten beeinträchtigen (als Erfahren Sie beispielsweise, wo sich die Komplexität der Verwendung von asynchronen E / A für Sie auszahlen kann und welche Nachteile dies hat.

  • Und noch schmerzhafter: Wir Unix-Administratoren möchten so viele Informationen wie möglich über den Status der von uns überwachten Umgebungen erhalten. Daher führen wir gerne Tools wie SNMP-Agenten, aktive Überwachungstools wie Nagios und Datenerfassungstools wie sar (1) aus. In einer Umgebung, in der Kontextwechsel absolut minimiert und die Verwendung von Festplatten- und Netzwerk-E / A streng kontrolliert werden muss, müssen wir jedoch den richtigen Kompromiss zwischen den Kosten für die Überwachung und der Bare-Metal-Leistung der überwachten Boxen finden. In ähnlicher Weise, welche Techniken verwenden Sie, die das Codieren erleichtern, aber Ihre Leistung kosten?

Schließlich gibt es noch andere Dinge, die mit der Zeit kommen. Tricks und Details, die Sie mit Erfahrung lernen. Diese sind jedoch spezialisierter (wann verwende ich epoll? Warum arbeiten zwei Modelle von HP Servern mit theoretisch identischen PCIe-Controllern so unterschiedlich?), Binden stärker an das, was Ihr spezifischer Shop verwendet, und ändern sich eher von einem Jahr zum anderen .

jimwise
quelle
1
Vielen Dank, obwohl ich an einer Programmierantwort interessiert war, war diese sehr nützlich und informativ.
user997112
5
@ user997112 Dies ist eine Programmierantwort. Wenn es nicht so aussieht, lesen Sie es weiter, bis es so ist :)
Tim Post
15

Zusätzlich zu der hervorragenden Antwort zur Hardware- / Setup-Optimierung von @jimwise bedeutet "Linux mit geringer Latenz":

  • C ++ aus Gründen des Determinismus (keine überraschende Verzögerung beim Einsetzen des GC), des Zugriffs auf Einrichtungen auf niedriger Ebene (E / A, Signale), Sprachleistung (volle Nutzung von TMP und STL, Typensicherheit).
  • bevorzugen Sie Speed-over-Memory:> 512 GB RAM sind üblich; Datenbanken sind speicherinterne, im Voraus zwischengespeicherte oder exotische NoSQL-Produkte.
  • Algorithmusauswahl: so schnell wie möglich im Vergleich zu vernünftigen / verständlichen / erweiterbaren, z. B. sperrfreien Mehrbit-Arrays anstelle von Array-von-Objekten-mit-Bool-Eigenschaften.
  • Vollständige Nutzung von Betriebssystemfunktionen wie Shared Memory zwischen Prozessen auf verschiedenen Kernen.
  • sichern. HFT-Software befindet sich normalerweise an einer Börse, sodass Malware-Möglichkeiten nicht akzeptabel sind.

Viele dieser Techniken überschneiden sich mit der Spieleentwicklung, was ein Grund dafür ist, dass die Finanzsoftwareindustrie kürzlich überflüssige Spieleprogrammierer aufnimmt (zumindest bis sie ihre Mietrückstände bezahlen).

Das zugrunde liegende Bedürfnis besteht darin, in der Lage zu sein, einen Strom von Marktdaten mit sehr hoher Bandbreite wie Wertpapierpreise (Aktien, Rohstoffe, Devisen) abzuhören und dann auf der Grundlage des Wertpapiers, des Preises, eine sehr schnelle Kauf- / Verkaufs- / Nichtstun-Entscheidung zu treffen und aktuelle Bestände.

Natürlich kann das alles auch spektakulär schief gehen .


Also werde ich auf den Punkt der Bit-Arrays näher eingehen . Nehmen wir an, wir haben ein Hochfrequenz-Handelssystem, das mit einer langen Liste von Aufträgen arbeitet (Kaufen Sie 5.000 IBM, verkaufen Sie 10.000 DELL usw.). Angenommen, wir müssen schnell feststellen, ob alle Aufträge erfüllt sind, damit wir mit der nächsten Aufgabe fortfahren können. In der traditionellen OO-Programmierung sieht dies folgendermaßen aus:

class Order {
  bool _isFilled;
  ...
public:
  inline bool isFilled() const { return _isFilled; }
};

std::vector<Order> orders;
bool needToFillMore = std::any_of(orders.begin(), orders.end(), 
  [](const Order & o) { return !o.isFilled(); } );

Die algorithmische Komplexität dieses Codes wird O (N) sein, da es sich um einen linearen Scan handelt. Werfen wir einen Blick auf das Leistungsprofil in Bezug auf Speicherzugriffe: Jede Iteration der Schleife in std :: any_of () ruft o.isFilled () auf, das inline ist, und wird so zu einem Speicherzugriff von _isFilled, 1 Byte (oder 4 abhängig von Ihrer Architektur, dem Compiler und den Compilereinstellungen) in einem Objekt von insgesamt 128 Bytes. Wir greifen also auf 1 Byte pro 128 Byte zu. Wenn wir das 1-Byte lesen, was im schlimmsten Fall angenommen wird, erhalten wir einen CPU-Datencache-Fehler. Dies führt zu einer Leseanforderung an den RAM, die eine ganze Zeile aus dem RAM liest ( siehe hier für weitere Informationen ), um nur 8 Bits auszulesen. Das Speicherzugriffsprofil ist also proportional zu N.

Vergleichen Sie dies mit:

const size_t ELEMS = MAX_ORDERS / sizeof (int);
unsigned int ordersFilled[ELEMS];

bool needToFillMore = std::any_of(ordersFilled, &ordersFilled[ELEMS+1],
   [](int packedFilledOrders) { return !(packedOrders == 0xFFFFFFFF); }

Das Speicherzugriffsprofil davon ist unter der Annahme des schlimmsten Falls ELEMS geteilt durch die Breite einer RAM-Leitung (variiert - kann zweikanalig oder dreikanalig sein usw.).

Tatsächlich optimieren wir Algorithmen für Speicherzugriffsmuster. Es hilft keine RAM-Größe - es ist die Größe des CPU-Datencaches, die diesen Bedarf verursacht.

Hilft das?


Auf YouTube gibt es einen ausgezeichneten CPPCon-Vortrag über Programmierung mit geringer Latenz (für HFT): https://www.youtube.com/watch?v=NH1Tta7purM

JBRWilkinson
quelle
"Mehrbit-Arrays anstelle von Array-von-Objekten-mit-Bool-Eigenschaften" Was meinen Sie damit?
user997112
1
Ich habe mit Beispielen und Links ausgearbeitet.
JBRWilkinson
Wenn Sie noch einen Schritt weiter gehen - anstatt ein ganzes Byte zu verwenden, um anzuzeigen, ob eine Bestellung ausgeführt wird oder nicht -, können Sie einfach ein einzelnes Bit verwenden. In einer einzelnen Cacheline (64 Byte) können Sie also den Status von 256 Bestellungen darstellen. Also - weniger Fehlschläge.
Quixver
Wenn Sie lineare Speicher-Scans durchführen, kann der Hardware-Prefetcher Ihre Daten hervorragend laden. Vorausgesetzt, Sie greifen nacheinander oder schrittweise auf den Speicher zu oder etwas Einfaches. Wenn Sie jedoch auf nicht sequentielle Weise auf den Speicher zugreifen, wird der CPU-Prefetcher verwirrt. ZB eine binäre Suche. An diesem Punkt kann der Programmierer der CPU mit Hinweisen helfen - _mm_prefetch.
Quixver
-2

Da ich nicht ein oder zwei Hochfrequenzsoftware in Produktion genommen hatte, würde ich die wichtigsten Dinge sagen:

  1. Hardwarekonfiguration und Systemadministratoren definieren zusammen mit Netzwerktechnikern NICHT das gute Ergebnis der Anzahl der vom Handelssystem verarbeiteten Aufträge, können sie jedoch erheblich herabstufen, wenn sie die oben beschriebenen Grundlagen nicht kennen.
  2. Die einzige Person, die das System tatsächlich dazu bringt, Hochfrequenzhandel zu betreiben, ist ein Informatiker, der den Code in c ++ zusammenstellt

    Zu den verwendeten Kenntnissen gehört

    A. Vergleichen und Tauschen von Operationen.

    • wie CAS im Prozessor verwendet wird und wie der Computer es unterstützt, um in der sogenannten No-Locking-Strukturverarbeitung verwendet zu werden. Oder sperrenfreie Verarbeitung. Ich werde hier nicht ein ganzes Buch schreiben. Kurz gesagt, der GNU-Compiler und der Microsoft-Compiler unterstützen die direkte Verwendung von CAS-Anweisungen. Es ermöglicht Ihrem Code, "No.Wair" zu haben, während Sie ein Element aus der Warteschlange extrahieren oder ein neues in die Warteschlange stellen.
  3. Der talentierte Wissenschaftler wird mehr verwenden. Er sollte in den letzten neuen "Mustern" eines finden, das zuerst in Java erschien. Wird als DISRUPTOR-Muster bezeichnet. Fold in LMAX Exchange in Europa erklärte der Hochfrequenz-Community, dass die threadbasierte Nutzung in modernen Prozessoren die Verarbeitungszeit bei der Freigabe des Speichercaches durch die CPU verlieren würde, wenn die Daya-Warteschlange nicht an der Größe des modernen CPU-Cache = 64 ausgerichtet ist

    Für dieses Readon haben sie einen Java-Code veröffentlicht, mit dem Multithreading-Prozesse den Hardware-CPU-Cache ohne Konfliktlösung korrekt verwenden können. Und ein guter Informatiker MUSS feststellen, dass das Muster bereits auf c ++ portiert wurde, oder sich selbst portieren.

    Dies ist eine Kompetenz, die weit über jede Administratorkonfiguration hinausgeht. Dies ist heute im Herzen der Hochfrequenz.

  4. Der Informatiker muss viel C ++ - Code schreiben, um nicht nur den QS-Leuten zu helfen. Aber auch zu
    • validieren in der Händler Gesicht nachweislich erreichte Geschwindigkeit
    • verurteilen verwendete verschiedene alte Technologien und entlarvte sie mit seinem eigenen Code, um zu zeigen, dass sie keine guten Ergebnisse liefern
    • Schreiben Sie Ihren eigenen C ++ - Code für die Multithreading-Kommunikation, der auf der bewährten Geschwindigkeit des Puppes / Select-Kernels basiert, anstatt wieder alte Technologien zu verwenden. Ich werde Ihnen ein Beispiel geben - moderne TCP-Bibliothek ist ICE. Und Leute, die es getan haben, sind hell. Ihre Prioritäten lagen jedoch im Bereich der Kompatibilität mit vielen Sprachen. So. Sie können es in c ++ besser machen. Suchen Sie also nach Beispielen mit der höchsten Leistung, die auf dem ASYNCHRONOUS-Auswahlaufruf basieren. Und gehen Sie nicht für mehrere Verbraucher mehrere Hersteller - nicht für HF.
      Und Sie werden erstaunt sein, dass die Pipe NUR FÜR die Kernel-Benachrichtigung über eingetroffene Nachrichten verwendet wird. Sie können dort die 64-Bit-Nachrichtennummer eingeben. Für Inhalte gehen Sie jedoch zu Ihrer nicht sperrenden CAS-Warteschlange. Ausgelöst durch asynchronen Kernelaufruf select().
    • Außerdem. Erfahren Sie, wie Sie Ihrem Thread, der Ihre Nachrichten weiterleitet / in die Warteschlange stellt, eine C ++ - Thread-Affinität zuweisen. Dieser Thread sollte eine Kernaffinität haben. Niemand sollte die gleiche CPU-Kernnummer verwenden.
    • und so weiter.

Wie Sie sehen können, ist Hochfrequenz ein ENTWICKLUNGSFELD. Sie können nicht nur ein C ++ - Programmierer sein, um erfolgreich zu sein.

Und wenn ich sage, um erfolgreich zu sein, meine ich, dass der Hedgefonds, für den Sie arbeiten würden, Tourbemühungen als jährliche Vergütung anerkennt, die über die Anzahl der Personen und Personalvermittler hinausgeht, über die gesprochen wird.

Die Zeiten einfacher FAQ zu Konstruktoren / Destruktoren sind für immer vorbei. Und c ++… selbst wurde mit neuen Compilern migriert, um Sie von der Speicherverwaltung zu entlasten und die Nichtvererbung von großer Tiefe in Klassen zu erzwingen. Zeitverschwendung. Das Paradigma der Wiederverwendung von Code hat sich geändert. Es geht nicht nur darum, wie viele Klassen Sie in Polymorph erstellt haben. Es geht um die direkt bestätigte Zeitleistung von Code, den Sie wiederverwenden können.

Sie haben also die Wahl, ob Sie dort in die Lernkurve einsteigen möchten oder nicht. Es wird niemals ein Stoppschild treffen.

alex p
quelle
6
Möglicherweise möchten Sie sich um Rechtschreibung und Formatierung bemühen. In seiner jetzigen Form ist dieser Beitrag kaum nachvollziehbar.
CodesInChaos
1
Sie beschreiben die Situation vor 10 Jahren. Hardwarebasierte Lösungen übertreffen heutzutage leicht reines C ++, egal wie optimiert Ihr C ++ ist.
Sjoerd
Für diejenigen, die wissen möchten, was eine hardwarebasierte Lösung ist - es handelt sich meistens um FPGA-Lösungen, bei denen Code tatsächlich in den schnellen Speicher gebrannt und nicht geändert wird, ohne dass der sogenannte ROM-Speicher erneut verwendet wird. Schreibgeschützt
Alex p
@alexp Du weißt eindeutig nicht, wovon du sprichst. FPGA ist etwas anderes als "Code, der in den schnellen Speicher gebrannt wird".
Sjoerd