返回题库

二进制协议编解码器

Binary Protocol Codec

专题
Systems & Architecture / 系统与架构
难度
L2
来源
MyntBit

题目详情

金融协议（如 FIX FAST、OUCH、MOLD/UDP）使用紧凑的二进制编码以减少带宽和延迟。二进制编解码器必须处理变长整数编码、位域打包和字节序转换。

任务：实现一个支持大端序和变长编码的二进制协议编解码器。

英文原题

In low-latency trading systems, financial messages are often transmitted using custom binary protocols rather than text-based formats to minimize bandwidth and parsing overhead. Implementing a binary codec requires packing and unpacking fields into fixed-width byte sequences while strictly adhering to network byte order (Big-Endian) conventions.
Task
Implement a BinaryCodec class to encode and decode a custom order message protocol. The protocol uses Big-Endian (Network Byte Order) for all mult

解析

问题分析

金融协议（如 FIX FAST、OUCH、MOLD/UDP）使用紧凑的二进制编码以减少带宽和延迟。二进制编解码器必须处理整数变长编码（varint）、位域打包、字节序转换和消息边界识别。

实现

class BinaryCodec {
    std::vector<uint8_t> buffer_;
    size_t read_pos_ = 0;
public:
    void writeUInt32(uint32_t val) {
        buffer_.push_back((val >> 24) & 0xFF);
        buffer_.push_back((val >> 16) & 0xFF);
        buffer_.push_back((val >> 8) & 0xFF);
        buffer_.push_back(val & 0xFF);
    }
    void writeVarInt(uint64_t val) { // 7-bit 编码
        do { buffer_.push_back((val & 0x7F) | (val > 0x7F ? 0x80 : 0)); val >>= 7; } while (val);
    }
    uint32_t readUInt32() {
        if (read_pos_ + 4 > buffer_.size()) throw std::runtime_error("Buffer underflow");
        uint32_t val = (buffer_[read_pos_] << 24) | (buffer_[read_pos_+1] << 16) |
                       (buffer_[read_pos_+2] << 8) | buffer_[read_pos_+3];
        read_pos_ += 4; return val;
    }
};

复杂度与边界

  • 时间复杂度：所有操作 O(1)
  • 空间复杂度：O(消息大小)
  • 边界条件：(1) 缓冲区不足时抛异常 (2) varint 最大 10 字节 (3) 网络字节序(大端)与主机字节序转换 (4) 超过消息边界时拒绝读取

英文解析

Analysis

Financial protocols (FIX FAST, OUCH, MOLD/UDP) use compact binary encoding to reduce bandwidth and latency. Binary codecs must handle integer variable-length encoding (varint), bitfield packing, byte order conversion, and message boundary identification.

Solution

class BinaryCodec {
    std::vector<uint8_t> buffer_;
    size_t read_pos_ = 0;
public:
    void writeUInt32(uint32_t val) {
        buffer_.push_back((val >> 24) & 0xFF);
        buffer_.push_back((val >> 16) & 0xFF);
        buffer_.push_back((val >> 8) & 0xFF);
        buffer_.push_back(val & 0xFF);
    }
    void writeVarInt(uint64_t val) { // 7-bit encoding
        do { buffer_.push_back((val & 0x7F) | (val > 0x7F ? 0x80 : 0)); val >>= 7; } while (val);
    }
    uint32_t readUInt32() {
        if (read_pos_ + 4 > buffer_.size()) throw std::runtime_error("Buffer underflow");
        uint32_t val = (buffer_[read_pos_] << 24) | (buffer_[read_pos_+1] << 16) |
                       (buffer_[read_pos_+2] << 8) | buffer_[read_pos_+3];
        read_pos_ += 4; return val;
    }
};

Complexity & Edge Cases

  • Time complexity: All operations O(1)
  • Space complexity: O(message size)
  • Edge cases: (1) Insufficient buffer throws exception (2) varint max 10 bytes (3) Network byte order (big-endian) vs host byte order conversion (4) Reject reads beyond message boundary

Key Considerations

  1. Byte order: Financial protocols (FIX binary, SBE) specify big-endian; ensure consistent byte order across encode/decode — never rely on host byte order
  2. Schema evolution: Field additions between protocol versions must maintain backward compatibility; use optional fields with default values
  3. Zero-copy decode: Performance-sensitive systems decode directly from wire buffer without copying; validate bounds before accessing fields
  4. Checksum integrity: Binary protocols include CRC/checksum; encoder must compute after payload assembly, decoder must verify before field extraction