返回题库

订单簿快照

Order Book Snapshot

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

题目详情

订单簿通过处理持续的行情数据消息，追踪金融标的的挂单买入（bid）和卖出（ask）订单。通过添加、修改和删除操作维护精确的低延迟限价订单簿，是现代量化交易系统的基础架构组件。

任务：实现 OrderBook 类，维护买卖双侧价格-数量映射，支持新增、修改、删除订单操作，并提供获取最优买卖价和各侧深度快照的方法。

英文原题

An order book tracks the resting buy (bid) and sell (ask) orders for a financial instrument by processing a continuous stream of market data messages. Maintaining an accurate, low-latency representation of this limit order book through add, modify, and delete operations is a fundamental architectural component of modern quantitative trading systems.
Task
Implement an OrderBook class that maintains a limit order book and generates snapshots of the top 5 bid and ask levels. The driver function pr

解析

问题分析

订单簿快照需要捕获某一时刻的完整买卖盘深度。由于订单簿持续更新，构建一致性快照需要处理并发更新——通常通过双缓冲或序列号机制实现。

解法

struct OrderBookSnapshot { double best_bid, best_ask; int bid_depth, ask_depth; std::vector<std::pair<double,int>> bids, asks; };
class Snapshotter {
    OrderBook& book_;
public:
    OrderBookSnapshot take() {
        OrderBookSnapshot snap;
        auto [bids, asks] = book_.getLevels();  // 原子获取所有档位
        snap.best_bid = bids.empty() ? 0 : bids[0].first;
        snap.best_ask = asks.empty() ? 0 : asks[0].first;
        snap.bids = bids; snap.asks = asks;
        return snap;
    }
};

复杂度与边界

  • 时间复杂度：O(档位数)，通常 < 100
  • 边界条件：(1) 空订单簿 best_bid/best_ask 为 0 (2) 快照时刻的瞬时状态，非原子 (3) 高频更新时使用序列号验证一致性

英文解析

Analysis

Order book snapshots capture the complete bid/ask depth at a specific moment. Since the order book updates continuously, building a consistent snapshot requires handling concurrent updates — typically via double buffering or sequence number mechanisms.

Solution

struct OrderBookSnapshot { double best_bid, best_ask; int bid_depth, ask_depth; std::vector<std::pair<double,int>> bids, asks; };
class Snapshotter {
    OrderBook& book_;
public:
    OrderBookSnapshot take() {
        OrderBookSnapshot snap;
        auto [bids, asks] = book_.getLevels();  // atomically retrieve all levels
        snap.best_bid = bids.empty() ? 0 : bids[0].first;
        snap.best_ask = asks.empty() ? 0 : asks[0].first;
        snap.bids = bids; snap.asks = asks;
        return snap;
    }
};

Complexity & Edge Cases

  • Time complexity: O(price levels), typically < 100
  • Edge cases: (1) Empty order book: best_bid/best_ask = 0 (2) Snapshot is instantaneous state, not atomic (3) High-frequency updates require sequence number validation for consistency

Key Considerations

  1. Snapshot consistency: Must capture all levels atomically; partial snapshot mixed with concurrent updates produces inconsistent crossed book views
  2. Depth limitation: Production books may have 1000+ levels; configurable depth limit (e.g., top 5, top 10) balances memory vs information needs
  3. Timestamp precision: Each level should carry update timestamp for staleness detection; stale levels (>100ms old) should be flagged or discarded
  4. Delta compression: Transmitting full snapshots repeatedly wastes bandwidth; use delta encoding — send only changed levels between consecutive snapshots