Razvoj arhitekture trgovalnega in klirinškega sistema Moskovske borze. 1. del

Pozdravljeni vsi skupaj! Moje ime je Sergey Kostanbaev, na borzi razvijam jedro trgovalnega sistema.

Ko hollywoodski filmi prikazujejo newyorško borzo, je vedno videti takole: množica ljudi, vsi nekaj kričijo, mahajo s papirji, dogaja se popoln kaos. Pri nas na moskovski borzi se to še nikoli ni zgodilo, saj je trgovanje že od vsega začetka potekalo elektronsko in temelji na dveh glavnih platformah – Spectra (forex trg) in ASTS (devizni, delniški in denarni trg). In danes želim govoriti o razvoju arhitekture trgovalnega in klirinškega sistema ASTS, o različnih rešitvah in ugotovitvah. Zgodba bo dolga, zato sem jo moral razdeliti na dva dela.

Smo ena redkih borz na svetu, ki trguje s sredstvi vseh razredov in nudi celotno paleto borznih storitev. Lani smo bili na primer drugi na svetu po obsegu trgovanja z obveznicami, 25. mesto med vsemi borzami, 13. mesto po kapitalizaciji med javnimi borzami.

Za profesionalne udeležence trgovanja so kritični parametri, kot so odzivni čas, stabilnost časovne porazdelitve (tresenje) in zanesljivost celotnega kompleksa. Trenutno obdelamo več deset milijonov transakcij na dan. Obdelava vsake transakcije s strani sistemskega jedra traja več deset mikrosekund. Seveda imajo mobilni operaterji na silvestrovo ali sami iskalniki večjo obremenitev od naše, vendar se po obremenjenosti, skupaj z zgoraj omenjenimi lastnostmi, malokdo lahko primerja z nami, se mi zdi. Hkrati nam je pomembno, da se sistem ne upočasni niti za sekundo, deluje popolnoma stabilno in so vsi uporabniki enakopravni.

Malo zgodovine

Leta 1994 je bil na Moskovski medbančni borzi (MICEX) uveden avstralski sistem ASTS in od tega trenutka se lahko šteje ruska zgodovina elektronskega trgovanja. Leta 1998 je bila borzna arhitektura posodobljena za uvedbo internetnega trgovanja. Od takrat se hitrost uvajanja novih rešitev in arhitekturnih sprememb v vse sisteme in podsisteme le še povečuje.

V tistih letih je sistem izmenjave deloval na vrhunski strojni opremi - izjemno zanesljivih strežnikih HP Superdome 9000 (zgrajenih na PA-RISC), v katerem je bilo podvojeno absolutno vse: vhodno/izhodni podsistemi, omrežje, RAM (pravzaprav je obstajal RAID niz RAM-a), procesorji (hot-swappable). Bilo je mogoče spremeniti katero koli komponento strežnika, ne da bi zaustavili stroj. Zanesli smo se na te naprave in menili, da so tako rekoč varne pred napakami. Operacijski sistem je bil sistem HP UX, podoben Unixu.

A od približno leta 2010 se je pojavil pojav, imenovan visokofrekvenčno trgovanje (HFT) ali visokofrekvenčno trgovanje – preprosto povedano, borzni roboti. V samo 2,5 letih se je obremenitev naših strežnikov povečala za 140-krat.

S staro arhitekturo in opremo ni bilo mogoče prenesti takšne obremenitve. Treba se je bilo nekako prilagoditi.

začenja

Zahteve za sistem izmenjave lahko razdelimo na dve vrsti:

• Transakcije. Če želite kupiti dolarje, delnice ali kaj drugega, pošljete transakcijo v trgovalni sistem in prejmete odgovor o uspehu.
• Zahteve po informacijah. Če želite izvedeti trenutno ceno, si oglejte knjigo naročil ali indekse, nato pošljite zahteve za informacije.

Shematično lahko jedro sistema razdelimo na tri ravni:

• Raven stranke, na kateri delajo posredniki in stranke. Vsi komunicirajo s strežniki za dostop.
• Prehodni strežniki so strežniki za predpomnjenje, ki lokalno obdelujejo vse zahteve po informacijah. Vas zanima, po kakšni ceni trenutno kotirajo delnice Sberbank? Zahteva gre na strežnik za dostop.
• Če pa želite kupiti delnice, potem gre zahteva na centralni strežnik (Trade Engine). Za vsako vrsto trga obstaja en tak strežnik, igrajo ključno vlogo, zanje smo ustvarili ta sistem.

Jedro trgovalnega sistema je pametna baza podatkov v pomnilniku, v kateri so vse transakcije menjalne transakcije. Osnova je bila napisana v C, edina zunanja odvisnost je bila knjižnica libc in sploh ni bilo dinamičnega dodeljevanja pomnilnika. Za skrajšanje časa obdelave se sistem začne s statičnim naborom nizov in s statično premestitvijo podatkov: najprej se vsi podatki za trenutni dan naložijo v pomnilnik in se ne izvede noben nadaljnji dostop do diska, vse delo se izvaja samo v pomnilniku. Ko se sistem zažene, so vsi referenčni podatki že razvrščeni, zato iskanje deluje zelo učinkovito in traja malo časa v času izvajanja. Vse tabele so narejene z vsiljivimi seznami in drevesi za dinamične podatkovne strukture, tako da ne zahtevajo dodelitve pomnilnika med izvajanjem.

Oglejmo si na kratko zgodovino razvoja našega trgovalnega in klirinškega sistema.
Prva različica arhitekture trgovalnega in klirinškega sistema je bila zgrajena na tako imenovani interakciji Unix: uporabljeni so bili skupni pomnilnik, semaforji in čakalne vrste, vsak proces pa je bil sestavljen iz ene niti. Ta pristop je bil zelo razširjen v zgodnjih devetdesetih letih.

Prva različica sistema je vsebovala dve ravni prehoda in centralni strežnik trgovalnega sistema. Potek dela je bil tak:

• Odjemalec pošlje zahtevo, ki doseže prehod. Preveri veljavnost formata (ne pa samih podatkov) in zavrne nepravilne transakcije.
• Če je bila poslana zahteva po informacijah, se izvrši lokalno; če govorimo o transakciji, potem je ta preusmerjena na centralni strežnik.
• Trgovalni mehanizem nato obdela transakcijo, spremeni lokalni pomnilnik in pošlje odgovor na transakcijo ter samo transakcijo za replikacijo z uporabo ločenega replikacijskega mehanizma.
• Gateway prejme odgovor iz osrednjega vozlišča in ga posreduje odjemalcu.
• Prehod čez nekaj časa prejme transakcijo prek mehanizma replikacije in jo tokrat izvede lokalno ter spremeni svoje podatkovne strukture, tako da naslednje zahteve po informacijah prikažejo najnovejše podatke.

Pravzaprav opisuje model podvajanja, v katerem je Gateway popolnoma posnemal dejanja, izvedena v sistemu trgovanja. Ločen replikacijski kanal je zagotovil, da so se transakcije izvajale v istem vrstnem redu v več dostopnih vozliščih.

Ker je bila koda enonitna, je bila uporabljena klasična shema s procesnimi vilicami za oskrbo številnih strank. Vendar pa je bilo zelo drago razcepiti celotno zbirko podatkov, zato so bili uporabljeni lahki storitveni procesi, ki so zbirali pakete iz sej TCP in jih prenašali v eno čakalno vrsto (SystemV Message Queue). Gateway in Trade Engine sta delovala samo s to čakalno vrsto in jemala transakcije od tam za izvedbo. Nanj ni bilo več mogoče poslati odgovora, ker ni bilo jasno, kateri servisni proces naj ga prebere. Zato smo se zatekli k triku: vsak razcepljen proces je zase ustvaril čakalno vrsto odgovorov in ko je v dohodno čakalno vrsto prišla zahteva, je bila vanjo takoj dodana oznaka za čakalno vrsto odgovorov.

Nenehno kopiranje velikih količin podatkov iz čakalne vrste v čakalno vrsto je povzročalo težave, še posebej značilne za zahteve po informacijah. Zato smo uporabili še en trik: poleg čakalne vrste odgovorov je vsak proces ustvaril tudi skupni pomnilnik (SystemV Shared Memory). Vanj so bili postavljeni sami paketi, v čakalni vrsti pa je bila shranjena samo oznaka, ki je omogočala iskanje originalnega paketa. To je pomagalo pri shranjevanju podatkov v predpomnilnik procesorja.

SystemV IPC vključuje pripomočke za ogledovanje stanja čakalne vrste, pomnilnika in objektov semaforja. To smo aktivno uporabljali, da bi razumeli, kaj se v določenem trenutku dogaja v sistemu, kje so se paketi kopičili, kaj je bilo blokirano itd.

Prve posodobitve

Najprej smo se znebili enoprocesnega prehoda. Njegova pomembna pomanjkljivost je bila, da je lahko obdelal eno transakcijo podvajanja ali eno zahtevo po informacijah od stranke. In ko se obremenitev poveča, bo prehod potreboval dlje časa za obdelavo zahtev in ne bo mogel obdelati toka replikacije. Poleg tega, če je stranka poslala transakcijo, morate samo preveriti njeno veljavnost in jo posredovati naprej. Zato smo zamenjali en sam proces Gateway z več komponentami, ki se lahko izvajajo vzporedno: večnitnimi informacijami in transakcijskimi procesi, ki tečejo neodvisno drug od drugega na območju skupnega pomnilnika z uporabo zaklepanja RW. Hkrati smo uvedli procese odpreme in replikacije.

Vpliv visokofrekvenčnega trgovanja

Zgornja različica arhitekture je obstajala do leta 2010. Medtem nismo bili več zadovoljni z delovanjem strežnikov HP Superdome. Poleg tega je bila arhitektura PA-RISC tako rekoč mrtva; prodajalec ni ponudil nobenih pomembnih posodobitev. Posledično smo začeli prehajati s HP UX/PA RISC na Linux/x86. Prehod se je začel s prilagoditvijo dostopovnih strežnikov.

Zakaj smo morali znova spreminjati arhitekturo? Dejstvo je, da je visokofrekvenčno trgovanje močno spremenilo profil obremenitve jedra sistema.

Recimo, da imamo majhno transakcijo, ki je povzročila znatno spremembo cene – nekdo je kupil pol milijarde dolarjev. Po nekaj milisekundah vsi udeleženci na trgu to opazijo in začnejo izvajati popravke. Zahteve se seveda vrstijo v ogromni čakalni vrsti, ki jo bo sistem dolgo počistil.

Pri tem intervalu 50 ms je povprečna hitrost okoli 16 tisoč transakcij na sekundo. Če okno zmanjšamo na 20 ms, dobimo povprečno hitrost 90 tisoč transakcij na sekundo, pri čemer je na vrhuncu 200 tisoč transakcij. Z drugimi besedami, obremenitev ni stalna, z nenadnimi izbruhi. In čakalna vrsta zahtev mora biti vedno hitro obdelana.

A zakaj sploh je čakalna vrsta? Tako je v našem primeru veliko uporabnikov opazilo spremembo cene in ustrezno poslalo transakcije. Pridejo v Gateway, jih serializirajo, nastavijo določen vrstni red in jih pošljejo v omrežje. Usmerjevalniki premešajo pakete in jih posredujejo naprej. Čigar paket je prispel prvi, ta transakcija je "zmagala". Posledično so stranke izmenjave začele opažati, da če je bila ista transakcija poslana z več prehodov, so se možnosti za njeno hitro obdelavo povečale. Kmalu so menjalni roboti začeli zasipavati Gateway z zahtevami in sprožil se je plaz transakcij.

Nov krog evolucije

Po obsežnem testiranju in raziskavah smo prešli na jedro operacijskega sistema v realnem času. Za to smo izbrali RedHat Enterprise MRG Linux, kjer MRG pomeni mrežo za sporočanje v realnem času. Prednost popravkov v realnem času je, da optimizirajo sistem za najhitrejšo možno izvedbo: vsi procesi so postavljeni v čakalno vrsto FIFO, jedra je mogoče izolirati, ni izmetov, vse transakcije se obdelujejo v strogem zaporedju.

Rdeča - delo s čakalno vrsto v običajnem jedru, zelena - delo v jedru v realnem času.

Toda doseganje nizke zakasnitve na običajnih strežnikih ni tako enostavno:

• Močno moti način SMI, ki je v arhitekturi x86 osnova za delo s pomembnejšo periferijo. Obdelavo vseh vrst strojnih dogodkov ter upravljanje komponent in naprav strojna programska oprema izvaja v tako imenovanem transparentnem načinu SMI, pri katerem operacijski sistem sploh ne vidi, kaj strojna programska oprema počne. Praviloma vsi večji proizvajalci ponujajo posebne razširitve za strežnike vdelane programske opreme, ki omogočajo zmanjšanje količine obdelave SMI.
• Ne bi smelo biti dinamičnega nadzora frekvence procesorja, to vodi do dodatnih izpadov.
• Ko se dnevnik datotečnega sistema izprazni, se v jedru pojavijo določeni procesi, ki povzročijo nepredvidljive zamude.
• Pozorni morate biti na stvari, kot so afiniteta procesorja, afiniteta prekinitev, NUMA.

Moram reči, da si tema nastavitve strojne opreme in jedra Linuxa za obdelavo v realnem času zasluži ločen članek. Preden smo dosegli dober rezultat, smo porabili veliko časa za eksperimentiranje in raziskovanje.

Pri prehodu s strežnikov PA-RISC na x86 nam sistemske kode tako rekoč ni bilo treba veliko spreminjati, le prilagodili smo jo in na novo konfigurirali. Hkrati smo odpravili več napak. Tako so se na primer hitro pokazale posledice dejstva, da je bil PA RISC Big endian sistem, x86 pa Little endian sistem: na primer, podatki so bili napačno prebrani. Težja napaka je bila, da uporablja PA RISC dosledno dosledno (Zaporedno dosledno) dostop do pomnilnika, medtem ko lahko x86 prerazporedi operacije branja, tako da je koda, ki je bila absolutno veljavna na eni platformi, na drugi pokvarjena.

Po prehodu na x86 se je zmogljivost povečala skoraj za trikrat, povprečni čas obdelave transakcij se je zmanjšal na 60 μs.

Oglejmo si zdaj podrobneje, katere ključne spremembe so bile narejene v sistemski arhitekturi.

Vroči rezervni ep

Pri prehodu na blagovne strežnike smo se zavedali, da so manj zanesljivi. Zato smo pri ustvarjanju nove arhitekture a priori predpostavili možnost odpovedi enega ali več vozlišč. Zato je bil potreben sistem vroče pripravljenosti, ki bi lahko zelo hitro preklopil na rezervne stroje.

Poleg tega so bile še druge zahteve:

• V nobenem primeru ne smete izgubiti obdelanih transakcij.
• Sistem mora biti popolnoma pregleden za našo infrastrukturo.
• Odjemalci ne smejo videti prekinjenih povezav.
• Rezervacije ne bi smele povzročiti znatne zamude, ker je to kritičen dejavnik za izmenjavo.

Pri ustvarjanju sistema vroče pripravljenosti takih scenarijev nismo upoštevali kot dvojne okvare (na primer omrežje na enem strežniku je prenehalo delovati in glavni strežnik je zamrznil); ni upošteval možnosti napak v programski opremi, ker so bile ugotovljene med testiranjem; in ni upošteval nepravilnega delovanja strojne opreme.

Kot rezultat smo prišli do naslednje sheme:

• Glavni strežnik je neposredno komuniciral s strežniki Gateway.
• Vse transakcije, prejete na glavnem strežniku, so bile takoj podvojene na rezervni strežnik prek ločenega kanala. Razsodnik (guverner) je koordiniral zamenjavo, če so se pojavile težave.

  

• Glavni strežnik je obdelal vsako transakcijo in čakal na potrditev rezervnega strežnika. Da bi zmanjšali zakasnitev na minimum, smo se izognili čakanju na dokončanje transakcije na rezervnem strežniku. Ker je bil čas, ki je potreben, da transakcija potuje po omrežju, primerljiv s časom izvedbe, ni bila dodana nobena dodatna zakasnitev.
• Preverili smo lahko le status obdelave glavnega in rezervnega strežnika za prejšnjo transakcijo, status obdelave trenutne transakcije pa ni bil znan. Ker smo še vedno uporabljali enonitne procese, bi čakanje na odgovor varnostne kopije upočasnilo celoten tok obdelave, zato smo naredili razumen kompromis: preverili smo rezultat prejšnje transakcije.

Shema je delovala na naslednji način.

Recimo, da se glavni strežnik preneha odzivati, vendar prehodi še naprej komunicirajo. Na rezervnem strežniku pride do časovne omejitve, vzpostavi stik z guvernerjem, ki mu dodeli vlogo glavnega strežnika, in vsi prehodi preklopijo na nov glavni strežnik.

Če glavni strežnik ponovno vzpostavi povezavo, sproži tudi notranjo časovno omejitev, ker s prehoda določen čas ni bilo nobenih klicev na strežnik. Nato se obrne tudi na guvernerja in ta ga izključi iz sheme. Posledično borza deluje z enim strežnikom do konca trgovalnega obdobja. Ker je verjetnost okvare strežnika precej nizka, se je ta shema štela za povsem sprejemljivo; ni vsebovala kompleksne logike in jo je bilo enostavno preizkusiti.

Se nadaljuje.

Vir: www.habr.com