Die Entwicklung der Architektur des Handels- und Clearingsystems der Moskauer Börse. Teil 1

Hallo zusammen! Mein Name ist Sergey Kostanbaev, an der Börse entwickle ich den Kern des Handelssystems.

Wenn Hollywood-Filme die New York Stock Exchange zeigen, sieht es immer so aus: Menschenmassen, alle schreien etwas, schwenken Papiere, es herrscht völliges Chaos. Dies ist hier an der Moskauer Börse noch nie passiert, da der Handel von Anfang an elektronisch abgewickelt wurde und auf zwei Hauptplattformen basiert – Spectra (Forex-Markt) und ASTS (Devisen-, Aktien- und Geldmarkt). Und heute möchte ich über die Entwicklung der Architektur des Handels- und Clearingsystems ASTS, über verschiedene Lösungen und Erkenntnisse sprechen. Die Geschichte wird lang sein, deshalb musste ich sie in zwei Teile aufteilen.

Wir sind eine der wenigen Börsen weltweit, die Vermögenswerte aller Klassen handelt und ein umfassendes Spektrum an Börsendienstleistungen anbietet. Im vergangenen Jahr belegten wir beispielsweise den zweiten Platz weltweit in Bezug auf das Anleihehandelsvolumen, den 25. Platz unter allen Börsen und den 13. Platz in Bezug auf die Kapitalisierung unter den öffentlichen Börsen.

Für professionelle Handelsteilnehmer sind Parameter wie Reaktionszeit, Stabilität der Zeitverteilung (Jitter) und Zuverlässigkeit des gesamten Komplexes von entscheidender Bedeutung. Wir verarbeiten derzeit zig Millionen Transaktionen pro Tag. Die Verarbeitung jeder Transaktion durch den Systemkern dauert mehrere zehn Mikrosekunden. Natürlich haben Mobilfunkbetreiber an Silvester oder Suchmaschinen selbst eine höhere Arbeitsbelastung als wir, aber was die Arbeitsbelastung und die oben genannten Eigenschaften angeht, können sich meiner Meinung nach nur wenige mit uns messen. Dabei ist es uns wichtig, dass das System keine Sekunde langsamer wird, absolut stabil arbeitet und alle Nutzer auf Augenhöhe sind.

Eine kleine Geschichte

1994 wurde das australische ASTS-System an der Moskauer Interbanken-Währungsbörse (MICEX) eingeführt, und von diesem Moment an kann die russische Geschichte des elektronischen Handels gezählt werden. Im Jahr 1998 wurde die Börsenarchitektur modernisiert, um den Internethandel einzuführen. Seitdem hat die Geschwindigkeit der Implementierung neuer Lösungen und Architekturänderungen in allen Systemen und Subsystemen immer weiter zugenommen.

In jenen Jahren lief das Austauschsystem auf High-End-Hardware – äußerst zuverlässigen HP Superdome 9000-Servern (aufgebaut auf dem PA-RISC), in dem absolut alles dupliziert war: Eingabe-/Ausgabe-Subsysteme, Netzwerk, RAM (tatsächlich gab es ein RAID-Array von RAM), Prozessoren (Hot-Swap-fähig). Es war möglich, jede Serverkomponente zu ändern, ohne die Maschine anzuhalten. Wir haben uns auf diese Geräte verlassen und sie für nahezu ausfallsicher gehalten. Das Betriebssystem war ein Unix-ähnliches HP UX-System.

Doch seit etwa 2010 ist ein Phänomen entstanden, das Hochfrequenzhandel (HFT) oder Hochfrequenzhandel – kurz: Börsenroboter – genannt wird. In nur 2,5 Jahren hat sich die Belastung unserer Server um das 140-fache erhöht.

Mit der alten Architektur und Ausstattung war es unmöglich, einer solchen Belastung standzuhalten. Es war notwendig, sich irgendwie anzupassen.

Hauptseite

Anfragen an das Börsensystem können in zwei Arten unterteilt werden:

• Transaktionen. Wenn Sie Dollar, Aktien oder etwas anderes kaufen möchten, senden Sie eine Transaktion an das Handelssystem und erhalten eine Rückmeldung über den Erfolg.
• Informationsanfragen. Wenn Sie den aktuellen Preis erfahren, das Orderbuch oder die Indizes einsehen und dann Informationsanfragen senden möchten.

Schematisch lässt sich der Kern des Systems in drei Ebenen unterteilen:

• Die Kundenebene, auf der Makler und Kunden arbeiten. Sie alle interagieren mit Zugriffsservern.
• Gateway-Server sind Caching-Server, die alle Informationsanfragen lokal verarbeiten. Möchten Sie wissen, zu welchem ​​Preis die Aktien der Sberbank derzeit gehandelt werden? Die Anfrage geht an den Zugriffsserver.
• Möchte man aber Aktien kaufen, dann geht die Anfrage an den zentralen Server (Trade Engine). Für jeden Markttyp gibt es einen solchen Server, sie spielen eine entscheidende Rolle, für sie haben wir dieses System geschaffen.

Der Kern des Handelssystems ist eine clevere In-Memory-Datenbank, in der alle Transaktionen Börsentransaktionen sind. Die Basis wurde in C geschrieben, die einzigen externen Abhängigkeiten waren die libc-Bibliothek und es gab überhaupt keine dynamische Speicherzuweisung. Um die Verarbeitungszeit zu verkürzen, beginnt das System mit einem statischen Array-Satz und einer statischen Datenverschiebung: Zunächst werden alle Daten für den aktuellen Tag in den Speicher geladen, und es erfolgt kein weiterer Festplattenzugriff, alle Arbeiten werden nur im Speicher ausgeführt. Beim Systemstart sind alle Referenzdaten bereits sortiert, sodass die Suche sehr effizient funktioniert und zur Laufzeit nur wenig Zeit in Anspruch nimmt. Alle Tabellen werden mit aufdringlichen Listen und Bäumen für dynamische Datenstrukturen erstellt, sodass zur Laufzeit keine Speicherzuweisung erforderlich ist.

Lassen Sie uns kurz auf die Entwicklungsgeschichte unseres Handels- und Clearingsystems eingehen.
Die erste Version der Handels- und Clearingsystemarchitektur basierte auf der sogenannten Unix-Interaktion: Es wurden gemeinsamer Speicher, Semaphoren und Warteschlangen verwendet, und jeder Prozess bestand aus einem einzelnen Thread. Dieser Ansatz war Anfang der 1990er Jahre weit verbreitet.

Die erste Version des Systems enthielt zwei Gateway-Ebenen und einen zentralen Server des Handelssystems. Der Arbeitsablauf war so:

• Der Client sendet eine Anfrage, die das Gateway erreicht. Es prüft die Gültigkeit des Formats (jedoch nicht der Daten selbst) und weist fehlerhafte Transaktionen zurück.
• Wurde eine Informationsanfrage gesendet, wird diese lokal ausgeführt; Wenn es sich um eine Transaktion handelt, wird diese an den zentralen Server weitergeleitet.
• Anschließend verarbeitet die Handels-Engine die Transaktion, ändert den lokalen Speicher und sendet eine Antwort an die Transaktion und die Transaktion selbst zur Replikation mithilfe einer separaten Replikations-Engine.
• Das Gateway empfängt die Antwort vom zentralen Knoten und leitet sie an den Client weiter.
• Nach einiger Zeit empfängt das Gateway die Transaktion über den Replikationsmechanismus und führt sie dieses Mal lokal aus, wobei es seine Datenstrukturen ändert, sodass bei den nächsten Informationsanfragen die neuesten Daten angezeigt werden.

Tatsächlich beschreibt es ein Replikationsmodell, bei dem das Gateway die im Handelssystem durchgeführten Aktionen vollständig repliziert. Ein separater Replikationskanal stellte sicher, dass Transaktionen über mehrere Zugangsknoten hinweg in derselben Reihenfolge ausgeführt wurden.

Da der Code Single-Threaded war, wurde ein klassisches Schema mit Prozesszweigen verwendet, um viele Kunden zu bedienen. Da es jedoch sehr teuer war, die gesamte Datenbank zu forken, wurden schlanke Serviceprozesse verwendet, die Pakete von TCP-Sitzungen sammelten und sie in eine Warteschlange (SystemV Message Queue) übertrugen. Gateway und Trade Engine arbeiteten nur mit dieser Warteschlange und übernahmen Transaktionen von dort zur Ausführung. Es war nicht mehr möglich, eine Antwort darauf zu senden, da nicht klar war, welcher Serviceprozess es lesen sollte. Deshalb griffen wir auf einen Trick zurück: Jeder geforkte Prozess erstellte eine Antwortwarteschlange für sich selbst, und wenn eine Anfrage in die Eingangswarteschlange einging, wurde ihr sofort ein Tag für die Antwortwarteschlange hinzugefügt.

Das ständige Kopieren großer Datenmengen von Warteschlange zu Warteschlange verursachte Probleme, die insbesondere bei Informationsanfragen typisch sind. Deshalb haben wir einen weiteren Trick angewendet: Zusätzlich zur Antwortwarteschlange erstellte jeder Prozess auch gemeinsam genutzten Speicher (SystemV Shared Memory). Die Pakete selbst wurden darin abgelegt und in der Warteschlange wurde nur ein Tag gespeichert, der es ermöglichte, das Originalpaket zu finden. Dies half dabei, Daten im Prozessor-Cache zu speichern.

SystemV IPC enthält Dienstprogramme zum Anzeigen des Status von Warteschlangen-, Speicher- und Semaphorobjekten. Wir haben dies aktiv genutzt, um zu verstehen, was zu einem bestimmten Zeitpunkt im System passierte, wo sich Pakete ansammelten, was blockiert wurde usw.

Erste Upgrades

Zunächst haben wir das Single-Process-Gateway abgeschafft. Der wesentliche Nachteil bestand darin, dass es entweder eine Replikationstransaktion oder eine Informationsanfrage eines Clients verarbeiten konnte. Und wenn die Last zunimmt, dauert die Verarbeitung von Anforderungen durch Gateway länger und kann den Replikationsfluss nicht verarbeiten. Wenn der Kunde außerdem eine Transaktion gesendet hat, müssen Sie nur deren Gültigkeit überprüfen und sie weiterleiten. Daher haben wir den einzelnen Gateway-Prozess durch mehrere Komponenten ersetzt, die parallel ausgeführt werden können: Multithread-Informations- und Transaktionsprozesse, die unabhängig voneinander in einem gemeinsam genutzten Speicherbereich unter Verwendung von RW-Sperren ausgeführt werden. Und gleichzeitig haben wir Versand- und Replikationsprozesse eingeführt.

Auswirkungen des Hochfrequenzhandels

Die obige Version der Architektur existierte bis 2010. Mittlerweile waren wir mit der Leistung der HP Superdome-Server nicht mehr zufrieden. Darüber hinaus war die PA-RISC-Architektur praktisch tot, der Hersteller bot keine nennenswerten Updates an. Infolgedessen begannen wir mit der Umstellung von HP UX/PA RISC auf Linux/x86. Der Übergang begann mit der Anpassung der Zugangsserver.

Warum mussten wir die Architektur erneut ändern? Tatsache ist, dass der Hochfrequenzhandel das Lastprofil auf dem Systemkern deutlich verändert hat.

Nehmen wir an, wir haben eine kleine Transaktion, die zu einer erheblichen Preisänderung geführt hat – jemand hat eine halbe Milliarde Dollar gekauft. Nach ein paar Millisekunden bemerken dies alle Marktteilnehmer und beginnen mit der Korrektur. Natürlich reihen sich Anfragen in einer riesigen Warteschlange an, deren Bereinigung durch das System lange dauern wird.

In diesem 50-ms-Intervall beträgt die durchschnittliche Geschwindigkeit etwa 16 Transaktionen pro Sekunde. Wenn wir das Fenster auf 20 ms reduzieren, erhalten wir eine durchschnittliche Geschwindigkeit von 90 Transaktionen pro Sekunde, wobei die Spitze 200 Transaktionen erreicht. Mit anderen Worten: Die Belastung ist nicht konstant und kann plötzlich auftreten. Und die Schlange an Anfragen muss immer schnell bearbeitet werden.

Aber warum gibt es überhaupt eine Warteschlange? In unserem Beispiel bemerkten also viele Benutzer die Preisänderung und schickten entsprechende Transaktionen. Sie kommen zum Gateway, es serialisiert sie, legt eine bestimmte Reihenfolge fest und sendet sie an das Netzwerk. Router mischen die Pakete und leiten sie weiter. Wessen Paket zuerst ankam, diese Transaktion hat „gewonnen“. Infolgedessen bemerkten Börsenkunden, dass die Wahrscheinlichkeit einer schnellen Verarbeitung zunahm, wenn dieselbe Transaktion von mehreren Gateways gesendet wurde. Bald begannen Börsenroboter, Gateway mit Anfragen zu bombardieren, und es entstand eine Lawine von Transaktionen.

Eine neue Runde der Evolution

Nach umfangreichen Tests und Recherchen sind wir auf den Echtzeit-Betriebssystemkernel umgestiegen. Hierfür haben wir uns für RedHat Enterprise MRG Linux entschieden, wobei MRG für Messaging Real-Time Grid steht. Der Vorteil von Echtzeit-Patches besteht darin, dass sie das System für die schnellstmögliche Ausführung optimieren: Alle Prozesse werden in einer FIFO-Warteschlange aufgereiht, Kerne können isoliert werden, es gibt keine Auswürfe, alle Transaktionen werden in strenger Reihenfolge verarbeitet.

Rot – Arbeiten mit einer Warteschlange in einem regulären Kernel, Grün – Arbeiten in einem Echtzeitkernel.

Aber auf regulären Servern eine niedrige Latenz zu erreichen, ist nicht so einfach:

• Der SMI-Modus, der in der x86-Architektur die Grundlage für die Arbeit mit wichtigen Peripheriegeräten ist, stört stark. Die Verarbeitung aller Arten von Hardwareereignissen und die Verwaltung von Komponenten und Geräten erfolgt durch die Firmware im sogenannten transparenten SMI-Modus, bei dem das Betriebssystem überhaupt nicht sieht, was die Firmware tut. In der Regel bieten alle großen Hersteller spezielle Erweiterungen für Firmware-Server an, die eine Reduzierung des SMI-Verarbeitungsaufwands ermöglichen.
• Es sollte keine dynamische Steuerung der Prozessorfrequenz erfolgen, dies führt zu zusätzlichen Ausfallzeiten.
• Wenn das Dateisystemprotokoll geleert wird, treten bestimmte Prozesse im Kernel auf, die unvorhersehbare Verzögerungen verursachen.
• Sie müssen auf Dinge wie CPU-Affinität, Interrupt-Affinität und NUMA achten.

Ich muss sagen, dass das Thema der Einrichtung von Linux-Hardware und -Kernel für die Echtzeitverarbeitung einen separaten Artikel verdient. Wir haben viel Zeit mit Experimentieren und Recherchieren verbracht, bevor wir ein gutes Ergebnis erzielt haben.

Bei der Umstellung von PA-RISC-Servern auf x86 mussten wir praktisch nicht viel am Systemcode ändern, wir haben ihn lediglich angepasst und neu konfiguriert. Gleichzeitig haben wir mehrere Fehler behoben. Beispielsweise zeigten sich schnell die Folgen der Tatsache, dass PA RISC ein Big-Endian-System und x86 ein Little-Endian-System war: Beispielsweise wurden Daten falsch gelesen. Der schwierigere Fehler war, dass PA RISC verwendet immer gleichbleibend (Sequenziell konsistent) Speicherzugriff, während x86 Lesevorgänge neu anordnen kann, sodass Code, der auf einer Plattform absolut gültig war, auf einer anderen fehlerhaft wurde.

Nach der Umstellung auf x86 stieg die Leistung fast um das Dreifache, die durchschnittliche Transaktionsverarbeitungszeit sank auf 60 μs.

Schauen wir uns nun genauer an, welche wesentlichen Änderungen an der Systemarchitektur vorgenommen wurden.

Heißes Reserve-Epos

Beim Umstieg auf Standardserver war uns bewusst, dass diese weniger zuverlässig waren. Daher gingen wir bei der Erstellung einer neuen Architektur von vornherein von der Möglichkeit des Ausfalls eines oder mehrerer Knoten aus. Daher wurde ein Hot-Standby-System benötigt, das sehr schnell auf Backup-Maschinen umschalten konnte.

Darüber hinaus gab es weitere Anforderungen:

• Unter keinen Umständen sollten Sie verarbeitete Transaktionen verlieren.
• Das System muss für unsere Infrastruktur absolut transparent sein.
• Clients sollten keine unterbrochenen Verbindungen sehen.
• Reservierungen sollten nicht zu erheblichen Verzögerungen führen, da dies ein kritischer Faktor für den Umtausch ist.

Bei der Erstellung eines Hot-Standby-Systems haben wir solche Szenarien wie Doppelausfälle nicht berücksichtigt (z. B. funktioniert das Netzwerk auf einem Server nicht mehr und der Hauptserver ist eingefroren); hat die Möglichkeit von Fehlern in der Software nicht berücksichtigt, da diese beim Testen festgestellt werden; und die fehlerhafte Bedienung der Hardware nicht berücksichtigt.

Als Ergebnis kamen wir zu folgendem Schema:

• Der Hauptserver interagierte direkt mit den Gateway-Servern.
• Alle auf dem Hauptserver empfangenen Transaktionen wurden über einen separaten Kanal sofort auf den Backup-Server repliziert. Der Schiedsrichter (Gouverneur) koordinierte den Wechsel, wenn Probleme auftraten.

  

• Der Hauptserver verarbeitete jede Transaktion und wartete auf die Bestätigung vom Backup-Server. Um die Latenz auf ein Minimum zu beschränken, haben wir es vermieden, auf den Abschluss der Transaktion auf dem Backup-Server zu warten. Da die Zeit, die eine Transaktion für die Übertragung durch das Netzwerk benötigte, mit der Ausführungszeit vergleichbar war, wurde keine zusätzliche Latenz hinzugefügt.
• Wir konnten nur den Verarbeitungsstatus der Haupt- und Backup-Server für die vorherige Transaktion überprüfen, und der Verarbeitungsstatus der aktuellen Transaktion war unbekannt. Da wir immer noch Single-Thread-Prozesse verwendeten, hätte das Warten auf eine Antwort von Backup den gesamten Verarbeitungsfluss verlangsamt, also gingen wir einen vernünftigen Kompromiss ein: Wir überprüften das Ergebnis der vorherigen Transaktion.

Das Schema funktionierte wie folgt.

Nehmen wir an, der Hauptserver reagiert nicht mehr, die Gateways kommunizieren jedoch weiterhin. Auf dem Backup-Server tritt eine Zeitüberschreitung auf, er kontaktiert den Governor, der ihm die Rolle des Hauptservers zuweist, und alle Gateways schalten auf den neuen Hauptserver um.

Kommt der Hauptserver wieder online, löst dies ebenfalls einen internen Timeout aus, da seit einer bestimmten Zeit keine Anrufe vom Gateway an den Server erfolgt sind. Dann wendet er sich ebenfalls an den Gouverneur und schließt ihn aus dem Plan aus. Dadurch arbeitet die Börse bis zum Ende des Handelszeitraums mit einem Server. Da die Wahrscheinlichkeit eines Serverausfalls recht gering ist, wurde dieses Schema als durchaus akzeptabel angesehen; es enthielt keine komplexe Logik und war leicht zu testen.

To be continued.

Source: habr.com