В этой статье я хочу в научно-популярной форме рассказать об оптимизации времени отклика в торговых платформах бирж и банков (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
