返回题库

扁平合并订单簿

Flat Combining Orderbook

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

题目详情

Flat Combining 是低延迟交易系统中缓解锁竞争的同步范式：线程将请求发布到线程本地记录，由合并者线程批量处理，显著减少锁获取次数和缓存行争用。

任务：实现 Flat Combining 订单簿类，使用 flat combining 更新订单簿。各线程将操作请求写入线程本地发布记录，合并者线程扫描所有记录批量执行。支持添加、取消、修改操作。

英文原题

Flat combining is a synchronization paradigm used in low-latency trading systems to mitigate lock contention by allowing threads to publish requests to thread-local records, which a single "combiner" thread processes in a batch. This technique drastically improves cache locality and reduces synchronization overhead, making it highly effective for maximizing throughput in high-frequency trading engines.
Task
Implement a simulator for a Flat Combining Order Book by completing the FlatCombiningSim

解析

问题分析

扁平合并（Flat Combining）是一种并发优化技术：多个生产者线程将请求提交到全局队列，单个合并线程批量处理并将结果返回。在订单簿场景中，这消除了对每个价格档位的锁竞争，显著提升多核吞吐量。

实现

class FlatCombiningOrderBook {
    struct Request { enum {ADD, CANCEL, GET} op; uint64_t id; double price; int qty; };
    std::vector<Request> reqs_[2];  // 双缓冲
    std::atomic<int> active_{0};
    std::mutex mtx_;
public:
    void submit(Request r) {
        std::lock_guard lk(mtx_);
        reqs_[active_].push_back(r);
    }
    void combine() {
        int batch = active_.exchange(1 - active_, std::memory_order_acq_rel);
        for (auto& r : reqs_[batch]) {
            switch (r.op) { /* 批量执行所有请求 */ }
        }
        reqs_[batch].clear();
    }
};

复杂度与边界

  • 时间复杂度：combine O(批量大小)，单请求均摊 O(1)
  • 空间复杂度：O(最大批量大小)
  • 边界条件：(1) 合并线程需定期唤醒（即使无请求）(2) 批量过大会增加单个请求延迟 (3) 请求需带序列号以正确返回结果

英文解析

Analysis

Flat Combining is a concurrency optimization technique: multiple producer threads submit requests to a global queue, and a single combiner thread processes them in batch and returns results. In order book scenarios, this eliminates lock contention on each price level, significantly improving multi-core throughput.

Solution

class FlatCombiningOrderBook {
    struct Request { enum {ADD, CANCEL, GET} op; uint64_t id; double price; int qty; };
    std::vector<Request> reqs_[2];  // double-buffer
    std::atomic<int> active_{0};
    std::mutex mtx_;
public:
    void submit(Request r) {
        std::lock_guard lk(mtx_);
        reqs_[active_].push_back(r);
    }
    void combine() {
        int batch = active_.exchange(1 - active_, std::memory_order_acq_rel);
        for (auto& r : reqs_[batch]) {
            switch (r.op) { /* batch-execute all requests */ }
        }
        reqs_[batch].clear();
    }
};

Complexity & Edge Cases

  • Time complexity: O(P) for P combining participants; O(log N) for order book priority queue insertion
  • Space complexity: O(N + P) for N orders and P combiner request slots
  • Edge cases: (1) Combiner thread starvation if no thread wins the lock frequently. (2) Request slot overflow during burst periods. (3) Delayed execution for non-combiner threads adds latency variance.

Key Considerations

  1. Batch processing: Combining multiple requests into one batch reduces per-request synchronization overhead.
  2. Double buffering: Active buffer accepts new requests while standby buffer is being processed.
  3. Combiner thread: Must periodically wake up (even with no requests) to check for pending work.
  4. Time complexity: combine O(batch size); single request amortized O(1).