Eine Börse, die keinen Cent verliert: die deterministische Engine eines Prediction Markets

Finanzsysteme · Rust · Node.js · gRPC · MemoryDB · PostgreSQL

Ein Prediction Market ist eine Börse, an der Prognosen gehandelt werden. Zu jedem Ereignis („Wer gewinnt das Spiel?“) gibt es mehrere mögliche Ausgänge, und für jeden Ausgang werden Kontrakte gekauft und verkauft: Ein JA-Kontrakt zahlt 1 aus, wenn der Ausgang eintritt, ein NEIN-Kontrakt zahlt 1 aus, wenn er nicht eintritt. Der Preis eines JA-Kontrakts zwischen 0,01 und 0,99 ist also die Wahrscheinlichkeit, die der Markt diesem Ausgang zuschreibt. Die Plattform wettet nie gegen ihre eigenen Nutzer: Sie bringt diejenigen, die an einen Ausgang glauben, mit denen zusammen, die vom Gegenteil überzeugt sind, und verdient an jedem gehandelten Kontrakt eine Gebühr.

Aus technischer Sicht ist das ein Problem, das keine Fehler verzeiht. Der Traffic ballt sich in den letzten Minuten jedes Ereignisses und auf denselben Ausgängen, also auf demselben Orderbuch. Jede Order bewegt Geld, und ein Rundungsfehler, eine doppelt angewendete Order oder zwei Server, die sich über den Zustand uneinig sind, sind keine Schönheitsfehler, sondern Geld, das entsteht oder vernichtet wird. Und da es sich um ein reguliertes Produkt handelt, gehören die Kontrollen zum Schutz der Nutzer und der Abgleich der Gelder vom ersten Tag an zum System.

Für diese Plattform haben wir das gesamte System entworfen und gebaut: Backend, Trading-Engine, Apps für iOS, Android und Web, Backoffice und Infrastruktur. Dieser Artikel beschreibt die Engine: eine Zustandsmaschine in Rust, die den gesamten Trading-Zustand im Speicher hält und ihn ausschließlich dadurch verändert, dass sie die Befehle eines persistenten Logs einzeln nacheinander anwendet. Die Idee, die alles Weitere trägt, lautet, dass Korrektheit in einem System, das Geld bewegt, als überprüfbare Eigenschaft gebaut werden muss: Ist der Zustand eine deterministische Funktion eines geordneten Logs, werden Duplikate, Neustarts und Repliken konstruktionsbedingt harmlos, statt Fälle zu sein, die man einzeln behandeln muss.

Ein einziges Orderbuch pro Ausgang macht die Buchhaltung zu einem Erhaltungssatz

Es gibt vier Operationen: JA kaufen oder verkaufen, NEIN kaufen oder verkaufen. 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, die zusammen genau ein Paar im Wert von 1 bilden, nie treffen: Es bräuchte eine Gegenpartei dazwischen, also genau die Rolle, auf die die Plattform bewusst verzichtet.

Wir haben jedem Ausgang ein einziges Orderbuch gegeben, in dem jeder Preis ein JA-Preis ist. NEIN zu 0,60 zu kaufen entspricht einer Order zu 0,40 auf der NEIN-Seite; einen JA-Kontrakt zu verkaufen, den man besitzt, entspricht im Marktrisiko dem Kauf eines NEIN-Kontrakts. Die vier Operationen landen auf nur zwei Seiten, und dasselbe Matching hat je nachdem, wer auf der anderen Seite steht, unterschiedliche, aber konsistente Auswirkungen:

Der Vorteil ist nicht nur die Liquidität. Aus diesem Modell folgt eine Invariante, die sich einfach formulieren lässt: Für jeden Ausgang sind stets genauso viele JA-Kontrakte im Umlauf wie NEIN-Kontrakte, und jedes Paar ist durch eine eingezahlte Geldeinheit gedeckt. Das eingegangene Geld abzüglich des ausgezahlten entspricht immer der Summe aus den Guthaben, dem durch offene Orders gebundenen Geld, den eingenommenen Gebühren und dem Wert der im Umlauf befindlichen Paare. Die Buchhaltung wird zu einem Erhaltungssatz, und einen Erhaltungssatz kann man nach jedem Befehl prüfen.

Die Marktregeln sind so entworfen, dass sie ihn in jeder Kombination einhalten. Jede Order reserviert im Voraus die höchste Gebühr, die auf sie entfallen könnte, auch bei gestaffelten Gebühren und Rabatten für Maker, und das System lehnt jede Konfiguration ab, bei der ein Matching mehr auszahlen würde, als es einnimmt. Die Eröffnungsauktion führt die sich kreuzenden Orders zu dem einheitlichen Preis aus, der das Volumen maximiert, mit einer Berechnung, die gegen eine quadratische Referenzimplementierung auf 20.000 zufälligen Orderbüchern verifiziert ist.

Der Engpass ist ein umkämpftes Orderbuch, nicht die Anzahl der Server

Den Ansturm von Orders auf denselben Ausgang, wenn ein Ereignis endet, löst man nicht mit zusätzlichen Servern: Die Orders eines Orderbuchs müssen in einer genau festgelegten Reihenfolge angewendet werden, und die Guthaben sind allen Orderbüchern gemeinsam, auf denen ein Nutzer handelt. Der verbreitetste Ansatz, eine relationale Datenbank mit einem Lock pro Order, würde den Ansturm genau dann in eine Warteschlange konkurrierender Transaktionen verwandeln, wenn es am meisten darauf ankommt.

Wir haben die Aufgaben getrennt. Das Backend in Node.js übernimmt Authentifizierung, Katalog, regulatorische Prüfungen und alles, was „Anwendung“ ist. Die Engine hält Orderbücher, Guthaben, Kontrakte, Gebühren und Ausgabenlimits im Speicher und wendet die Befehle auf einem einzigen Thread an. Das ist die Entscheidung von LMAX, Coinbase und TigerBeetle: Da sich die Orderbücher den Zustand teilen, würde ein Thread pro Orderbuch Koordination zwischen den Threads erfordern und die Repliken nichtdeterministisch machen.

Die Sprache haben wir gewählt, indem wir dieselbe vereinfachte Engine mit einem großen Zustand gemessen haben, jeweils in Blöcken von 1.000 Orders:

Entscheidend ist das Maximum: Die 658 ms von Node.js sind eine Pause des Garbage Collectors, und in der Engine einer Börse fällt eine solche Pause tendenziell genau dann an, wenn das Orderbuch am vollsten ist, weil dort am meisten alloziert wird. Ohne Garbage Collector bleibt die Tail-Latenz in Rust nahe am Median.

Determinismus ist eine Disziplin, keine Eigenschaft des Codes

Ein einziger Thread garantiert eine Reihenfolge, nicht dasselbe Ergebnis auf verschiedenen Maschinen. Divergenzen zwischen Repliken entstehen selten durch einen Fehler im Matching, sondern durch Details, die harmlos wirken, etwa die Systemzeit, die Iterationsreihenfolge einer Map oder eine Rundung. Deshalb ist der Kern der Engine eine Bibliothek ohne Zugriff auf Netzwerk, Festplatte oder Uhr, mit einer einzigen Funktion, die einen Befehl entgegennimmt und Antwort und Events zurückgibt. Daraus ergibt sich die Eigenschaft, auf der das gesamte System beruht: Dieselben Befehle in derselben Reihenfolge erzeugen denselben Zustand, dieselben Antworten und dieselben Events, auf jeder Maschine und bei jeder erneuten Ausführung.

Jede Regel der Disziplin versperrt einen konkreten Weg zur Divergenz. Die Zeit stammt aus dem Zeitstempel, den das Log dem Befehl zuweist, nie von der Uhr, sodass zwei Repliken nicht unterschiedlich entscheiden können, ob eine Order vor oder nach der Schließung eingegangen ist. Hash-Maps dienen nur für Lookups, nie zur Iteration. Geld ist im gesamten System ganzzahlig, in Millionsteln als 64-Bit-Integer, und ein Betrag, der keine ganze Zahl von Cent ist, wird abgelehnt, nie gerundet. Jede Operation prüft alles, bevor sie schreibt, sodass ein abgelehnter Befehl den Zustand so hinterlässt, wie er war. Die Overflow-Prüfungen bleiben in Produktion aktiv: Ein Guthaben, das „überläuft“, würde von jeder Replika angewendet und als korrekt exportiert, während eine angehaltene Engine ein weitaus kleineres Problem ist.

Zwei Werkzeuge machen den Determinismus überprüfbar, statt ihn nur zu behaupten. Ein Audit berechnet jede Invariante von Grund auf neu, von der Erhaltung des Geldes bis zur Parität zwischen JA und NEIN, und die Tests führen es nach jedem Befehl aus. Ein Digest berechnet einen 64-Bit-Fingerabdruck des gesamten Zustands über eine explizite kanonische Kodierung und zerlegt dabei jede Struktur Feld für Feld: Wer dem Zustand ein Feld hinzufügt, ohne es in den Digest aufzunehmen, erhält Code, der nicht kompiliert, und so bleibt die Prüfung auch nach der nächsten Änderung gültig. Zwei Repliken an derselben Position im Log müssen denselben Digest haben, und ein geladener Snapshot mit abweichendem Digest wird abgelehnt.

Ein Log statt Konsens

Ist der Zustand eine Funktion der Befehle, genügt es, die Befehle persistent zu machen. Bleibt zu entscheiden, wer ihre Reihenfolge festlegt. Die klassische Antwort ist ein Konsensprotokoll wie Raft, bei dem ein von der Mehrheit der Knoten gewählter Leader die Befehle entgegennimmt und repliziert. Aeron Cluster, das es implementiert, bietet Commits unter einer Millisekunde, bringt aber ein zusätzliches Gateway, Knoten mit stabiler Identität und orchestrierte Releases mit sich. Kafka und Kinesis hätten einen ganzen Cluster für einen einzigen Stream oder rund 200 ms Leseverzögerung bedeutet, und eine Queue wie SQS FIFO lässt sich nicht erneut lesen.

Wir haben uns entschieden, die Reihenfolge dem Log statt einem Leader zu überlassen und keinen Konsenscode zu schreiben. Jeder Befehl wird in einen Redis-Stream auf Amazon MemoryDB geschrieben, das einen Schreibvorgang erst bestätigt, wenn er in seinem Transaktionslog über mehrere Availability Zones hinweg erfasst ist. Jede Replika 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 zwei Repliken, die während eines Deployments gleichzeitig laufen, divergieren nicht, weil sie dieselben Befehle in derselben Reihenfolge anwenden.

Ohne Leader verlagern sich drei Probleme.

Das erste ist der Durchsatz. Ein Schreibvorgang auf das Log pro Befehl sättigt in unseren Messungen bei rund 40.000 Orders pro Sekunde, und Bündeln in festen Intervallen würde auch bei wenig Traffic Wartezeit hinzufügen. Stattdessen hat jede Replika einen einzigen Writer mit nur einem laufenden Schreibvorgang, und die Befehle, die in der Zwischenzeit eintreffen, gehen gemeinsam im nächsten Eintrag hinaus: Das ist das Smart Batching von Martin Thompson, dasselbe Prinzip wie der Group Commit von Datenbanken. Ein einzelner Befehl geht sofort hinaus, unter Last wachsen die Einträge mit dem Traffic, und die Obergrenze steigt auf etwa 80.000 Orders pro Sekunde.

Das zweite ist die Zeit: Wenn die Engine die Uhr nicht liest, muss ihr etwas mitteilen, dass ein Ereignis geschlossen werden muss. Sind Eröffnung oder Schließung fällig, hängt jede Replika einen „Tick“-Befehl an, wie die Timer von Aeron Cluster: Der erste, der angewendet wird, führt die Schließung aus, die anderen finden nichts mehr zu tun. Die Schließung bleibt millisekundengenau, weil eine Order mit späterem Zeitstempel das Ereignis bereits geschlossen vorfindet, noch bevor ein Tick eintrifft. Das Backend braucht keine Cronjobs, um Märkte zu öffnen oder zu schließen.

Das dritte sind die Lesezugriffe. Ein Lesezugriff kann bei einer Replika ankommen, die etwas zurückliegt, und ein Nutzer darf die Order, die er gerade platziert hat, nicht verschwinden sehen. Jeder Schreibvorgang gibt seine eigene Position im Log zurück, die App schickt sie beim nächsten Lesezugriff mit, und die Replika wartet bei Bedarf, bis sie diese Position angewendet hat, wie bei den Session Tokens von Cosmos DB.

Wiederholen muss sicher sein, von der App bis zur Engine

Eine Antwort kann verloren gehen, nachdem der Befehl ausgeführt wurde, und bei einer Order, oder schlimmer noch bei einer Auszahlung, muss „erneut versuchen“ „höchstens einmal anwenden“ bedeuten. 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: Das Backend leitet die ID des Befehls aus dem Idempotenzschlüssel der App ab, und die Deduplizierung übernimmt die Engine.

Die Engine merkt sich für ein bestimmtes Zeitfenster jede angewendete ID, zusammen mit einem Fingerabdruck des Befehls und der gegebenen Antwort, Ablehnungen eingeschlossen: Derselbe wiederholte Befehl erhält die ursprüngliche Antwort ohne jede Wirkung, ein anderer Befehl mit derselben ID einen expliziten Fehler, wie bei den idempotenten APIs von Stripe und im IETF-Entwurf zum Idempotency-Key-Header. Auf dieser Grundlage geht das Backend mit Unsicherheit um, statt sie zu verbergen: Es versucht es einige Sekunden lang mit zufälligem Backoff erneut, immer mit derselben ID und auch über eine andere Replika, und wenn die Zeit abgelaufen ist, antwortet es explizit „Ergebnis unbekannt, bitte erneut versuchen“. Fehlgeschlagener Schreibvorgang, verlorene Antwort oder eine Replika, die direkt nach dem Schreiben ausfällt: Der Befehl wird höchstens einmal angewendet.

Ein Detail unterscheidet ein System, das theoretisch idempotent ist, von einem, das es tatsächlich ist: Jede automatische Wiederholung, von der App bis zu den Jobs, die Geld bewegen, muss deutlich abgeschlossen sein, bevor die Engine den Befehl vergisst. Das Backend prüft diese Bedingungen beim Start und verweigert den Start, wenn die Konfiguration sie verletzt. Es ist ein Fehler, der sonst erst in Produktion auffallen würde, an dem Tag, an dem jemand einen Timeout verlängert.

Derselbe Mechanismus schützt das ein- und ausgehende Geld: Jede Geldbewegung verwendet als ID die der fachlichen Anfrage, und das Guthaben wird erst gutgeschrieben, nachdem der Zahlungseingang abgeglichen wurde. Auch die Ausgabenlimits sitzen dort, wo sich Korrektheit am einfachsten garantieren lässt: Die Engine setzt sie im selben Schritt durch, in dem sie das Geld für die Order reserviert, sodass zwischen Prüfung und Schreibvorgang kein Raum für eine Race Condition bleibt.

Jeder Output hat eine Identität, und ein Duplikat kostet nichts

Die Plattform braucht außerdem eine abfragbare Historie und Echtzeit-Benachrichtigungen. Genau hier wird ein repliziertes System meist kompliziert: Wer exportiert, wer schreibt die Snapshots, wie vermeidet man Duplikate? Der Determinismus erlaubt es, ohne Koordination zu antworten, weil jedes Event eine deterministische Identität hat: die Position des Eintrags im Log plus eine fortlaufende Nummer innerhalb des Eintrags, auf jeder Replika und bei jeder erneuten Ausführung dieselbe.

Die persistenten Events verlassen die Engine außerhalb des kritischen Pfads, und PostgreSQL verwendet ihre Identität als eindeutigen Schlüssel und verwirft Duplikate. Deshalb genügt eine Standard-SQS-Queue, die At-least-once-Zustellung garantiert, eine Nachricht aber auch mehrfach oder außer der Reihe zustellen kann: Erneute Zustellungen sind harmlos, und die Reihenfolge steckt in den Positionen, nicht in der Queue. Es exportiert jeweils nur eine Replika, dank eines Leases, doch der Lease dient der Effizienz, nicht der Korrektheit, im Sinne von Martin Kleppmann: Exportieren für einen Moment zwei Repliken gleichzeitig, erhält die Datenbank lediglich Duplikate. Es braucht weder Fencing noch Konsens. Bleibt die Queue längere Zeit unerreichbar, setzt die Engine neue Befehle kontrolliert aus, statt den Speicher zu erschöpfen, und bei der Wiederaufnahme ist nichts verloren gegangen.

Für die Snapshots gilt dieselbe Überlegung: Jede Replika kann einen schreiben, gerade weil der Zustand an einer Position deterministisch ist. Ebenso für die Benachrichtigungen: Jeder Prozess des Backends leitet den gRPC-Stream einer Replika an seine eigenen Clients weiter, ohne gemeinsamen Broker, weil alle Repliken dieselben Benachrichtigungen erzeugen. Preise werden alle 100 ms als vollständiger Zustand verschickt, nicht als Differenz, sodass ein verlorenes Update durch das nächste repariert wird.

Der Kern ist viel schneller als das, was ihn speist

Die Performance haben wir in einer Benchmark-Umgebung gemessen, mit einem Open-Loop-Lastgenerator: Die Latenz wird ab dem Zeitpunkt gemessen, zu dem die Anfrage vorgesehen war, wie Gil Tene es empfiehlt, sodass sich Warteschlangen nicht verstecken können.

Jede am Kern gemessene Order durchläuft alles, was auch eine echte Order durchläuft: Validierung, Reservierung des Geldes, Ausgabenlimits, Matching, Abwicklung beider Seiten, Events und Deduplizierung. Der Durchsatz über das Log hängt dank der gebündelten Schreibvorgänge nicht von der Commit-Latenz ab. Der Kern wendet Orders weit schneller an, als Log und Backend sie liefern können: Der Spielraum liegt genau dort, wo er liegen soll.

Tests, die das System mit einer einfachen Referenz vergleichen

Der Determinismus erlaubt es, jedes Ergebnis mit einer einfachen Referenz zu vergleichen. Die Property-based Tests erzeugen zufällige Sitzungen aus Hunderten von Befehlen, mit festem Seed und daher reproduzierbar, und prüfen, dass die Invarianten nach jedem Befehl gültig bleiben, dass zwei Engines mit denselben Eingaben in Antworten, Events und Digest übereinstimmen, dass die Events ausreichen, um jedes Guthaben zu rekonstruieren, und dass das Matching dieselben Ergebnisse liefert wie eine bewusst naive Implementierung.

Dasselbe gilt für die Repliken: Cluster aus 2, 3, 6 und 10 Repliken müssen unter zufälligem nebenläufigem Traffic mit doppelten Aufrufen, abrupten Abstürzen, Deployments und Neustarts dieselben Ergebnisse liefern wie eine einzelne Engine, die das Log der Reihe nach liest. In den Tests zum Failover des Primärknotens des Logs betrug die längste Pause zwischen zwei Antworten während eines geplanten Failovers etwa 50 ms, und bei einem blockierten Primärknoten werden die Schreibvorgänge innerhalb weniger Sekunden wieder aufgenommen, ohne dass bestätigte Befehle verloren gehen. Im Backend werden Race Conditions und verlorene Antworten nach einer ausgeführten Order deterministisch gegen ein echtes Binary der Engine reproduziert, sodass ein Nebenläufigkeitsfehler den Test bei jedem Lauf fehlschlagen lässt, nicht nur einmal von hundert.

Auch ein Deployment ist eine Frage der Korrektheit, denn während seiner gesamten Dauer wenden zwei Versionen der Engine dieselben Einträge an. Die Formate von Einträgen und Snapshots sind versioniert, zuerst wird der Leser ausgerollt, dann der Schreiber, und eine Replika, die auf einen Eintrag stößt, den sie nicht lesen kann, hält an, bevor sie ihn anwendet, statt zu divergieren. So wird die Engine mit einem gewöhnlichen Rolling Deployment aktualisiert.

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 drei Garantien, die nicht vom Glück abhängen: Das Geld bleibt erhalten, und das prüft in den Tests ein Audit nach jedem Befehl; jede Operation wird höchstens einmal angewendet, von der App bis zum Log; jede Replika erreicht denselben Zustand, was sich durch den Vergleich eines Fingerabdrucks überprüfen lässt. Es sind auch die Entscheidungen, die das System einfach zu betreiben machen: ein einziger Thread für die sensible Arbeit, Persistenz und Replikation bei einem Managed Service, Outputs, die Duplikate und Neustarts tolerieren. Neue Zugangspunkte kommen rund um den Kern hinzu, ohne dass er neu geschrieben werden muss.

Die Methode gilt über dieses Projekt hinaus. Divergierende Repliken, verlorene Antworten, doppelte Nachrichten und Neustarts mitten im Ablauf löst man nicht, indem man sie einzeln behandelt, sondern indem man das System deterministisch und jeden seiner Outputs identifizierbar macht. Dann ist es harmlos, eine Operation zu wiederholen, und Korrektheit ist keine Hoffnung mehr, sondern etwas, das die Tests prüfen.