Введение
В один прекрасный день мне написал рекрутер с крайне заманчивым предложением
Дмитрий, привет!
Наткнулся на твой профиль и подумал, что тебе может быть интересна вакансия в независимой 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'ы.
Спасибо, что почитали до конца. Напишите в комментариях была ли полезной статья. Буду признателен любой оценке.