第28章：设计虚拟证券交易所

简介​

在本章中，我们将设计一个电子证券交易所。其基本功能是高效地撮合买卖双方。主要的证券交易所包括纽约证券交易所, 纳斯达克等。​

​

​

​

​

步骤1：理解问题并确定设计范围​

•

问：我们将交易哪些证券？股票、期权还是期货？​

•

I：为简化起见，仅限股票​

•

问：支持哪些订单类型——市价单、取消单、替换单？限价单、市价单、条件单又如何呢？​

•

I：我们需要支持委托和撤单功能。订单类型方面，我们只需考虑限价单。​

•

C：系统是否需要支持盘后交易？​

•

I：不，只是正常交易时段​

•

提问：您能介绍一下该交易所的基本功能吗？​

•

用户：客户可以下达或取消限价订单，并实时接收成交信息。他们应当能够实时查看订单簿。​

•

C：交易所的规模有多大？​

•

一：数以万计的用户同时交易，约100种交易品种。每日产生数十亿笔订单。我们还需支持合规性风险校验。​

•

C：会进行哪些风险校验？​

•

一：我们来做一些简单的风险校验——例如限制用户每日只能交易100万股苹果股票​

•

C：用户钱包的参与度如何？​

•

一：我们需要在客户下单前确保其账户中有足够的资金。用于待处理订单的资金需被冻结，直至订单最终确认。​

Non-functional requirements​

面试官提到的规模暗示我们需要设计一个中小型的交易所。同时，我们还需确保系统具备足够的灵活性，以便在未来支持更多的交易品种和用户。​

其他非功能性需求：​

•

可用性——至少99.99%。停机可能损害声誉​

•

容错性——需要具备容错能力及快速恢复机制，以降低生产事故的影响​

•

延迟——往返延迟应控制在毫秒级别，并重点关注99百分位。持续较高的99百分位延迟会导致少数用户的体验不佳。​

•

安全性——我们应当构建一套账户管理系统。为满足法律法规要求，需支持KYC以验证用户身份。同时，还应针对公共资源防范DDoS攻击。​

Back-of-the-envelope estimation​

•

100个符号，每天10亿笔订单​

•

正常交易时间为09:30至16:00（6.5小时）​

•

QPS = 10亿 / 6.5 / 3600 = 43000​

•

峰值QPS = 5×QPS = 215000​

•

市场开盘时的交易量会显著增加​

​

​

步骤2：提出高层次设计方案并获得认可​

Business Knowledge 101​

让我们讨论一些与交易所相关的基本概念。​

经纪商在交易所与终端用户之间起到中介作用——例如Robinhood、Fidelity等。​

机构客户通过专用交易软件进行大额交易，需要得到专门的处理。例如，在大额交易时采用订单拆分策略，以避免对市场造成影响。​

订单类型：​

•

限价单——以固定价格买入或卖出。可能无法立即成交，也可能仅部分成交。​

•

市价单——不指定价格，立即以当前市场价格成交。​

价格：​

•

买价——买家愿意买入某只股票的最高价格​

•

卖价——卖家愿意卖出某只股票的最低价格​

美国市场设有三档报价层级——L1、L2、L3。​

L1 市场数据包含最佳买卖价及其数量：​

​

​

L2 包含更多价格档位：​

​

​

L3显示各价位的挂单深度及对应挂单数量：​

​

​

蜡烛图显示了市场在特定时间区间内的开盘价、收盘价，以及最高价和最低价：​

​

​

FIX 是一种用于交换证券交易信息的协议，被大多数供应商所采用。以下是一个证券交易示例：​

​

代码块​

Plain Text

8=FIX.4.2 | 9=176 | 35=8 | 49=PHLX | 56=PERS | 52=20071123-05:30:00.000 | 11=ATOMNOCCC9990900 | 20=3 | 150=E | 39=E | 55=MSFT | 167=CS | 54=1 | 38=15 | 40=2 | 44=15 | 58=PHLX EQUITY TESTING | 59=0 | 47=C | 32=0 | 31=0 | 151=15 | 14=0 | 6=0 | 10=128 |​

​

High-level design​

​

​

交易流程：​

•

客户通过交易界面下单​

•

经纪商将订单发送至交易所​

•

订单通过客户端网关进入交易所，该网关负责验证、速率限制、身份认证等操作，随后订单被转发至订单管理模块。​

•

订单管理器根据风险经理设定的规则执行风险检查​

•

通过风险检查后，订单管理器会核实钱包中是否有足够的资金以完成该订单​

•

订单被发送至撮合引擎。当匹配成功时，撮合引擎会为买入和卖出各生成一笔成交（称为“填充”）。这两笔订单均经过排序，以确保其顺序具有确定性。​

•

成交结果返回给客户端​

市场数据流（M1-M3）：​

•

撮合引擎生成执行流，并将其发送至行情数据发布器​

•

行情数据发布者构建K线图并将其发送至数据服务​

•

行情数据存储于专用存储中，用于实时分析。经纪商通过数据服务获取及时的行情数据。​

报告者流程（R1-R2）：​

•

报告器从订单和成交中收集所有必要的报告字段，并将其写入数据库​

•

报告字段：client_id、price、quantity、order_type、filled_quantity、remaining_quantity​

交易流程处于关键路径上，而其他流程则不在其上，因此它们的时延要求各不相同。​

交易流程​

交易流程处于关键路径上，因此应高度优化以实现低延迟。​

撮合引擎是其核心，也称为交叉引擎。主要职责：​

•

为每个交易品种维护订单簿——即该品种的买卖订单列表。​

•

撮合买卖订单——一次撮合会产生两笔成交（填充），分别对应买方和卖方。此功能必须快速且准确​

•

将执行流作为市场数据进行分发​

•

匹配结果必须以确定性顺序生成。这是高可用性的基础​

接下来是序列器——它是使撮合引擎具备确定性的关键组件，通过为每笔入站订单和出站成交打上序列ID来实现。​

​

​

我们为入站订单和出站成交打上时间戳，主要有以下几个原因：​

•

时效性与公平性​

•

快速恢复/重放​

•

精确一次保证​

从概念上讲，我们可以将 Kafka 用作我们的序列器，因为它本质上就是一个双向的消息队列。不过，为了实现更低的延迟，我们决定自行实现。​

订单管理器负责管理订单状态，同时与撮合引擎交互——发送订单并接收成交。​

订单管理器的职责：​

•

发送订单以进行风险审核——例如，验证用户的交易量是否低于100万​

•

根据用户钱包检查订单，并验证是否有足够的资金执行该订单​

•

它将订单发送至排序器，再转发至撮合引擎。为降低带宽消耗，仅向撮合引擎传递必要的订单信息​

•

执行（成交）结果由排序器返回，随后通过客户端网关发送至各经纪商​

实现订单管理器的主要挑战在于状态转换的管理。事件溯源是一种可行的解决方案（已在深度剖析中讨论）。​

最后，客户端网关接收来自用户的订单，并将其发送至订单管理器。其职责如下：​

​

​

由于客户端网关处于关键路径上，因此应保持轻量级设计。​

针对不同的客户端，可以存在多个客户端网关。例如，一个托管机房引擎就是交易引擎服务器，由经纪商在交易所的数据中心租用：​

​

​

市场数据流​

市场数据发布者从撮合引擎接收成交信息，并基于该成交流构建订单簿与K线图。​

​

​

该数据会被发送至数据服务，由其负责向订阅者展示聚合后的数据：​

报告流程​

​

​

报告器并不处于关键路径上，但仍然是一个重要的组成部分。​

它负责交易历史记录、税务申报、合规报告、结算等业务。对于报表流程而言，延迟并非关键要求，准确性和合规性更为重要。​

API Design​

客户通过经纪商与证券交易所交互，以提交订单、查看成交记录、获取市场数据、下载历史数据用于分析等。​

我们在客户端网关与代理之间采用RESTful API进行通信。​

针对机构客户，我们使用专有协议以满足其低延迟需求。​

创建订单：​

​

代码块​

Plain Text

POST /v1/order​

​

参数：​

•

股票代码 - 股票代码。字符串​

•

side - 买入或卖出。String​

•

价格 - 限价单的价格。多头​

•

订单类型——限价单或市价单（在我们的设计中仅支持限价单）。字符串​

•

quantity - 订单数量。Long​

响应：​

•

id - 订单ID。Long​

•

创建时间——该订单的系统创建时间。长整型​

•

filledQuantity - 已成功成交的数量。Long​

•

remainingQuantity - 仍未成交的数量。Long​

•

status - 新建/已取消/已成交。String​

•

其余属性与输入参数相同​

获取执行记录：​

​

代码块​

Plain Text

GET /execution?symbol={:symbol}&orderId={:orderId}&startTime={:startTime}&endTime={:endTime}​

​

参数：​

•

股票代码 - 股票代码。字符串​

•

orderId - 订单ID。可选。字符串​

•

startTime - 查询开始时间，以Epoch时间戳表示[11]。长整型​

•

endTime - 查询结束时间，以Epoch时间戳表示。Long​

响应：​

•

executions - 包含该范围内每次执行记录的数组（详见下方属性）。数组​

•

id - 执行记录ID。Long​

•

orderId - 订单的ID。Long​

•

股票代码 - 股票代码。字符串​

•

side - 买入或卖出。String​

•

price - 执行价格。Long​

•

orderType - 限价单或市价单。String​

•

quantity - 已成交数量。Long​

获取订单簿：​

​

代码块​

Plain Text

GET /marketdata/orderBook/L2?symbol={:symbol}&depth={:depth}​

​

参数：​

•

股票代码 - 股票代码。字符串​

•

深度 - 每侧的委托簿深度。整数​

响应：​

•

买盘 - 包含价格和数量的数组。数组​

•

卖盘 - 包含价格和数量的数组。数组​

获取蜡烛图：​

​

代码块​

Plain Text

GET /marketdata/candles?symbol={:symbol}&resolution={:resolution}&startTime={:startTime}&endTime={:endTime}​

​

参数：​

•

股票代码 - 股票代码。字符串​

•

resolution - K线图的时间窗口长度，单位为秒。长整型​

•

startTime - 时间窗口的起始时间，单位为 epoch 时间戳。长整型​

•

endTime - 时间窗口的结束时间，单位为 epoch 时间戳。长整型​

响应：​

•

蜡烛图——一个包含每根K线数据的数组（属性如下所示）。数组​

•

open - 每根K线的开盘价。双精度浮点数​

•

close - 每根K线的收盘价。双精度浮点数​

•

最高价——每根K线的最高价格。双倍​

•

低——每根K线的低价。双倍​

Data models​

我们的交易所中主要有三种类型的数据：​

•

产品、订单、执行​

•

订单簿​

•

蜡烛图​

产品、订单、执行​

产品用于描述交易品种的属性——产品类型、交易代码、界面显示符号等。​

这些数据更新频率不高，主要用于在用户界面中进行渲染。​

订单表示一笔买入或卖出的指令。成交则是匹配后的结果。​

以下是数据模型：​

​

​

我们在三个业务流程中都会遇到订单和成交：​

•

在关键路径上，它们以内存方式处理，以实现高性能。它们会被存储，并从序列器中恢复。​

•

报告人员将订单和成交记录写入数据库，用于报表场景​

•

成交信息会被转发至市场数据系统，以重建订单簿和K线图​

订单簿​

订单簿是按价格水平排列的某金融工具的买卖委托单列表。​

针对该模型，一种高效的数据结构需满足：​

•

常数时间的查询效率——即在某一价格水平或两个价格水平之间获取成交量​

•

快速添加/执行/取消操作​

•

查询最佳买卖价​

•

遍历价格层级​

订单簿执行示例：​

​

​

在完成这笔大单后，随着买卖价差扩大，价格随之上涨。​

伪代码中的订单簿实现示例：​

​

代码块​

Plain Text

​

为了实现更高效的方案，我们可以使用双向链表而非普通列表：​

•

新增订单的时间复杂度为O(1)，因为我们是在链表尾部添加一条新订单。​

•

匹配订单的时间复杂度为O(1)，因为我们是从链表头部删除一条订单。​

•

取消订单意味着从订单簿中删除该订单。我们采用orderMap以实现 O(1) 的查找和 O(1) 的删除操作（由于Order在链表中拥有指向前一个元素的引用）。​

​

​

该数据结构也用于市场数据服务中，以重建订单簿。​

蜡烛图​

K线数据是在行情数据服务中，基于对某一时间区间内订单的处理计算得出的：​

​

代码块​

Plain Text

​

一些避免占用过多内存的优化措施：​

•

使用预先分配的环形缓冲区来存放数据块，以减少内存分配次数​

•

限制内存中数据块的数量，并将剩余部分持久化到磁盘​

我们将使用内存列式数据库（如 KDB）进行实时分析。收盘后，数据将被持久化到历史数据库中。​

​

​

步骤3：设计深度剖析​

关于现代交易所，有一点值得特别注意：与大多数其他软件不同，它们通常将所有业务都运行在一台超大型服务器上。​

让我们深入探讨细节。​

Performance​

对于一个交易所而言，所有分位数的总体延迟都至关重要。​

我们如何降低延迟？​

•

减少关键路径上的任务数量​

•

通过减少网络/磁盘使用量和/或缩短任务执行时间，从而缩短每项任务的耗时​

为实现第一个目标，我们已将关键路径上的所有非必要职责剥离，甚至连日志记录也被移除，以达到最优的延迟性能。​

如果按照最初的设计，存在几个性能瓶颈——服务间的网络延迟以及序列器的磁盘使用量。​

按照这种设计，我们能够实现数十毫秒的端到端延迟。但我们希望将其降至数十微秒。​

因此，我们将所有组件部署在一台服务器上，并通过内存映射文件（mmap）作为事件存储来实现进程间通信：​

​

​

另一种优化方法是使用应用循环（即通过while循环执行关键任务），并将该循环固定在同一个CPU上，以避免上下文切换：​

​

​

使用应用循环的另一个副作用是，不会出现锁竞争——即多个线程争夺同一资源的情况。​

接下来我们来探讨 mmap 的工作原理——它是一种 UNIX 系统调用，用于将磁盘上的文件映射到应用程序的内存空间。​

这是一个名为“system-design-notes/01. Scaling at main · liquidslr/system-design-notes”的GitHub仓库页面。上下文。 /dev/shm​

Event sourcing​

事件溯源在数字钱包章节中有深入讨论。有关所有细节，请参阅该章节。​

简而言之，我们不是存储当前状态，而是存储不可变的状态变更记录：​

​

​

•

左侧——传统模式​

•

右侧——事件源模式​

到目前为止，我们的设计方案如下：​

​

​

•

外部域名通过FIX协议与我们的客户端网关进行交互​

•

订单管理器接收到新的订单事件，对其进行校验并将其加入内部状态。随后，该订单被发送至撮合核心​

•

If order is matched, the OrderFilledEvent is generated and sent over mmap​

•

其他组件订阅事件存储，并执行各自的部分处理工作​

一项额外的优化——所有组件都持有订单管理器的副本，并将其封装为库，以避免在管理订单时进行额外的调用​

在本设计中，序列器不再是一个事件存储，而是一个单一的写入者，负责对事件进行排序后再将其转发至事件存储：​

​

​

High availability​

我们致力于实现99.99%的可用性——每天的停机时间仅为8.64秒。​

为此，我们必须识别交易所架构中的单点故障：​

•

部署关键服务（如撮合引擎）的备用实例，并使其处于待命状态​

•

积极主动地实现故障检测与故障转移至备用实例​

诸如客户端网关之类的无状态服务可通过增加更多服务器轻松实现水平扩展。​

对于有状态组件，我们能够处理入站事件，但若非主节点，则无法发布出站事件：​

​

​

为检测主副本是否宕机，我们可以发送心跳以确认其处于非正常状态。​

这种机制仅在单台服务器的范围内有效。若需将其扩展，我们可以将整台服务器配置为热/温副本，并在发生故障时实现故障转移。​

为了在各副本之间复制事件存储，我们可以使用可靠的UDP以实现更快速的通信。​

Fault tolerance​

如果连热备实例也宕机了怎么办？虽然这种情况发生的概率很低，但我们仍应做好应对准备。​

大型科技公司通过将核心数据复制到多个城市的数据中心来应对这一问题，以降低诸如自然灾害等风险。​

需要考虑的问题：​

•

如果主实例宕机，我们如何以及何时切换到备用实例？​

•

我们如何在各备用实例中选出主节点？​

•

所需的恢复时间（RTO——恢复时间目标）是多少？​

•

需要恢复哪些功能？我们的系统能否在降级状态下运行？​

如何应对这些问题：​

•

系统可能因缺陷而宕机（影响主节点和副本节点），我们可以通过混沌工程发现此类边缘场景及灾难性后果​

•

不过，最初我们可以手动执行故障转移，直到我们充分了解系统的故障模式​

•

可采用领导者选举机制（如Raft）来确定在主节点宕机时由哪个副本担任领导者​

不同服务器间复制工作原理示例：​

​

​

选主任期示例：​

​

​

有关 Raft 的工作原理的详细信息，请参阅此处​

最后，我们还需考虑容错能力——在情况变得严重之前，我们能承受多大的数据丢失？这将决定我们备份数据的频率。​

对于证券交易所而言，数据丢失是不可接受的，因此我们必须频繁备份数据，并依赖Raft协议的复制机制来降低数据丢失的概率。​

Matching algorithms​

顺便简单介绍一下匹配机制的工作原理（伪代码）：​

​

代码块​

Plain Text

Context handleOrder(OrderBook orderBook, OrderEvent orderEvent) {​

if (orderEvent.getSequenceId() != nextSequence) {​

return Error(OUT_OF_ORDER, nextSequence);​

}​

​

if (!validateOrder(symbol, price, quantity)) {​

return ERROR(INVALID_ORDER, orderEvent);​

}​

​

Order order = createOrderFromEvent(orderEvent);​

switch (msgType):​

​

该撮合算法采用先进先出（FIFO）策略，用于确定在某一价格水平上应匹配哪些订单。​

Determinism​

我们采用的定序器技术确保了功能确定性。​

事件实际发生的时间并不重要：​

​

​

延迟的确定性是我们必须持续关注的指标。我们可以根据监控中的99分位或99.99分位延迟来计算它。​

可能导致延迟突增的因素包括例如Java中的垃圾回收器事件。​

Market data publisher optimizations​

市场数据发布者从撮合引擎接收匹配结果，并据此重建订单簿和K线图。​

我们仅保留部分蜡烛图数据，因为内存并非无限。客户端可自行选择所需信息的粒度。更细粒度的信息可能需要更高的费用：​

​

​

环形缓冲区（又称循环缓冲区）是一种固定大小的队列，其头部与尾部相连。空间预先分配，以避免动态内存分配。该数据结构还实现了无锁设计。​

另一种优化环形缓冲区的技术是填充，它确保序列号永远不会与任何其他数据位于同一缓存行中。​

Distribution fairness of market data and multicast​

我们必须确保所有订阅者同时收到数据，因为如果某个订阅者先于其他订阅者收到数据，就会获得关键的市场洞察，并可能借此操纵市场。​

为此，我们可以在向订阅者发布数据时使用基于可靠UDP的组播技术。​

数据可以通过互联网以三种方式传输：​

•

单播——一个源，一个目的​

•

广播——一个源向整个子网发送​

•

组播——一个源向不同子网中的多台主机发送数据​

理论上，通过使用组播，所有订阅者应该能够同时接收到数据。​

然而，UDP 是不可靠的，数据可能无法送达所有用户。不过，可以通过重传机制加以改进。​

Colocation​

交易所为经纪商提供将其服务器与交易所部署在同一数据中心的能力。​

这能大幅降低延迟，可被视为一项VIP服务。​

Network Security​

DDoS对交易所构成挑战，因为存在一些面向互联网的服务。以下是我们的应对方案：​

•

将公共服务和数据与私有服务隔离，从而避免DDoS攻击影响最重要的客户​

•

使用缓存层存储更新频率较低的数据​

•

强化URL抵御DDoS攻击，例如优先使用https://my.website.com/data/recent与https://my.website.com/data?from=123&to=456相比，因为前者更易于缓存​

•

需要有效的白名单/黑名单机制。​

•

速率限制可用于缓解DDoS攻击​

​

​

步骤4：总结​

其他有趣的笔记：​

•

并非所有交易所都依赖将所有数据集中部署在一台大型服务器上，但仍有部分交易所如此​

•

现代交易所更多地依赖云基础设施，并借助自动做市商（AMM）来避免维护订单簿​