Finanzsysteme · Rust · Node.js · gRPC · MemoryDB · PostgreSQL
TL;DR: Für einen Prediction Market haben wir in Rust eine Trading-Engine gebaut, deren Zustand nur von einem geordneten, dauerhaften Log von Befehlen abhängt. Orders werden im Speicher von einem einzigen Thread angewendet, also ohne Locks und ohne Pausen des Garbage Collectors in der Spitze am Ende eines Ereignisses, und die Reihenfolge der Befehle legt ein verwaltetes Log auf Amazon MemoryDB fest statt eines Konsensprotokolls. In unseren Benchmarks verarbeitet der Kern rund 250.000 Orders pro Sekunde auf einem einzigen Thread. Daraus ergeben sich überprüfbare Garantien: Jeder Befehl wird höchstens einmal angewendet, von der App bis zur Engine; jede Replik erreicht denselben Zustand; jede Geldbewegung ist eine doppelte Buchung, die stündlich mit der Datenbank abgeglichen wird; neue Regeln werden durch einen Befehl im Log aktiviert. Die Tests vergleichen das System mit bewusst einfachen Referenzen.
Ein Prediction Market ist eine Börse, an der Prognosen gehandelt werden. Für jedes Ereignis („Wer gewinnt das Spiel?“) werden Kontrakte auf die möglichen Ausgänge gekauft und verkauft: Ein JA-Kontrakt zahlt 1, wenn der Ausgang eintritt, ein NEIN-Kontrakt zahlt 1, wenn er nicht eintritt, und der Preis des JA-Kontrakts, zwischen 0,01 und 0,99, ist die Wahrscheinlichkeit, die der Markt diesem Ausgang zuschreibt. Die Plattform wettet nie gegen ihre Nutzer: Sie bringt diejenigen zusammen, die an einen Ausgang glauben, mit denen, die das Gegenteil erwarten, und verdient an jedem Handel eine Gebühr.
Für diesen Kunden haben wir das gesamte System gebaut: Backend, Apps für iOS, Android und Web, Backoffice, Infrastruktur und Trading-Engine. Die Engine ist die Komponente, in der ein Fehler am meisten kostet. Eine doppelt angewendete Order, eine falsche Rundung oder zwei Server, die sich über den Zustand uneinig sind, sind keine Schönheitsfehler, sondern Geld, das entsteht oder verschwindet, in einem regulierten Produkt, in dem die Gelder der Nutzer abgeglichen werden müssen. Und die Last ist nicht gleichmäßig verteilt: Sie konzentriert sich auf die letzten Minuten jedes Ereignisses und auf dieselben Ausgänge, also genau dann, wenn die Nutzer am aktivsten sind und die Plattform am meisten einnimmt.
Der übliche Weg für ein solches System ist, die schwierigen Fälle einzeln zu behandeln: hier ein Lock, dort eine Idempotenztabelle, ein Job, der nachts abgleicht. Wir haben den umgekehrten Ansatz gewählt: eine Engine in Rust, deren Zustand ausschließlich von einer geordneten, dauerhaften Folge von Befehlen abhängt. Wenn dieselben Befehle immer denselben Zustand erzeugen, sind Repliken, Neustarts, Retries und doppelte Nachrichten keine Fälle mehr, die man behandeln muss, sondern werden durch Konstruktion harmlos. Und dieselben Entscheidungen, die sie korrekt machen, machen sie auch schnell: In unseren Benchmarks verarbeitet der Kern rund 250.000 Orders pro Sekunde.
Der Engpass ist ein umkämpftes Orderbuch, und mehr Server helfen nicht
Bei einer Lastspitze ist der natürliche Reflex, horizontal zu skalieren. Hier funktioniert das nicht: Die Orders eines Orderbuchs müssen nacheinander angewendet werden, in einer Reihenfolge, die alle teilen müssen, und das Guthaben eines Nutzers gilt für alle Orderbücher, auf denen er handelt. Eine relationale Datenbank mit einem Lock pro Order würde den Ansturm am Schluss in eine Warteschlange konkurrierender Transaktionen verwandeln, genau dann, wenn es am meisten darauf ankommt.
Deshalb haben wir die Verantwortlichkeiten getrennt. Das Backend in Node.js übernimmt alles, was „Anwendung“ ist: Authentifizierung, Katalog, regulatorische Prüfungen, Benachrichtigungen an die Apps. Die Engine hält Orderbücher, Guthaben, Kontrakte, Gebühren und Ausgabelimits im Speicher und wendet die Befehle einzeln an, auf einem einzigen Thread. Das wirkt wie ein Rückschritt, ist aber die Wahl von Systemen wie LMAX und TigerBeetle: Ohne Locks und ohne Koordination zwischen Threads braucht eine vollständige Order, von der Validierung bis zur Abwicklung beider Seiten, wenige Mikrosekunden.
Auch die Sprache ist das Ergebnis einer Messung, nicht einer Vorliebe. Wir haben die Zeit verglichen, die dieselbe vereinfachte Engine mit einem großen Zustand für einen Block von 1.000 Orders braucht:
| Sprache | Median | p99,9 | Schlechtester Fall |
|---|---|---|---|
| Rust | 0,85 ms | 1,42 ms | 1,6 ms |
| Node.js | 4 ms | 21 ms | 658 ms |
Entscheidend ist die letzte Spalte. Die 658 ms von Node.js sind eine Pause des Garbage Collectors, und an einer Börse fällt eine solche Pause tendenziell genau in die Spitze, weil dort am meisten Speicher angelegt wird. In Rust, ohne Garbage Collector, bleibt der schlechteste Fall nahe am typischen: Die Order in der letzten Sekunde wird behandelt wie die, die in aller Ruhe platziert wurde.
Ein Orderbuch pro Ausgang: mehr Liquidität für die Nutzer, überprüfbare Konten für die Plattform
Das naheliegendste Modell behandelt JA und NEIN als zwei getrennte Wertpapiere mit jeweils eigenem Orderbuch. Dann aber würden sich jemand, der JA zu 0,40 kauft, und jemand, der NEIN zu 0,60 kauft, nie begegnen, obwohl sie zusammen genau ein Paar im Wert von 1 bilden: Es bräuchte eine Gegenpartei dazwischen, also genau die Rolle, die die Plattform nicht einnehmen will, und das Ergebnis wären dünnere Orderbücher und schlechtere Preise.
Wir haben jedem Ausgang ein einziges Orderbuch gegeben, in dem jeder Preis ein JA-Preis ist. NEIN zu 0,60 zu kaufen entspricht einem Gebot von 0,40 auf der Gegenseite, und einen gehaltenen JA-Kontrakt zu verkaufen wirkt im Orderbuch wie der Kauf eines NEIN-Kontrakts. Alle Orders landen auf nur zwei Seiten, und jedes Matching erzeugt ein neues Kontraktpaar, gibt es von einem Nutzer an einen anderen weiter oder löst es auf und zahlt das Geld zurück.
Der Nutzen geht über die Liquidität hinaus. Aus diesem Modell folgt eine einfache Invariante: Für jeden Ausgang sind ebenso viele JA- wie NEIN-Kontrakte im Umlauf, und jedes Paar ist durch eine eingezahlte Geldeinheit gedeckt. Das eingezahlte Geld abzüglich des ausgezahlten entspricht immer den Guthaben, plus dem durch offene Orders gebundenen Geld, plus den Gebühren, plus dem Wert der umlaufenden Paare. Die Buchhaltung wird zu einem Erhaltungssatz, und einen Erhaltungssatz kann man prüfen. Auch die Gebühren sind so gestaltet, dass sie ihn einhalten: Eine Konfiguration, in der ein Matching mehr auszahlen würde, als es einnimmt, wird abgelehnt.
Determinismus ist eine Disziplin, und wir machen sie überprüfbar
Ein einziger Thread garantiert eine Reihenfolge, nicht dasselbe Ergebnis auf verschiedenen Maschinen. Abweichungen zwischen Repliken entstehen selten durch einen Fehler im Matching: Sie entstehen durch Details, die harmlos wirken, etwa die Systemzeit, die Reihenfolge, in der eine Map durchlaufen wird, oder eine Rundung. Deshalb ist der Kern eine reine Bibliothek, und jede ihrer Regeln verschließt einen dieser Wege.
Die Zeit kommt mit dem Befehl, vergeben vom Log, nie von der Uhr der Maschine: Zwei Repliken können nicht unterschiedlich entscheiden, ob eine Order vor oder nach dem Handelsschluss eingegangen ist. Geld ist im gesamten System eine ganze Zahl, und ein ungültiger Betrag wird abgelehnt, nie gerundet. Jede Operation prüft alles, bevor sie schreibt, sodass ein abgelehnter Befehl den Zustand genau so lässt, wie er war. Über diesen Regeln liegt ein Sicherheitsnetz: Schlägt eine interne Prüfung fehl, während die Engine einen Befehl anwendet, hält die Engine an, statt weiterzumachen, denn ein falsches Guthaben würde überallhin repliziert und als korrekt dargestellt. Die Regeln sind so gestaltet, dass das nicht passiert, und die Tests prüfen es nach jedem Befehl.
Zwei Werkzeuge machen die Disziplin überprüfbar. Ein Audit berechnet jede Invariante von Grund auf neu, von der Erhaltung des Geldes bis zur Parität zwischen JA und NEIN: Die Tests führen es nach jedem Befehl aus, und zur Laufzeit führt jede Replik es auf jedem Snapshot aus, den sie speichert, sodass eine Anomalie binnen Minuten auffällt und nicht erst am Monatsende. Ein Fingerabdruck (Digest) des gesamten Zustands erlaubt es, zwei Repliken an derselben Position im Log mit einer einzigen Zahl zu vergleichen, und ein Snapshot, der nach dem Laden einen anderen Fingerabdruck ergibt, wird verworfen. Der Fingerabdruck ist so aufgebaut, dass ein neues Feld im Zustand, das nicht einbezogen wird, nicht kompiliert: Die Prüfung bleibt auch nach der nächsten Änderung gültig, wer auch immer sie vornimmt.
Ein verwaltetes Log statt eines Konsensprotokolls
Wenn der Zustand eine Funktion der Befehle ist, genügt es, die Befehle dauerhaft zu machen. Bleibt die Frage, wer ihre Reihenfolge festlegt. Die Lehrbuchantwort ist ein Konsensprotokoll wie Raft, bei dem ein von den Knoten gewählter Leader die Befehle empfängt und repliziert. Wir haben es in Form von Aeron Cluster geprüft: Commits unter einer Millisekunde, aber auch Betriebskosten, mit Knoten fester Identität und orchestrierten Releases, die der Kunde für immer getragen hätte.
Wir haben uns entschieden, die Reihenfolge dem Log zu überlassen statt einem Leader. Jeder Befehl wird in einen Redis-Stream auf Amazon MemoryDB geschrieben, das einen Schreibvorgang erst bestätigt, nachdem es ihn in seinem eigenen, über mehrere Availability Zones verteilten Transaktionslog festgehalten hat: Ein Failover verliert keinen bestätigten Befehl. Jede Replik der Engine nimmt Befehle an, hängt sie an das Log an, liest das gesamte Log und berechnet den gesamten Zustand. Es gibt keinen Leader, der gewählt werden muss, und während eines Releases können alte und neue Version nebeneinander laufen, sofern sie dieselben Regeln anwenden: Wie wir das sicherstellen, zeigen wir weiter unten.
Ohne Leader bleiben drei Probleme offen, und jedes hat eine einfache Antwort.
Das erste ist der Durchsatz: Befehle einzeln in das Log zu schreiben, sättigt die Replik schnell. Stattdessen fasst jede Replik die Befehle zusammen, die eintreffen, während der vorherige Schreibvorgang läuft, und schreibt sie gemeinsam, nach demselben Prinzip wie der Group Commit von Datenbanken. Bei wenig Traffic geht ein Befehl sofort hinaus, unter Last wachsen die Gruppen mit dem Traffic, und in unseren Benchmarks verdoppelt sich der Durchsatz nahezu. Repliken dienen der Verfügbarkeit und den Lesezugriffen, und das Log liegt hinter einer Schnittstelle, die es ersetzbar macht, ohne den Kern neu zu schreiben, an dem Tag, an dem mehr Kapazität gebraucht wird.
Das zweite ist die Zeit: Wenn die Engine die Uhr nicht liest, muss ihr etwas mitteilen, dass ein Ereignis geschlossen werden muss. Wenn eine Frist erreicht ist, hängt jede Replik einen „Tick“-Befehl an: Der erste angewendete führt den Handelsschluss aus, die anderen finden nichts mehr zu tun. Eine Order, die auch nur eine Millisekunde nach dem Schluss eintrifft, findet das Ereignis bereits geschlossen, sodass niemand nach Handelsschluss noch handeln kann, und es gibt keinen Cronjob im Backend, der sich in der Zeit irren oder der Engine widersprechen könnte.
Das dritte sind die Lesezugriffe. Eine Replik kann einige Millisekunden zurückliegen, und ein Nutzer darf die gerade platzierte Order nicht verschwinden sehen. Jeder Schreibvorgang gibt seine Position im Log zurück, die App sendet sie mit dem nächsten Lesezugriff mit, und die Replik wartet bei Bedarf, bis sie diese Position angewendet hat: Auf keiner Replik sieht der Nutzer je einen älteren Zustand als einen bereits gesehenen.
Hunderttausende Orders pro Sekunde: Korrektheit kostet keine Geschwindigkeit
So starke Garantien bezahlt man meist mit Performance. Hier ist es umgekehrt: Ohne Locks, ohne Garbage Collector und ohne Konsensprotokoll schrumpft die sensible Arbeit auf wenige Mikrosekunden Rechenzeit im Speicher. In unseren Benchmarks, in denen jede Order alles zahlt, was eine echte Order zahlt, von der Validierung bis zur Abwicklung beider Seiten:
| Szenario | Orders pro Sekunde |
|---|---|
| Alle Orders auf demselben Ausgang | rund 250.000 |
| 1.000 offene Ausgänge und eine Million Nutzer | über 150.000 |
| Vollständige Engine, jeder Befehl dauerhaft geschrieben | etwa 80.000 |
Die wichtigste Zahl ist die erste: Das Szenario, vor dem sich jede Börse fürchtet, alle auf demselben Ausgang in den letzten Minuten, ist genau das, in dem der Kern am schnellsten ist. Und damit die Performance mit der Zeit nicht nachlässt, sind Speicher und Instruktionen pro Order Schwellenwerte in der CI: Ein Pull Request, der die Engine spürbar langsamer macht, kommt nicht durch.
Retries sind immer sicher, von der App bis zur Engine
Ein Nutzer, der in einem instabilen Netz auf „Kaufen“ tippt, weiß nicht, ob die Order durchgegangen ist. Versucht er es erneut, muss er die Order genau einmal erhalten, und bei einer Auszahlung kostet ein Duplikat noch mehr. Die verbreitetste Lösung ist eine Idempotenztabelle im Backend, doch hier tritt die Wirkung in der Engine ein, und eine externe Tabelle lässt immer ein Fenster zwischen der Ausführung und der Erfassung des Ergebnisses. Wir haben die Garantie dorthin verlegt, wo die Wirkung eintritt: Die ID des Befehls entsteht aus der Absicht des Nutzers, und die Deduplizierung übernimmt die Engine.
Die App erzeugt für jede Absicht einen Schlüssel und verwendet ihn erneut, bis das Ergebnis feststeht. Das Backend leitet daraus die ID des Befehls ab, die auch an den Nutzer gebunden ist, sodass ein Schlüssel nie die Order eines anderen bezeichnen kann. Die Engine merkt sich jede angewendete ID für eine gewisse Zeit zusammen mit der gegebenen Antwort, Ablehnungen eingeschlossen, und beantwortet einen wiederholten Befehl mit der ursprünglichen Antwort, ohne Wirkung. Das Backend kann es daher mit derselben ID erneut versuchen, auch auf einer anderen Replik, und wenn die verfügbare Zeit abläuft, antwortet es ehrlich: „Ergebnis unbekannt, bitte erneut versuchen“. Ob der Schreibvorgang fehlgeschlagen ist, die Antwort verloren ging oder die Replik direkt nach dem Schreiben ausgefallen ist: Der Befehl wird höchstens einmal angewendet.
Bleibt eine Bedingung, die meist niemand festhält: Jede automatische Wiederholung, von der App bis zu den Jobs, die Geld bewegen, muss abgeschlossen sein, bevor die Engine diese ID vergisst. Das Backend prüft das beim Start und verweigert den Start, wenn die Konfiguration dagegen verstößt. Es ist die Art von Fehler, die man sonst in Produktion entdeckt, an dem Tag, an dem jemand ein Timeout verlängert.
Jede Geldbewegung hat eine Identität, und ein Duplikat kostet nichts
Eine regulierte Plattform braucht nicht nur korrekte Guthaben, sondern muss auch nachweisen können, wie sie zustande gekommen sind. Deshalb verlässt jede Bewegung, von Geld oder von Kontrakten, die Engine als Übertrag zwischen zwei Konten, in doppelter Buchführung: Die Überträge allein genügen, um jedes Guthaben zu rekonstruieren, und die Tests prüfen das nach jedem Befehl.
Diese Bewegungen in die Datenbank zu bringen, ist die Stelle, an der ein repliziertes System meist kompliziert wird: Wer exportiert, wie vermeidet man Duplikate, was passiert, wenn der Exporteur mittendrin ausfällt? Der Determinismus erlaubt eine Antwort ohne Koordination, weil jedes Ereignis eine deterministische Identität hat: die Position im Log plus eine laufende Nummer, gleich auf jeder Replik und bei jeder erneuten Ausführung. PostgreSQL nutzt sie als eindeutigen Schlüssel und verwirft Duplikate, deshalb genügt eine gewöhnliche SQS-Queue, die eine Nachricht auch mehrfach zustellen kann. Es exportiert immer nur eine Replik, aber nur aus Effizienzgründen: Exportieren für einen Moment zwei Repliken gleichzeitig, erhält die Datenbank lediglich Duplikate, und es braucht kein Koordinationsprotokoll.
Auf dieser Grundlage wird der Abgleich zur Routine: Jede Stunde vergleicht ein Job die Summen der Engine mit der Summe der Buchungen in PostgreSQL an derselben Position im Log, und jede Abweichung wird gemeldet. Bevor das Log kompaktiert wird, wird es archiviert, sodass jeder archivierte Zeitraum für eine Prüfung von Grund auf neu ausgeführt werden kann.
Die Regeln einer Börse ändern, während sie geöffnet ist
Eine deterministische Engine stellt ein Problem, das herkömmliche Systeme nicht haben. Bei einem Rolling Release laufen die neue und die alte Replik nebeneinander auf demselben Log: Würde die neue eine andere Gebühr oder eine neue Prüfung anwenden, liefen die beiden auseinander. Und beim Start spielt die neue Version Befehle erneut ab, die die alte bereits angewendet und den Nutzern bestätigt hatte: Sie mit neuen Regeln neu zu berechnen, hieße, die Vergangenheit umzuschreiben.
Wir haben das Release von der Aktivierung getrennt. Die Version der Regeln ist Teil des Zustands und ändert sich nur durch einen Befehl im Log, den ein Operator aus dem Backoffice sendet: Jede Replik wechselt die Regeln genau an diesem Eintrag, und eine erneute Ausführung wendet jeden Eintrag mit den Regeln seines Zeitpunkts an. Solange die neue Version nicht aktiv ist, berechnet und schreibt das neue Binary genau das, was das vorherige geschrieben hat, sodass das Release nichts ändert und zurückgenommen werden kann. Eine Replik, die auf eine Version trifft, die sie nicht kennt, hält vor deren Anwendung an, statt abzuweichen, und startet mit dem neuen Binary neu. Jedes Release enthält einen Zustand und einen Abschnitt des Logs, die vom vorherigen Binary geschrieben wurden, und die CI prüft bei jedem Pull Request, dass das neue Binary sie wieder einliest und identisch zurückschreibt: Die Möglichkeit eines Rollbacks ist geprüft, nicht angenommen.
So wächst die Engine mit dem Produkt. Die Kosten jeder Position einschließlich der gezahlten Gebühren, die verändern, was die Engine für jeden Nutzer berechnet und was die App im Profil anzeigt, wurden auf diese Weise ausgeliefert: abgeschaltet, bereit zur Aktivierung durch einen Befehl im Log, ohne den Zustand zurückzusetzen oder die Geschichte umzuschreiben.
Tests, die das System mit einer einfachen Referenz vergleichen
Ein verteiltes System zu testen, das Geld bewegt, heißt meist, viele Szenarien zu schreiben und zu hoffen, an die richtigen gedacht zu haben. Der Determinismus erlaubt etwas Stärkeres: das System mit einer Referenz zu vergleichen, die einfach genug ist, um sie von Hand zu prüfen. Property-based Tests erzeugen zufällige, reproduzierbare Sitzungen aus Hunderten von Befehlen und prüfen, dass die Invarianten nach jedem Befehl gelten, dass zwei Engines mit denselben Eingaben bei Antworten, Ereignissen und Fingerabdruck übereinstimmen und dass das Matching dieselben Ergebnisse liefert wie eine bewusst naive Implementierung.
Dasselbe Prinzip gilt für die Repliken. Cluster aus 2 bis 10 Repliken müssen unter zufälligem, gleichzeitigem Traffic mit doppelten Übermittlungen, abrupten Stopps, Releases und Neustarts genau dieselben Ergebnisse liefern wie eine einzelne Engine, die das Log der Reihe nach liest. In den Failover-Tests des Logs betrug die längste Pause zwischen zwei Antworten bei einem geplanten Knotenwechsel etwa 50 ms, und wenn der primäre Knoten plötzlich einfriert, werden Schreibvorgänge etwa drei Sekunden, nachdem der Standby-Knoten übernommen hat, fortgesetzt, ohne dass ein bestätigter Befehl verloren geht. Im Backend werden Race Conditions und Antworten, die nach einer ausgeführten Order verloren gehen, deterministisch gegen ein echtes Binary der Engine nachgestellt, sodass ein Nebenläufigkeitsfehler den Test bei jedem Durchlauf scheitern lässt, nicht einmal in hundert Durchläufen.
Der Wert für die Plattform
Für einen Prediction Market ist die Trading-Engine das Produkt: Sie entscheidet, wer was zu welchem Preis gekauft hat und wer am Ende ausgezahlt wird. Was wir gebaut haben, gibt dem Kunden überprüfbare Garantien statt Versprechen. Das Geld bleibt erhalten, und ein Audit prüft es. Jede Operation wird höchstens einmal angewendet, von der App bis zum Log. Jede Replik erreicht denselben Zustand, vergleichbar mit einer einzigen Zahl. Jede Bewegung hat eine Buchung, und jede Stunde werden die Summen der Engine mit der Datenbank abgeglichen. Und all das kostet keine Geschwindigkeit: In Benchmarks verarbeitet der Kern Hunderttausende Orders pro Sekunde, selbst wenn der gesamte Traffic auf demselben Ausgang liegt. Dieselben Entscheidungen machen das System einfach zu betreiben und weiterzuentwickeln: Die sensible Arbeit liegt in einem einzigen Thread, die Dauerhaftigkeit ist einem verwalteten Dienst anvertraut, und neue Regeln treten in Kraft, ohne den Markt anzuhalten.
Die Methode gilt über dieses Projekt hinaus. Auseinanderlaufende Repliken, verlorene Antworten, doppelte Nachrichten und abgebrochene Neustarts löst man nicht, indem man sie einzeln behandelt, sondern indem man das System deterministisch und jede seiner Ausgaben identifizierbar macht. Dann ist es harmlos, eine Operation zu wiederholen, und Korrektheit ist keine Hoffnung mehr, sondern etwas, das die Tests bei jeder Änderung prüfen.