В этой статье я хочу в научно-популярной форме рассказать об оптимизации времени отклика в торговых платформах бирж и банков (HFT). Для справки речь идет о временах от сотен наносекунд до сотен микросекунд. Для большинства других приложений многие приведенные ниже методы оптимизации неактуальны просто в силу отсутствия столь жестких требований.
Обычно мы рассматриваем производительность в единицах пропускной способности. Например в Гигафлопах. Задача оптимизации в таких случаях сводится к выполнению максимального количества вычислений за единицу времени или решение задачи за минимальное время. Дизайн процессора рассчитан в первую очередь на достижение максимального количества вычислений за единицу времени и стандартные техники оптимизации на то же самое.
Однако существуют приложения где важнее время отклика, например торговые платформы в компьютерном трейдинге (HFT), поисковики, робототехника и телеком. Время отклика – это время выполнения «единичной» операции данного типа, например от получения пакета с текущими котировками с биржи до посылки заказа на биржевую операцию. На самом деле время отклика и пропускная способность (количество операций данного типа в единицу времени) тесно связаны, но разница – принципиальна. Увеличить пропускную способность часто можно просто добавив железа (больше серверов), но улучшить время отклика подобным образом проблематично (кроме случаев пиковых нагрузок).
Для оптимизации времени отклика используются несколько отличные методы. Некоторые улучшают и время отклика и пропускную способность одновременно, другие улучшают одно за счет другого. Например, для улучшения пропускной способности типична буфферизация, чтобы обрабатывать массив пакетов за раз. Очевидно, что для времени отклика на единичный пакет такой подход вреден.
В торговых платформах также очень важна стабильность времени отклика. Большая часть прибылей и убытков случается при резких движениях рынков, сопровождающихся аномально высокой активностью. Платформа должна выдерживать такие нагрузки. Любой затык может привести к ощутимым потерям.
В целом такая низкоуровневая оптимизация времени отклика – это сложная тема, требующая хорошего понимания сетевого стека, работы ядра операционной системы, производительности процессора и платформы и эффективной синхронизации потоков. Моя задача – объяснить все эти сложные вещи на простом и понятном примере.
Работа офиса
Давайте воспользуемся следующей аналогией. Представьте группу людей работающих в офисе. Коммуникации происходят посредством обмена сообщений на бумажном носителе (писем). Каждое письмо содержит адресата, отправителя и задание. Письма кладутся на определенные столы в офисе. Есть работники, задача которых – получать письма из внешнего мира и класть их на столы. Другие забирают письма со столов и передают их тем, кто принимает решения. Каждый принимающий решения работает только с определенным типом писем (или заданий).
Принимающий решения читает предназначенные ему письма и решает будет ли выполнено данное задание, отложено или проигнорировано. Задания к выполнению складываются на отдельный стол. Специальные работники забирают письма с этого стола и раздают исполнителям. На некоторые письма надо отвечать вовне офиса, например послать внешнему отправителю подтверждение.
Чтобы быть ближе к реальности давайте еще немного усложним условия. Например, офис представляет собой сложную сеть комнат и коридоров и разным типам работников можно ходить только в определенные места, куда у них оформлен доступ. Как говорят математики, не нарушая общности, предположим что наш офис при нормальных условиях обрабатывает 200 сообщений в день при среднем времени обработки сообщения в 5 минут.
Итак, наша задача – максимально сократить время обработки сообщений. При этом желательно, чтобы максимальное время обработки не превышало среднее более чем, скажем, вдвое. То есть всплески активности должны быть эффективно обработаны.
Итак, с чего начнем? Проще всего нанять больше работников чтобы обрабатывать больше сообщений. Неплохо поискать быстрых работников, тогда сократится время обработки. Допустим, мы наняли Усейна Болта и других финалистов Олимпийских игр. Возможно время обработки снизилось до 2 минут. Но очевидно, что в этом направлении двигаться дальше некуда. Быстрее не бегает никто. Предел достигнут. Сравнивая эти подходы с компьютером, найм людей есть покупка дополнительного железа (сервера, процессоры, ядра) чтобы увеличить количество потоков исполнения. Найм спортсменов аналогичен покупке максимально быстрого железа (максимальная частота в первую очередь).
Возможно планировка нашего офиса не оптимальна. Надо обеспесить достаточно места, чтобы работники работали эффективно. Может быть расширить коридоры, а то людям приходится уступать друг другу дорогу теряя драгоценное время? Давайте расширим. Давайте также слегка увеличим комнаты чтобы люди не толпились при подходе к столам. Это все равно что купить сервера с большим количеством ядер и большей пропускной способностью памяти и ввода/вывода.
Кроме того, мы можем перейти на экспресс сервис вместо обычной почты для обмена сообщениями с внешним миром. В компьютерных терминах это аналогично выбору и оптимизации сетевого оборудования и сетевого стека операционной системы. Все это – дополнительные затраты, но будем считать, что они однозначно окупятся.
Итак, после нововведений, наше время обработки сообщений упало до, допустим, одной минуты. Можно еще потренировать работников для улучшения процесса коммуникации и исполнения. Возможно это даст процентов 15 при правильной мотивации. Знасит мы достигли 51 секунды. Это похоже на оптимизацию программного обеспечения.
Следующим шагом постараемся избежать столкновений наших быстро бегающих работников. Вероятное узкое место – подход к столам. Желательно, чтобы работники имели мнгновенный и одновременный доступ к нужным им столам. Можно сортировать сообщения на столах при выкладке (класть в отдельные папки) чтобы ускорить доступ. Сообщения могут также иметь разный приоритет. В программе это аналог синхронизации потоков. Потоки должны иметь неограниченно параллельный и максимально быстрый доступ к данным. Исправление проблем с синхронизацией потоков часто дает огромный рост пропускной способности системы и помогает улучшить время отклика. В смысле обработки всплесков активности влияние оптимального алгоритма синхронизации вообще трудно переоценить.
Помимо этого, работники иногда могут оказаться перед закрытой дверью. Другие мелкие проблемы подобного свойства могут вызвать неудобства и задержки. Желательно выполнить следующие условия: количество людей в данном помещении никогда не превышает его вместимости, скорость работников ничем не ограничена, никаких не относящихся к основной работе действий не производится и никто посторонний не влезает в процесс работы. В компьютерных терминах это означает, что количество потоков никогда не превышает количество доступных ядер, платформа настроена на максимальную частоту/производительность, экономные режимы отключены, режим Турбо включен и работа ядра операционной системы и других приложений изолирована и (почти) не влияет на торговую платформу.
Теперь пора рассмотреть еще внимательнее условия в офисе. Открываются ли двери легко? Не скользит ли пол? Это примерно тоже самое что анализ взаимодействия с операционной системой. Если улучшить уже нечего, можно попытаться избежать использования некоторых частей. Например, вместо того чтобы разносить письма через офис, почему бы не попробовать кидать их из окна в окно? Скажете неудобно? Может и неудобно, зато быстро. Это аналог использования подхода kernel bypass в сетевом стеке.
Вместо использования сетевого стека операционной системы, kernel bypass исполняет сетевой стек в user space. Это помогает избавиться от ненужных копирований данных между стеком системы и пользователя и задержки исполнения потока получения сообщения. В kernel bypass поток получения обычно ждет активно. Он не сидит на локе операционной системы, а непрерывно проверяет переменную лока до тех пор пока она не даст ему разрешение на исполнение.
На самом деле если уж мы начали бросать сообщения через окна, давайте сделаем это эффективно. Наиболее надежный вариант это передать через окно из рук в руки. Этот принцип используется в TCP протоколе. Это не самый быстрый вариант. UDP разрешает просто бросить сообщение без подтверждений. Это быстрее. Никого ждать не требуется. Думаете это предел? Нет, можно еще научиться бросать через окно так, чтобы письмо падал прямо на нужный стол и в нужную папку. Такой подход называется remote direct memory access (RDMA). Думаю, мы понизили время обработки секунд до 35-ти.
А может быть построить офис с нуля вместо того чтобы приспосабливать существующий к нашим нуждам? Такой, чтобы обеспечивал идеальные условия работы. Наверное это позволит улучшить время отклика секунд до 20-ти, а то и меньше. Собственный дизайн офиса – это использование field programmable gate array (FPGA). FPGA – это нечто вроде процессора, железо которого программируется под решение конкретной задачи. Обычный процессор закодирован на выполнение определенного набора инструкций на определенных типах данных и поток исполнения (не путать с потоком приложения) тоже фиксирован. В отличии от процессора, FPGA не запрограммированы заранее под набор инструкций, типов данных и поток исполнения. Они программируются под конкретную задачу и в таком состоянии способны исполнять только ее (до последующего перепрограммирования). Эффективное программирование FPGA – не самая простая задача. Внесение изменений в программу также может потребовать больших усилий. И хотя FPGA не подразумевает найм Усейна Болта (частоты намного ниже, чем процессорные), но неограниченный параллелизм исполнения инструкций позволяет добиваться более низких времен обработки сообщений, чем на процессоре.
Ну и в заключение порекомендую инструменты анализа производительности для программного обеспечения. Intel VTune TM Amplifier и Intel Processor Trace technology помогут увидеть в деталях где и почему тратится процессорное время.
Если есть интерес к теме, можно почитать мои статьи на Intel Developer Zone (на английском), где также приводятся практические технические советы по оптимизации времени отклика.
- https://software.intel.com/en-us/articles/optimizing-computer-applications-for-latency-part-1-configuring-the-hardware
- https://software.intel.com/en-us/articles/optimizing-computer-applications-for-latency-part-2-tuning-applications
rPman
На сколько я знаю, биржи не обеспечивают ИСПОЛНЕНИЕ торговой заявки за эти миллисекунды. Речь идет исключительно о приеме заявки пользователя и постановки ее в очередь, не более. А запросы на получение информации — и вовсе обычные и линейно масштабируются от количества серверов и ширины каналов (за исключением пользовательских данных депозитов но и там есть где разгуляться).
Исполнение сделки в реалиях откладывается на потом, и зависит от способа реализации их исполнения, в момент подачи ордера или же параллельно по стакану гуляет специальный сервис (в этом случае встречные сделки в стакане временно могут иметь пересечения).
Ожидал от статьи внутренности этого процесса, разделение сделок на микротранзакции, способ хранения собственно списка лимитных сделок, использование нестандартного железа и прочее прочее.
p.s. просто от балды, без какого либо опыта и использования готовых библиотек, писал на php сервер торговой биржи (однопоточный) с подключением клиентов по websocket (react php) и получал десятки тысяч сделок в секунду от сотни 'тестовых клиентов' на слабом десктопном железе (там все сильно зависело, сколько встречных заявок затрагивает ордер, но реалии таковы что обычно таких единицы максимум десятки, никто не 'торгует широко', так как это увеличивает неопределенность, гораздо выгоднее и проще строить свои стратегии, дробя свои объемы как раз по структуре стакана).
maydjin
По поводу ощущений от статьи — действительно пара унылых аналогий без каких либо подробностей.
По поводу выполнения заявок — ваша информация сильно устарела, либо вы путаете биржу с брокером, либо классическую биржу с биржей криптовалюты.
При определённых усилиях можно поставить заявку за <= 100us. Про то как приходит информация, у вас и вовсе крайне примитивное понимание. На самом деле в 99% случаев имеет место rpc протокол, который поддерживает слепок рыночного состояния на машинах клиентов командами вида add/delete/change. Время отклика разное у разных торговых систем, но у самих биржевых движков, исключая всяких паразитических сущностей типа брокера, это обычно не больше десятков микросекунд.
rPman
Вы умудрились написать слова но ничего не объяснили, зато интонация такая будто вы много знаете, может ответите полнее?
remote procedure call и локальный слепок рыночного состояния на машинах, вы о чем вообще? биржа никаким боком не занимается клиентскими машинами, она дает только поток сырых данных по своему протоколу или по фикс.
Я имел в виду именно биржу а не посредника. Конечно, я не знаком на практике с современными движками, но я уже несколько лет 'пристально' изучаю криптовалютные биржи, так как они банально доступнее тех двух-трех единственных, существующих сейчас в большом мире денег.
Вот вам ваши add remove change:
1539172819543 {»table":«instrument»,«action»:«update»,«data»:[{«symbol»:«XBTUSD»,«lastTickDirection»:«ZeroMinusTick»,«timestamp»:«2018-10-10T12:00:11.320Z»}]}
1539172819568 {«table»:«orderBookL2»,«action»:«update»,«data»:[{«symbol»:«XBTUSD»,«id»:8799349650,«side»:«Buy»,«size»:1423529}]}
…
1539172819579 {«table»:«orderBookL2»,«action»:«update»,«data»:[{«symbol»:«XBTUSD»,«id»:8799349650,«side»:«Buy»,«size»:1423495}]}
1539172819580 {«table»:«orderBookL2»,«action»:«delete»,«data»:[{«symbol»:«XBTUSD»,«id»:8799997900,«side»:«Buy»}]}
1539172819580 {«table»:«orderBookL2»,«action»:«insert»,«data»:[{«symbol»:«XBTUSD»,«id»:8799997800,«side»:«Buy»,«size»:31,«price»:22}]}
maydjin
Про incremental refresh. В нативных протоколах по сути тоже самое, но они рассчитаны на rdma/sharedmemory в кейсе высокой отзывчивости и не масштабируются по количеству клиентов, поэтому используют шлюзы ретрансляторы. От FAST и SBE, до просто предачи всё тех же сообщений но закодированных в виде POD объектов. Сходу могу предложить почитать спеку moex на этот счёт(у остальных всё более менее похоже) — http://ftp.moex.com/pub/FAST/.
FIX — это либо послеторговый контроль, либо торговля. Маркет дату так передавать супер неээфективно, и, на сколько я знаю, особо никто так и не делает. Ну точнее как, это конечно сообщения из спеки FIX (X и W), вот только закодированы они в FIX/SBE/wte и вещаются через мультикаст.
Про крипто биржи даже врать не буду, не знаю, последние мои взгляды в ту сторону показывали какие-то унылые джейсоны и задержи по пол-секунды ибо интернет и прочие мегаоптимизации, есть тут как минимум один такой оптимизатор на хабре.
rPman
Да, криптовалютные биржи рядом с высокоскоростной торговлей не стояли, но мое мнение в некоторых случаях это искусственно созданные ограничения, использующиеся как инструмент манипуляций тот же bitmex утверждает что их ddos-ят в моменты сильных движений, только почему то отказы в принятии сделок начинаются за секунды до этого движения без отказов в других разделах их сайта, в т.ч. на других биржах, что само собой говорит о манипуляциях.
Некоторые биржи в криптовалютах 'третьего эшелона' написаны на столько криворукими разработчиками что лагают и тормозят на секунды и даже минуты (тот же yobit, 'не к столу будет сказано'), так будто внутри у них ядро на sql с блокировками на обычных десктопных машинах ;)
p.s. особенности ДОСТАВКИ данных до клиента никаким образом не связаны с тем как именно данные обрабатываются внутри биржи.
Меня немного интересует, популярно, как именно внутри высокоскоростной бирже реализовано торговое ядро, способное обрабатывать очень большое количество транзакций с минимальной задержкой как на прием заявок так на их исполнение.
RISENT
Согласен, вряд ли глючный софт биржи на плюсах 10 летней давности, что-то там тебе обеспечит.
maydjin
Так то — 10 лет назад на плюсах писали что бы уместится в железках, и в идеале, ещё и отмасштабироваться через n лет. А сейчас, что бы с умным видом смузи хлебнуть.
RISENT
Особенно интересно, где fstrlab нашел шлюзы для выставления заявок по UDP (не путать с получением рыночных данных вроде FAST). maydjin странно почему они не могут обновлять софт — на питерской бирже НКД по бондам до сих пор нет в FIX-протоколе. А от большинства отечественных поделок вроде QUIK вообще тошнит, если взглянуть внутрь хотя бы тех же SQL таблиц с данными.
polarnik
Интересная статья, спасибо. Аналогии может и хороши, но их недостаточно, мне — человеку не погруженному в тему RDMA, DPDK,… чтобы понять их суть и пользу. Можно ли попросить дополнить статью ссылками на полезные материалы по указанным технологиям. Вероятно, ссылки от погруженного в тему человека будет полезнее, чем ссылки от поисковой системы.
Я нашел такие ссылки:
Первая статья хороша, интересные рекомендации — Optimizing Computer Applications for Latency: Part 1: Configuring the Hardware.
Возможно, ссылки были в оригинале. Но удалились по каким-то причинам.
И какая технология по опыту даёт наибольшее ускорение для торговых платформ? Если верить аналогиям, то профилирование кода с помощью Intel VTune TM Amplifier и Intel Processor Trace technology с последующим его ускорением (замена обычных работников на Усейнов Болтов) даёт наибольший выигрыш с 5-ти до 2-х минут. Как оно на практике?
ksergey01
Очень интересно по теме пишет cloudflare (сетевая часть):
blog.cloudflare.com/single-rx-queue-kernel-bypass-with-netmap
blog.cloudflare.com/io_submit-the-epoll-alternative-youve-never-heard-about
По программной части интересно рассказывают вот эти докладчики:
www.youtube.com/watch?v=BxfT9fiUsZ4
www.youtube.com/watch?v=MHaZwyhpl-M
Ну и статья на хабре:
habr.com/ru/post/339702 — так же советую посмотреть их код на githab-е, по части solarflare
vmescheryakov
Outdated
vmescheryakov
Есть еще например такая оптимизация. Письма на столе могут лежать неаккуратно и занимать много места. Более того, часть писем лежат в каких-то больших запечатанных конвертах. В этом случае чтобы положить на стол новое письмо надо сначала убрать самое старое с поверхности стола в ящик. Если письмо запечатано в большой красивый дизайнерский конверт, то его приходится оттуда для начала достать. Тут поможет несколько вещей. Во-первых, письма надо складывать поаккуратнее, чтобы большее их количество влезло на поверхность стола. Во-вторых, их стоит доставать из лишних упаковок, чтобы они занимали меньше места и чтоб сотрудникам, которые будут их читать, не требовалось делать это самостоятельно. В-третьих, стоит увеличить поверхность стола по возможности. При этом увеличение количества ящиков в столе не особо поможет. Главное чтобы ящики легко выдвигались. А лучше вообще избежать их использования.