Evolusi arsitektur sistem perdagangan dan kliring Bursa Moskow. Bagian 1

Halo semua! Nama saya Sergey Kostanbaev, di Bursa saya sedang mengembangkan inti sistem perdagangan.

Ketika film-film Hollywood menayangkan Bursa Efek New York, selalu terlihat seperti ini: kerumunan orang, semua orang meneriakkan sesuatu, melambaikan kertas, kekacauan total sedang terjadi. Hal ini belum pernah terjadi di Bursa Moskow, karena perdagangan telah dilakukan secara elektronik sejak awal dan didasarkan pada dua platform utama - Spectra (pasar valas) dan ASTS (valuta asing, pasar saham, dan pasar uang). Dan hari ini saya ingin berbicara tentang evolusi arsitektur sistem perdagangan dan kliring ASTS, tentang berbagai solusi dan temuan. Ceritanya akan panjang, jadi saya harus membaginya menjadi dua bagian.

Kami adalah salah satu dari sedikit bursa di dunia yang memperdagangkan aset dari semua kelas dan menyediakan berbagai layanan pertukaran. Misalnya, tahun lalu kami menduduki peringkat kedua dunia dalam hal volume perdagangan obligasi, peringkat 25 di antara semua bursa saham, dan peringkat 13 dalam kapitalisasi di antara bursa publik.

Untuk peserta perdagangan profesional, parameter seperti waktu respons, stabilitas distribusi waktu (jitter), dan keandalan seluruh kompleks sangatlah penting. Saat ini kami memproses puluhan juta transaksi per hari. Pemrosesan setiap transaksi oleh kernel sistem membutuhkan waktu puluhan mikrodetik. Tentu saja, operator seluler di Malam Tahun Baru atau mesin pencari sendiri memiliki beban kerja yang lebih tinggi daripada kami, tetapi dalam hal beban kerja, ditambah dengan karakteristik yang disebutkan di atas, menurut saya hanya sedikit yang dapat menandingi kami. Pada saat yang sama, penting bagi kami agar sistem tidak melambat sedetik pun, bekerja dengan sangat stabil, dan semua pengguna berada pada posisi yang sama.

Sedikit sejarah

Pada tahun 1994, sistem ASTS Australia diluncurkan di Moscow Interbank Currency Exchange (MICEX), dan sejak saat itu sejarah perdagangan elektronik Rusia dapat dihitung. Pada tahun 1998, arsitektur bursa dimodernisasi untuk memperkenalkan perdagangan Internet. Sejak itu, kecepatan implementasi solusi baru dan perubahan arsitektur di semua sistem dan subsistem semakin meningkat.

Pada tahun-tahun itu, sistem pertukaran bekerja pada perangkat keras kelas atas - server HP Superdome 9000 yang sangat andal (dibangun di atas PA-RISC), di mana semuanya benar-benar diduplikasi: subsistem input/output, jaringan, RAM (sebenarnya, ada array RAID dari RAM), prosesor (hot-swappable). Dimungkinkan untuk mengubah komponen server apa pun tanpa menghentikan mesin. Kami mengandalkan perangkat ini dan menganggapnya aman dari kegagalan. Sistem operasinya adalah sistem HP UX mirip Unix.

Namun sejak sekitar tahun 2010, muncul fenomena yang disebut perdagangan frekuensi tinggi (HFT), atau perdagangan frekuensi tinggi - sederhananya, robot bursa. Hanya dalam 2,5 tahun, beban di server kami meningkat 140 kali lipat.

Tidak mungkin menahan beban seperti itu dengan arsitektur dan peralatan lama. Entah bagaimana, kita perlu beradaptasi.

awal

Permintaan ke sistem pertukaran dapat dibagi menjadi dua jenis:

• Transaksi. Jika Anda ingin membeli dolar, saham, atau yang lainnya, Anda mengirimkan transaksi ke sistem perdagangan dan menerima respons tentang keberhasilan.
• Permintaan informasi. Jika Anda ingin mengetahui harga saat ini, lihat buku pesanan atau indeks, lalu kirimkan permintaan informasi.

Secara skematis, inti sistem dapat dibagi menjadi tiga tingkatan:

• Tingkat klien, tempat broker dan klien bekerja. Mereka semua berinteraksi dengan server akses.
• Server gateway adalah server cache yang memproses semua permintaan informasi secara lokal. Ingin tahu berapa harga saham Bank Tabungan saat ini diperdagangkan? Permintaan masuk ke server akses.
• Namun jika ingin membeli saham, maka requestnya masuk ke server pusat (Trade Engine). Ada satu server untuk setiap jenis pasar, mereka memainkan peran penting, bagi merekalah kami menciptakan sistem ini.

Inti dari sistem perdagangan adalah database dalam memori yang cerdas dimana semua transaksi adalah transaksi pertukaran. Basisnya ditulis dalam C, satu-satunya dependensi eksternal adalah perpustakaan libc dan tidak ada alokasi memori dinamis sama sekali. Untuk mengurangi waktu pemrosesan, sistem dimulai dengan kumpulan array statis dan dengan relokasi data statis: pertama, semua data untuk hari ini dimuat ke dalam memori, dan tidak ada akses disk lebih lanjut yang dilakukan, semua pekerjaan dilakukan hanya di memori. Saat sistem dimulai, semua data referensi sudah diurutkan, sehingga pencarian bekerja sangat efisien dan hanya memakan sedikit waktu saat runtime. Semua tabel dibuat dengan daftar dan pohon intrusif untuk struktur data dinamis sehingga tidak memerlukan alokasi memori saat runtime.

Mari kita bahas secara singkat sejarah perkembangan sistem perdagangan dan kliring kita.
Versi pertama arsitektur sistem perdagangan dan kliring dibangun berdasarkan apa yang disebut interaksi Unix: memori bersama, semaphore, dan antrian digunakan, dan setiap proses terdiri dari satu thread. Pendekatan ini tersebar luas pada awal tahun 1990an.

Versi pertama dari sistem berisi dua tingkat Gateway dan server pusat dari sistem perdagangan. Alur kerjanya seperti ini:

• Klien mengirimkan permintaan, yang mencapai Gateway. Ia memeriksa validitas format (tetapi bukan data itu sendiri) dan menolak transaksi yang salah.
• Jika permintaan informasi telah dikirim, permintaan tersebut dijalankan secara lokal; jika kita berbicara tentang suatu transaksi, maka transaksi tersebut dialihkan ke server pusat.
• Mesin perdagangan kemudian memproses transaksi, memodifikasi memori lokal, dan mengirimkan respons terhadap transaksi dan transaksi itu sendiri untuk direplikasi menggunakan mesin replikasi terpisah.
• Gateway menerima respon dari node pusat dan meneruskannya ke klien.
• Setelah beberapa waktu, Gateway menerima transaksi melalui mekanisme replikasi, dan kali ini mengeksekusinya secara lokal, mengubah struktur datanya sehingga permintaan informasi berikutnya menampilkan data terbaru.

Faktanya, ini menggambarkan model replikasi di mana Gateway sepenuhnya mereplikasi tindakan yang dilakukan dalam sistem perdagangan. Saluran replikasi terpisah memastikan bahwa transaksi dieksekusi dalam urutan yang sama di beberapa node akses.

Karena kodenya berulir tunggal, skema klasik dengan garpu proses digunakan untuk melayani banyak klien. Namun, membagi seluruh database sangat mahal, sehingga proses layanan ringan digunakan yang mengumpulkan paket dari sesi TCP dan mentransfernya ke satu antrian (SystemV Message Queue). Gateway dan Trade Engine hanya bekerja dengan antrean ini, mengambil transaksi dari sana untuk dieksekusi. Tidak mungkin lagi mengirimkan respons karena tidak jelas proses layanan mana yang harus membacanya. Jadi kami menggunakan sebuah trik: setiap proses bercabang membuat antrean respons untuk dirinya sendiri, dan ketika permintaan masuk ke antrean masuk, tag untuk antrean respons segera ditambahkan ke dalamnya.

Menyalin data dalam jumlah besar secara terus-menerus dari antrean ke antrean menimbulkan masalah, terutama yang umum terjadi pada permintaan informasi. Oleh karena itu, kami menggunakan trik lain: selain antrian respons, setiap proses juga membuat memori bersama (SystemV Shared Memory). Paket-paket itu sendiri ditempatkan di dalamnya, dan hanya sebuah tag yang disimpan dalam antrian, memungkinkan seseorang untuk menemukan paket aslinya. Ini membantu menyimpan data dalam cache prosesor.

SystemV IPC menyertakan utilitas untuk melihat status objek antrian, memori, dan semaphore. Kami secara aktif menggunakan ini untuk memahami apa yang terjadi di sistem pada saat tertentu, di mana paket terakumulasi, apa yang diblokir, dll.

Peningkatan pertama

Pertama-tama, kami menyingkirkan Gateway proses tunggal. Kelemahan signifikannya adalah ia dapat menangani satu transaksi replikasi atau satu permintaan informasi dari klien. Dan seiring bertambahnya beban, Gateway akan memerlukan waktu lebih lama untuk memproses permintaan dan tidak akan dapat memproses alur replikasi. Selain itu, jika klien mengirimkan transaksi, maka Anda hanya perlu memeriksa keabsahannya dan meneruskannya lebih lanjut. Oleh karena itu, kami mengganti proses Gateway tunggal dengan beberapa komponen yang dapat berjalan secara paralel: proses informasi dan transaksi multi-thread berjalan secara independen satu sama lain pada area memori bersama menggunakan penguncian RW. Dan pada saat yang sama kami memperkenalkan proses pengiriman dan replikasi.

Dampak Perdagangan Frekuensi Tinggi

Versi arsitektur di atas ada hingga 2010. Sementara itu, kami tidak lagi puas dengan kinerja server HP Superdome. Selain itu, arsitektur PA-RISC hampir mati; vendor tidak menawarkan pembaruan signifikan. Hasilnya, kami mulai berpindah dari HP UX/PA RISC ke Linux/x86. Transisi dimulai dengan adaptasi server akses.

Mengapa kita harus mengubah arsitekturnya lagi? Faktanya adalah perdagangan frekuensi tinggi telah mengubah profil beban pada inti sistem secara signifikan.

Katakanlah kita melakukan transaksi kecil yang menyebabkan perubahan harga yang signifikan - seseorang membeli setengah miliar dolar. Setelah beberapa milidetik, semua pelaku pasar memperhatikan hal ini dan mulai melakukan koreksi. Tentu saja, permintaan berbaris dalam antrian besar, yang memerlukan waktu lama untuk diselesaikan oleh sistem.

Pada interval 50 ms ini, kecepatan rata-ratanya sekitar 16 ribu transaksi per detik. Jika kita mengurangi jendela menjadi 20 ms, kita mendapatkan kecepatan rata-rata 90 ribu transaksi per detik, dengan 200 ribu transaksi pada puncaknya. Dengan kata lain, bebannya tidak konstan, terjadi semburan secara tiba-tiba. Dan antrian permintaan harus selalu diproses dengan cepat.

Tapi kenapa ada antrian sama sekali? Jadi, dalam contoh kami, banyak pengguna yang memperhatikan perubahan harga dan mengirimkan transaksi yang sesuai. Mereka datang ke Gateway, membuat serialisasinya, menetapkan urutan tertentu dan mengirimkannya ke jaringan. Router mengacak paket dan meneruskannya. Yang paketnya sampai lebih dulu, transaksi itu “menang”. Akibatnya, klien bursa mulai menyadari bahwa jika transaksi yang sama dikirim dari beberapa Gateway, maka peluang pemrosesan cepatnya meningkat. Segera, robot pertukaran mulai membombardir Gateway dengan permintaan, dan banyak sekali transaksi yang terjadi.

Babak baru evolusi

Setelah pengujian dan penelitian ekstensif, kami beralih ke kernel sistem operasi real-time. Untuk ini kami memilih RedHat Enterprise MRG Linux, di mana MRG adalah singkatan dari pengiriman pesan grid real-time. Keuntungan dari patch real-time adalah mengoptimalkan sistem untuk eksekusi secepat mungkin: semua proses disusun dalam antrian FIFO, inti dapat diisolasi, tidak ada ejeksi, semua transaksi diproses dalam urutan yang ketat.

Merah - bekerja dengan antrian di kernel biasa, hijau - bekerja di kernel real-time.

Namun mencapai latensi rendah pada server reguler tidaklah mudah:

• Mode SMI, yang dalam arsitektur x86 merupakan dasar untuk bekerja dengan periferal penting, sangat mengganggu. Pemrosesan semua jenis peristiwa perangkat keras dan pengelolaan komponen dan perangkat dilakukan oleh firmware dalam apa yang disebut mode SMI transparan, di mana sistem operasi tidak melihat apa yang dilakukan firmware sama sekali. Biasanya, semua vendor besar menawarkan ekstensi khusus untuk server firmware yang memungkinkan pengurangan jumlah pemrosesan SMI.
• Seharusnya tidak ada kontrol dinamis terhadap frekuensi prosesor, hal ini menyebabkan waktu henti tambahan.
• Ketika log sistem file dihapus, proses tertentu terjadi di kernel yang menyebabkan penundaan yang tidak terduga.
• Anda perlu memperhatikan hal-hal seperti CPU Affinity, Interrupt affinity, NUMA.

Saya harus mengatakan bahwa topik menyiapkan perangkat keras dan kernel Linux untuk pemrosesan waktu nyata layak mendapat artikel terpisah. Kami menghabiskan banyak waktu untuk bereksperimen dan meneliti sebelum mencapai hasil yang baik.

Saat berpindah dari server PA-RISC ke x86, praktis kami tidak perlu banyak mengubah kode sistem, kami hanya mengadaptasi dan mengkonfigurasi ulang. Pada saat yang sama, kami memperbaiki beberapa bug. Misalnya, konsekuensi dari fakta bahwa PA RISC adalah sistem Big endian, dan x86 adalah sistem Little endian, dengan cepat muncul: misalnya, data dibaca secara tidak benar. Bug yang lebih rumit adalah yang digunakan PA RISC secara konsisten konsisten (Konsisten secara berurutan) akses memori, sedangkan x86 dapat menyusun ulang operasi baca, sehingga kode yang benar-benar valid di satu platform menjadi rusak di platform lain.

Setelah beralih ke x86, kinerja meningkat hampir tiga kali lipat, waktu pemrosesan transaksi rata-rata menurun menjadi 60 s.

Sekarang mari kita lihat lebih dekat perubahan penting apa yang telah dilakukan pada arsitektur sistem.

Epik cadangan panas

Saat beralih ke server komoditas, kami menyadari bahwa server tersebut kurang dapat diandalkan. Oleh karena itu, ketika membuat arsitektur baru, kami secara apriori mengasumsikan kemungkinan kegagalan satu atau lebih node. Oleh karena itu, diperlukan sistem hot standby yang dapat dengan cepat beralih ke mesin cadangan.

Selain itu, ada persyaratan lain:

• Dalam situasi apa pun Anda tidak boleh kehilangan transaksi yang telah diproses.
• Sistem ini harus benar-benar transparan terhadap infrastruktur kita.
• Klien tidak akan melihat koneksi terputus.
• Reservasi tidak boleh menimbulkan penundaan yang signifikan karena ini merupakan faktor penting untuk pertukaran.

Saat membuat sistem siaga panas, kami tidak mempertimbangkan skenario seperti kegagalan ganda (misalnya, jaringan di satu server berhenti bekerja dan server utama membeku); tidak mempertimbangkan kemungkinan kesalahan pada perangkat lunak karena teridentifikasi selama pengujian; dan tidak mempertimbangkan pengoperasian perangkat keras yang salah.

Hasilnya, kami sampai pada skema berikut:

• Server utama berinteraksi langsung dengan server Gateway.
• Semua transaksi yang diterima di server utama langsung direplikasi ke server cadangan melalui saluran terpisah. Arbiter (Gubernur) mengoordinasikan peralihan jika timbul masalah.

  

• Server utama memproses setiap transaksi dan menunggu konfirmasi dari server cadangan. Untuk meminimalkan latensi, kami menghindari menunggu transaksi selesai di server cadangan. Karena waktu yang diperlukan suatu transaksi untuk melakukan perjalanan melintasi jaringan sebanding dengan waktu eksekusi, tidak ada latensi tambahan yang ditambahkan.
• Kami hanya dapat memeriksa status pemrosesan server utama dan cadangan untuk transaksi sebelumnya, dan status pemrosesan transaksi saat ini tidak diketahui. Karena kami masih menggunakan proses single-thread, menunggu respons dari Cadangan akan memperlambat seluruh alur pemrosesan, jadi kami membuat kompromi yang masuk akal: kami memeriksa hasil transaksi sebelumnya.

Skema ini bekerja sebagai berikut.

Katakanlah server utama berhenti merespons, namun Gateway terus berkomunikasi. Batas waktu terjadi pada server cadangan, ia menghubungi Gubernur, yang memberinya peran sebagai server utama, dan semua Gateway beralih ke server utama yang baru.

Jika server utama kembali online, hal ini juga memicu internal timeout, karena tidak ada panggilan ke server dari Gateway selama waktu tertentu. Kemudian dia juga beralih ke Gubernur, dan dia mengeluarkannya dari skema tersebut. Hasilnya, bursa bekerja dengan satu server hingga akhir periode perdagangan. Karena kemungkinan kegagalan server cukup rendah, skema ini dianggap cukup dapat diterima; tidak mengandung logika yang rumit dan mudah untuk diuji.

Untuk dilanjutkan.

Sumber: www.habr.com