Skip to content
BranchesTags

Repository files navigation

Latency Spring 2025

Описание задачи

Общее описание задачи было также дано на вступительной лекции.

В рамках соревнования вам нужно написать программу, которая получает данные по ордербукам по многим инструментам и поддерживает корректные ордербуки по заданному заранее подмножеству инструментов. В ордербуке необходимо корректно поддерживать первые 5 ненулевых уровней. Обозначим уровни цен для асков как $p_1^a, p_2^a, ..., p_{5}^a$ и аналогично для бидов $p_i^b$. Обозначим также объемы, на соответствующих уровнях как $q_1^a, ..., q_{5}^a$. Вам необходимо подсчитывать VWAP (volume-weighted average price), считаемый как

$$VWAP = \frac{\sum_{i=0}^{5} p_i^a \cdot q_i^a + p_i^b \cdot q_i^b}{\sum_{i=0}^{5} q_i^a + q_i^b}$$

Публичные данные доступны по ссылке: https://drive.google.com/file/d/1UQ7j7bBomu1fHSqJRxnOORKCbfk_3z1f/view?usp=sharing

Лидерборд: https://lat.spectral.tech/

Формат данных

Сетевой стек

Входные данные подаются в виде udp трафика, записанного в pcap файлах. Исходный протокол используется на реальных биржах, но был немного изменен для целей данного соревнования. Также в рамках проекта ряд полей в данных были изменены (ip и mac адреса, названия инструментов и т.д.). В остальном же данные максимально близки к записи сырого сетевого трафика.

Каждый udp пакет содержит только один eth фрейм. Каждый фрейм в данных содержит информацию с обновлениями ордербуков по одному или нескольким инструментам. Помимо этого встречаются и данные других типов, но в рамках этого проекта их можно пропускать.

Поскольку разных инструментов в данных много (несколько тысяч), то обновления ордербуков по всем могут занимать много фреймов. Однако, гарантируется, что в рамках одного фрейма для каждого инструмента в этом фрейме содержится полное обновление ордербука. Иными словами, после обработки каждого фрейма все ордербуки находятся в валидном состоянии.

Протокол данных

Здесь описан непосредственно протокол кодирования данных (т.е. содержимое udp payload, т.е. Application Layer). В описании помимо понятных названий типов вроде int32 или uint32 будет встречаться vint. Последний представляет собой схему кодирования знаковых 64-битных чисел, используя переменное число байт (от 1 до 10).

vint сначала кодирует число в беззнаковое 64-битное с помощью ZigZag, а затем полученное беззнаковое число кодируется с помощью varint. В целом, vint совпадает с sint64 из Google Protocol Buffers, его описание может быть найдено здесь: https://protobuf.dev/programming-guides/encoding/.

Таким образом, для декодирования vint нужно сделать все в обратном порядке:

Все числа в протоколе записаны в little-endian. Выравнивание не используется ни для каких полей.

Также в типах встречается char[n]. Данный тип кодирует 0-terminated строку длиной не более n-1 (т.е. тип занимает ровно n байт, чтобы прочитать строку, нужно читать до первого нулевого байта).

Структура данных

Каждый фрейм может содержать один или более пакет с данными ("пакет" в Application Layer).

Каждый пакет с данными состоит из хедера и следующего непосредственно за ним содержимого пакета. Хедер задает описание пакета и представляет собой набор типизированных записей. В начале всегда следуют следующие 3 записи:

  • uint8 dummy - в рамках проекта нас не интересует
  • uint8 typeid - тип сообщения, по нему можно определить сообщение какого типа далее следует.
  • uint16 length - длина сообщения (без учета хедера).

В рамках проекта нас интересуют только сообщениях двух типов: снепшоты (typeid=0x32) и инкрементальные апдейты (typeid=0x01). В обоих случаях хедеры содержат дополнительные записи, которые тут не описаны. В случае снепшота хедер включает в себя еще 4 байта, а в случае апдейта еще 20 байт.

Содержимое пакета после хедера представляет собой последовательность полей. Каждое поле также состоит из хедера и содержимого поля. Хедер любого поля состоит из 2 чисел:

  • uint16 field_id - задает тип поля
  • uint16 field_len - длина содержимого поля. Важно: в некоторых полях нефиксированного размера при чтении может получаться ситуация, что реальное количество прочитанного внутри поля меньше, чем field_len. В этом случае необходимо пропустить ненужные байты вплоть до конца поля согласно field_len.

Содержимое поля представляет собой последовательность типизированных записей (как в хедере) и зависит от типа поля.

Снепшоты (typeid=0x32)

Снепшот содержит большое количество полей, однако большая их часть в рамках проекта нам не интересна. Для таких полей указано только field_id и field_size, чтобы их можно было пропустить. Поля следуют в таком порядке:

  • Ненужные нам поля. Этот блок обычно встречается только внутри первого фрейма в последовательности фреймов со снепшотами.
    • field_id=0x0032, field_size=9 (может быть несколько таких полей или 0)
    • field_id=0x0031, field_size=22
    • field_id=0x1001, field_size=6
    • field_id=0x1003, field_size=37
    • field_id=0x1002, field_size=22
    • field_id=0x1004, field_size=4
  • Далее следует ненулевое количество групп со следующими полями (фактически, каждая группа на инструмент):
    • Instrument information field (field_id=0x0101). Содержит общую информацию об инструменте, включает в себя:
      • char[31] instrument_name - текстовое название инструмента.
      • 61 байт, с информацией, которая нам не нужна
      • double tick_size - используется при расчете уровня цены в ордербуке (описано далее).
      • double reference_price - базовая цена, от которой отсчитываются смещения в инкрементальных апдейтах.
      • int32 instrument_id - код инструмента, который в дальнейшем используется в апдейтах для идентификации инструмента.
    • Общая информация о торгах по данному инструменту, field_id=0x0102, field_size=154. В рамках проекта нас не интересуют практически все это поле за исключением последних 4 байт:
      • int32 change_no - используется при мерже снепшотов и апдейтов, описано далее.
    • Непосредственно содержимое ордербука (field_id=0x0103). Состоит из не более, чем 10 записей следующего вида:
      • int32 instrument_id - номер инструмента, совпадает с таковым в information field.
      • char direction - '0' для бидов и '1' для асков.
      • double price - уровень цены (абсолютный, в апдейтах цена будет задаваться немного по-другому)
      • int32 volume - объем на данной цене.

Инкрементальные апдейты (typeid=0x01)

Каждый апдейт содержит ненулевое количество групп (каждая группа отвечает какому-то инструменту). Каждая группа включает в себя: поле с хедером, какое-то количество полей с непосредственно обновлениями ордербука (может быть и нулевое), а также может содержать summary-поля, которые нас не интересуют.

Поле с хедером (field_id=0x0003) содержит:

  • vint instrument_id - код инструмента, по которому идут дальнейшие поля
  • vint change_no - номер инкремента, используется для корректного мержа снепшотов и апдейтов (описано далее)

Непосредственно поле с обновлениями (field_id=0x1001) содержит:

  • char event_type. '1' при добавлении нового уровня, '2' при изменении существующего, '3' при удалении уровня.
  • char md_entry_type. '0' если это обновление бидов, '1' если асков.
  • vint price_level. Номер уровня цены (индексация с 1), где необходимо применить изменение.
  • vint price_offset. Непосредственно уровень цены. Задается как прибавка, которую нужно добавить к reference price из снепшота для текущего инструмента. Т.е. если данное значение равно n, то реальный уровень цены равен reference + n * tick_size.
  • vint volume - объем на данном уровне цены.

Интерпретироать event_type можно следующим образом (пример приведен для бидов, для асков логика аналогичная): представим, что ордербук представлен как массив пар (price, volume). Тогда price_level - это индекс в этом массиве (с 1). Смысл операций следующий:

  • event_type = 1 - вставить в позицию price_level пару (price, volume) (размер массива увеличивается на 1)
  • event_type = 2 - изменить пару в позиции price_level (размер массива не меняется). Гарантируется, что volume != 0.
  • event_type = 3 - удалить элемент с позиции price_level (размер массива уменьшается на 1). Обратите внимание, что при этом price_offset и volume совпадают с удаляемыми значениями.

Обратите внимание на следующие особенности:

  1. В процессе применения индивидуальных обновлений (с field_id=0x1001) ордербук может находиться в некорректном состоянии. Его корректность гарантируется только по завершению всего апдейта.
  2. Непосредственно в данных будет дана информация только про первые 5 ненулевых уровня (и вам необходимо корректно их поддерживать). Однако в процессе применения апдейта размер массива, описанного выше, может быть больше.

summary-поля включают в себя поля с field_id из списка (0x1002, 0x1011, 0x1012, 0x1013, 0x1014, 0x1015, 0x1016). Каждый field_id может встречаться не более 1 раза в рамках каждой группы.

Как правильно поддерживать ордербук

Ордербуки по разным инструментам независимы друг от друга. В общем алгоритм состоит в последовальном чтении снепшотов и апдейтов, и применении апдейтов поверх текущего состояния ордербука. Особенность состоит в том, что иногда необходимо восстанавливать ордербук из снепшота заново (например, в начале считывания данных, при потере каких-то апдейтов или же просто при получении нового снепшота).

Для синхронизации снепшотов и апдейтов используюся поля change_no в снепшоте и change_no в апдейтах. При применении апдейтов если очередной change_no не равен предыдущему+1, то необходимо пропустить все апдейты до следующего снепшота (фактически, часть данных была потеряна). Обратите внимание при этом, что снепшоты обычно приходят асинхронно с апдейтами, т.е. вполне возможна ситуация, когда апдейты с бОльшим change_no находятся перед снепшотом в записи трафика. Чтобы корректно обрабатывать такие случаи вам нужно кешировать приходящие апдейты до тех пор пока не был получен снепшот и восстановлен корректный ордербук.

После применения снепшота применять апдейты к нему стоит начинать только когда change_no(update) = change_no(snapshot) + 1.

Основные части окружения

Окружение проекта включает в себя:

  • сырые данные
  • ваше решение
  • бинарь (runner), взаимодействующий с вашим решением. runner запускает решение как дочерний процесс, читает данные из pcap файлов и подает их на вход в shared memory, а также вычитывает вывод решения из shared memory. Также производит замеры времени.
  • scorer, по выводу раннера считает итоговый скор, пишет значения latency. Также может сравнивать ответ с правильным (при наличии).

runner не имеет никаких динамических зависимостей и может быть запущен на любой достаточно свежей linux-системе. Если в вашем случае это не так, то вы можете использовать докер для запуска, достаточно образа с ubuntu:22.04 или новее.

Раннер принимает следующие аргументы:

  • -sol - путь до бинаря с решением
  • -meta - путь до файла с метаданными (описано далее)
  • -b - префикс, который стоит использовать при создании буферов в shared memory.
  • -rc - (опциональный) номер ядра, куда запинить сам раннер.
  • -sc - (опциональный) аналогично для решения. Ему предоставляется 2 ядра: sc и sc+1.
  • -disable-hugepages - (опциональный) отключить использование hugepages для очередей в shared memory. Может пригодиться, если на вашей системе локально не включены hugepages.
  • -o - (опциональный) файл, куда выводить ответ раннера. При отсутствии вывод будет в stdout.
  • Оставшийся аргумент является путем до pcapng файла с данными.

Пример запуска:

./runner -b test_buffer -sol ./build/solution -meta public.meta public.pcapng

В случае запуска в докере крайне рекомендуется использовать следующие флаги при запуске контейнера (mount нужен только если вы используете hugepages)

--ipc=host --mount type=bind,src=/dev/hugepages,dst=/dev/hugepages --ulimit memlock=-1`

Формат решения

Формат ввода-вывода

Общение между runner и решением происходит с помощью двух single-producer-single-consumer очередей. Каждая очередь задается двумя файлами в /dev/shm: хедером и буфером. Формат хедера может быть описан следующим образом:

struct spsc_header_t {
    alignas(64) std::atomic<uint32_t> producer_offset;
    alignas(64) std::atomic<uint32_t> consumer_offset;
};

Т.е. хедер ключает в себя текущие оффсеты писателя и читателя в буфере, выровненные по границе 64 байт. Буфер размера N байт (этот размер передается в решение отдельно) представляет собой файл размера N в shared memory. Для того, чтобы закольцевать его вы сначала можете сделать анонимный mmap размера 2N, а затем дважды замапить переданный вам файл поверх разных половинок вашего анонимного мапинга. Для этого ввам понадобится флаг MAP_FIXED при вызове mmap.

При запуске решения runner сам создаст нужные файлы и проинициализирует оффсеты в 0. Протокол общения устроен следующим образом (пусть размер буфера равен N как в примере выше):

  • для записи k байт producer берет текущий producer_offset по модулю N, после чего пишет k байт, начиная с данной позиции. По завершению producer_offset увеличивается на k.
  • для чтения consumer берет текущий consumer_offset и сравнивает с producer_offset. Если последний больше на t байт, это означает, что с consumer_offset % N можно прочитать t байт. По завершению чтения consumer_offset должен быть увеличен на t.

Гарантируется, что N это всегда степень двойки. Также обратите внимание, что оффсеты в хедере хранятся в абсолютном значении, взятие по модулю производится уже непосредственно при чтении/записи в буфер. За счет того, что N всегда является степенью двойки, переполнения uint32_t тут не влияют на корректность.

Обратите внимание, что все фреймы выравниваются в очереди по 8 байтовой границе.

Информация о том, используются ли hugepages, не пробрасывается из раннера в решение. Однако вы можете это понять, проверив расположен ли буфер где-то в /dev/hugepages/.... В противном случае он будет по пути /dev/shm/... (хедеры всегда не используют hugepages). При мапинге файла с mmap вам необходимо использовать в том числе флаг MAP_HUGETLB, чтоб использовать hugepages.

Работа с pcap файлами

Для просмотра данных в pcap файлах лучше всего подходит Wireshark. У него есть консольный аналог tshark, но последний не очень удобен для интерактивной работы с данными. Промежуточным вариантом между двумя является termshark (https://github.com/gcla/termshark), который предоставляет консольный интерфейс.

Для упрощения дебага перед взаимодействием с раннером рекомендуется отладить свое решение, напрямую работая с pcap файлами. Для чтения pcap из C++ можно использовать одну из двух библиотек:

Требования к решению

Что именно считать

В вашем репозитории должен находиться скрипт build.sh, который запускает сборку. По итогу должен быть создан бинарь solution, который должен быть запускаемым с помощью runner (т.к. именно так будет произодиться тестирование). Для этого он должен принимать следующие аргументы по порядку:

  • имя хедера для входной очереди
  • имя буфера для входной очереди
  • имя хедера для выходной очереди
  • имя буфера для выходной очереди
  • размер обоих буферов (он одинаковый)
  • путь до файла с метой

Ваше решение запускается внутри образа с ubuntu:24.04. Внутри уже стоят clang-18, gcc-13, cmake. Вы можете ставить произольные пакеты внутри build.sh, однако учтите, что это влияет на время пайплайна, которое ограничено. Мы можем добавить какие-то пакеты в базовый образ, если будет такая потребность.

Метаданные

Файл с метой представляет собой текстовый файл следующего формата:

ip1 ip2
instrument1
instrument2
...

ip1 и ip2 это интересующие нас ip-адреса. Как говорилось на лекции, данные по снепшотам и апдейтам изначально приходят по разным каналам, и эти адреса им соответствуют. В данных помимо пакетов с этих адресов могут встречаться и другие, их нужно пропускать. Список instrument1,... это список интересующих нас инструментов (instrument_name), по которым нужно поддерживать ордербуки.

Что выводить в ответ

Для каждого обновления ордербука по заданным в мете инструментам вам нужно пересчитать VWAP. При этом делать это не нужно в следующих случаях:

  • пришел снепшот
  • не смогли прочитать сообщение (будь то битый фрейм или данные с другими ip или т.п.)

Во всех этих случаях пишите в выходную очередь единственное 4-байтовое число 0. В противном случае обозначим за s_1, ..., s_k id инструментов, для которых верно:

  • VWAP изменился по сравнению с предыдущим апдейтом
  • ордербук по данному инструменту в данный момент валиден
  • обе стороны ордербука (аски и биды) непустые

Тогда в выходную очередь необходимо вывести сначала 4-байтовое k, а затем последоательно k 4-байтовых троек (в любом порядке):

<s_i, VWAP_numerator_i, VWAP_denominator_i>

Поскольку VWAP представляет собой дробь, то чтобы не сражаться с ошибками округления, выводите прямо числитель и знаменатель. При подсчете величин нормируйте цены на tick_size (это будет целое число). Обе величины вычисляйте в uint32_t.

Как устроено тестирование и замер результатов

Окружение

  • Машина для тестирования: Intel Xeon Gold 5412U
  • Тактовая частота: 2900MHz
  • TSC_MZ: 2100MHz
  • hyper-threading отключен

Параллельно на сервере может быть запущено не более, чем 4 решения. Каждое решение запускается на своем подмножестве изолированных ядер. Помимо этого L3 кеш поделен на 5 равных частей с помощью resctrl (4 для решений и 1 для самой системы), т.е. каждому решению доступно ~9MB L3 кеша.

Запуск устроен следующим образом:

  • раннер вычитывает фрейм из pcap файла и подает на вход решению
  • таймер запускается непосредственно перед сдвигом оффсета в очереди раннер->решение
  • таймер останавливается при получении новых данных в очереди решение->раннер
  • таким образом раннер подает следующий фрейм только при получении ответ на текущий.

В качестве "таймера" используется https://en.wikipedia.org/wiki/Time_Stamp_Counter, мы замеряем непосредственно тики, без перевода в секунды. Замеры для фреймов, на которых ответ имеет нулевую длину (будь то ненужные пакеты, снепшоты, апдейты без изменений), не используются в подсчете финального скора.

Скрипт scorer.py может принимать аргумент --tsc, если вы хотите конвертировать тики в прошедшее время.

Итоговый скор

Пусть результаты замеров равны t_1, ..., t_n на фреймах размера s_1, ..., s_n. Тогда скор считается как

$$Score = \sum_{i=1}^n \frac{t_i}{s_i}$$

В процессе соревнования скор считается на наборе данных, отличном от выданного публично. Итоговое тестирование с финальными результатами будет проведено на отдельном (третьем) наборе данных.

About

No description, website, or topics provided.

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

Packages

Contributors

Languages