万字长文详解低时延股票交易系统的设计

今天我们来聊聊股票交易所的具体设计、性能优化以及事件溯源在其中的应用。

下图显示的是一个总体架构。

步骤 1

客户通过券商的网页或移动端 app 下单。

步骤 2

券商将订单发送至交易所。

步骤 3

交易所客户端网关执行验证、速率限制、身份验证、规范化等操作，并将订单发送给订单管理模块。

步骤 4-5

订单管理模块根据风险管理模块设定的规则执行风险检查（Risk Check）。

步骤 6

通过风险检查后，订单管理模块会验证钱包中是否有足够的资金来支付订单。

步骤 7 - 9

订单被发送到匹配引擎（Matching Engine）。如果找到匹配的订单，匹配引擎会返回成交回报。订单和成交回报都需要先在定序器中排序，以保证匹配的确定性。

步骤 10 - 14

成交回报会经过多个模块传回客户端。

步骤 M1 - M3（市场数据流）

市场数据（包括 k 线图和订单簿）被发送到数据服务进行整合。券商查询数据服务以获取市场数据。

步骤 R1 - R2（报告流程）

订单报告模块收集所有必要的报告字段（如客户编号、价格、数量、订单类型、已成交数量、剩余数量），并将数据写入数据库。

请注意，步骤 1 至 14 位于关键路径（交易流）上，而市场数据流和报告流则不在关键路径上。它们有不同的延迟要求。

01

数据模型

交易所的数据主要有三种：

• 股票产品、订单和执行结果

• 订单簿

• k 线图

这里需要注意的是，交易关键路径上没有数据库。为了实现低时延的要求，订单匹配和其他关键功能都依赖于精心设计的数据结构。

股票产品、订单、执行结果

• 股票产品描述交易标的的属性，如产品类型、股票名称、用户界面显示名称、结算货币、手数、价格点差等。

• 订单代表买入或卖出的输入指令。限价单可以设置固定的价格，而市价单则按现行价格成交。

• 执行结果或成交回报代表订单匹配的结果。并非每个订单都能找到匹配。

下图是数据模型的逻辑图。

值得一提的是，匹配引擎的输出可能包含两个成交回报（买入和卖出）。它们代表了匹配订单的对手双方（买入和卖出）。为确保数据完整性，我们应将这两个执行单保存到数据库中。

订单簿

订单簿是按价格水平排列的买卖订单列表。订单簿的高效数据结构必须满足以下要求：

• 恒定的查询时间。操作包括：获取某个价格水平的订单或几个价格水平之间的成交量。

• 快速添加/取消/执行订单，时间复杂度最好为 O(1)。操作包括：下新订单、取消订单和匹配订单。

• 快速更新。操作：替换订单。

• 查询最佳出价/卖价。

• 遍历各个价格水平。

下图所示的是 L3 订单簿。

在上面的示例中，有一个买入 2700 股苹果公司股票的大额市价单。该买单匹配了最佳卖价队列中的所有市价单和 100.11 价格队列中的第一个卖单（以浅色显示）。完成这个大订单后，买卖价差扩大，价格上涨一级（现在的最佳卖价是 100.11）。

以下代码片段显示了订单簿的执行情况。

class PriceLevel{    private Price limitPrice;    private long totalVolume;    private List<Order> orders;}class Book<Side> {    private Side side;    private Map<Price, PriceLevel> limitMap;}class OrderBook {    private Book<Buy> buyBook;    private Book<Sell> sellBook;    private PriceLevel bestBid;    private PriceLevel bestOffer;    private Map<OrderID, PriceLevel> orderMap;}

代码是否满足前面所述的所有设计要求？例如，在添加/取消限价单时，时间复杂度是否为 O(1)？答案是否定的，因为我们在这里使用的是普通列表。要想获得更高效的订单簿，可以将这一行的数据结构（Listorders）改为双向链表，这样删除类型的操作（取消和匹配）也是 O(1)。

k 线图

k 线图表示一定时期内的股票价格。下图是一个典型的 k 线图。k 线图显示市场在某一时间区间内的开盘价、收盘价、最高价和最低价。常见的时间间隔有一分钟、五分钟、一小时、一天、一周和一个月。

我们使用一个 Candlestick 类和一个 CandlestickChart 类对此进行建模。当烛台的时间间隔过去后，我们会为下一个时间间隔实例化一个新的 Candlestick 类，并将其添加到 CandleStickChart 实例的链表中。

class Candlestick {    private long openPrice;    private long closePrice;    private long highPrice;    private long lowPrice;    private long volume;    private long timestamp;    private int interval;}class CandlestickChart {    private LinkedList<Candlestick> sticks;}

在 k 线图中跟踪大量股票的价格历史会消耗大量内存。如何优化它呢？这里有两种方法：

• 使用预先分配的 Ring Buffer 来保存记录，以减少新对象分配的数量。

• 限制内存中的数据量，将其余数据持久化到磁盘。

02

订单管理

从狭义上讲，订单管理模块跟踪订单的生命周期。从广义上讲，它可以是一个订单管理系统，可以执行订单、管理订单生命周期，并连接到各种中后台系统（处理确认、客户报告、结算、清算等）。不同的市场参与者使用订单管理模块的目的不一样。例如，券商使用订单管理作为交易服务的一部分，可能包含大订单分割功能。对于交易引擎来说，订单管理模块用于对市场数据做出相应决策。对于交易所而言，订单管理模块主要用于寻找流动性，为订单簿创造更多深度。

订单管理应快速、高效、准确。事件溯源（Event Sourcing）和 CQRS 是订单管理设计的完美选择。

我们先详细介绍一下事件溯源。事件源的核心是事件存储（Event Store），它是数据的 Golden Source。我们可以为领域设计好事件的模型，订单管理通过处理事件来更新每个订单的状态。内存中不可能保存所有订单，只有打开的订单才会保存在内存中，关闭的订单会存储在磁盘上并按需加载。下面是一个简单的示例：

class MyOrderManager {  private Map<OrderId, Order> openOrders;  private PersistedMap<OrderId, Order> closedOrders;  private ExecutionReportHandler executionReportHandler;
  public void onNewOrderEvent(NewOrderEvent newOrderEvent) {      // create a new entry in openOrders, send to the matching engine  }
  public void onNewOrderAckedEvent(NewOrderAckedEvent newOrderAckedEvent) {      // update openOrders, the order state transitioned from NEW to NEW_ACKED      // invoke executionReportHandler  }
  public void onOrderFilledEvent(OrderFilledEvent orderFilledEvent) {      // update openOrders, the order state transitioned from NEW_ACKED to FILLED; if it is fully filled, it can be moved to closedOrders      // invoke executionReportHandler  }}

这里有几个有趣的问题：

• 单线程还是多线程。订单状态的更新必须是确定性的，因此主工作线程必须是单线程。即使使用事件溯源，我们也需要将同一用户的消息分派给同一线程。

• 系统重放（Replay）。所有事件都会存入事件存储。如果订单管理模块因故崩溃，我们可以通过重放事件存储中的所有事件来恢复其状态。

• 系统状态快照。由于从头开始重放所有事件以重建状态需要不少时间，我们可以每隔几分钟进行一次快照，并且只从最后一次持久化的快照开始重放。类似的设计在 Redis 中也有，我们可以选择 RDB + AOF 混合的方式来持久化内存数据。

• 效率。新订单中有很多字段属性，但没有必要将所有字段都发送给匹配引擎。为了减少数据传输量，我们只发送必要的属性。

• 钩子（Hook）ExecutionReportHandler 只是钩子的一个例子。我们还可以使用其他钩子对订单状态变化做出决策。

市场数据发布模块从匹配算法中我们可以看出，L3 订单簿数据能让我们更好地了解市场。我们可以从 Google Finance 获得免费的单日 k 线图数据，但要获得更详细的 L2 和 L3 订单簿数据则价格不菲。许多对冲基金通过交易所实时 API 自行记录数据，以构建自己的 k 线图和其他图表，用于技术分析。

市场数据发布模块 (MDP) 从匹配引擎接收匹配结果，并在此基础上重建订单簿和蜡烛图。然后，它将数据发布给订阅者。

订单簿的重建与匹配引擎中提到的伪代码类似。MDP 是一种多层次的服务。例如，零售客户默认只能查看 5 个级别的 L2 数据，需要额外付费才能获得 10 个级别的数据。MDP 的内存不可能永远扩展，因此我们需要为 k 线图设定一个上限。下图是 MDP 的简要设计图。

这种设计采用了 Ring Buffer。它是一个固定大小的队列，头部与尾部相连。一个生产者持续生产数据，一个或多个消费者从中提取数据。Ring Buffer 的空间是预先分配的，因此无需创建或删除对象。数据结构也是无锁的。

03

性能优化

我们从吞吐量（Throughput）和时延（Latency）两个方面来看性能的优化。

从高层次来看，有三种方法可以提高吞吐量：

• 异步处理

• 使用缓存层

• 使用多线程

下面的公式解释了这些方法可以提高吞吐量的原因：

Throughput = nThreads x (1/taskExecutionTimeBySingleThread) 

我们可以增加线程数或缩短任务执行时间来提高吞吐量。但是我们不能使用无限多的线程。如果服务器只有 4 个 CPU 内核，分配 20 个线程会导致线程间大量的上下文切换。

除了吞吐量，时延也很重要。这与平均时延无关。我们要衡量交易执行的稳定性，第 99 百分位数时延是更好的监控指标，如下面公式所示：

Latency = ∑executionTimeAlongCriticalPath

因此减少延迟有两种方法：

1. 减少关键路径上的任务数量。

2. 缩短每个任务的执行时间：

• 减少 I/O，包括网络跳数和磁盘使用

• 缩短每个任务在进程内的执行时间

对于第一点，我们可以从高层设计中看到，关键路径包括以下部分：网关 - 定序 - 订单管理器 - 匹配引擎。关键路径一旦确定，任何新的组件在添加到关键路径之前都需要经过仔细审核。

对于第二点，我们应仔细评估网络跳转所花费的时间。如果端到端时延要求达到微秒级，我们就应该考虑放弃网络传输。请参阅 Jeff Dean 多年前写的 "Latency Numbers Every Programmer Should Know"。一旦涉及磁盘或网络，我们就无法将整体延迟降至设计目标。

这里我们有两种选择：

1. 将所有组件放在同一进程或同一服务器上，从而减少网络跳数。如果我们将所有组件放在同一台服务器上，它们就可以通过 MMap 进行通信。

2. 利用组播（Multicast）进行跨服务器通信。组播本质上是一种交换机级的扇出，可有效实现局域网内一对多的通信。这里数据的拷贝是零成本的。

如何减少每个任务的执行时间呢？交易领域需要最大限度提高单个 CPU 效率。这里使用一种新的设计范式：使用多进程而非多线程，并将线程固定在一个 CPU 上。我们以订单管理模块为例。Application Loop 是用来执行任务的核心线程，各个事件在其中排队顺序执行。这样订单的状态更新具有很大的确定性。

这确实使编码变得更加复杂。开发需要考虑每项任务需要花费多少时间，以及是否有可能导致应用程序循环线程停滞太久，因为这有可能阻塞后续任务。不过，这样做的好处还是很大的：

• 无需上下文切换。CPU 1 完全分配给订单管理的 Application Loop 线程。

• 不需要锁，因为只有一个线程负责写操作。

下图显示了低时延服务器的设计和所有组件：

04

事件溯源

我们在前面的章节中提到了事件源。这个概念并不难理解。

在传统应用程序中，状态被持久保存在数据库中。当出现问题时，很难追溯问题的源头，因为我们并没有保存改变状态的事件。

事件溯源的核心是导致状态变化的事件，它们是不可变的。下图比较了两种编程范式的区别。我们可以通过顺序重放所有事件来恢复状态。

事件溯源的概念不难理解，困难在于具体实施。我们如何设计不同领域的事件？如何执行编码准则？我们需要设计一个框架来处理大部分底层繁重的工作，应用层只负责处理业务逻辑。下图显示了一个设计示例。事件溯源的框架帮我们处理了消息发送和收取，编码和解编码等。这看起来非常像 Kafka 中的 Pub-Sub 模型。事实上，如果没有延迟要求，也可以使用 Kafka。

在图中，外部域可以使用不同的协议与交易域进行通信。

• 以 FIX 为例。网关将 FIX 转换为 "FIX over SBE"，以实现快速、紧凑的编码，并通过事件存储客户端以预定义格式发送事件。

• 然后，订单管理模块（嵌入在匹配引擎中）从事件存储中提取 NewOrderEvent，对其进行验证，并将其发送到状态机，用于维护订单状态转换。之后，订单被发送到匹配核心。

• 如果订单匹配成功，就会生成 OrderFilledEvent 并发送到事件存储区。

• 其他组件（如 MDP 和 Reporter）会订阅事件存储并相应地处理这些事件。

由于订单状态对多个交易组件都很重要，因此嵌入组件的订单管理模块可能不止一个。虽然每个组件都自行维护订单状态，但在事件溯源的设计中，这些状态应该是相同的，并且可以顺序重放。

下面我们来看看事件溯源设计中的定序模块。

每个事件存储区只有一个序列器。在分布式环境中，有多个进程/线程同时写入通常是不推荐的。在繁忙的系统中，大量时间将浪费在试图获得锁的过程中。因此，定序模块是一个单线程的写入模块，负责对事件进行排序，并将其持久化到事件存储区中。定序模块只做非常简单的事情，而且速度要超快；否则，它会成为系统的瓶颈。下图显示了在 MMap 环境中定序模块的可能设计。

定序模块从每个组件本地的 Ring Buffer 中提取数据，在数据上加盖一个唯一的序列号，并将其写入事件存储区。