网站开发招标文件范本商城网站建设视频教程

张

张建站

2026/4/7 8:49:57

10分钟阅读

网站开发招标文件范本,商城网站建设视频教程,邯郸建设网站的公司,企业网站改版seo订单簿#xff08;Order Book#xff09;#xff1a;从原理到工业级实现什么是订单簿订单簿#xff08;Order Book#xff09;是交易所撮合引擎#xff08;Matching Engine#xff09;的核心数据结构。它维护着市场上所有未成交的限价单#xff08;Limit Order#…订单簿Order Book从原理到工业级实现什么是订单簿订单簿Order Book是交易所撮合引擎Matching Engine的核心数据结构。它维护着市场上所有未成交的限价单Limit Order按照价格优先、时间优先Price-Time Priority也叫 FIFO matching的规则进行撮合。买方订单簿Buy Book / Bid Book中出价最高的排在最前面因为出价高的买家更积极卖方订单簿Sell Book / Ask Book中要价最低的排在最前面因为要价低的卖家更积极。买一价Best Bid和卖一价Best Ask之间的差值叫做价差Spread。当一个新的卖单进来时它会尝试与买方订单簿从最优价格开始进行撮合。如果卖单价格低于或等于买一价就会发生成交Fill。同一价格档位内先到的订单先被撮合这就是时间优先原则。核心操作一个订单簿需要支持以下核心操作添加订单Add、取消订单Cancel、撮合Match、查询最优价格GetBestPrice以及查询某一价位的总量GetQuantityAtLevel。在高频交易High-Frequency Trading, HFT的场景下这些操作的延迟Latency要求极其苛刻通常需要在亚微秒Sub-microsecond级别完成。数据结构选型订单簿的数据结构设计需要在多个操作之间取得平衡。对于价格档位Price Level的组织最直观的选择是std::map。买方用std::mapuint64_t, Level, std::greater实现降序排列卖方用std::mapuint64_t, Level实现升序排列。std::map底层是红黑树Red-Black Tree查找和插入都是 O(log N)且迭代器在插入删除后保持有效Iterator Stability。但红黑树的节点在内存中不连续遍历时会产生大量缓存未命中Cache Miss这在低延迟场景下是不可接受的。对于同一档位内的订单队列需要支持头部插入新订单和尾部消费最老的订单先成交同时还需要支持任意位置删除取消订单。std::list是天然的选择——双向链表支持 O(1) 的任意位置插入删除且插入删除不会使其他迭代器失效。但和红黑树一样链表节点在内存中不连续缓存局部性Cache Locality很差。对于按订单 ID 快速查找需要一个哈希表将订单 ID 映射到它在订单簿中的位置。std::unordered_map是标准选择平均 O(1) 查找。但标准库的实现通常使用链地址法Separate Chaining每个桶是一个链表同样有缓存不友好的问题。工业级实现通常会使用开放寻址法Open Addressing的扁平哈希表Flat Hash Map比如 Google 的absl::flat_hash_map或 Facebook 的folly::F14FastMap它们将元素直接存储在连续内存中缓存命中率显著提高。完整实现以下是一个功能完整的订单簿实现包含买方和卖方的撮合逻辑#includecstdint#includefunctional#includeiostream#includelist#includemap#includestdexcept#includeunordered_map// ----- Type Definitions -----enumclassSide{BUY,SELL};structOrder{Side side;uint64_torderId;uint64_tprice;uint64_tquantity;};// A price level holds the aggregate quantity and a FIFO queue of orders.// New orders are pushed to the front; matching consumes from the back (oldest// first).structLevel{uint64_ttotalQuantity;std::listOrderorders;Level():totalQuantity(0){}};// OrderHash allows O(1) lookup from orderId to the exact position in the book.// It stores a pointer to the Level and an iterator into that Levels order// list. IMPORTANT: This design relies on two stability guarantees:// 1. std::map does not invalidate pointers/references to elements on// insert/erase of OTHER elements.// 2. std::list does not invalidate iterators on insert/erase of OTHER// elements.structOrderLocation{Level*level;uint64_tprice;// stored separately to locate the level in the map for cleanupstd::listOrder::iterator it;// stable as long as this specific node is not erased};// ----- Order Book -----classOrderBook{public:// Add a new limit order to the book // Returns the quantity matched. Any remaining quantity rests in the book.uint64_tAddOrder(Order order){// Reject duplicate order IDsif(orderMap_.find(order.orderId)!orderMap_.end()){return0;}// Step 1: Attempt to match the incoming order against the opposite sideuint64_tmatchedMatch(order);// Step 2: If there is remaining quantity, insert it into the resting bookif(order.quantity0){InsertIntoBook(order);}returnmatched;}// Cancel an existing order by ID // Returns true if the order was found and removed.boolCancelOrder(uint64_torderId){autoitorderMap_.find(orderId);if(itorderMap_.end()){returnfalse;}// Retrieve the location info BEFORE erasing from orderMapOrderLocation locit-second;Order order*loc.it;// Update the level: decrement total quantity, remove the order nodeloc.level-totalQuantity-order.quantity;loc.level-orders.erase(loc.it);// Remove from the orderId lookup maporderMap_.erase(it);// If this was the last order at this price level, remove the level// entirely. This keeps the book clean and ensures GetBestPrice() is// correct.if(loc.level-totalQuantity0){if(order.sideSide::BUY){buyBook_.erase(order.price);}else{sellBook_.erase(order.price);}}returntrue;}// Query the best bid (highest buy price) uint64_tGetBestBid()const{if(buyBook_.empty()){throwstd::runtime_error(buy book is empty);}returnbuyBook_.begin()-first;}// Query the best ask (lowest sell price) uint64_tGetBestAsk()const{if(sellBook_.empty()){throwstd::runtime_error(sell book is empty);}returnsellBook_.begin()-first;}// Query total resting quantity at a given price and side uint64_tGetQuantityAtLevel(Side side,uint64_tprice)const{constautobook(sideSide::BUY)?buyBook_:sellBook_;autoitbook.find(price);if(itbook.end()){return0;}returnit-second.totalQuantity;}private:// Buy book: sorted descending by price (highest best bid begin)std::mapuint64_t,Level,std::greaterbuyBook_;// Sell book: sorted ascending by price (lowest best ask begin)std::mapuint64_t,LevelsellBook_;// Global order lookup: orderId - location in the bookstd::unordered_mapuint64_t,OrderLocationorderMap_;// ----- Internal: Insert a resting order into the appropriate book -----voidInsertIntoBook(constOrderorder){autobook(order.sideSide::BUY)?buyBook_:sellBook_;// operator[] default-constructs a Level if the price doesnt exist yet.// This is safe because Level() initializes totalQuantity to 0.autolevelbook[order.price];level.totalQuantityorder.quantity;// push_front: newest orders go to the front.// Matching consumes from the back (oldest first) FIFO within a level.level.orders.push_front(order);// Record the position in orderMap for O(1) cancel.// level is stable because std::map guarantees pointer stability.// level.orders.begin() is stable because std::list guarantees iterator// stability.orderMap_[order.orderId]OrderLocation{.levellevel,.priceorder.price,.itlevel.orders.begin()};}// ----- Internal: Match an incoming order against the opposite book -----// Modifies order.quantity in place (decremented by the amount filled).// Returns the total matched quantity.uint64_tMatch(Orderorder){if(order.sideSide::SELL){returnMatchAgainstBook(order,buyBook_);}else{returnMatchAgainstBook(order,sellBook_);}}// Generic matching logic that works for both sides.// Template parameter allows it to work with both map orderings.//// The price matching condition differs by side:// - Incoming SELL matches against buy levels where buyPrice sellPrice// - Incoming BUY matches against sell levels where sellPrice buyPrice// Because both books are sorted with the best price at begin(),// and we iterate from begin(), the condition simplifies to:// - For SELL matching against buyBook (descending): stop when buyPrice // sellPrice// - For BUY matching against sellBook (ascending): stop when sellPrice // buyPrice// Both are equivalent to: the resting price is worse than the incoming// price.templatetypenameComparatoruint64_tMatchAgainstBook(Orderorder,std::mapuint64_t,Level,Comparatorbook){uint64_ttotalMatched0;for(autoitbook.begin();it!book.end()order.quantity0;){auto[price,level]*it;// Check if this price level can trade with the incoming order.// For a SELL order hitting the buy book: buy price must be sell price.// For a BUY order hitting the sell book: sell price must be buy price.if(!PricesCross(order.side,order.price,price)){break;// No more matchable levels (book is sorted by attractiveness)}if(order.quantitylevel.totalQuantity){// --- Optimization: sweep the entire level ---// When the incoming quantity exceeds the levels total,// we can skip per-order quantity arithmetic.// However, we still must iterate to clean up orderMap entries.totalMatchedlevel.totalQuantity;order.quantity-level.totalQuantity;for(autorestingOrder:level.orders){orderMap_.erase(restingOrder.orderId);}// erase returns the next valid iteratoritbook.erase(it);}else{// --- Partial fill of this level ---// Consume orders from the back (oldest first FIFO).while(order.quantity0){// IMPORTANT: Fetch the reference INSIDE the loop.// After pop_back(), the previous reference is dangling.autobackOrderlevel.orders.back();if(order.quantitybackOrder.quantity){// Fully fill this resting ordertotalMatchedbackOrder.quantity;order.quantity-backOrder.quantity;level.totalQuantity-backOrder.quantity;orderMap_.erase(backOrder.orderId);level.orders.pop_back();// The reference backOrder is now dangling.// The next iteration will fetch a fresh one.}else{// Partially fill this resting order// IMPORTANT: Update totalQuantity and backOrder.quantity// BEFORE zeroing order.quantity, otherwise you subtract 0.totalMatchedorder.quantity;level.totalQuantity-order.quantity;backOrder.quantity-order.quantity;order.quantity0;}}// Dont advance the iterator; we break out since the incoming order is// filled.break;}}returntotalMatched;}// Returns true if the incoming order price and resting price can trade.staticboolPricesCross(Side incomingSide,uint64_tincomingPrice,uint64_trestingPrice){if(incomingSideSide::SELL){// Seller is willing to sell at incomingPrice or higher.// Buyer is willing to buy at restingPrice or lower.// Trade happens if buyPrice sellPrice.returnrestingPriceincomingPrice;}else{// Buyer is willing to buy at incomingPrice or lower.// Seller is willing to sell at restingPrice or higher.// Trade happens if sellPrice buyPrice.returnrestingPriceincomingPrice;}}};容易出错的地方在实现过程中有几类 bug 极其常见值得专门讨论。多数据结构同步问题Multi-Structure Consistency。这是最核心的难点。订单簿本质上维护着三套相互关联的数据价格档位映射buyBook_/sellBook_、每个档位内的订单队列Level::orders、以及全局订单索引orderMap_。每一次 Add、Cancel、Match 操作都必须同时更新所有相关的数据结构且更新顺序不能出错。举个例子Cancel 操作需要依次完成以下四步从orderMap_查到订单位置、从链表中删除订单节点、更新档位的totalQuantity、如果档位清空则从 map 中移除该档位。遗漏任何一步都会导致数据不一致。最好的做法是在写代码之前先用注释列出每一步需要更新的数据结构然后逐一实现。引用与拷贝的混淆Reference vs. Copy。C 中auto默认产生拷贝。在使用结构化绑定Structured Binding遍历 map 时auto [price, level] *it会拷贝整个Level包括其中的std::list。之后对level的修改不会反映到 map 中。正确写法是auto [price, level] *it。这类 bug 编译器不会报错运行时也不一定立即崩溃非常隐蔽。养成习惯每次写auto时都显式决定是否需要。悬垂引用Dangling Reference。当你持有一个容器元素的引用或迭代器然后对容器做了修改操作这个引用可能就失效了。典型场景用auto back list.back()取得引用后调用list.pop_back()此时back已经指向被释放的内存。正确做法是在每次可能使引用失效的操作之后重新获取引用。在上面的 Match 实现中我们将auto backOrder level.orders.back()放在 while 循环内部而非外部就是为了避免这个问题。运算顺序导致的逻辑错误Order of Operations。在部分成交Partial Fill的逻辑中如果先执行order.quantity 0再执行level.totalQuantity - order.quantity实际上减去的是 0。一个变量同时承担剩余待撮合量和本次成交量两个语义时这种顺序错误极易发生。更安全的写法是引入一个局部变量uint64_t filled ...来显式分离这两个概念。空状态处理Empty State Cleanup。当一个档位的所有订单都被撮合或取消后totalQuantity归零但该档位仍然存在于 map 中。如果不清理GetBestBid()会返回一个没有实际订单的幽灵档位。必须在每次可能清空档位的操作后检查并清理。迭代器与指针的稳定性这是选择容器时最关键的考量之一值得单独说明。std::map的迭代器稳定性Iterator Stability是指对 map 进行插入或删除操作时不会影响指向其他元素的迭代器、引用和指针。这是红黑树的天然属性——每个节点是独立分配的增删一个节点不需要移动其他节点。我们的OrderLocation存储了Level*指针这个指针在其他价格档位增删时保持有效依赖的就是这个保证。std::list同样具备迭代器稳定性。链表节点是独立分配的插入或删除某个节点不影响其他节点的迭代器。OrderLocation中存储的std::listOrder::iterator正是依赖了这一点。std::deque的情况更微妙。std::deque保证引用和指针的稳定性Pointer/Reference Stability——在两端插入时已有元素不会被移动所以指向它们的指针和引用依然有效。但迭代器会失效Iterator Invalidation因为deque内部的分块索引结构可能被重组。这意味着如果想用deque替代list就不能在OrderLocation中存储迭代器而需要改用指针或其他定位方式这会显著增加实现复杂度。std::vector在插入或删除时可能触发重新分配Reallocation或元素搬移所有迭代器、引用和指针都可能失效。因此vector不适合作为需要稳定引用的订单队列。性能优化上面的实现在正确性上没有问题但在低延迟交易系统中性能是生命线。以下是从数据结构到系统层面的优化思路。价格档位从红黑树到数组直接寻址。std::map的红黑树结构每次查找需要 O(log N) 次比较和指针跳转每次跳转都可能导致缓存未命中。在实际市场中活跃的价格范围通常很窄——以股票为例价格在 tick 级别上可能只有几百个档位。这意味着我们可以预分配一个固定大小的数组用price - basePrice作为下标直接索引到对应的 Level。查找变成了一次数组访问O(1) 且完全缓存友好。对于最优价格的维护可以用一个变量跟踪当前最优价格在插入时取 max/min 更新在删除最优档位时向下扫描或借助位图Bitmap快速找到下一个非空档位。价格范围偏移时可以使用环形缓冲区Circular Buffer用取模运算替代重新分配。订单队列缓存友好的替代方案。std::list的每个节点独立分配在堆上遍历时指针跳跃严重。一个折中方案是使用内存池Memory Pool / Object Pool分配链表节点——预先分配一大块连续内存每次需要新节点时从池中取释放时归还。这样节点在物理上大致连续缓存局部性大幅提升同时保留了链表的迭代器稳定性。另一种方案是使用侵入式链表Intrusive List将链表的 prev/next 指针直接嵌入 Order 结构体中省去标准链表节点的额外内存分配开销。Boost.Intrusive 提供了现成的实现。哈希表从标准实现到扁平哈希。std::unordered_map使用链地址法每个桶是一个链表查找时需要先定位桶再遍历链表。扁平哈希表如absl::flat_hash_map使用开放寻址法和 SSE 指令加速探测所有键值对内联存储在连续数组中单次查找通常只需要一到两次缓存行加载。在订单簿场景下orderMap_是每次 Add 和 Cancel 都要访问的热路径Hot Path换用扁平哈希表带来的提升非常显著。内存分配消除动态分配。在低延迟系统中malloc/new的调用本身就是性能杀手——它们可能涉及系统调用、锁竞争和内存碎片。解决方案是使用自定义分配器Custom Allocator。为std::list和std::map提供基于内存池的分配器或者干脆用预分配的数组替代这些容器从根本上消除运行时的动态内存分配。在极致优化的系统中整个订单簿的内存在启动时一次性分配完毕运行时不再有任何堆操作。系统层面的优化。在代码之外还有许多系统层面的手段。CPU 核心绑定Core Pinning / CPU Affinity可以将撮合线程固定在一个物理核心上避免操作系统调度导致的上下文切换和缓存污染。内核旁路Kernel Bypass技术如 DPDK 或 Solarflare OpenOnload 可以绕过操作系统网络栈直接从网卡读取市场数据将网络延迟从微秒级降到纳秒级。NUMA 感知NUMA Awareness确保撮合线程使用的内存分配在同一 NUMA 节点上避免跨节点访问的额外延迟。关闭超线程Hyper-Threading可以避免同一物理核心上两个逻辑核心争夺执行资源。工业级实现中的额外考量真实的交易所订单簿比上面的实现复杂得多还需要处理许多额外的问题。订单类型。除了基本的限价单还需要支持市价单Market Order不指定价格直接吃对手盘、立即成交否则取消IOC, Immediate or Cancel能撮合多少撮合多少剩余部分直接取消、全部成交否则取消FOK, Fill or Kill要么全部成交要么全部取消、止损单Stop Order价格触及特定水平后触发、冰山单Iceberg Order只显示部分数量成交后自动补充显示量等。每种订单类型都需要在撮合逻辑中特殊处理。修改订单Amend / Modify。大多数交易所支持在不取消重发的情况下修改订单的价格或数量。减少数量通常保留时间优先级而修改价格或增加数量通常会失去原有的时间优先级等价于取消旧单再下新单。这个语义在实现时需要非常小心。多撮合规则。不是所有市场都用价格-时间优先。有些市场使用 Pro-Rata 撮合即同一价格档位内按照挂单量的比例分配成交量大单获得更多成交。还有些市场混合使用多种规则。持久化与恢复。交易所不允许丢失订单状态。所有操作通常会先写入预写日志Write-Ahead Log, WAL再执行内存操作。系统崩溃后可以通过重放日志恢复状态。这引入了 I/O 延迟的问题通常通过异步写入、批量刷盘或使用持久化内存Persistent Memory, PMem来缓解。公平性与确定性。监管要求交易所对所有参与者公平。撮合引擎必须是完全确定性的Deterministic——给定相同的输入序列必须产生完全相同的输出。这意味着不能使用非确定性的数据结构如某些哈希表的遍历顺序来影响撮合结果也不能依赖墙钟时间Wall Clock Time来决定优先级。并发模型。大多数高性能撮合引擎采用单线程模型处理核心撮合逻辑原因是加锁的开销在纳秒级别下是不可接受的。LMAX Disruptor 模式是业界的经典参考——使用无锁环形缓冲区Lock-Free Ring Buffer接收输入事件单个撮合线程顺序处理输出结果再通过另一个环形缓冲区分发。不同品种Symbol / Instrument可以分配到不同的撮合线程上实现品种级别的并行。常用英文术语对照以下是本文涉及的核心术语对照在面试和工作中经常出现订单簿Order Book、撮合引擎Matching Engine、限价单Limit Order、市价单Market Order、价格-时间优先Price-Time Priority / FIFO、买方/买入方Bid Side、卖方/卖出方Ask Side、价差Spread、价格档位Price Level、成交Fill、部分成交Partial Fill、挂单/休息订单Resting Order、吃单/主动订单Aggressive Order、最小价格变动Tick Size、迭代器稳定性Iterator Stability、缓存局部性Cache Locality、热路径Hot Path、延迟Latency、吞吐量Throughput以及核心绑定Core Pinning / CPU Affinity。