Всім привіт! Мене звуть Сергій Костанбаєв, на Біржі займаюся розробкою ядра торгової системи.
Коли в голлівудських фільмах показують Нью-Йоркську фондову біржу, це завжди виглядає так: натовп людей, все щось кричать, махають папірцями, твориться повний хаос. У нас на Московській біржі такого ніколи не було, тому що торги від початку ведуться електронно і базуються на двох основних платформах — Spectra (терміновий ринок) та ASTS (валютний, фондовий та грошовий ринок). І сьогодні хочу розповісти про еволюцію архітектури торгово-клірингової системи ASTS, про різні рішення та знахідки. Розповідь буде довга, так що довелося розбити її на дві частини.
Ми є однією з небагатьох бірж світу, на яких проводяться торги активами всіх класів та надається повний спектр біржових послуг. Наприклад, минулого року ми посідали друге місце у світі за обсягом торгів облігаціями, 25 місце серед усіх фондових бірж, 13 місце з капіталізації серед публічних бірж.
Для професійних учасників торгів критичні такі параметри, як час відгуку, стабільність розподілу часів (джиттер) та надійність всього комплексу. На даний момент ми обробляємо десятки мільйонів транзакцій на день. Обробка кожної транзакції ядром системи займає десятки мікросекунд. Звичайно, у стільникових операторів під Новий рік або у пошуковиків навантаженість сама по собі вища за нашу, але ось за навантаженістю разом із вищезазначеними характеристиками з нами мало хто може зрівнятися, як мені здається. При цьому нам важливо, щоб система ні на секунду не гальмувала, працювала абсолютно стабільно, і всі користувачі знаходилися в рівних умовах.
трошки історії
У 1994 році на Московській міжбанківській валютній біржі (ММВБ) було запущено австралійську систему ASTS, і з цього моменту можна відраховувати російську історію електронних торгів. 1998 року архітектуру біржі модернізували задля впровадження інтернет-трейдингу. З того часу швидкість впровадження нових рішень та архітектурних змін у всіх системах та підсистемах лише набирає обертів.
У ті роки біржова система працювала на hi-end залізі - наднадійних серверах HP Superdome 9000 (побудованих на архітектурі), у яких дублювалося абсолютно все: підсистеми введення-виводу, мережа, оперативна пам'ять (фактично був RAID-масив з RAM), процесори (підтримувалася гаряча заміна). Можна було змінити будь-який компонент сервера без зупинки машини. Ми покладалися ці пристрої, вважали їх практично безвідмовними. У ролі операційної системи виступала Unix-подібна система HP UX.
Але приблизно з 2010 року виникло таке явище, як high-frequency trading (HFT), або високочастотна торгівля — просто кажучи, біржові роботи. Усього за 2,5 роки навантаження на наші сервери збільшилося у 140 разів.
Витримувати таке навантаження зі старою архітектурою та обладнанням було неможливо. Треба було якось адаптуватись.
Початок
Запити до біржової системи можна поділити на два типи:
- Транзакції. Якщо ви хочете купити долари, акції або ще щось, то відправляєте в торгову систему транзакцію і отримуєте відповідь про успішність.
- Інформаційні запити. Якщо ви хочете дізнатися про поточну ціну, подивитися книгу заявок або індекси, то надсилаєте інформаційні запити.
Схематично ядро системи можна поділити на три рівні:
- Клієнтський рівень, у якому працюють брокери, клієнти. Усі вони взаємодіють із серверами доступу.
- Сервери доступу (Gateway) - це сервери, що кешують, які локально обробляють всі інформаційні запити. Бажаєте дізнатися, за якою ціною зараз торгуються акції «Сбербанку»? Запит іде на сервер доступу.
- Але якщо ви хочете купити акції, то запит уже йде на центральний сервер (Trade Engine). Таких серверів по одному на кожен вид ринку, вони відіграють найважливішу роль, саме заради них ми й створювали цю систему.
Ядро торгової системи є хитрою in-memory базою даних, де всі транзакції — це біржові транзакції. База була написана на З, із зовнішніх залежностей була тільки бібліотека libc і повністю не було динамічного виділення пам'яті. Щоб зменшити час обробки, система запускається зі статичним набором масивів і статичною релокацією даних: спочатку всі дані на поточний день завантажуються в пам'ять, і далі звернень до диска не виконується, вся робота ведеться тільки в пам'яті. При запуску системи всі довідкові дані вже відсортовані, тому пошук працює дуже ефективно і займає мало часу в timer. Всі таблиці зроблені з інтрузивними списками та деревами для динамічних структур даних, щоб вони не вимагали виділення пам'яті в runtime.
Давайте коротко пробіжимося з історії розвитку нашої торговельно-клірингової системи.
Перша версія архітектури торгово-клірингової системи була побудована на так званій Unix-взаємодії: застосовувалися пам'ять, що розділяється, семафори і черги, а кожен процес складався з одного потоку. Цей підхід був поширений на початку 1990-х.
Перша версія системи містила два рівні Gateway та центральний сервер торгової системи. Схема роботи була така:
- Клієнт надсилає запит, який потрапляє на Gateway. Той перевіряє валідність формату (але не самих даних) та відкидає неправильні транзакції.
- Якщо було надіслано інформаційний запит, він виконується локально; якщо йдеться про транзакцію, вона перенаправляється на центральний сервер.
- Потім торговий двигун обробляє транзакцію, змінює локальну пам'ять і відправляє у відповідь транзакцію, та її саму — на реплікацію з допомогою окремого механізму реплікації.
- Gateway отримує від центрального вузла відповідь та перенаправляє його клієнту.
- Через деякий час Gateway отримує транзакцію по механізму реплікації, і цього разу він виконує її локально, змінюючи свої структури даних, щоб наступні інформаційні запити відображали актуальні дані.
Фактично тут описана реплікаційна модель, в якій Gateway повністю повторював дії, що виконуються в торговій системі. Окремий канал реплікації забезпечував той самий порядок виконання транзакцій на безлічі вузлів доступу.
Оскільки код був однопоточним, для обслуговування багатьох клієнтів використовувалася класична схема з fork-ами процесів. Однак робити fork для всієї бази даних було дуже накладно, тому застосовувалися легковажні процеси-сервіси, які збирали пакети з TCP-сесій та перекладали їх в одну чергу (SystemV Message Queue). Gateway та Trade Engine працювали тільки з цією чергою, забираючи звідти транзакції на виконання. Відправити в неї відповідь вже не можна, тому що незрозуміло, який сервіс-процес повинен його прочитати. Так що ми вдалися до хитрощів: кожен fork-нутий процес створював для себе чергу відповідей, і коли в чергу приходив запит, до нього відразу додавався тег для черги відповідей.
Постійне копіювання з черги до черги великих обсягів даних створювало проблеми, особливо характерні для інформаційних запитів. Тому ми скористалися ще одним трюком: крім черги відповідей, кожен процес створював також і загальну пам'ять (SystemV Shared Memory). У неї містилися самі пакети, а черзі зберігався лише тег, що дозволяє знайти вихідний пакет. Це допомогло зберігати дані в кеш-пам'яті процесора.
SystemV IPC включає утиліти для перегляду стану об'єктів черг, пам'яті та семафорів. Ми активно цим скористалися, щоб розуміти, що відбувається у системі у конкретний момент, де накопичуються пакети, що у блокуванні тощо.
Перші модернізації
Насамперед ми позбулися однопроцесового Gateway. Його істотним недоліком було те, що він міг обробляти одну реплікаційну транзакцію, або один інформаційний запит від клієнта. І зі зростанням навантаження Gateway все довше оброблятиме запити і не зможе обробляти реплікаційний потік. До того ж, якщо клієнт відправив транзакцію, потрібно лише перевірити її валідність і переадресувати далі. Тому ми замінили один процес Gateway на безліч компонентів, які можуть працювати паралельно: багатопотокові інформаційні та транзакційні процеси, що працюють незалежно один від одного із загальною областю пам'яті із застосуванням RW-блокування. І заразом запровадили процеси диспетчеризації та реплікації.
Вплив високочастотної торгівлі
Вищеописана версія архітектури проіснувала до 2010 року. Тим часом, нас вже перестала задовольняти продуктивність серверів HP Superdome. До того ж архітектура PA-RISC фактично померла, вендор не пропонував жодних суттєвих оновлень. В результаті ми почали переходити з HP UX/PA RISC на Linux/x86. Перехід розпочався з адаптації серверів доступу.
Чому нам знову довелося змінювати архітектуру? Справа в тому, що високочастотна торгівля значно змінила профіль навантаження на ядро системи.
Припустимо, ми маємо невелику транзакцію, яка викликала значну зміну ціни — хтось купив півмільярда доларів. Через пару мілісекунд усі учасники ринку це помічають і починають коригувати. Звичайно, запити вибудовуються у велику чергу, яку система довго розгрібатиме.
На цьому інтервалі 50 мс середня швидкість становить близько 16 тис. транзакцій в секунду. Якщо зменшити вікно до 20 мс, то отримаємо середню швидкість вже 90 тис. транзакцій за секунду, причому на піку буде 200 тис. транзакцій. Іншими словами, навантаження непостійне, з різкими сплесками. А чергу запитів потрібно завжди обробляти швидко.
Але чому взагалі виникає черга? Отже, у нашому прикладі багато користувачів помітили зміну ціни та відправляють відповідні транзакції. Ті приходять у Gateway, він їх серіалізує, ставить якийсь порядок і відправляє до мережі. Маршрутизатори перемішують пакети та відправляють їх далі. Чий пакет прийшов раніше, та транзакція і виграла. У результаті клієнти біржі почали помічати, що й ту саму транзакцію відправляти з кількох Gateway, то шанси її швидку обробку зростають. Незабаром біржові роботи почали закидати Gateway запитами і виникла лавина транзакцій.
Новий виток еволюції
Після тривалого тестування та досліджень ми перейшли на real-time ядро операційної системи. Для цього вибрали RedHat Enterprise MRG Linux, де MRG розшифровується як messaging real-time grid. Перевага real-time-патчів у тому, що вони оптимізують систему під максимально швидке виконання: усі процеси вишиковуються у FIFO-чергу, можна ізолювати ядра, жодних викидів, усі транзакції обробляються у суворій послідовності.
Червоний – робота з чергою у звичайному ядрі, зелений – робота у real-time ядрі.
Але досягти низького рівня затримки на звичайних серверах не так просто:
- Сильно заважає режим SMI, який в архітектурі x86 є основою роботи з важливою периферією. Обробка всіляких апаратних подій та управління компонентами та пристроями виконується прошивкою у так званому прозорому SMI-режимі, при якому операційна система взагалі не бачить, що робить прошивка. Як правило, всі великі вендори пропонують спеціальні розширення для firmware-серверів, що дозволяють зменшити обсяг SMI-обробки.
- Не повинно бути динамічного керування частотою процесора, це призводить до додаткового простою.
- Коли скидається журнал файлової системи, у ядрі з'являються деякі процеси, які призводять до непередбачуваним затримкам.
- Потрібно звертати увагу на такі речі як CPU Affinity, Interrupt affinity, NUMA.
Треба сказати, тема налаштування заліза і ядра Linux під realtime-обробку заслуговує на окрему статтю. Ми багато часу витратили на експерименти та дослідження, перш ніж досягли гарного результату.
При переході з PA-RISC-серверів на x86 нам мало довелося сильно змінювати код системи, ми лише адаптували і переналаштували її. Заодно поправили кілька багів. Наприклад, швидко випливли наслідки того, що PA RISC була Big endian-системою, а x86 — Little endian: наприклад, неправильно зчитувалися дані. Більш хитрий баг полягав у тому, що PA RISC використовує () доступ до пам'яті, тоді як x86 може переупорядковувати операції на читання, тому код, абсолютно валідний на одній платформі, став неробочим на іншій.
Після переходу на х86 продуктивність зросла майже тричі, середня тривалість обробки транзакції знизилася до 60 мкс.
Давайте розглянемо детальніше, які ключові зміни були внесені в архітектуру системи.
Епопея з гарячим резервуванням
Переходячи на commodity-сервери ми усвідомлювали, що вони менш надійні. Тому при створенні нової архітектури ми апріорі припускали можливість виходу з ладу одного чи кількох вузлів. Тому потрібна була система гарячого резервування, здатна дуже швидко перейти на резервні машини.
Крім того, були й інші вимоги:
- Не можна в жодному разі втрачати оброблені транзакції.
- Система має бути абсолютно прозорою для нашої інфраструктури.
- Клієнти не повинні бачити розриви з'єднань.
- Резервування має вносити істотну затримку, оскільки це критичний чинник для біржі.
Під час створення системи гарячого резервування ми розглядали такі сценарії, як подвійні відмови (наприклад, перестала працювати мережу одному сервері і завис основний сервер); не розглядали можливість помилок у ПЗ, тому що вони виявляються під час тестування; та не розглядали неправильну роботу заліза.
В результаті ми дійшли наступної схеми:
- Головний сервер безпосередньо взаємодіяв із серверами Gateway.
- Усі транзакції, які надходили головний сервер, моментально реплікувалися на резервний сервер окремим каналом. Арбітр (Governor) координував перемикання у разі виникнення будь-яких проблем.
- Головний сервер обробляв кожну транзакцію і очікував на підтвердження від резервного сервера. Щоб затримка була мінімальною, ми відмовилися очікувати виконання транзакції на резервному сервері. Оскільки тривалість переміщення транзакції по мережі була порівнянна з тривалістю виконання, додаткової затримки не додавалася.
- Звіряти стан обробки головним та резервним сервером ми могли лише попередньої транзакції, а статус обробки поточної транзакції був невідомий. Оскільки тут все ще використовувалися однопотокові процеси, очікування відповіді від Backup загальмувало б весь потік обробки, тому ми пішли на розумний компроміс: звіряли результат попередньої транзакції.
Схема працювала в такий спосіб.
Допустимо, головний сервер перестав відповідати, але Gateway продовжують взаємодіяти. На резервному сервері спрацьовує тайм-аут, він звертається до Governor, а той призначає йому роль головного сервера, і всі Gateway перемикаються на новий головний сервер.
Якщо головний сервер знову входить до ладу, на ньому також спрацьовує внутрішній тайм-аут, тому що протягом певного часу до сервера не було звернень від Gateway. Тоді він теж звертається до Governor, і той виключає його зі схеми. У результаті біржа остаточно торгового періоду працює з одним сервером. Оскільки ймовірність виходу сервера з ладу досить низька, така схема вважалася цілком прийнятною, вона містила складної логіки і легко тестувалася.
Далі буде.
Джерело: habr.com