Введение
В один прекрасный день мне написал рекрутер с крайне заманчивым предложением
Дмитрий, привет!
Наткнулся на твой профиль и подумал, что тебе может быть интересна вакансия в независимой HFT-компании, где много свободы и крутого R&D. Они не просто гонятся за скоростью, а активно используют машинное обучение в своем трейдинге.
На проде C++ (17/20), упор на многопоточку, Linux, оптимизацию и низколатентные системы. В зависимости от опыта есть несколько направлений — от гринфилд-разработки платформы до создания симулятора для тестирования стратегий. Команда сильная, процесс собеседования непростой, но если тебя драйвит алгоритмика и системное программирование, может быть, это как раз то, что ты ищешь.
Буду рад сотруднечиству!
Я на тот момент как раз находился в поиске новой работы, поэтому предложение принял. Опустим стандартный звонок с этим рекрутером, с HR'ом компании и онлайн-тестовое и перейдём к более интересному - тестовому заданию. Сразу скажу, что тестовое не оплачивалось, и я взялся за него по нескольким причинам. Во-первых, оно мне и вправду понравилось, во-вторых, кодовую базу я планировал использовать в своём с корешами pet-проекте по финансам, в-третьих, не оставлял надежд пройти отбор до конца и получить желаемый offer. Спойлер - игра стоила свеч, поэтому прошу к прочтению.
Тестовое задание
Требовалось реализовать на C++ парсер pcap-файла, декодер протокола Spectra Simba (пары сообщений достаточно), проверить их в связке на тестовых данных Мосбиржы и сохранить результат в .jsonl-файле. И это всё без сторонних библиотек. Ни с чем из вышеперечисленного я раньше не работал, поэтому давайте разбираться вместе.
Парсер pcap-файла
Pcap (англ. Packet Capture) - это бинарный формат со структурой GlobalHeader, PacketHeader, PacketData, ..., PacketHeader, PacketData. Т.е. сначала идёт глобальный заголовок с полями, относящимися ко всему файлу, а дальше чередуются в паре заголовок пакета и его данные (см. руководства 1 и 2).
struct GlobalHeader { uint32_t magic_number; uint16_t version_major; uint16_t version_minor; int32_t thiszone; uint32_t sigfigs; uint32_t snaplen; uint32_t network; }; struct PacketHeader { uint32_t ts_sec; uint32_t ts_usec; uint32_t incl_len; uint32_t orig_len; }; using PacketData = std::vector<uint8_t>; struct Packet { PacketHeader header; PacketData data; };
Если говорить про поля глобального заголовка, то
magic_number - магическое число=)
version_major/version_minor - версии формата, обычно 2 и 4 соответственно
thiszone - смещение от UTC в сек., чаще всего 0
sigfigs - точность времени, чаще всего 0
snaplen - максимальная длина пакета, обычно 65535
network - тип канального уровня
Из всех полей больший интерес представляет network, которое в нашем случае должно соответствовать Ethernet, т.к. протокол Spectra Simba перекидывает сообщения именно по Ethernet.
Если говорить про поля заголовка пакета, то
ts_sec - время захвата в сек.
ts_usec - микросекунды времени захвата
incl_len - длина фактических данных
orig_len - длина оригинальных данных
Если бы не ограничение на использование сторонних библиотек, то можно было подтянуть libpcap. Собственная же реализация получилась следующей
GlobalHeader Parser::ParseGlobalHeader(std::istream& file) { GlobalHeader global_header{}; file.read(reinterpret_cast<char*>(&global_header), sizeof(global_header)); if (!file) throw std::runtime_error("Can't read global header"); return global_header; } Packet Parser::ParsePacket(std::istream& file) { PacketHeader header{}; file.read(reinterpret_cast<char*>(&header), sizeof(header)); if (!file) throw std::runtime_error("Can't read packet header"); PacketData data(header.incl_len); file.read(reinterpret_cast<char*>(data.data()), header.incl_len); if (!file) throw std::runtime_error("Can't read packet data"); return {header, data}; }
Декодер протокола Spectra Simba
Это бинарный протокол для срочного рынка Мосбиржы. Декодировать просили не все сообщения, а лишь OrderUpdate (обновления заявок), OrderExecution (исполнение заявок) и OrderBookSnapshot (снимок стакана).
Скрытый текст
Срочный рынок - это рынок форвардов, фьючерсов, опционов и свопов.
Форвард (англ. forward) - это обязательство купли/продажи в будущем, не регулируемое биржей.
Фьючерс (англ. future) - это обязательство купли/продажи в будущем, регулируемое биржей.
Опцион (англ. option) - это право купли/продажи в будущем, но в отличие от фьючерса сделка может быть отклонена.
Свап (англ. swap) - это денежный обмен в будущем.
Биржевая заявка (англ. order) - это указание купли/продажи.
Биржевой стакан (англ. order book) - это таблица лимитных заявок, т.е. тех, для которых указана желаемая цена (лимит) купли/продажи.
Заголовки
Согласно спецификации протокольные сообщения лежат внутри UDP-пакета, который внутри IPv4-пакета, а тот уже �� Ethernet-пакете. Прям как с Кощеем - ... игла в яйце, яйцо в утке, утка в зайце и т.д.
Подключаем заголовочные файлы netinet и приступаем к разбору. Не лишним проверить, что протокол в Ethernet-заголовке именно IPv4, а протокол в IPv4-заголовке именно UDP
Decoder::PacketData Decoder::DecodeNetworkHeaders(const PacketData &packet_data) { auto payload = packet_data.data(); const auto ethernet_header = reinterpret_cast<const struct ether_header*>(payload); if (ntohs(ethernet_header->ether_type) != ETHERTYPE_IP) throw std::runtime_error("Packet data isn't IPv4"); payload += sizeof(ether_header); const auto ip_header = reinterpret_cast<const struct ip*>(payload); if (ip_header->ip_p != IPPROTO_UDP) throw std::runtime_error("Packet data isn't UDP"); const auto ip_header_size = (ip_header->ip_v & 0x0F) * 4; payload += ip_header_size; payload += sizeof(struct udphdr); const auto payload_size = packet_data.size() - (sizeof(struct ether_header) + ip_header_size + sizeof(struct udphdr)); return {payload, payload + payload_size}; }
И только после всего этого можно разбирать заголовки протокола, первое из которых MarketDataPacketHeader. В зависимости от значения его поля msg_flags можно перейти к разбору либо сообщений с инкрементом либо со снимком
void Decoder::DecodeMessage(const PacketData& packet_data) { size_t offset = 0; const auto market_data_packet_header = Cast<MarketDataPacketHeader>(packet_data.data(), offset); const bool is_incremental = market_data_packet_header.msg_flags & 0x8; if (is_incremental) DecodeIncrementalMessage(packet_data, offset); else { DecodeSnapshotMessage(packet_data, offset); } }
Incremental Packet
Это OrderUpdate и OrderExecution
struct OrderUpdate { static constexpr uint16_t TEMPLATE_ID = 15; int64_t md_entry_id; Decimal5 md_entry_px; int64_t md_entry_size; MDFlagsSet md_flags; MDFlags2Set md_flags2; int32_t security_id; uint32_t rpt_seq; MDUpdateAction md_update_action; MDEntryType md_entry_type; }; struct OrderExecution { static constexpr uint16_t TEMPLATE_ID = 16; int64_t md_entry_id; Decimal5NULL md_entry_px; int64_t md_entry_size; Decimal5 last_px; int64_t last_qty; int64_t trade_id; MDFlagsSet md_flags; MDFlags2Set md_flags2; int32_t security_id; uint32_t rpt_seq; MDUpdateAction md_update_action; MDEntryType md_entry_type; };
Но перед их разбором требуется обработать IncrementalPacketHeader, а затем уже в цикле читать вместе с SimpleBinaryEncodingHeader, т.к. их может быть больше одного сообщения в пакете
void Decoder::DecodeIncrementalMessage(const PacketData& packet_data, size_t& offset) { Cast<IncrementalPacketHeader>(packet_data.data(), offset); while (offset < packet_data.size()) { const auto simple_binary_encoding_header = Cast<SimpleBinaryEncodingHeader>(packet_data.data(), offset); switch (simple_binary_encoding_header.template_id) { case OrderUpdate::TEMPLATE_ID: _message_handler(Cast<OrderUpdate>(packet_data.data(), offset)); break; case OrderExecution::TEMPLATE_ID: _message_handler(Cast<OrderExecution>(packet_data.data(), offset)); break; default: offset += simple_binary_encoding_header.block_length; break; } } }
Snapshot Packet
Это OrderBookSnapshot
struct OrderBookSnapshot { static constexpr uint16_t TEMPLATE_ID = 17; int32_t security_id; uint32_t last_msg_seq_num_processed; uint32_t rpt_seq; uint32_t exchange_trading_session_id; GroupSize no_md_entries; struct Entry { int64_t md_entry_id; uint64_t transact_time; Decimal5NULL md_entry_px; int64_t md_entry_size; int64_t trade_id; MDFlagsSet md_flags; MDFlags2Set md_flags2; MDEntryType md_entry_type; }; std::vector<Entry> entries; static constexpr size_t SIZE = sizeof(security_id) + sizeof(last_msg_seq_num_processed) + sizeof(rpt_seq) + sizeof(exchange_trading_session_id) + sizeof(no_md_entries); };
С этим типом пакета можно сразу перейти к чтению одного SimpleBinaryEncodingHeader и одного сообщения
void Decoder::DecodeSnapshotMessage(const PacketData& packet_data, size_t& offset) { const auto simple_binary_encoding_header = Cast<SimpleBinaryEncodingHeader>(packet_data.data(), offset); switch (simple_binary_encoding_header.template_id) { case OrderBookSnapshot::TEMPLATE_ID: { OrderBookSnapshot order_book_snapshot{}; std::memcpy(&order_book_snapshot, &packet_data[offset], OrderBookSnapshot::SIZE); offset += OrderBookSnapshot::SIZE; order_book_snapshot.entries.resize(order_book_snapshot.no_md_entries.num_in_group); for (auto& entry: order_book_snapshot.entries) { std::memcpy(&entry, &packet_data[offset], sizeof(OrderBookSnapshot::Entry)); offset += sizeof(OrderBookSnapshot::Entry); } _message_handler(order_book_snapshot); break; } default: break; } }
Сохранение в .jsonl
.jsonl - это формат такого файла, каждая строчка которого является JSON'ом. Ну т.е. требовалось вести потоковую запись JSON'ов в файл. Если бы не ограничение на использование сторонних библиотек, то можно было взять одну из библиотек libjsoncpp, rapidjson или nlohmann_json. Но как оказалось формировать JSON на голом STL не такая уж и сложная задача, особенно в современных стандартах C++. Начиная с C++20 появился долгожданный std::format. Например, для сообщения OrderUpdate будет
struct MessageVisitor { std::string operator()(const OrderUpdate& message); std::string operator()(const OrderExecution& message); std::string operator()(const OrderBookSnapshot& message); }; template<class T> requires requires(T t) { { T::exponent } -> std::same_as<const double&>; { t.mantissa } -> std::same_as<int64_t&>; } double to_decimal(const T& value) { return static_cast<double>(value.mantissa) * T::exponent; } std::string MessageVisitor::operator()(const OrderUpdate& message) { return std::format( R"({{"md_entry_id": {}, "md_entry_px": {}, "md_entry_size": {}, "md_flags": {}, "md_flags2": {}, "security_id": {}, "rpt_seq": {}, "md_update_action": {}, "md_entry_type": {}}})", message.md_entry_id, to_decimal(message.md_entry_px), message.md_entry_size, std::to_underlying(message.md_flags), std::to_underlying(message.md_flags2), message.security_id, message.rpt_seq, std::to_underlying(message.md_update_action), std::to_underlying(message.md_entry_type)); }
Для сообщения OrderExecution примерно тоже самое. А вот с сообщением OrderBookSnapshot оказалось не так просто из-за вектора Entry, но и тут на помощь пришёл C++20 с std::formatter. Достаточно определить способ форматирования для вектора
template<typename T> struct std::formatter<std::vector<T>> { constexpr auto parse(std::format_parse_context& ctx) { return ctx.begin(); } auto format(const std::vector<T>& vec, std::format_context& ctx) const { auto out = ctx.out(); out = std::format_to(out, "["); for (size_t i = 0; i < vec.size(); ++i) { if (i > 0) out = std::format_to(out, ", "); out = std::format_to(out, "{}", vec[i]); } out = std::format_to(out, "]"); return out; } };
Ну и в итоге
std::string MessageVisitor::operator()(const OrderBookSnapshot& message) { std::vector<std::string> entries; entries.resize(message.entries.size()); std::transform(message.entries.begin(), message.entries.end(), entries.begin(), [](const auto& entry) { return std::format( R"({{"md_entry_id": {}, "transact_time": {}, "md_entry_px": {}, "md_entry_size": {}, "trade_id": {}, "md_flags": {}, "md_flags2": {}, "md_entry_type": {}}})", entry.md_entry_id, entry.transact_time, to_decimal(entry.md_entry_px), entry.md_entry_size, entry.trade_id, std::to_underlying(entry.md_flags), std::to_underlying(entry.md_flags2), std::to_underlying(entry.md_entry_type)); } ); return std::format( R"({{"security_id": {}, "last_msg_seq_num_processed": {}, "rpt_seq": {}, "exchange_trading_session_id": {}, "no_md_entries": {{"block_length": {}, "num_in_group": {}}}, "entries": {}}})", message.security_id, message.last_msg_seq_num_processed, message.rpt_seq, message.exchange_trading_session_id, message.no_md_entries.block_length, message.no_md_entries.num_in_group, entries); }
Заключение
В общей сложности тестовое заняло у меня одну неделю. Основные трудности лично у меня были по связке парсера Pcap-файла с декодером протокола Spectra Simba - долго не мог понять, что перед декодированием протокольных сообщений нужно прочитать заголовки Ethernet, IPv4 и UDP.
Все исходные тексты выложены в открытый доступ - https://github.com/dkosaty/simba_pcap_decoder. Ставьте звёзды, добавляйтесь в follower'ы.
Спасибо, что почитали до конца. Напишите в комментариях была ли полезной статья. Буду признателен любой оценке.
