Eine Matching Engine in Rust entwerfen: Price-Time Priority ohne GC-Pausen

Eine Matching Engine an einer Spot-Börse hat eine eng umrissene Aufgabe. Sie nimmt einen geordneten Strom von Commands - neue Order, Cancel, Replace -, wendet sie unter Price-Time Priority auf ein Order Book an und gibt einen geordneten Strom von Events aus: Trades, Buch-Updates, Rejects, Bestätigungen.

Alles Schwierige daran kommt aus drei Randbedingungen, die auf dieser Aufgabe liegen: Das Ergebnis muss bei jedem Replay derselben Eingabe identisch sein, der Rest einer teilweise ausgeführten Order muss seinen Platz in der Queue behalten, und der Latency-Tail darf sich bei einem Burst nicht bewegen.

Das Order Book ist ein sortierter Index von Preisleveln über FIFO-Queues

Das Buch besteht aus zwei Seiten, jede eine preisgeordnete Sammlung von Leveln. Ein Level ist keine Zahl - es ist eine Queue ruhender Orders zu diesem Preis, in Ankunftsreihenfolge. Matching berührt das beste Level ständig und die tiefen Level selten, deshalb wird die Struktur nach diesem Zugriffsmuster gewählt und nicht nach Eleganz.

• Preise sind ganzzahlige Ticks, nie Fließkomma - ein Tick ist die Einheit des Instruments, und Vergleich und Arithmetik auf Ganzzahlen sind exakt
• Jede Seite hält ihre Level in Preisreihenfolge, mit dem besten Preis ohne Suche erreichbar - der Top of Book wird bei jedem einzelnen Command gelesen
• Ein Level hält eine FIFO-Queue ruhender Orders sowie die aggregierte ruhende Menge, damit das Aggregat nicht durch Durchlaufen der Queue neu berechnet werden muss
• Orders liegen in einem vorab allokierten Slab und werden über Index-Handles referenziert, und die Queue ist intrusiv: Die Vorwärts- und Rückwärtsverweise leben im Order-Record selbst
• Eine separate Map von Client-Order-ID auf Slab-Handle macht Cancel und Replace zu einem direkten Lookup, sodass ein Cancel nie das Buch durchsucht
• Das Entfernen aus einer Queue geschieht per Handle, nicht per Suche - ein Cancel einer tief liegenden ruhenden Order kostet genauso viel wie ein Cancel am Top of Book

Die Folge intrusiver Queues und Index-Handles ist, dass eine ruhende Order sich zu Lebzeiten nie im Speicher bewegt. Ihre Queue-Position ist eine Eigenschaft ihrer Verweise und nicht davon, wo sie zufällig liegt - genau das macht Teilausführungen später billig.

Price-Time Priority ist eine Schleife über Level, dann über eine Queue

Eine eingehende aggressive Order läuft die Gegenseite vom besten Preis nach innen ab. Auf jedem Level durchläuft sie die FIFO-Queue von vorn. Sie stoppt, wenn der Levelpreis für die eingehende Order nicht mehr akzeptabel ist oder wenn die eingehende Menge null erreicht.

• Das beste Gegenlevel nehmen; kreuzt sein Preis den eingehenden Limitpreis nicht, stoppen
• Die vorderste Order dieser Level-Queue nehmen - sie ist die älteste zu diesem Preis, und Zeitpriorität heißt, sie wird zuerst ausgeführt
• Die gehandelte Menge ist die kleinere der beiden Restmengen; der Trade-Preis ist der Preis der ruhenden Order, denn die ruhende Order hat die Bedingungen gesetzt
• Beide Reste dekrementieren, das Trade-Event ausgeben und das Level-Aggregat dekrementieren
• Erreicht der Rest der ruhenden Order null, wird sie aus der Queue ausgehängt und ihr Slab-Slot zurückgegeben; wird das Level leer, wird das Level entfernt
• Wiederholen, bis die eingehende Menge null ist oder kein akzeptables Level mehr bleibt

Die Semantik der Ordertypen wird an der Grenze dieser Schleife entschieden, nicht in ihr. Immediate-or-Cancel verwirft den Rest, statt ihn ruhen zu lassen. Fill-or-Kill macht zuerst einen Trockendurchlauf und führt entweder ganz aus oder lehnt ab. Post-Only lehnt ab, wenn die Order bei Ankunft kreuzen würde. Diese außerhalb der Schleife zu halten heißt, dass die Schleife der einzige Ort bleibt, an dem sich der Buchzustand ändert.

Self-Trade Prevention, Mindestmengen sowie Tick- und Lot-Validierung gehören ebenfalls vor die Schleife. Eine Order, die das Matching erreicht, ist bereits als wohlgeformt erwiesen, sodass die Schleife keine Fehlerzweige hat, die sie bremsen oder uneins machen könnten.

Determinismus macht den Tail vorhersagbar, und Allokation zerstört ihn

Die durchschnittliche Latenz ist selten das Problem. Das Problem ist die schlechteste Messung während eines Bursts - also dann, wenn die Engine am meisten zählt und eine Stop-the-World-Pause am wahrscheinlichsten hineinfällt. Unter einer Managed Runtime mit Garbage Collector wird diese Pause vom Collector geplant und nicht von Ihnen, und sie landet mitten im Burst, der den Müll erzeugt hat.

Manuelle Allokation ist eine kleinere Ausgabe desselben Problems. Ein Allzweck-Allokator kann Free Lists durchlaufen, ein Lock nehmen oder den Kernel um mehr Speicher bitten, und genau dieser Aufruf taucht im Tail auf. Die Lösung ist in beiden Fällen dieselbe: auf dem Hot Path überhaupt nicht allokieren.

• Order-Records, Level-Records und Event-Buffer stammen aus beim Start dimensionierten Arenen - die Zahl der Allokationen auf dem Matching-Pfad ist im eingeschwungenen Zustand null
• Freigegebene Slots kehren in eine Free List innerhalb der Arena zurück, sodass ein aktives Instrument die ganze Session denselben Speicher wiederverwendet
• Strukturen haben feste Form und feste Größe, mit Kapazitätsgrenzen, die als Ablehnung durchgesetzt werden und nicht als Wachstumsereignis
• Ausgehende Events werden in einen vorab allokierten Ringpuffer geschrieben, den ein anderer Thread leert - der Matching-Thread blockiert nie auf einem Consumer
• Der Matching-Thread ist ein einzelner Writer über dem Buch, also gibt es kein Lock auf dem Buchzustand und keine Reihenfolge-Mehrdeutigkeit aufzulösen
• Eingaben werden sequenziert, bevor sie die Engine erreichen, und über die Reihenfolge entscheidet die Sequenznummer, nicht die Ankunftszeit

Eine Engine ist deterministisch, wenn dieselbe Eingabefolge dieselbe Ausgabefolge erzeugt, Byte für Byte, auf einer anderen Maschine und ein Jahr später. Alles, was im Matching-Pfad die Wall-Clock-Zeit, das Thread-Scheduling oder die Iterationsreihenfolge von Hashes liest, zerstört diese Eigenschaft.

Zeitstempel sind daher eine Eingabe und nichts, was die Engine selbst liest. Der Sequencer stempelt ein Command, wenn er es annimmt, und die Matching-Schleife behandelt den Stempel als Daten. Zufall, falls nötig, kommt aus einem Generator, dessen Seed Teil des Journals ist.

Das Journal ist der Zustand der Engine, und das Buch ist ein Cache davon

Wiederherstellung ist kein Feature, das nach dem Matching angeschraubt wird. Die Engine schreibt ein Append-only-Journal der angenommenen Commands in Sequenzreihenfolge, und das Buch im Speicher ist nichts anderes als das Ergebnis des Faltens dieses Journals. Der Wiederaufbau nach einem Absturz heißt, es wieder einzuspielen.

• Ein Command wird protokolliert und dauerhaft gesichert, bevor er gematcht wird, damit eine angenommene Order nicht durch einen Absturz zwischen Bestätigung und Ausführung verloren gehen kann
• Das Journal ist die Eingabefolge, nicht die Ausgabe - Ausgaben sind abgeleitet, und genau ihr erneutes Ableiten ist das, was Replay tut
• Periodische Snapshots des Buchs tragen die Sequenznummer, zu der sie genommen wurden, sodass die Wiederherstellung einen Snapshot lädt und nur den Rest des Journals wieder einspielt
• Die Übereinstimmung von Snapshot und Replay wird geprüft statt angenommen: Ein Replay ab dem vorherigen Snapshot muss den nächsten reproduzieren
• Der Event-Strom trägt dieselben Sequenznummern, sodass nachgelagerte Consumer - Risk, Settlement, Marktdaten - ab einem bekannten Punkt fortgesetzt werden können, statt von Hand resynchronisiert zu werden

Die Engine schreibt das Journal, aber Dauerhaftigkeit ist eine Eigenschaft des Speicherpfads und der Frage, wie viele Maschinen den Eintrag haben, bevor die Bestätigung hinausgeht. Das ist eine Replikations- und Hardwareentscheidung, und dort wird die Wiederherstellungszeit tatsächlich gewonnen oder verloren.

Testen heißt deterministisches Replay plus Invarianten, die immer gelten müssen

Determinismus macht die Engine testbar. Weil dieselbe Eingabe dieselbe Ausgabe liefert, ist eine aufgezeichnete Session ein Regressionstest, und ein einmal gefundener Fehler lässt sich exakt reproduzieren, statt ihm nachzujagen.

• Replay-Harness: eine aufgezeichnete Command-Folge einspeisen, den ausgegebenen Event-Strom mit dem gespeicherten vergleichen und bei der ersten Abweichung mit der Sequenznummer fehlschlagen
• Invariantenprüfungen nach jedem Command in Test-Builds - Queues nach Ankunft sortiert, Level-Aggregate gleich der Summe ihrer Queue, kein gekreuztes Buch, Gesamtmenge über jeden Trade erhalten
• Property-based Tests, die zufällige, aber wohlgeformte Command-Folgen erzeugen und die Invarianten prüfen statt konkreter Ergebnisse
• Ein differenzielles Referenzmodell: eine langsame, offensichtlich korrekte Implementierung mit naiven Datenstrukturen, auf denselben Eingaben ausgeführt, wobei jede Abweichung als Bug in der schnellen gilt
• Fuzzing an der Decoder-Grenze, wo fehlerhafte Eingaben von außen ankommen und wo eine Panic den Matching-Thread mitreißen würde
• Latenzmessung unter der Burst-Form, die Sie beunruhigt, mit Aufzeichnung der Verteilung statt eines Durchschnitts, denn der Tail ist die Zahl, die das Design entscheidet

Was Rust hier bringt und was nicht

Rust nimmt eine Klasse von Problemen weg, statt die Schleife selbst schneller zu machen. Es gibt keinen Garbage Collector, also wird hinter Ihrem Rücken keine Pause eingeplant. Ownership macht die Single-Writer-Disziplin zu etwas, das der Compiler durchsetzt, statt zu etwas, das ein Code-Review bemerken muss. Slab-Handles und intrusive Verweise, die in einer Sprache ohne Lifetimes fehleranfällig sind, sind hier prüfbar. Panics bei Integer-Überlauf in Debug-Builds fangen eine Fehlerklasse ab, die ein Buch still beschädigt.

Die ehrliche Grenze ist: Das meiste, was die Tail-Latenz bestimmt, ist nicht die Sprache:

• Kernel-Scheduling, Interrupt-Behandlung, CPU-Pinning und Power-Management bewegen den Tail stärker als der Matching-Code
• Netzwerkkarte, Kernel-Bypass oder dessen Fehlen und der physische Weg zum Venue setzen eine Untergrenze, die die Engine nicht unterschreiten kann
• Serialisierung und das Wire-Protokoll an der Grenze sind häufig der dominierende Kostenfaktor, nicht das Match selbst
• Matching-Semantik, Ordertypen, Gebühren- und Rebate-Regeln sowie Marktphasen sind Geschäftsentscheidungen - eine schnell umgesetzte falsche Regel bleibt falsch
• Risk-Checks, Positionslimits und der Settlement-Pfad liegen außerhalb der Engine und haben eigene Latenzen und eigene Fehlermodi
• Betrieb - Deployment, Monitoring, das Runbook für ein fehlgeschlagenes Replay - entscheidet, ob die Garantien den Kontakt mit einem Produktionsvorfall überstehen

Rust kostet auch etwas. Der Borrow Checker bremst die ersten Wochen eines Designs, das noch in Bewegung ist, das Ökosystem für börsenspezifische Protokolle ist dünner als in älteren Sprachen, und unsafe-Blöcke um lock-freie Strukturen brauchen dieselbe Review-Disziplin wie vergleichbarer Code anderswo. Die Wahl ist eine Entscheidung über den Latency-Tail und über Speichersicherheit in einem Single-Writer-Kern, keine Entscheidung über Entwicklerkomfort.

amBrain baut seit 2019 in Jerewan, Armenien, Trading-Infrastruktur mit Hot Paths in Rust - Marktdaten in unter 5 ms ausgeliefert, Pre-Trade-Risk-Checks in unter 1 ms. Wenn Sie eine Matching Engine entwerfen und Buchstruktur, Journalformat oder Replay-Harness durchgehen möchten, lohnt sich dieses Gespräch, bevor die erste Zeile des Hot Path geschrieben ist.