De evolutie van de architectuur van het handels- en clearingsysteem van de Moscow Exchange. Deel 1

Dag Allemaal! Mijn naam is Sergey Kostanbaev, op de beurs ontwikkel ik de kern van het handelssysteem.

Als Hollywoodfilms de New York Stock Exchange laten zien, ziet het er altijd zo uit: massa's mensen, iedereen roept iets, zwaait met papieren, er ontstaat een complete chaos. Dit is hier op de Moskouse Beurs nog nooit gebeurd, omdat de handel vanaf het allereerste begin elektronisch is uitgevoerd en gebaseerd is op twee hoofdplatforms: Spectra (forexmarkt) en ASTS (buitenlandse valuta, aandelen- en geldmarkt). En vandaag wil ik het hebben over de evolutie van de architectuur van het ASTS-handels- en clearingsysteem, over verschillende oplossingen en bevindingen. Het verhaal zal lang worden, dus ik heb het in twee delen moeten opdelen.

Wij zijn een van de weinige beurzen ter wereld die activa van alle klassen verhandelen en een volledig scala aan beursdiensten aanbieden. Vorig jaar stonden we bijvoorbeeld op de tweede plaats in de wereld wat betreft het handelsvolume in obligaties, op de 25e plaats van alle aandelenbeurzen en op de 13e plaats wat betreft kapitalisatie van de openbare beurzen.

Voor professionele handelsdeelnemers zijn parameters als responstijd, stabiliteit van de tijdsverdeling (jitter) en betrouwbaarheid van het gehele complex van cruciaal belang. Momenteel verwerken wij tientallen miljoenen transacties per dag. De verwerking van elke transactie door de systeemkernel duurt tientallen microseconden. Natuurlijk hebben mobiele operators op oudejaarsavond of zoekmachines zelf een hogere werkdruk dan de onze, maar qua werkdruk, in combinatie met de bovengenoemde kenmerken, kunnen weinigen met ons vergelijken, lijkt mij. Tegelijkertijd is het voor ons belangrijk dat het systeem geen seconde langzamer gaat werken, absoluut stabiel werkt en dat alle gebruikers op gelijke voet staan.

Een beetje geschiedenis

In 1994 werd het Australische ASTS-systeem gelanceerd op de Moskouse Interbank Valutabeurs (MICEX), en vanaf dat moment kan de Russische geschiedenis van elektronische handel worden geteld. In 1998 werd de beursarchitectuur gemoderniseerd om internethandel te introduceren. Sindsdien is de snelheid waarmee nieuwe oplossingen en architectonische veranderingen in alle systemen en subsystemen worden geïmplementeerd alleen maar aan kracht gewonnen.

In die jaren werkte het uitwisselingssysteem op high-end hardware: ultrabetrouwbare HP Superdome 9000-servers (gebouwd op de PA-RISC), waarin absoluut alles werd gedupliceerd: invoer/uitvoer-subsystemen, netwerk, RAM (in feite was er een RAID-array van RAM), processors (hot-swappable). Het was mogelijk om elk serveronderdeel te wijzigen zonder de machine te stoppen. We vertrouwden op deze apparaten en beschouwden ze als vrijwel storingsvrij. Het besturingssysteem was een Unix-achtig HP UX-systeem.

Maar sinds ongeveer 2010 is er een fenomeen ontstaan ​​dat hoogfrequente handel (HFT) wordt genoemd, of hoogfrequente handel – simpel gezegd: beursrobots. In slechts 2,5 jaar tijd is de belasting van onze servers 140 keer toegenomen.

Met de oude architectuur en uitrusting was het onmogelijk om een ​​dergelijke belasting te weerstaan. Het was noodzakelijk om zich op de een of andere manier aan te passen.

begin

Verzoeken aan het uitwisselingssysteem kunnen in twee typen worden verdeeld:

• Transacties. Als je dollars, aandelen of iets anders wilt kopen, stuur je een transactie naar het handelssysteem en ontvang je een reactie over succes.
• Informatieverzoeken. Als u de huidige prijs wilt weten, het orderboek of de indexen wilt bekijken, kunt u informatieverzoeken verzenden.

Schematisch kan de kern van het systeem in drie niveaus worden verdeeld:

• Het klantniveau, waarop makelaars en opdrachtgevers werken. Ze communiceren allemaal met toegangsservers.
• Gatewayservers zijn cachingservers die lokaal alle informatieverzoeken verwerken. Wilt u weten tegen welke prijs de aandelen van Sberbank momenteel worden verhandeld? Het verzoek gaat naar de toegangsserver.
• Maar wil je aandelen kopen, dan gaat het verzoek naar de centrale server (Trade Engine). Er is zo'n server voor elk type markt, ze spelen een cruciale rol, voor hen hebben we dit systeem gemaakt.

De kern van het handelssysteem is een slimme in-memory database waarin alle transacties beurstransacties zijn. De basis was geschreven in C, de enige externe afhankelijkheden waren de libc-bibliotheek en er was helemaal geen dynamische geheugentoewijzing. Om de verwerkingstijd te verkorten, begint het systeem met een statische set arrays en met statische gegevensverplaatsing: eerst worden alle gegevens voor de huidige dag in het geheugen geladen en wordt er geen verdere schijftoegang uitgevoerd; al het werk wordt alleen in het geheugen uitgevoerd. Wanneer het systeem opstart, zijn alle referentiegegevens al gesorteerd, waardoor het zoeken zeer efficiënt werkt en weinig tijd in beslag neemt. Alle tabellen zijn gemaakt met opdringerige lijsten en bomen voor dynamische datastructuren, zodat er tijdens runtime geen geheugentoewijzing nodig is.

Laten we kort de geschiedenis van de ontwikkeling van ons handels- en clearingsysteem doornemen.
De eerste versie van de architectuur van het handels- en clearingsysteem was gebouwd op de zogenaamde Unix-interactie: er werd gebruik gemaakt van gedeeld geheugen, semaforen en wachtrijen, en elk proces bestond uit een enkele thread. Deze aanpak was begin jaren negentig wijdverbreid.

De eerste versie van het systeem bevatte twee Gateway-niveaus en een centrale server van het handelssysteem. De werkstroom was als volgt:

• De client verzendt een verzoek dat de Gateway bereikt. Het controleert de geldigheid van het formaat (maar niet de gegevens zelf) en wijst onjuiste transacties af.
• Als er een informatieverzoek is verzonden, wordt dit lokaal uitgevoerd; als we het over een transactie hebben, wordt deze doorgestuurd naar de centrale server.
• De handelsengine verwerkt vervolgens de transactie, wijzigt het lokale geheugen en verzendt een reactie op de transactie en de transactie zelf voor replicatie met behulp van een afzonderlijke replicatie-engine.
• De Gateway ontvangt het antwoord van het centrale knooppunt en stuurt dit door naar de client.
• Na enige tijd ontvangt de Gateway de transactie via het replicatiemechanisme en voert deze deze keer lokaal uit, waarbij de datastructuren worden gewijzigd, zodat bij de volgende informatieverzoeken de nieuwste gegevens worden weergegeven.

In feite beschrijft het een replicatiemodel waarin de Gateway de acties die in het handelssysteem worden uitgevoerd volledig repliceert. Een afzonderlijk replicatiekanaal zorgde ervoor dat transacties in dezelfde volgorde over meerdere toegangsknooppunten werden uitgevoerd.

Omdat de code single-threaded was, werd een klassiek schema met procesvorken gebruikt om veel klanten te bedienen. Het was echter erg duur om de hele database te splitsen, dus werden lichtgewicht serviceprocessen gebruikt die pakketten van TCP-sessies verzamelden en deze naar één wachtrij (SystemV Message Queue) overbrachten. Gateway en Trade Engine werkten alleen met deze wachtrij en haalden daar transacties op voor uitvoering. Het was niet meer mogelijk om daar een reactie op te sturen, omdat niet duidelijk was welk serviceproces deze moest lezen. Daarom namen we onze toevlucht tot een truc: elk gevorkt proces creëerde voor zichzelf een antwoordwachtrij, en als er een verzoek in de binnenkomende wachtrij kwam, werd er onmiddellijk een tag voor de antwoordwachtrij aan toegevoegd.

Het voortdurend kopiëren van grote hoeveelheden gegevens van wachtrij naar wachtrij zorgde voor problemen, vooral typisch voor informatieverzoeken. Daarom hebben we nog een truc gebruikt: naast de responswachtrij creëerde elk proces ook gedeeld geheugen (SystemV Shared Memory). De pakketten zelf werden erin geplaatst en er werd alleen een tag in de wachtrij opgeslagen, waardoor men het originele pakket kon vinden. Dit hielp bij het opslaan van gegevens in de cache van de processor.

SystemV IPC bevat hulpprogramma's voor het bekijken van de status van wachtrij-, geheugen- en semafoorobjecten. We hebben dit actief gebruikt om te begrijpen wat er op een bepaald moment in het systeem gebeurde, waar pakketten zich opstapelden, wat werd geblokkeerd, enz.

Eerste upgrades

Allereerst hebben we de Gateway met één proces verwijderd. Het belangrijke nadeel was dat het één replicatietransactie of één informatieverzoek van een klant kon afhandelen. En naarmate de belasting toeneemt, duurt het langer voordat Gateway aanvragen verwerkt en kan de replicatiestroom niet meer worden verwerkt. Als de klant een transactie heeft verzonden, hoeft u bovendien alleen de geldigheid ervan te controleren en deze verder door te sturen. Daarom hebben we het enkele Gateway-proces vervangen door meerdere componenten die parallel kunnen draaien: informatie- en transactieprocessen met meerdere threads die onafhankelijk van elkaar draaien op een gedeeld geheugengebied met behulp van RW-vergrendeling. En tegelijkertijd introduceerden we verzend- en replicatieprocessen.

Impact van hoogfrequente handel

De bovenstaande versie van de architectuur bestond tot 2010. Ondertussen waren we niet langer tevreden over de prestaties van HP Superdome-servers. Bovendien was de PA-RISC-architectuur vrijwel dood; de leverancier bood geen noemenswaardige updates aan. Als gevolg hiervan zijn we begonnen met de overstap van HP UX/PA RISC naar Linux/x86. De transitie begon met de aanpassing van toegangsservers.

Waarom moesten we de architectuur opnieuw veranderen? Feit is dat hoogfrequente handel het belastingsprofiel van de systeemkern aanzienlijk heeft veranderd.

Laten we zeggen dat we een kleine transactie hebben die een aanzienlijke prijsverandering veroorzaakte: iemand kocht een half miljard dollar. Na een paar milliseconden merken alle marktdeelnemers dit op en beginnen ze een correctie uit te voeren. Uiteraard staan ​​verzoeken in een enorme wachtrij, waarbij het systeem veel tijd nodig heeft om te wissen.

Bij dit interval van 50 ms bedraagt ​​de gemiddelde snelheid ongeveer 16 transacties per seconde. Als we het venster terugbrengen tot 20 ms, halen we een gemiddelde snelheid van 90 transacties per seconde, met 200 transacties op het hoogtepunt. Met andere woorden, de belasting is niet constant, met plotselinge uitbarstingen. En de wachtrij met aanvragen moet altijd snel worden verwerkt.

Maar waarom staat er überhaupt een wachtrij? In ons voorbeeld merkten veel gebruikers dus de prijsverandering op en stuurden ze dienovereenkomstig transacties. Ze komen naar Gateway, het serialiseert ze, stelt een bepaalde volgorde in en stuurt ze naar het netwerk. Routers schudden de pakketten in willekeurige volgorde en sturen ze door. Wiens pakket als eerste arriveerde, heeft die transactie “gewonnen”. Als gevolg hiervan begonnen beursklanten te merken dat als dezelfde transactie vanaf verschillende gateways werd verzonden, de kans op een snelle verwerking toenam. Al snel begonnen uitwisselingsrobots Gateway te bombarderen met verzoeken, en er ontstond een lawine aan transacties.

Een nieuwe ronde van evolutie

Na uitgebreid testen en onderzoek zijn we overgestapt op de real-time besturingssysteemkernel. Hiervoor hebben we gekozen voor RedHat Enterprise MRG Linux, waarbij MRG staat voor messaging real-time grid. Het voordeel van real-time patches is dat ze het systeem optimaliseren voor de snelst mogelijke uitvoering: alle processen staan ​​opgesteld in een FIFO-wachtrij, kernen kunnen worden geïsoleerd, geen uitwerpingen, alle transacties worden in strikte volgorde verwerkt.

Rood - werken met een wachtrij in een reguliere kernel, groen - werken in een realtime kernel.

Maar het bereiken van een lage latentie op reguliere servers is niet zo eenvoudig:

• De SMI-modus, die in de x86-architectuur de basis vormt voor het werken met belangrijke randapparatuur, interfereert enorm. Het verwerken van allerlei hardware-events en het beheer van componenten en apparaten gebeurt door de firmware in de zogenaamde transparante SMI-modus, waarbij het besturingssysteem helemaal niet ziet wat de firmware doet. In de regel bieden alle grote leveranciers speciale uitbreidingen voor firmwareservers waarmee de hoeveelheid SMI-verwerking kan worden verminderd.
• Er mag geen dynamische controle zijn over de processorfrequentie, dit leidt tot extra downtime.
• Wanneer het bestandssysteemlogboek wordt leeggemaakt, vinden er bepaalde processen in de kernel plaats die onvoorspelbare vertragingen veroorzaken.
• Je moet aandacht besteden aan zaken als CPU-affiniteit, Interrupt-affiniteit, NUMA.

Ik moet zeggen dat het onderwerp van het opzetten van Linux-hardware en -kernel voor realtime verwerking een apart artikel verdient. We hebben veel tijd besteed aan experimenteren en onderzoeken voordat we een goed resultaat bereikten.

Bij de overstap van PA-RISC-servers naar x86 hoefden we de systeemcode praktisch niet veel te veranderen, we hebben deze alleen maar aangepast en opnieuw geconfigureerd. Tegelijkertijd hebben we verschillende bugs opgelost. Zo kwamen de gevolgen van het feit dat PA RISC een Big endian-systeem was en x86 een Little endian-systeem al snel boven water: data werden bijvoorbeeld verkeerd uitgelezen. De lastigere bug was die PA RISC gebruikt consequent consistent (Sequentieel consistent) geheugentoegang, terwijl x86 leesbewerkingen kan herschikken, zodat code die absoluut geldig was op het ene platform, op het andere niet meer werkte.

Na de overstap naar x86 zijn de prestaties bijna verdrievoudigd, de gemiddelde verwerkingstijd van transacties daalde tot 60 μs.

Laten we nu eens nader bekijken welke belangrijke wijzigingen zijn aangebracht in de systeemarchitectuur.

Heet reserve-epos

Toen we overstapten naar commodity-servers, waren we ons ervan bewust dat deze minder betrouwbaar waren. Daarom zijn we bij het creëren van een nieuwe architectuur a priori uitgegaan van de mogelijkheid van het falen van een of meer knooppunten. Daarom was er een hot standby-systeem nodig dat zeer snel kon overschakelen naar back-upmachines.

Daarnaast waren er nog andere vereisten:

• In geen geval mag u verwerkte transacties kwijtraken.
• Het systeem moet absoluut transparant zijn voor onze infrastructuur.
• Clients mogen geen verbroken verbindingen zien.
• Voorbehouden mogen geen aanzienlijke vertraging met zich meebrengen, omdat dit een cruciale factor is voor de uitwisseling.

Bij het maken van een hot standby-systeem hebben we dergelijke scenario's niet als dubbele mislukkingen beschouwd (het netwerk op één server werkte bijvoorbeeld niet meer en de hoofdserver liep vast); heeft geen rekening gehouden met de mogelijkheid van fouten in de software, omdat deze tijdens het testen worden ontdekt; en hield geen rekening met de onjuiste werking van de hardware.

Hierdoor kwamen we tot het volgende schema:

• De hoofdserver communiceerde rechtstreeks met de Gateway-servers.
• Alle transacties die op de hoofdserver werden ontvangen, werden via een apart kanaal onmiddellijk gerepliceerd naar de back-upserver. De arbiter (gouverneur) coördineerde de omschakeling als er zich problemen voordeden.

  

• De hoofdserver verwerkte elke transactie en wachtte op bevestiging van de back-upserver. Om de latentie tot een minimum te beperken, hebben we vermeden te wachten tot de transactie op de back-upserver was voltooid. Omdat de tijd die een transactie nodig had om over het netwerk te reizen vergelijkbaar was met de uitvoeringstijd, werd er geen extra latentie toegevoegd.
• We konden alleen de verwerkingsstatus van de hoofd- en back-upservers voor de vorige transactie controleren, en de verwerkingsstatus van de huidige transactie was onbekend. Omdat we nog steeds single-threaded processen gebruikten, zou het wachten op een reactie van Backup de hele verwerkingsstroom hebben vertraagd. Daarom hebben we een redelijk compromis gesloten: we hebben het resultaat van de vorige transactie gecontroleerd.

Het schema werkte als volgt.

Laten we zeggen dat de hoofdserver niet meer reageert, maar dat de gateways blijven communiceren. Er vindt een time-out plaats op de back-upserver, deze neemt contact op met de gouverneur, die hem de rol van hoofdserver toewijst, en alle Gateways schakelen over naar de nieuwe hoofdserver.

Als de hoofdserver weer online komt, veroorzaakt dit ook een interne time-out, omdat er al een bepaalde tijd geen oproepen meer zijn geweest naar de server vanaf de Gateway. Vervolgens wendt hij zich ook tot de gouverneur en sluit hem uit van het plan. Hierdoor werkt de beurs tot het einde van de handelsperiode met één server. Omdat de kans op een serverstoring vrij laag is, werd dit schema als zeer acceptabel beschouwd; het bevatte geen complexe logica en was gemakkelijk te testen.

Worden voortgezet.

Bron: www.habr.com