Evoluzione dell'architettura del sistema di negoziazione e compensazione della Borsa di Mosca. Parte 1

Ciao a tutti! Mi chiamo Sergey Kostanbaev, alla Borsa sto sviluppando il nucleo del sistema commerciale.

Quando i film di Hollywood mostrano la Borsa di New York, appare sempre così: folle di persone, tutti gridano qualcosa, sventolano documenti, sta accadendo il caos più totale. Questo non è mai successo qui alla Borsa di Mosca, perché le negoziazioni sono state condotte elettronicamente fin dall'inizio e si basano su due piattaforme principali: Spectra (mercato forex) e ASTS (mercato valutario, azionario e monetario). E oggi voglio parlare dell'evoluzione dell'architettura del sistema di negoziazione e compensazione ASTS, di varie soluzioni e risultati. La storia sarà lunga, quindi ho dovuto dividerla in due parti.

Siamo una delle poche borse al mondo che negozia asset di tutte le classi e fornisce una gamma completa di servizi di cambio. Ad esempio, l'anno scorso ci siamo classificati al secondo posto nel mondo in termini di volume di scambi di obbligazioni, al 25° posto tra tutte le borse valori, al 13° posto per capitalizzazione tra le borse pubbliche.

Per i partecipanti al trading professionisti, parametri come il tempo di risposta, la stabilità della distribuzione temporale (jitter) e l'affidabilità dell'intero complesso sono fondamentali. Attualmente elaboriamo decine di milioni di transazioni al giorno. L'elaborazione di ogni transazione da parte del kernel del sistema richiede decine di microsecondi. Naturalmente, gli operatori di telefonia mobile a Capodanno o gli stessi motori di ricerca hanno un carico di lavoro maggiore del nostro, ma in termini di carico di lavoro, unito alle caratteristiche di cui sopra, pochi possono essere paragonati a noi, mi sembra. Allo stesso tempo, per noi è importante che il sistema non rallenti per un secondo, funzioni in modo assolutamente stabile e tutti gli utenti siano su un piano di parità.

Un po 'di storia

Nel 1994, il sistema ASTS australiano è stato lanciato sul mercato interbancario di Mosca (MICEX) e da quel momento si può contare la storia russa del commercio elettronico. Nel 1998, l’architettura dello scambio è stata modernizzata per introdurre il commercio su Internet. Da allora, la velocità di implementazione di nuove soluzioni e cambiamenti architettonici in tutti i sistemi e sottosistemi ha continuato a guadagnare slancio.

In quegli anni, il sistema di scambio funzionava su hardware di fascia alta: server HP Superdome 9000 ultra affidabili (costruiti sulla base di PA-RISC), in cui assolutamente tutto era duplicato: sottosistemi di input/output, rete, RAM (in effetti, c'era un array RAID di RAM), processori (swap a caldo). Era possibile modificare qualsiasi componente del server senza arrestare la macchina. Abbiamo fatto affidamento su questi dispositivi e li abbiamo considerati praticamente a prova di guasto. Il sistema operativo era un sistema HP UX simile a Unix.

Ma dal 2010 circa è emerso un fenomeno chiamato trading ad alta frequenza (HFT), o trading ad alta frequenza - in poche parole, robot di borsa. In soli 2,5 anni, il carico sui nostri server è aumentato di 140 volte.

Era impossibile sopportare un carico del genere con la vecchia architettura e le vecchie attrezzature. Era necessario adattarsi in qualche modo.

Inizio

Le richieste al sistema di scambio possono essere suddivise in due tipologie:

• Transazioni. Se desideri acquistare dollari, azioni o qualcos'altro, invii una transazione al sistema di trading e ricevi una risposta sul successo.
• Richieste di informazioni. Se vuoi conoscere il prezzo attuale, visualizzare il book degli ordini o gli indici, quindi inviare richieste di informazioni.

Schematicamente il nucleo del sistema può essere suddiviso in tre livelli:

• Il livello del cliente, al quale lavorano broker e clienti. Interagiscono tutti con i server di accesso.
• I server gateway sono server di memorizzazione nella cache che elaborano localmente tutte le richieste di informazioni. Vuoi sapere a quale prezzo vengono attualmente scambiate le azioni Sberbank? La richiesta va al server di accesso.
• Ma se desideri acquistare azioni, la richiesta va al server centrale (Trade Engine). Esiste uno di questi server per ogni tipo di mercato, svolgono un ruolo vitale, è per loro che abbiamo creato questo sistema.

Il nucleo del sistema di trading è un intelligente database in-memory in cui tutte le transazioni sono transazioni di scambio. La base era scritta in C, le uniche dipendenze esterne erano la libreria libc e non c'era alcuna allocazione dinamica della memoria. Per ridurre i tempi di elaborazione, il sistema inizia con un set statico di array e con il riposizionamento statico dei dati: innanzitutto tutti i dati del giorno corrente vengono caricati in memoria e non viene eseguito alcun ulteriore accesso al disco, tutto il lavoro viene eseguito solo in memoria. All'avvio del sistema, tutti i dati di riferimento sono già ordinati, quindi la ricerca funziona in modo molto efficiente e richiede poco tempo in fase di esecuzione. Tutte le tabelle sono realizzate con elenchi e alberi intrusivi per strutture dati dinamiche in modo da non richiedere l'allocazione di memoria in fase di esecuzione.

Ripercorriamo brevemente la storia dello sviluppo del nostro sistema di negoziazione e compensazione.
La prima versione dell'architettura del sistema di negoziazione e compensazione era basata sulla cosiddetta interazione Unix: venivano utilizzate memoria condivisa, semafori e code e ogni processo consisteva in un singolo thread. Questo approccio era diffuso all’inizio degli anni ’1990.

La prima versione del sistema conteneva due livelli di Gateway e un server centrale del sistema di trading. Il flusso di lavoro è stato questo:

• Il client invia una richiesta, che raggiunge il Gateway. Controlla la validità del formato (ma non i dati stessi) e rifiuta le transazioni errate.
• Se è stata inviata una richiesta di informazioni, questa viene eseguita localmente; se stiamo parlando di una transazione, viene reindirizzata al server centrale.
• Il motore di trading quindi elabora la transazione, modifica la memoria locale e invia una risposta alla transazione e alla transazione stessa per la replica utilizzando un motore di replica separato.
• Il Gateway riceve la risposta dal nodo centrale e la inoltra al client.
• Dopo un po' di tempo, il Gateway riceve la transazione attraverso il meccanismo di replica, e questa volta la esegue localmente, modificando le sue strutture dati in modo che le successive richieste di informazioni visualizzino i dati più recenti.

Infatti, descrive un modello di replica in cui il Gateway replica completamente le azioni eseguite nel sistema di trading. Un canale di replica separato assicurava che le transazioni venissero eseguite nello stesso ordine su più nodi di accesso.

Poiché il codice era a thread singolo, per servire molti client è stato utilizzato uno schema classico con fork di processo. Tuttavia, era molto costoso eseguire il fork dell'intero database, quindi sono stati utilizzati processi di servizio leggeri che raccoglievano i pacchetti dalle sessioni TCP e li trasferivano in una coda (SystemV Message Queue). Gateway e Trade Engine funzionavano solo con questa coda, prelevando le transazioni da lì per l'esecuzione. Non era più possibile inviare una risposta perché non era chiaro quale processo di servizio dovesse leggerlo. Quindi abbiamo fatto ricorso a un trucco: ogni processo biforcato creava una coda di risposta per se stesso e quando una richiesta entrava nella coda in entrata, ad essa veniva immediatamente aggiunto un tag per la coda di risposta.

La copia costante di grandi quantità di dati da una coda all'altra creava problemi, tipici soprattutto delle richieste di informazioni. Abbiamo quindi utilizzato un altro trucco: oltre alla coda di risposta, ogni processo ha creato anche una memoria condivisa (SystemV Shared Memory). I pacchi stessi venivano inseriti al suo interno e in coda veniva memorizzata solo un'etichetta che consentiva di ritrovare il pacco originale. Ciò ha aiutato a memorizzare i dati nella cache del processore.

SystemV IPC include utilità per visualizzare lo stato degli oggetti coda, memoria e semaforo. Lo abbiamo utilizzato attivamente per capire cosa stava succedendo nel sistema in un determinato momento, dove si accumulavano i pacchetti, cosa era bloccato, ecc.

Primi aggiornamenti

Prima di tutto, ci siamo sbarazzati del Gateway a processo singolo. Il suo svantaggio significativo era che poteva gestire una transazione di replica o una richiesta di informazioni da parte di un client. Inoltre, con l'aumento del carico, il gateway impiegherà più tempo per elaborare le richieste e non sarà in grado di elaborare il flusso di replica. Inoltre, se il cliente ha inviato una transazione, è sufficiente verificarne la validità e inoltrarla ulteriormente. Pertanto, abbiamo sostituito il singolo processo Gateway con più componenti che possono essere eseguiti in parallelo: informazioni multi-thread e processi di transazione eseguiti indipendentemente l'uno dall'altro su un'area di memoria condivisa utilizzando il blocco RW. E allo stesso tempo abbiamo introdotto processi di spedizione e replica.

Impatto del trading ad alta frequenza

La versione di cui sopra dell'architettura esisteva fino al 2010. Nel frattempo, non eravamo più soddisfatti delle prestazioni dei server HP Superdome. Inoltre, l'architettura PA-RISC era praticamente morta; il fornitore non offriva aggiornamenti significativi. Di conseguenza, abbiamo iniziato a passare da HP UX/PA RISC a Linux/x86. La transizione è iniziata con l'adeguamento dei server di accesso.

Perché abbiamo dovuto cambiare nuovamente l’architettura? Il fatto è che il trading ad alta frequenza ha cambiato in modo significativo il profilo di carico sul nucleo del sistema.

Diciamo che abbiamo una piccola transazione che ha causato una significativa variazione di prezzo: qualcuno ha acquistato mezzo miliardo di dollari. Dopo un paio di millisecondi, tutti i partecipanti al mercato se ne accorgono e iniziano ad apportare una correzione. Naturalmente, le richieste si allineano in un'enorme coda, che il sistema impiegherà molto tempo per eliminare.

In questo intervallo di 50 ms, la velocità media è di circa 16mila transazioni al secondo. Se riduciamo la finestra a 20 ms otteniamo una velocità media di 90mila transazioni al secondo, con un picco di 200mila transazioni. In altre parole, il carico non è costante, con scatti improvvisi. E la coda delle richieste deve essere sempre evasa velocemente.

Ma perché c'è una coda? Quindi, nel nostro esempio, molti utenti hanno notato la variazione di prezzo e hanno inviato transazioni di conseguenza. Arrivano al Gateway, li serializza, imposta un certo ordine e li invia alla rete. I router mescolano i pacchetti e li inoltrano. Il pacco di chi è arrivato per primo, quella transazione “ha vinto”. Di conseguenza, i clienti dello scambio hanno iniziato a notare che se la stessa transazione veniva inviata da più gateway, aumentavano le possibilità di una sua rapida elaborazione. Ben presto, i robot degli scambi iniziarono a bombardare Gateway di richieste e si verificò una valanga di transazioni.

Un nuovo ciclo di evoluzione

Dopo test e ricerche approfonditi, siamo passati al kernel del sistema operativo in tempo reale. Per questo abbiamo scelto RedHat Enterprise MRG Linux, dove MRG sta per messaggistica real-time grid. Il vantaggio delle patch in tempo reale è che ottimizzano il sistema per l'esecuzione più rapida possibile: tutti i processi sono allineati in una coda FIFO, i core possono essere isolati, nessuna espulsione, tutte le transazioni vengono elaborate in sequenza rigorosa.

Rosso: funziona con una coda in un kernel normale, verde: funziona in un kernel in tempo reale.

Ma ottenere una bassa latenza sui server normali non è così semplice:

• Interferisce notevolmente la modalità SMI, che nell'architettura x86 è la base per lavorare con periferiche importanti. L'elaborazione di tutti i tipi di eventi hardware e la gestione di componenti e dispositivi viene eseguita dal firmware nella cosiddetta modalità SMI trasparente, in cui il sistema operativo non vede affatto cosa sta facendo il firmware. Di norma, tutti i principali fornitori offrono estensioni speciali per i server firmware che consentono di ridurre la quantità di elaborazione SMI.
• Non dovrebbe esserci alcun controllo dinamico della frequenza del processore, ciò comporta tempi di inattività aggiuntivi.
• Quando il registro del file system viene svuotato, nel kernel si verificano alcuni processi che causano ritardi imprevedibili.
• Devi prestare attenzione a cose come Affinità CPU, Affinità Interrupt, NUMA.

Devo dire che l'argomento relativo alla configurazione dell'hardware e del kernel Linux per l'elaborazione in tempo reale merita un articolo a parte. Abbiamo trascorso molto tempo sperimentando e ricercando prima di ottenere un buon risultato.

Passando dai server PA-RISC a x86, praticamente non abbiamo dovuto modificare molto il codice del sistema, lo abbiamo semplicemente adattato e riconfigurato. Allo stesso tempo, abbiamo corretto diversi bug. Ad esempio, le conseguenze del fatto che PA RISC era un sistema Big Endian e x86 era un sistema Little Endian sono emerse rapidamente: ad esempio, i dati venivano letti in modo errato. Il bug più complicato era quello utilizzato da PA RISC costantemente coerente (Sequenzialmente coerente) accesso alla memoria, mentre x86 può riordinare le operazioni di lettura, quindi il codice che era assolutamente valido su una piattaforma veniva danneggiato su un'altra.

Dopo il passaggio a x86, le prestazioni sono aumentate di quasi tre volte, il tempo medio di elaborazione delle transazioni è sceso a 60 μs.

Diamo ora uno sguardo più da vicino a quali modifiche principali sono state apportate all'architettura del sistema.

Epica della riserva calda

Quando siamo passati ai server di base, eravamo consapevoli che erano meno affidabili. Pertanto, quando si crea una nuova architettura, si assume a priori la possibilità di guasto di uno o più nodi. Pertanto era necessario un sistema hot standby in grado di passare molto rapidamente alle macchine di backup.

Inoltre c'erano altri requisiti:

• In nessun caso dovresti perdere le transazioni elaborate.
• Il sistema deve essere assolutamente trasparente per la nostra infrastruttura.
• I client non dovrebbero vedere le connessioni interrotte.
• Le prenotazioni non dovrebbero introdurre ritardi significativi perché questo è un fattore critico per lo scambio.

Durante la creazione di un sistema hot standby, non abbiamo considerato scenari come doppi guasti (ad esempio, la rete su un server ha smesso di funzionare e il server principale si è bloccato); non ha considerato la possibilità di errori nel software perché identificati durante i test; e non ha considerato il funzionamento errato dell'hardware.

Di conseguenza, siamo arrivati ​​al seguente schema:

• Il server principale ha interagito direttamente con i server Gateway.
• Tutte le transazioni ricevute sul server principale venivano immediatamente replicate sul server di backup tramite un canale separato. L'arbitro (Governatore) ha coordinato il cambio in caso di problemi.

  

• Il server principale elaborava ogni transazione e attendeva la conferma dal server di backup. Per mantenere la latenza al minimo, abbiamo evitato di attendere il completamento della transazione sul server di backup. Poiché il tempo impiegato da una transazione per viaggiare attraverso la rete era paragonabile al tempo di esecuzione, non è stata aggiunta alcuna latenza aggiuntiva.
• Abbiamo potuto verificare solo lo stato di elaborazione dei server principale e di backup per la transazione precedente e lo stato di elaborazione della transazione corrente era sconosciuto. Poiché utilizzavamo ancora processi a thread singolo, attendere una risposta da Backup avrebbe rallentato l'intero flusso di elaborazione, quindi abbiamo raggiunto un ragionevole compromesso: abbiamo controllato il risultato della transazione precedente.

Lo schema ha funzionato come segue.

Diciamo che il server principale smette di rispondere, ma i gateway continuano a comunicare. Si verifica un timeout sul server di backup, contatta il Governatore, che gli assegna il ruolo di server principale, e tutti i Gateway passano al nuovo server principale.

Se il server principale torna online, si attiva anche un timeout interno, perché per un certo tempo non ci sono state chiamate al server dal Gateway. Poi si rivolge anche al Governatore, e lo esclude dal regime. Di conseguenza, lo scambio funziona con un server fino alla fine del periodo di scambio. Poiché la probabilità di un guasto del server è piuttosto bassa, questo schema è stato considerato abbastanza accettabile; non conteneva una logica complessa ed era facile da testare.

Per essere continuato.

Fonte: habr.com