Evolusi seni bina sistem perdagangan dan penjelasan Bursa Moscow. Bahagian 1

Hai semua! Nama saya Sergey Kostanbaev, di Bursa saya sedang membangunkan teras sistem perdagangan.

Apabila filem Hollywood menunjukkan Bursa Saham New York, ia sentiasa kelihatan seperti ini: orang ramai, semua orang menjerit sesuatu, melambai kertas, huru-hara sepenuhnya berlaku. Ini tidak pernah berlaku di sini di Bursa Moscow, kerana perdagangan telah dijalankan secara elektronik dari awal lagi dan berdasarkan dua platform utama - Spectra (pasaran forex) dan ASTS (pasaran pertukaran asing, saham dan wang). Dan hari ini saya ingin bercakap tentang evolusi seni bina sistem perdagangan dan penjelasan ASTS, tentang pelbagai penyelesaian dan penemuan. Ceritanya akan panjang, jadi saya terpaksa memecahkannya kepada dua bahagian.

Kami adalah salah satu daripada beberapa bursa di dunia yang memperdagangkan aset dari semua kelas dan menyediakan rangkaian penuh perkhidmatan pertukaran. Sebagai contoh, tahun lepas kami menduduki tempat kedua di dunia dari segi volum dagangan bon, tempat ke-25 di antara semua bursa saham, tempat ke-13 dalam permodalan di kalangan bursa awam.

Bagi peserta perdagangan profesional, parameter seperti masa tindak balas, kestabilan pengagihan masa (jitter) dan kebolehpercayaan keseluruhan kompleks adalah kritikal. Pada masa ini kami memproses berpuluh juta transaksi setiap hari. Pemprosesan setiap transaksi oleh kernel sistem mengambil masa berpuluh-puluh mikrosaat. Sudah tentu, pengendali mudah alih pada Malam Tahun Baru atau enjin carian sendiri mempunyai beban kerja yang lebih tinggi daripada kami, tetapi dari segi beban kerja, ditambah dengan ciri-ciri yang disebutkan di atas, sedikit yang dapat membandingkan dengan kami, nampaknya saya. Pada masa yang sama, adalah penting bagi kami bahawa sistem tidak melambatkan sesaat, berfungsi dengan benar-benar stabil, dan semua pengguna berada pada kedudukan yang sama.

Sedikit sejarah

Pada tahun 1994, sistem ASTS Australia telah dilancarkan di Moscow Interbank Currency Exchange (MICEX), dan sejak saat itu sejarah perdagangan elektronik Rusia boleh dikira. Pada tahun 1998, seni bina pertukaran telah dimodenkan untuk memperkenalkan perdagangan Internet. Sejak itu, kelajuan pelaksanaan penyelesaian baharu dan perubahan seni bina dalam semua sistem dan subsistem hanya mendapat momentum.

Pada tahun-tahun itu, sistem pertukaran berfungsi pada perkakasan hi-end - pelayan HP Superdome 9000 yang sangat boleh dipercayai (dibina pada PA-RISC), di mana semuanya telah diduplikasi: subsistem input/output, rangkaian, RAM (sebenarnya, terdapat array RAID RAM), pemproses (hot-swappable). Ia adalah mungkin untuk menukar mana-mana komponen pelayan tanpa menghentikan mesin. Kami bergantung pada peranti ini dan menganggapnya hampir selamat gagal. Sistem pengendalian ialah sistem HP UX seperti Unix.

Tetapi sejak kira-kira 2010, satu fenomena telah muncul yang dipanggil perdagangan frekuensi tinggi (HFT), atau perdagangan frekuensi tinggi - secara ringkasnya, robot bursa saham. Hanya dalam 2,5 tahun, beban pada pelayan kami telah meningkat 140 kali ganda.

Ia adalah mustahil untuk menahan beban sedemikian dengan seni bina dan peralatan lama. Ia adalah perlu untuk menyesuaikan diri.

bermula

Permintaan kepada sistem pertukaran boleh dibahagikan kepada dua jenis:

• Transaksi. Jika anda ingin membeli dolar, saham atau sesuatu yang lain, anda menghantar transaksi ke sistem perdagangan dan menerima maklum balas tentang kejayaan.
• Permintaan maklumat. Jika anda ingin mengetahui harga semasa, lihat buku pesanan atau indeks, kemudian hantar permintaan maklumat.

Secara skematik, teras sistem boleh dibahagikan kepada tiga peringkat:

• Tahap pelanggan, di mana broker dan pelanggan bekerja. Mereka semua berinteraksi dengan pelayan akses.
• Pelayan gateway ialah pelayan caching yang memproses semua permintaan maklumat secara setempat. Adakah anda ingin tahu berapa harga saham Sberbank yang didagangkan pada masa ini? Permintaan pergi ke pelayan akses.
• Tetapi jika anda ingin membeli saham, maka permintaan pergi ke pelayan pusat (Trade Engine). Terdapat satu pelayan sedemikian untuk setiap jenis pasaran, mereka memainkan peranan penting, untuk mereka kami mencipta sistem ini.

Teras sistem perdagangan ialah pangkalan data dalam memori yang bijak di mana semua transaksi adalah transaksi pertukaran. Pangkalan ditulis dalam C, satu-satunya kebergantungan luaran ialah perpustakaan libc dan tiada peruntukan memori dinamik sama sekali. Untuk mengurangkan masa pemprosesan, sistem bermula dengan set tatasusunan statik dan dengan penempatan semula data statik: pertama, semua data untuk hari semasa dimuatkan ke dalam memori, dan tiada akses cakera selanjutnya dilakukan, semua kerja dijalankan hanya dalam ingatan. Apabila sistem bermula, semua data rujukan telah diisih, jadi carian berfungsi dengan sangat cekap dan mengambil sedikit masa dalam masa jalan. Semua jadual dibuat dengan senarai mengganggu dan pepohon untuk struktur data dinamik supaya ia tidak memerlukan peruntukan memori pada masa jalan.

Mari kita lihat secara ringkas sejarah perkembangan sistem perdagangan dan penjelasan kami.
Versi pertama seni bina sistem perdagangan dan penjelasan telah dibina atas apa yang dipanggil interaksi Unix: memori yang dikongsi, semaphore dan baris gilir digunakan, dan setiap proses terdiri daripada satu utas. Pendekatan ini telah meluas pada awal 1990-an.

Versi pertama sistem mengandungi dua peringkat Gateway dan pelayan pusat sistem perdagangan. Aliran kerja adalah seperti ini:

• Pelanggan menghantar permintaan, yang sampai ke Gateway. Ia menyemak kesahihan format (tetapi bukan data itu sendiri) dan menolak transaksi yang salah.
• Jika permintaan maklumat telah dihantar, ia dilaksanakan secara tempatan; jika kita bercakap tentang transaksi, maka ia dialihkan ke pelayan pusat.
• Enjin dagangan kemudiannya memproses urus niaga, mengubah suai memori tempatan dan menghantar respons kepada urus niaga dan transaksi itu sendiri untuk replikasi menggunakan enjin replikasi yang berasingan.
• Gateway menerima respons daripada nod pusat dan memajukannya kepada klien.
• Selepas beberapa lama, Gateway menerima transaksi melalui mekanisme replikasi, dan kali ini ia melaksanakannya secara tempatan, mengubah struktur datanya supaya permintaan maklumat seterusnya memaparkan data terkini.

Malah, ia menerangkan model replikasi di mana Gateway mereplikasi sepenuhnya tindakan yang dilakukan dalam sistem perdagangan. Saluran replikasi yang berasingan memastikan bahawa urus niaga telah dilaksanakan dalam susunan yang sama merentas berbilang nod akses.

Memandangkan kod itu berbenang tunggal, skema klasik dengan garpu proses telah digunakan untuk melayani ramai pelanggan. Walau bagaimanapun, adalah sangat mahal untuk memotong keseluruhan pangkalan data, jadi proses perkhidmatan yang ringan digunakan yang mengumpul paket daripada sesi TCP dan memindahkannya ke satu baris gilir (SystemV Message Queue). Gateway dan Enjin Perdagangan hanya berfungsi dengan baris gilir ini, mengambil transaksi dari sana untuk pelaksanaan. Ia tidak lagi boleh menghantar respons kepadanya, kerana proses perkhidmatan mana yang harus membacanya tidak jelas. Oleh itu, kami menggunakan helah: setiap proses bercabang mencipta baris gilir respons untuk dirinya sendiri, dan apabila permintaan masuk ke baris gilir masuk, teg untuk baris gilir respons ditambah dengan serta-merta.

Menyalin sejumlah besar data dari baris ke baris gilir secara berterusan menimbulkan masalah, terutamanya yang biasa untuk permintaan maklumat. Oleh itu, kami menggunakan helah lain: sebagai tambahan kepada baris gilir tindak balas, setiap proses juga mencipta memori kongsi (Memori Dikongsi SystemV). Pakej itu sendiri diletakkan di dalamnya, dan hanya tag disimpan dalam baris gilir, membolehkan seseorang mencari pakej asal. Ini membantu menyimpan data dalam cache pemproses.

SystemV IPC termasuk utiliti untuk melihat keadaan baris gilir, memori dan objek semaphore. Kami secara aktif menggunakan ini untuk memahami apa yang berlaku dalam sistem pada masa tertentu, di mana paket terkumpul, apa yang disekat, dsb.

Pemodenan pertama

Pertama sekali, kami menyingkirkan Gateway satu proses. Kelemahan ketaranya ialah ia boleh mengendalikan sama ada satu transaksi replikasi atau satu permintaan maklumat daripada pelanggan. Dan apabila beban meningkat, Gateway akan mengambil masa yang lebih lama untuk memproses permintaan dan tidak akan dapat memproses aliran replikasi. Di samping itu, jika pelanggan menghantar transaksi, maka anda hanya perlu menyemak kesahihannya dan memajukannya lagi. Oleh itu, kami menggantikan proses Gerbang tunggal dengan berbilang komponen yang boleh berjalan secara selari: maklumat berbilang benang dan proses transaksi berjalan secara berasingan antara satu sama lain pada kawasan memori yang dikongsi menggunakan penguncian RW. Dan pada masa yang sama kami memperkenalkan proses penghantaran dan replikasi.

Kesan Dagangan Frekuensi Tinggi

Versi seni bina di atas wujud sehingga 2010. Sementara itu, kami tidak lagi berpuas hati dengan prestasi pelayan HP Superdome. Di samping itu, seni bina PA-RISC hampir mati; vendor tidak menawarkan sebarang kemas kini penting. Akibatnya, kami mula beralih daripada HP UX/PA RISC ke Linux/x86. Peralihan bermula dengan penyesuaian pelayan akses.

Mengapa kita perlu menukar seni bina sekali lagi? Hakikatnya ialah perdagangan frekuensi tinggi telah mengubah profil beban dengan ketara pada teras sistem.

Katakan kami mempunyai transaksi kecil yang menyebabkan perubahan harga yang ketara - seseorang membeli setengah bilion dolar. Selepas beberapa milisaat, semua peserta pasaran menyedari perkara ini dan mula membuat pembetulan. Sememangnya, permintaan berbaris dalam baris gilir yang besar, yang sistem akan mengambil masa yang lama untuk dibersihkan.

Pada selang 50 ms ini, kelajuan purata adalah kira-kira 16 ribu transaksi sesaat. Jika kita mengurangkan tetingkap kepada 20 ms, kita mendapat kelajuan purata 90 ribu transaksi sesaat, dengan 200 ribu transaksi pada puncaknya. Dalam erti kata lain, beban tidak tetap, dengan pecah secara tiba-tiba. Dan barisan permintaan mesti sentiasa diproses dengan cepat.

Tetapi kenapa ada barisan sama sekali? Jadi, dalam contoh kami, ramai pengguna menyedari perubahan harga dan menghantar transaksi dengan sewajarnya. Mereka datang ke Gateway, ia mensirikannya, menetapkan pesanan tertentu dan menghantarnya ke rangkaian. Penghala mengocok paket dan meneruskannya. Pakej siapa yang sampai dahulu, transaksi itu "menang". Akibatnya, pelanggan pertukaran mula menyedari bahawa jika transaksi yang sama dihantar dari beberapa Gateway, maka peluang pemprosesannya yang cepat meningkat. Tidak lama kemudian, robot pertukaran mula membombardir Gateway dengan permintaan, dan banyak urus niaga timbul.

Satu pusingan baru evolusi

Selepas ujian dan penyelidikan yang meluas, kami beralih kepada kernel sistem pengendalian masa nyata. Untuk ini kami memilih RedHat Enterprise MRG Linux, di mana MRG bermaksud grid masa nyata pemesejan. Kelebihan tampalan masa nyata ialah mereka mengoptimumkan sistem untuk pelaksanaan terpantas yang mungkin: semua proses disusun dalam baris gilir FIFO, teras boleh diasingkan, tiada lentingan, semua transaksi diproses dalam urutan yang ketat.

Merah - berfungsi dengan baris gilir dalam kernel biasa, hijau - berfungsi dalam kernel masa nyata.

Tetapi untuk mencapai kependaman rendah pada pelayan biasa tidaklah begitu mudah:

• Mod SMI, yang dalam seni bina x86 adalah asas untuk bekerja dengan persisian penting, sangat mengganggu. Pemprosesan semua jenis acara perkakasan dan pengurusan komponen dan peranti dilakukan oleh perisian tegar dalam apa yang dipanggil mod SMI telus, di mana sistem pengendalian tidak melihat apa yang dilakukan oleh perisian tegar itu sama sekali. Sebagai peraturan, semua vendor utama menawarkan sambungan khas untuk pelayan perisian tegar yang membolehkan mengurangkan jumlah pemprosesan IKS.
• Seharusnya tiada kawalan dinamik frekuensi pemproses, ini membawa kepada masa henti tambahan.
• Apabila log sistem fail disiram, proses tertentu berlaku dalam kernel yang menyebabkan kelewatan yang tidak dapat diramalkan.
• Anda perlu memberi perhatian kepada perkara seperti CPU Affinity, Interrupt affinity, NUMA.

Saya mesti mengatakan bahawa topik menyediakan perkakasan dan kernel Linux untuk pemprosesan masa nyata memerlukan artikel yang berasingan. Kami menghabiskan banyak masa untuk mencuba dan menyelidik sebelum kami mencapai keputusan yang baik.

Apabila beralih dari pelayan PA-RISC ke x86, kami secara praktikalnya tidak perlu banyak menukar kod sistem, kami hanya menyesuaikan dan mengkonfigurasinya semula. Pada masa yang sama, kami membetulkan beberapa pepijat. Sebagai contoh, akibat fakta bahawa PA RISC ialah sistem Endian Besar, dan x86 ialah sistem Endian Kecil, muncul dengan cepat: sebagai contoh, data dibaca dengan salah. Pepijat yang lebih rumit ialah penggunaan PA RISC konsisten secara konsisten (Konsisten secara berurutan) akses memori, manakala x86 boleh menyusun semula operasi baca, jadi kod yang benar-benar sah pada satu platform menjadi rosak pada platform yang lain.

Selepas bertukar kepada x86, prestasi meningkat hampir tiga kali ganda, purata masa pemprosesan transaksi menurun kepada 60 μs.

Sekarang mari kita lihat dengan lebih dekat apakah perubahan utama yang telah dibuat pada seni bina sistem.

Epik simpanan panas

Apabila bertukar kepada pelayan komoditi, kami sedar bahawa pelayan itu kurang dipercayai. Oleh itu, apabila mencipta seni bina baharu, kami a priori menganggap kemungkinan kegagalan satu atau lebih nod. Oleh itu, sistem siap sedia panas diperlukan yang boleh bertukar kepada mesin sandaran dengan cepat.

Di samping itu, terdapat keperluan lain:

• Dalam apa jua keadaan, anda tidak boleh kehilangan transaksi yang diproses.
• Sistem ini mesti benar-benar telus kepada infrastruktur kami.
• Pelanggan tidak sepatutnya melihat sambungan yang terputus.
• Tempahan tidak sepatutnya menyebabkan kelewatan yang ketara kerana ini merupakan faktor kritikal untuk pertukaran.

Apabila mencipta sistem siap sedia panas, kami tidak menganggap senario seperti kegagalan berganda (contohnya, rangkaian pada satu pelayan berhenti berfungsi dan pelayan utama membeku); tidak mempertimbangkan kemungkinan ralat dalam perisian kerana ia dikenal pasti semasa ujian; dan tidak menganggap pengendalian perkakasan yang salah.

Akibatnya, kami mencapai skema berikut:

• Pelayan utama berinteraksi secara langsung dengan pelayan Gateway.
• Semua transaksi yang diterima pada pelayan utama serta-merta direplikasi ke pelayan sandaran melalui saluran yang berasingan. Pengadil (Gabenor) menyelaraskan pertukaran sekiranya timbul sebarang masalah.

  

• Pelayan utama memproses setiap transaksi dan menunggu pengesahan daripada pelayan sandaran. Untuk mengekalkan kependaman pada tahap minimum, kami mengelak daripada menunggu transaksi selesai pada pelayan sandaran. Memandangkan masa yang diambil untuk transaksi merentasi rangkaian adalah setanding dengan masa pelaksanaan, tiada kependaman tambahan ditambahkan.
• Kami hanya boleh menyemak status pemprosesan pelayan utama dan sandaran untuk transaksi sebelumnya dan status pemprosesan transaksi semasa tidak diketahui. Memandangkan kami masih menggunakan proses berbenang tunggal, menunggu respons daripada Sandaran akan memperlahankan keseluruhan aliran pemprosesan, jadi kami membuat kompromi yang munasabah: kami menyemak hasil transaksi sebelumnya.

Skim ini berfungsi seperti berikut.

Katakan pelayan utama berhenti bertindak balas, tetapi Gerbang terus berkomunikasi. Tamat masa berlaku pada pelayan sandaran, ia menghubungi Gabenor, yang memberikannya peranan pelayan utama, dan semua Gerbang bertukar kepada pelayan utama baharu.

Jika pelayan utama kembali dalam talian, ia juga mencetuskan tamat masa dalaman, kerana tiada panggilan ke pelayan daripada Gateway untuk masa tertentu. Kemudian dia juga berpaling kepada Gabenor, dan dia mengecualikan dia daripada skim itu. Akibatnya, pertukaran berfungsi dengan satu pelayan sehingga akhir tempoh dagangan. Memandangkan kebarangkalian kegagalan pelayan adalah agak rendah, skim ini dianggap agak boleh diterima; ia tidak mengandungi logik yang rumit dan mudah untuk diuji.

Untuk diteruskan.

Sumber: www.habr.com