Un exchange che non perde un centesimo: il motore deterministico di un prediction market

Sistemi finanziari · Rust · Node.js · gRPC · MemoryDB · PostgreSQL

Un prediction market è una borsa in cui si scambiano previsioni. Per ogni evento (“chi vince la partita?”) ci sono più esiti possibili, e per ogni esito si comprano e si vendono contratti: un contratto SÌ paga 1 se l’esito si verifica, un contratto NO paga 1 se non si verifica. Il prezzo di un contratto SÌ, fra 0,01 e 0,99, è quindi la probabilità che il mercato assegna a quell’esito. La piattaforma non scommette mai contro i propri utenti: fa incontrare chi crede in un esito con chi crede nel contrario, e guadagna una commissione su ogni contratto scambiato.

Dal punto di vista ingegneristico è un problema che non perdona. Il traffico si concentra negli ultimi minuti di ogni evento e sugli stessi esiti, cioè sullo stesso order book. Ogni ordine sposta denaro, e un errore di arrotondamento, un ordine applicato due volte o due server che non concordano sullo stato non sono difetti estetici, ma soldi creati o distrutti. E trattandosi di un prodotto regolamentato, i controlli a tutela degli utenti e la riconciliazione dei fondi fanno parte del sistema fin dal primo giorno.

Per questa piattaforma abbiamo progettato e costruito l’intero sistema: backend, motore di trading, app per iOS, Android e web, back office e infrastruttura. Questo articolo racconta il motore: una macchina a stati in Rust che tiene tutto lo stato di trading in memoria e lo modifica solo applicando, uno alla volta, i comandi di un log durevole. L’idea che regge il resto è che in un sistema che muove denaro la correttezza va costruita come una proprietà verificabile: se lo stato è funzione deterministica di un log ordinato, duplicati, riavvii e repliche diventano innocui per costruzione, invece di essere casi da gestire uno per uno.

Un solo book per esito trasforma la contabilità in una legge di conservazione

Le operazioni sono quattro: comprare o vendere SÌ, comprare o vendere NO. La modellazione più immediata tratta SÌ e NO come due titoli distinti, ciascuno con il proprio book. Ma così chi compra SÌ a 0,40 e chi compra NO a 0,60, che insieme formano esattamente una coppia da 1, non si incontrerebbero mai: servirebbe una controparte in mezzo, cioè il ruolo che la piattaforma ha scelto di non avere.

Abbiamo dato a ogni esito un solo order book, in cui ogni prezzo è un prezzo del SÌ. Comprare NO a 0,60 equivale a un ordine a 0,40 sul lato NO; vendere un SÌ posseduto espone al mercato come comprare un NO. Le quattro operazioni finiscono su due soli lati, e lo stesso abbinamento ha effetti diversi ma coerenti a seconda di chi c’è dall’altra parte:

Il vantaggio non è solo la liquidità. Da questo modello discende un invariante semplice da enunciare: per ogni esito i contratti SÌ in circolazione sono sempre quanti i NO, e ogni coppia è coperta da un’unità di denaro depositata. Il denaro entrato, meno quello uscito, è sempre uguale ai saldi, più il denaro bloccato dagli ordini aperti, più le commissioni incassate, più il valore delle coppie in circolazione. La contabilità diventa una legge di conservazione, e una legge di conservazione si controlla dopo ogni comando.

Le regole di mercato sono progettate per rispettarla in ogni combinazione. Ogni ordine riserva in anticipo la commissione massima che potrebbe toccargli, anche con commissioni a fasce e sconti per i maker, e il sistema rifiuta qualunque configurazione in cui un abbinamento pagherebbe più di quanto incassa. L’asta di apertura esegue gli ordini incrociati al prezzo unico che massimizza il volume, con un calcolo verificato contro un’implementazione di riferimento quadratica su 20.000 book casuali.

Il collo di bottiglia è un book conteso, non il numero di server

La raffica di ordini sullo stesso esito alla chiusura di un evento non si risolve aggiungendo server: gli ordini di un book vanno applicati in un ordine preciso, e i saldi sono condivisi fra tutti i book su cui un utente opera. L’approccio più comune, un database relazionale con un lock per ordine, trasformerebbe la raffica in una coda di transazioni in conflitto proprio quando conta di più.

Abbiamo separato i mestieri. Il backend in Node.js gestisce autenticazione, catalogo, verifiche regolamentari e tutto ciò che è “applicazione”. Il motore tiene in memoria book, saldi, contratti, commissioni e limiti di spesa, e applica i comandi su un solo thread. È la scelta di LMAX, Coinbase e TigerBeetle: con lo stato condiviso fra i book, un thread per book richiederebbe coordinamento fra thread e renderebbe le repliche non deterministiche.

Il linguaggio l’abbiamo scelto misurando lo stesso motore semplificato, con uno stato di grandi dimensioni, su blocchi di 1.000 ordini:

Il dato che conta è il massimo: i 658 ms di Node.js sono una pausa del garbage collector, e nel motore di una borsa una pausa del genere tende a cadere proprio quando il book è più affollato, perché è lì che si alloca di più. Senza garbage collector, in Rust la latenza di coda resta vicina alla mediana.

Il determinismo è una disciplina, non una proprietà del codice

Un solo thread garantisce un ordine, non lo stesso risultato su macchine diverse. Le divergenze fra repliche raramente nascono da un errore nell’abbinamento: nascono da dettagli che sembrano innocui, come l’ora di sistema, l’ordine di iterazione di una mappa o un arrotondamento. Per questo il nucleo del motore è una libreria senza accesso a rete, disco od orologio, con una sola funzione che riceve un comando e restituisce risposta ed eventi. Ne risulta la proprietà che regge tutto il sistema: gli stessi comandi, nello stesso ordine, producono lo stesso stato, le stesse risposte e gli stessi eventi, su qualunque macchina e a ogni riesecuzione.

Ogni regola della disciplina chiude una strada concreta alla divergenza. Il tempo viene dal timestamp che il log assegna al comando, mai dall’orologio, quindi due repliche non possono decidere diversamente se un ordine è arrivato prima o dopo la chiusura. Le mappe hash servono solo alle ricerche, mai all’iterazione. Il denaro è intero in tutto il sistema, in milionesimi su interi a 64 bit, e un importo non intero in centesimi viene rifiutato, mai arrotondato. Ogni operazione verifica tutto prima di scrivere, quindi un comando rifiutato lascia lo stato com’era. I controlli di overflow restano attivi in produzione: un saldo che “gira” verrebbe applicato da ogni replica ed esportato come vero, mentre un motore fermo è un problema molto più piccolo.

Due strumenti rendono il determinismo verificabile, non soltanto dichiarato. Un audit ricalcola da zero ogni invariante, dalla conservazione del denaro alla parità fra SÌ e NO, e i test lo eseguono dopo ogni comando. Un digest calcola un’impronta a 64 bit dell’intero stato su una codifica canonica esplicita, scomponendo ogni struttura campo per campo: aggiungere un campo allo stato senza includerlo nel digest non compila, così il controllo resta valido anche dopo la prossima modifica. Due repliche nella stessa posizione del log devono avere lo stesso digest, e uno snapshot ricaricato con un digest diverso viene rifiutato.

Un log al posto del consenso

Se lo stato è funzione dei comandi, basta rendere durevoli i comandi. Resta da decidere chi ne stabilisce l’ordine. La risposta classica è un protocollo di consenso come Raft, in cui un leader eletto dalla maggioranza dei nodi riceve i comandi e li replica. Aeron Cluster, che lo implementa, offre commit sotto il millisecondo, ma porta con sé un gateway in più, nodi con identità stabile e rilasci orchestrati. Kafka e Kinesis avrebbero richiesto un intero cluster per un solo stream o circa 200 ms di ritardo in lettura, e una coda come SQS FIFO non si può rileggere.

Abbiamo scelto di affidare l’ordine al log invece che a un leader, e di non scrivere codice di consenso. Ogni comando viene scritto su uno stream Redis ospitato su Amazon MemoryDB, che conferma una scrittura solo quando è registrata nel suo log transazionale su più zone di disponibilità. Ogni replica del motore accetta comandi, li accoda al log, legge l’intero log e calcola l’intero stato. Non c’è un leader da eleggere, e due repliche che girano insieme durante un rilascio non divergono, perché applicano gli stessi comandi nello stesso ordine.

Togliere il leader sposta tre problemi.

Il primo è il throughput. Una scrittura sul log per ogni comando, nelle nostre misure, satura intorno ai 40.000 ordini al secondo, e raggruppare a intervalli fissi aggiungerebbe attesa anche a basso traffico. Ogni replica ha invece un solo scrittore con una sola scrittura in volo, e i comandi arrivati nel frattempo partono insieme nella voce successiva: è lo smart batching di Martin Thompson, lo stesso principio del group commit dei database. Un comando isolato parte subito, sotto carico le voci crescono con il traffico, e il tetto sale a circa 80.000 ordini al secondo.

Il secondo è il tempo: se il motore non legge l’orologio, qualcosa deve dirgli che un evento va chiuso. Quando apertura o chiusura sono dovute, ogni replica accoda un comando di “tick”, come i timer di Aeron Cluster: il primo applicato esegue la chiusura, gli altri non trovano nulla da fare. La chiusura resta esatta al millisecondo, perché un ordine con timestamp successivo trova l’evento già chiuso anche prima che arrivi un tick. Il backend non ha cron per aprire o chiudere i mercati.

Il terzo sono le letture. Una lettura può arrivare a una replica un po’ indietro, e un utente non deve veder sparire l’ordine appena piazzato. Ogni scrittura restituisce la propria posizione nel log, l’app la rimanda con la lettura successiva e la replica aspetta, se serve, di averla applicata, come con i session token di Cosmos DB.

Riprovare deve essere sicuro, dall’app fino al motore

Una risposta può perdersi dopo che il comando è stato eseguito, e per un ordine, o peggio per un prelievo, “riprova” deve significare “applica al massimo una volta”. La soluzione più diffusa è una tabella di idempotenza nel backend, ma qui l’effetto avviene nel motore, e una tabella esterna lascia sempre una finestra fra l’esecuzione e la registrazione dell’esito. Abbiamo portato la garanzia dove avviene l’effetto: il backend deriva l’id del comando dalla chiave di idempotenza dell’app, e la deduplica la fa il motore.

Il motore ricorda per un intervallo di tempo ogni id applicato, con un’impronta del comando e la risposta data, rifiuti compresi: lo stesso comando ripetuto riceve la risposta originale senza effetti, un comando diverso con lo stesso id riceve un errore esplicito, come nelle API idempotenti di Stripe e nella bozza IETF sull’header Idempotency-Key. Su questa base il backend gestisce l’incertezza invece di nasconderla: ritenta per pochi secondi con backoff casuale, sempre con lo stesso id e anche su un’altra replica, e allo scadere risponde in modo esplicito “esito sconosciuto, riprova”. Scrittura fallita, risposta persa o replica caduta subito dopo la scrittura: il comando viene applicato al massimo una volta.

Un dettaglio distingue un sistema idempotente in teoria da uno che lo è davvero: ogni ripetizione automatica, dall’app ai job che muovono denaro, deve concludersi ben prima che il motore dimentichi il comando. Il backend verifica questi vincoli all’avvio e, se la configurazione li viola, si rifiuta di partire. È un errore che altrimenti si scoprirebbe solo in produzione, il giorno in cui qualcuno allunga un timeout.

Lo stesso meccanismo protegge il denaro in entrata e in uscita: ogni movimentazione usa come id quello della richiesta di business, e il saldo viene accreditato solo dopo che l’incasso è stato riconciliato. Anche i limiti di spesa stanno dove la correttezza è più semplice da garantire: li applica il motore nello stesso passaggio in cui riserva il denaro dell’ordine, quindi fra controllo e scrittura non c’è spazio per una corsa.

Ogni uscita ha un’identità, e un duplicato non costa nulla

La piattaforma ha bisogno anche di uno storico interrogabile e di notifiche in tempo reale. È qui che un sistema replicato di solito si complica: chi esporta, chi scrive gli snapshot, come si evitano i doppioni. Il determinismo permette di rispondere senza coordinamento, perché ogni evento ha un’identità deterministica: la posizione della voce nel log più un numero progressivo al suo interno, uguale su ogni replica e a ogni riesecuzione.

Gli eventi durevoli escono dal motore fuori dal percorso critico, e PostgreSQL usa la loro identità come chiave univoca, scartando i duplicati. Per questo basta una coda SQS standard, che garantisce la consegna almeno una volta ma può consegnare un messaggio più volte o fuori ordine: le riconsegne sono innocue, e l’ordine sta nelle posizioni, non nella coda. Esporta una replica alla volta, grazie a un lease, ma il lease serve all’efficienza, non alla correttezza, nel senso descritto da Martin Kleppmann: se per un attimo due repliche esportano insieme, il database riceve solo duplicati. Non servono né fencing né consenso. Se la coda resta irraggiungibile a lungo, il motore sospende in modo controllato i nuovi comandi invece di esaurire la memoria, e alla ripresa non si è perso nulla.

Gli snapshot seguono lo stesso ragionamento: qualunque replica può scriverne uno, proprio perché lo stato in una posizione è deterministico. Anche le notifiche: ogni processo del backend inoltra ai propri client il flusso gRPC di una replica, senza un broker condiviso, perché tutte le repliche producono le stesse notifiche. I prezzi partono ogni 100 ms come stato completo, non come differenza, così un aggiornamento perso viene riparato dal successivo.

Il nucleo è molto più veloce di ciò che lo alimenta

Le prestazioni le abbiamo misurate in un ambiente di benchmark, con un generatore a carico aperto: la latenza si misura dall’istante in cui la richiesta era prevista, come raccomanda Gil Tene, così le code non si nascondono.

Ogni ordine misurato sul nucleo paga tutto ciò che paga un ordine reale: validazione, riserva del denaro, limiti di spesa, abbinamento, regolamento di entrambe le parti, eventi e deduplica. Il throughput attraverso il log non dipende dalla latenza di commit, grazie al raggruppamento delle scritture. Il nucleo applica ordini molto più in fretta di quanto log e backend riescano a consegnarli: il margine è dove deve essere.

Test che confrontano il sistema con un riferimento semplice

Il determinismo permette di confrontare ogni risultato con un riferimento semplice. I test basati su proprietà generano sessioni casuali di centinaia di comandi, con seme fisso e quindi riproducibili, e verificano che gli invarianti reggano dopo ogni comando, che due motori con gli stessi input concordino su risposte, eventi e digest, che gli eventi bastino a ricostruire ogni saldo e che l’abbinamento dia gli stessi risultati di un’implementazione volutamente ingenua.

Lo stesso vale per le repliche: cluster da 2, 3, 6 e 10 repliche, sotto traffico concorrente casuale con invii duplicati, arresti improvvisi, rilasci e riavvii, devono produrre gli stessi risultati di un singolo motore che legge il log in ordine. Nei test sul failover del nodo primario del log, durante un failover pianificato la pausa più lunga fra due risposte è stata di circa 50 ms, e con un primario bloccato le scritture riprendono in pochi secondi senza perdere comandi confermati. Nel backend, le condizioni di gara e le risposte perse dopo un ordine eseguito sono riprodotte in modo deterministico contro un vero binario del motore, così un difetto di concorrenza fa fallire il test a ogni esecuzione, non una volta su cento.

Anche un rilascio è un problema di correttezza, perché per tutta la sua durata due versioni del motore applicano le stesse voci. I formati di voci e snapshot sono versionati, si rilascia prima chi legge e poi chi scrive, e una replica che incontra una voce che non sa leggere si ferma prima di applicarla invece di divergere. Il motore si aggiorna così con un normale rilascio progressivo.

Il valore per la piattaforma

Per un prediction market il motore di trading è il prodotto: decide chi ha comprato cosa, a quale prezzo, e chi viene pagato alla fine. Quello che abbiamo costruito dà al cliente tre garanzie che non dipendono dalla fortuna: il denaro si conserva, e lo verifica un audit dopo ogni comando nei test; ogni operazione è applicata al massimo una volta, dall’app fino al log; ogni replica arriva allo stesso stato, verificabile confrontando un’impronta. Sono anche le scelte che rendono il sistema semplice da gestire: un solo thread per il lavoro sensibile, durabilità e replica affidate a un servizio gestito, uscite che tollerano duplicati e riavvii. Nuovi punti di accesso si aggiungono attorno al nucleo senza riscriverlo.

Il metodo vale oltre questo progetto. Repliche che divergono, risposte perse, messaggi duplicati e riavvii a metà non si risolvono gestendoli uno per uno, ma rendendo il sistema deterministico e ogni sua uscita identificabile. A quel punto ripetere un’operazione è innocuo, e la correttezza smette di essere una speranza per diventare qualcosa che i test verificano.