Ebolusyon ng arkitektura ng trading at clearing system ng Moscow Exchange. Bahagi 1

Kamusta kayong lahat! Ang pangalan ko ay Sergey Kostanbaev, sa Exchange ay binubuo ko ang core ng sistema ng kalakalan.

Kapag ang mga pelikula sa Hollywood ay nagpapakita ng New York Stock Exchange, palaging ganito: pulutong ng mga tao, lahat ay sumisigaw ng kung ano, kumakaway ng mga papel, ganap na kaguluhan ang nangyayari. Ito ay hindi kailanman nangyari dito sa Moscow Exchange, dahil ang pangangalakal ay isinasagawa nang elektroniko mula pa sa simula at batay sa dalawang pangunahing platform - Spectra (forex market) at ASTS (foreign exchange, stock at money market). At ngayon gusto kong pag-usapan ang tungkol sa ebolusyon ng arkitektura ng ASTS trading at clearing system, tungkol sa iba't ibang solusyon at natuklasan. Mahahaba ang kwento, kaya kinailangan kong hatiin ito sa dalawang bahagi.

Isa kami sa iilang exchange sa mundo na nakikipagkalakalan ng mga asset ng lahat ng klase at nagbibigay ng buong hanay ng mga serbisyo ng exchange. Halimbawa, noong nakaraang taon ay niraranggo namin ang pangalawa sa mundo sa mga tuntunin ng dami ng kalakalan ng bono, ika-25 na puwesto sa lahat ng stock exchange, ika-13 na puwesto sa capitalization sa mga pampublikong palitan.

Para sa mga propesyonal na kalahok sa pangangalakal, ang mga parameter tulad ng oras ng pagtugon, katatagan ng pamamahagi ng oras (jitter) at pagiging maaasahan ng buong complex ay kritikal. Kasalukuyan kaming nagpoproseso ng sampu-sampung milyong mga transaksyon bawat araw. Ang pagproseso ng bawat transaksyon ng kernel ng system ay tumatagal ng sampu-sampung microseconds. Siyempre, ang mga mobile operator sa Bisperas ng Bagong Taon o mga search engine mismo ay may mas mataas na workload kaysa sa atin, ngunit sa mga tuntunin ng workload, kasama ang mga nabanggit na katangian, kakaunti ang maaaring ihambing sa amin, tila sa akin. Kasabay nito, mahalaga para sa amin na ang system ay hindi bumagal nang isang segundo, gumagana nang ganap na matatag, at lahat ng mga gumagamit ay nasa pantay na katayuan.

Isang maliit na kasaysayan

Noong 1994, ang sistema ng Australian ASTS ay inilunsad sa Moscow Interbank Currency Exchange (MICEX), at mula sa sandaling iyon ay mabibilang ang kasaysayan ng elektronikong kalakalan ng Russia. Noong 1998, ang arkitektura ng palitan ay ginawang makabago upang ipakilala ang kalakalan sa Internet. Simula noon, ang bilis ng pagpapatupad ng mga bagong solusyon at pagbabago sa arkitektura sa lahat ng mga sistema at subsystem ay nagkakaroon lamang ng momentum.

Sa mga taong iyon, nagtrabaho ang exchange system sa hi-end na hardware - napaka-maaasahang mga server ng HP Superdome 9000 (na binuo sa PA-RISC), kung saan ganap na nadoble ang lahat: mga subsystem ng input/output, network, RAM (sa katunayan, mayroong isang RAID array ng RAM), mga processor (hot-swappable). Posibleng baguhin ang anumang bahagi ng server nang hindi pinipigilan ang makina. Umasa kami sa mga device na ito at itinuring namin ang mga ito na halos hindi ligtas. Ang operating system ay isang Unix-like HP UX system.

Ngunit mula noong mga 2010, lumitaw ang isang phenomenon na tinatawag na high-frequency trading (HFT), o high-frequency trading - sa madaling salita, mga stock exchange robot. Sa loob lamang ng 2,5 taon, ang pag-load sa aming mga server ay tumaas ng 140 beses.

Imposibleng makayanan ang gayong pagkarga sa lumang arkitektura at kagamitan. Ito ay kinakailangan upang kahit papaano ay umangkop.

simula

Ang mga kahilingan sa exchange system ay maaaring nahahati sa dalawang uri:

• Mga transaksyon. Kung gusto mong bumili ng dolyar, share o iba pa, magpapadala ka ng transaksyon sa sistema ng kalakalan at makatanggap ng tugon tungkol sa tagumpay.
• Mga kahilingan sa impormasyon. Kung gusto mong malaman ang kasalukuyang presyo, tingnan ang order book o mga indeks, pagkatapos ay magpadala ng mga kahilingan sa impormasyon.

Sa eskematiko, ang core ng system ay maaaring nahahati sa tatlong antas:

• Ang antas ng kliyente, kung saan nagtatrabaho ang mga broker at kliyente. Nakikipag-ugnayan silang lahat sa mga server ng pag-access.
• Ang mga gateway server ay mga caching server na lokal na nagpoproseso ng lahat ng mga kahilingan sa impormasyon. Gusto mo bang malaman kung anong presyo ang kasalukuyang kinakalakal ng mga pagbabahagi ng Sberbank? Ang kahilingan ay mapupunta sa access server.
• Ngunit kung gusto mong bumili ng mga pagbabahagi, pagkatapos ang kahilingan ay mapupunta sa gitnang server (Trade Engine). Mayroong isang ganoong server para sa bawat uri ng merkado, gumaganap sila ng isang mahalagang papel, ito ay para sa kanila na nilikha namin ang sistemang ito.

Ang core ng trading system ay isang matalinong in-memory database kung saan ang lahat ng mga transaksyon ay exchange transactions. Ang base ay isinulat sa C, ang tanging panlabas na mga dependency ay ang libc library at walang pabago-bagong paglalaan ng memorya. Upang bawasan ang oras ng pagpoproseso, ang system ay nagsisimula sa isang static na hanay ng mga arrays at sa static na relocation ng data: una, ang lahat ng data para sa kasalukuyang araw ay na-load sa memorya, at walang karagdagang disk access ang ginagawa, ang lahat ng trabaho ay isinasagawa lamang sa memorya. Kapag nagsimula ang system, ang lahat ng reference na data ay pinagsunod-sunod na, kaya ang paghahanap ay gumagana nang napakahusay at tumatagal ng kaunting oras sa runtime. Ang lahat ng mga talahanayan ay ginawa gamit ang mga mapanghimasok na listahan at mga puno para sa mga dynamic na istruktura ng data upang hindi sila nangangailangan ng paglalaan ng memorya sa runtime.

Tingnan natin sandali ang kasaysayan ng pag-unlad ng ating sistema ng kalakalan at paglilinis.
Ang unang bersyon ng arkitektura ng trading at clearing system ay binuo sa tinatawag na Unix interaction: ginamit ang shared memory, semaphores at queues, at ang bawat proseso ay binubuo ng isang thread. Ang pamamaraang ito ay laganap noong unang bahagi ng 1990s.

Ang unang bersyon ng system ay naglalaman ng dalawang antas ng Gateway at isang sentral na server ng sistema ng kalakalan. Ang daloy ng trabaho ay ganito:

• Nagpapadala ang kliyente ng kahilingan, na umaabot sa Gateway. Sinusuri nito ang bisa ng format (ngunit hindi ang data mismo) at tinatanggihan ang mga maling transaksyon.
• Kung ang isang kahilingan sa impormasyon ay naipadala, ito ay isinasagawa nang lokal; kung pinag-uusapan natin ang tungkol sa isang transaksyon, ito ay na-redirect sa gitnang server.
• Pagkatapos ay pinoproseso ng trading engine ang transaksyon, binabago ang lokal na memorya, at nagpapadala ng tugon sa transaksyon at mismong transaksyon para sa pagtitiklop gamit ang isang hiwalay na replication engine.
• Ang Gateway ay tumatanggap ng tugon mula sa gitnang node at ipinapasa ito sa kliyente.
• Pagkaraan ng ilang oras, natatanggap ng Gateway ang transaksyon sa pamamagitan ng mekanismo ng pagtitiklop, at sa pagkakataong ito ay lokal itong isinasagawa, binabago ang mga istruktura ng data nito upang ang mga susunod na kahilingan ng impormasyon ay magpakita ng pinakabagong data.

Sa katunayan, inilalarawan nito ang isang modelo ng pagtitiklop kung saan ganap na kinopya ng Gateway ang mga aksyon na ginawa sa sistema ng kalakalan. Tiniyak ng isang hiwalay na channel ng pagtitiklop na ang mga transaksyon ay naisakatuparan sa parehong pagkakasunud-sunod sa maraming access node.

Dahil single-threaded ang code, ginamit ang isang klasikong scheme na may process forks para maglingkod sa maraming kliyente. Gayunpaman, napakamahal na i-fork ang buong database, kaya ang magaan na mga proseso ng serbisyo ay ginamit na nakolekta ang mga packet mula sa mga session ng TCP at inilipat ang mga ito sa isang queue (SystemV Message Queue). Gumana lamang ang Gateway at Trade Engine sa queue na ito, na kumukuha ng mga transaksyon mula doon para sa pagpapatupad. Hindi na posible na magpadala ng tugon dito, dahil hindi malinaw kung aling proseso ng serbisyo ang dapat basahin ito. Kaya gumawa kami ng isang trick: bawat forked process ay lumikha ng isang response queue para sa sarili nito, at kapag may isang request na dumating sa papasok na queue, isang tag para sa response queue ay agad na idinagdag dito.

Ang patuloy na pagkopya ng malaking halaga ng data mula sa pila patungo sa pila ay lumikha ng mga problema, lalo na karaniwan para sa mga kahilingan sa impormasyon. Samakatuwid, gumamit kami ng isa pang trick: bilang karagdagan sa queue ng tugon, ang bawat proseso ay lumikha din ng shared memory (SystemV Shared Memory). Ang mga pakete mismo ay inilagay sa loob nito, at isang tag lamang ang nakaimbak sa pila, na nagpapahintulot sa isa na mahanap ang orihinal na pakete. Nakatulong ito sa pag-imbak ng data sa cache ng processor.

Kasama sa SystemV IPC ang mga utility para sa pagtingin sa estado ng queue, memory, at semaphore na mga bagay. Aktibong ginamit namin ito upang maunawaan kung ano ang nangyayari sa system sa isang partikular na sandali, kung saan naipon ang mga packet, kung ano ang na-block, atbp.

Mga unang modernisasyon

Una sa lahat, inalis namin ang single-process na Gateway. Ang makabuluhang disbentaha nito ay kaya nitong pangasiwaan ang alinman sa isang transaksyon sa pagtitiklop o isang kahilingan sa impormasyon mula sa isang kliyente. At habang tumataas ang load, magtatagal ang Gateway sa pagproseso ng mga kahilingan at hindi na maproseso ang daloy ng pagtitiklop. Bilang karagdagan, kung nagpadala ang kliyente ng isang transaksyon, kailangan mo lamang suriin ang bisa nito at ipasa ito nang higit pa. Samakatuwid, pinalitan namin ang nag-iisang proseso ng Gateway ng maraming bahagi na maaaring tumakbo nang magkatulad: multi-threaded na impormasyon at mga proseso ng transaksyon na tumatakbo nang hiwalay sa isa't isa sa isang shared memory area gamit ang RW locking. At sa parehong oras ipinakilala namin ang mga proseso ng pagpapadala at pagtitiklop.

Epekto ng High Frequency Trading

Ang nasa itaas na bersyon ng arkitektura ay umiral hanggang 2010. Samantala, hindi na kami nasiyahan sa pagganap ng mga server ng HP Superdome. Bilang karagdagan, ang arkitektura ng PA-RISC ay halos patay na; ang vendor ay hindi nag-aalok ng anumang makabuluhang mga update. Bilang resulta, nagsimula kaming lumipat mula sa HP UX/PA RISC patungo sa Linux/x86. Nagsimula ang paglipat sa adaptasyon ng mga access server.

Bakit kailangan nating baguhin muli ang arkitektura? Ang katotohanan ay ang high-frequency na kalakalan ay makabuluhang nabago ang profile ng pagkarga sa core ng system.

Sabihin nating mayroon tayong maliit na transaksyon na nagdulot ng malaking pagbabago sa presyo - may bumili ng kalahating bilyong dolyar. Pagkatapos ng ilang millisecond, napansin ito ng lahat ng kalahok sa merkado at nagsimulang gumawa ng pagwawasto. Naturally, ang mga kahilingan ay nakalinya sa isang malaking pila, na ang system ay magtatagal upang maalis.

Sa pagitan ng 50 ms na ito, ang average na bilis ay humigit-kumulang 16 libong mga transaksyon bawat segundo. Kung babawasan natin ang window sa 20 ms, makakakuha tayo ng average na bilis na 90 libong mga transaksyon sa bawat segundo, na may 200 libong mga transaksyon sa tuktok. Sa madaling salita, ang pagkarga ay hindi pare-pareho, na may mga biglaang pagsabog. At ang pila ng mga kahilingan ay dapat palaging maproseso nang mabilis.

Pero bakit parang may pila? Kaya, sa aming halimbawa, napansin ng maraming user ang pagbabago ng presyo at nagpadala ng mga transaksyon nang naaayon. Dumating sila sa Gateway, sine-serialize ang mga ito, nagtatakda ng isang tiyak na order at ipinapadala sila sa network. I-shuffle ng mga router ang mga packet at i-forward ang mga ito. Kaninong pakete ang unang dumating, ang transaksyong iyon ay "nanalo". Bilang resulta, nagsimulang mapansin ng mga exchange client na kung ang parehong transaksyon ay ipinadala mula sa ilang mga Gateway, kung gayon ang mga pagkakataon ng mabilis na pagproseso nito ay tumaas. Di-nagtagal, sinimulan ng mga exchange robot ang pagbomba sa Gateway ng mga kahilingan, at isang avalanche ng mga transaksyon ang lumitaw.

Isang bagong yugto ng ebolusyon

Pagkatapos ng malawak na pagsubok at pananaliksik, lumipat kami sa real-time na kernel ng operating system. Para dito, pinili namin ang RedHat Enterprise MRG Linux, kung saan ang MRG ay kumakatawan sa real-time na grid ng pagmemensahe. Ang bentahe ng real-time na mga patch ay na-optimize nila ang system para sa pinakamabilis na posibleng pagpapatupad: ang lahat ng mga proseso ay naka-line up sa isang FIFO queue, ang mga core ay maaaring ihiwalay, walang ejections, ang lahat ng mga transaksyon ay pinoproseso sa mahigpit na pagkakasunud-sunod.

Pula - nagtatrabaho sa isang queue sa isang regular na kernel, berde - nagtatrabaho sa isang real-time na kernel.

Ngunit ang pagkamit ng mababang latency sa mga regular na server ay hindi napakadali:

• Ang mode ng SMI, na sa arkitektura ng x86 ay ang batayan para sa pagtatrabaho sa mahahalagang peripheral, ay lubos na nakakasagabal. Ang pagpoproseso ng lahat ng uri ng mga kaganapan sa hardware at pamamahala ng mga bahagi at device ay ginagawa ng firmware sa tinatawag na transparent SMI mode, kung saan hindi nakikita ng operating system kung ano ang ginagawa ng firmware. Bilang panuntunan, nag-aalok ang lahat ng pangunahing vendor ng mga espesyal na extension para sa mga server ng firmware na nagbibigay-daan sa pagbawas sa dami ng pagproseso ng SMI.
• Dapat ay walang dynamic na kontrol sa dalas ng processor, humahantong ito sa karagdagang downtime.
• Kapag na-flush ang log ng file system, nangyayari ang ilang proseso sa kernel na nagdudulot ng mga hindi inaasahang pagkaantala.
• Kailangan mong bigyang pansin ang mga bagay tulad ng CPU Affinity, Interrupt affinity, NUMA.

Dapat kong sabihin na ang paksa ng pag-set up ng Linux hardware at kernel para sa realtime na pagproseso ay nararapat sa isang hiwalay na artikulo. Kami ay gumugol ng maraming oras sa pag-eksperimento at pagsasaliksik bago namin nakamit ang isang magandang resulta.

Kapag lumipat mula sa mga server ng PA-RISC patungo sa x86, halos hindi namin kailangang baguhin ang code ng system, inangkop lang namin ito at muling na-configure. Sa parehong oras, naayos namin ang ilang mga bug. Halimbawa, ang mga kahihinatnan ng katotohanan na ang PA RISC ay isang Big endian system, at ang x86 ay isang Little endian system, ay mabilis na lumabas: halimbawa, ang data ay hindi nabasa nang tama. Ang mas nakakalito na bug ay ang ginagamit ng PA RISC pare-parehong pare-pareho (Sunud-sunod na pare-pareho) access sa memorya, samantalang ang x86 ay maaaring muling ayusin ang mga operasyon sa pagbasa, kaya ang code na ganap na wasto sa isang platform ay nasira sa isa pa.

Pagkatapos lumipat sa x86, tumaas ang pagganap ng halos tatlong beses, ang average na oras ng pagproseso ng transaksyon ay bumaba sa 60 μs.

Tingnan natin ngayon kung anong mga pangunahing pagbabago ang ginawa sa arkitektura ng system.

Mainit na reserbang epiko

Noong lumipat sa mga server ng kalakal, alam namin na hindi gaanong maaasahan ang mga ito. Samakatuwid, kapag lumilikha ng isang bagong arkitektura, a priori namin ang posibilidad ng pagkabigo ng isa o higit pang mga node. Samakatuwid, kailangan ang isang mainit na standby system na maaaring mabilis na lumipat sa mga backup na makina.

Bilang karagdagan, mayroong iba pang mga kinakailangan:

• Sa anumang pagkakataon dapat kang mawala ang mga naprosesong transaksyon.
• Ang sistema ay dapat na ganap na transparent sa ating imprastraktura.
• Hindi dapat makita ng mga kliyente ang mga bumabagsak na koneksyon.
• Ang mga pagpapareserba ay hindi dapat magpakilala ng malaking pagkaantala dahil ito ay isang kritikal na kadahilanan para sa palitan.

Kapag lumilikha ng isang mainit na standby system, hindi namin isinasaalang-alang ang mga ganitong senaryo bilang dobleng pagkabigo (halimbawa, ang network sa isang server ay tumigil sa paggana at ang pangunahing server ay nagyelo); hindi isinasaalang-alang ang posibilidad ng mga error sa software dahil natukoy ang mga ito sa panahon ng pagsubok; at hindi isinasaalang-alang ang maling operasyon ng hardware.

Bilang resulta, dumating kami sa sumusunod na pamamaraan:

• Direktang nakipag-ugnayan ang pangunahing server sa mga server ng Gateway.
• Ang lahat ng mga transaksyon na natanggap sa pangunahing server ay agad na kinopya sa backup na server sa pamamagitan ng isang hiwalay na channel. Ang arbiter (Gobernador) ang nag-coordinate sa paglipat kung may mga problemang lumitaw.

  

• Pinoproseso ng pangunahing server ang bawat transaksyon at naghintay ng kumpirmasyon mula sa backup server. Upang mapanatiling minimum ang latency, iniwasan naming maghintay para makumpleto ang transaksyon sa backup na server. Dahil ang oras na inabot para sa isang transaksyon sa paglalakbay sa buong network ay maihahambing sa oras ng pagpapatupad, walang karagdagang latency ang idinagdag.
• Maaari lamang naming suriin ang katayuan sa pagpoproseso ng pangunahing at backup na mga server para sa nakaraang transaksyon, at ang katayuan sa pagpoproseso ng kasalukuyang transaksyon ay hindi alam. Dahil gumagamit pa rin kami ng mga single-threaded na proseso, ang paghihintay ng tugon mula sa Backup ay magpapabagal sa buong daloy ng pagproseso, kaya gumawa kami ng makatwirang kompromiso: sinuri namin ang resulta ng nakaraang transaksyon.

Ang scheme ay nagtrabaho bilang mga sumusunod.

Sabihin nating ang pangunahing server ay huminto sa pagtugon, ngunit ang mga Gateway ay patuloy na nakikipag-ugnayan. Ang isang timeout ay nangyayari sa backup server, ito ay nakikipag-ugnayan sa Gobernador, na nagtatalaga dito ng papel ng pangunahing server, at lahat ng mga Gateway ay lumipat sa bagong pangunahing server.

Kung ang pangunahing server ay bumalik sa online, ito rin ay nagti-trigger ng isang panloob na timeout, dahil walang mga tawag sa server mula sa Gateway para sa isang tiyak na oras. Pagkatapos ay bumaling din siya sa Gobernador, at ibinukod niya siya sa plano. Bilang resulta, gumagana ang palitan sa isang server hanggang sa katapusan ng panahon ng pangangalakal. Dahil ang posibilidad ng isang pagkabigo ng server ay medyo mababa, ang pamamaraan na ito ay itinuturing na katanggap-tanggap; hindi ito naglalaman ng kumplikadong lohika at madaling subukan.

Upang magpatuloy.

Pinagmulan: www.habr.com