大家好！ 我的名字是 Sergey Kostanbaev，在交易所我正在开发交易系统的核心。
当好莱坞电影展示纽约证券交易所时，它总是这样的：人山人海，每个人都在喊着什么，挥舞着文件，正在发生完全的混乱。 这种情况在莫斯科交易所从未发生过，因为交易从一开始就以电子方式进行，并且基于两个主要平台 - Spectra（外汇市场）和 ASTS（外汇、股票和货币市场）。 今天我想谈谈 ASTS 交易和清算系统架构的演变，以及各种解决方案和发现。 故事很长，所以我不得不把它分成两部分。
我们是世界上为数不多的交易所有类别资产并提供全方位交易服务的交易所之一。 例如，去年我们的债券交易量在全球排名第二，在所有证券交易所中排名第25位，在公开交易所中排名第13位。
对于专业交易参与者来说，响应时间、时间分布稳定性（抖动）和整个综合体的可靠性等参数至关重要。 目前我们每天处理数千万笔交易。 系统内核处理每笔交易需要几十微秒的时间。 当然，除夕夜的移动运营商或者搜索引擎本身的工作量比我们高，但就工作量而言，加上上述特点，在我看来，很少有人能与我们相比。 同时，对我们来说重要的是系统一秒不慢，工作绝对稳定，所有用户都是平等的。
一点历史
1994年，澳大利亚ASTS系统在莫斯科银行间货币交易所（MICEX）上线，俄罗斯电子交易的历史从此开始。 1998 年，交易所架构进行了现代化改造，引入了互联网交易。 从那时起，所有系统和子系统中新解决方案的实施和架构变化的速度不断加快。
那些年，交换系统运行在高端硬件上——超可靠的 HP Superdome 9000 服务器（基于），其中所有内容绝对都是重复的：输入/输出子系统、网络、RAM（事实上，有一个 RAM 的 RAID 阵列）、处理器（可热插拔）。 可以在不停止机器的情况下更改任何服务器组件。 我们依赖这些设备并认为它们实际上是安全的。 操作系统是类Unix的HP UX系统。
但从2010年左右开始，出现了一种现象，称为高频交易（HFT），或者高频交易——简单地说，就是证券交易所机器人。 短短2,5年，我们服务器的负载增加了140倍。
以旧的建筑和设备根本无法承受这样的荷载。 有必要以某种方式适应。
开始
对交换系统的请求可以分为两种类型：
- 交易。 如果您想购买美元、股票或其他东西，您可以向交易系统发送一笔交易并收到有关成功的响应。
- 信息请求。 如果您想了解当前价格，请查看订单簿或指数，然后发送信息请求。
概括地说，系统的核心可以分为三个层次：
- 客户级别，经纪人和客户在该级别工作。 它们都与访问服务器交互。
- 网关服务器是本地处理所有信息请求的缓存服务器。 您想知道俄罗斯联邦储蓄银行股票目前的交易价格吗？ 该请求发送至访问服务器。
- 但如果您想购买股票，则请求会发送到中央服务器（交易引擎）。 每种类型的市场都有一个这样的服务器，它们发挥着至关重要的作用，我们正是为它们创建了这个系统。
交易系统的核心是一个巧妙的内存数据库，其中所有交易都是交易所交易。 基础是用 C 编写的，唯一的外部依赖项是 libc 库，并且根本没有动态内存分配。 为了减少处理时间，系统从一组静态数组和静态数据重定位开始：首先，将当天的所有数据加载到内存中，不再执行进一步的磁盘访问，所有工作仅在内存中进行。 当系统启动时，所有参考数据都已经排序，因此搜索工作非常高效，并且在运行时花费的时间很少。 所有表都是用动态数据结构的侵入式列表和树制成的，因此它们在运行时不需要内存分配。
让我们简单回顾一下我们的交易和清算系统的发展历史。
第一个版本的交易和清算系统架构建立在所谓的Unix交互之上：使用共享内存、信号量和队列，每个进程由单个线程组成。 这种方法在 1990 世纪 XNUMX 年代初很流行。
该系统的第一个版本包含两层网关和交易系统的中央服务器。 工作流程是这样的：
- 客户端发送请求，该请求到达网关。 它检查格式的有效性（但不检查数据本身）并拒绝不正确的交易。
- 如果已发送信息请求，则在本地执行； 如果我们谈论的是交易，那么它会被重定向到中央服务器。
- 然后交易引擎处理交易，修改本地存储器，并向交易发送响应以及交易本身以使用单独的复制引擎进行复制。
- 网关接收中心节点的响应并将其转发给客户端。
- 一段时间后，网关通过复制机制接收到事务，这次在本地执行，改变其数据结构，以便下一个信息请求显示最新的数据。
事实上，它描述了一种复制模型，其中网关完全复制了交易系统中执行的操作。 单独的复制通道确保事务在多个访问节点上以相同的顺序执行。
由于代码是单线程的，因此使用具有进程分叉的经典方案来为许多客户端提供服务。 然而，分叉整个数据库的成本非常高，因此使用了轻量级服务进程，从 TCP 会话中收集数据包并将其传输到一个队列（SystemV 消息队列）。 网关和交易引擎仅与该队列一起工作，从那里获取交易以执行。 无法再向它发送响应，因为不清楚哪个服务进程应该读取它。 所以我们采取了一个技巧：每个分叉进程为自己创建一个响应队列，当请求进入传入队列时，响应队列的标签立即添加到其中。
不断地将大量数据从一个队列复制到另一个队列会产生问题，对于信息请求尤其常见。 因此，我们使用了另一个技巧：除了响应队列之外，每个进程还创建共享内存（SystemV Shared Memory）。 包裹本身被放置在其中，队列中只存储一个标签，以便人们可以找到原始包裹。 这有助于将数据存储在处理器缓存中。
SystemV IPC 包括用于查看队列、内存和信号量对象状态的实用程序。 我们积极地利用它来了解系统在特定时刻发生了什么、数据包在哪里累积、什么被阻止等。
首次升级
首先，我们摆脱了单进程网关。 它的显着缺点是它只能处理一个复制事务或来自客户端的一个信息请求。 并且随着负载的增加，网关将需要更长的时间来处理请求，并且将无法处理复制流。 此外，如果客户端发送了一笔交易，那么您只需检查其有效性并进一步转发即可。 因此，我们用多个可以并行运行的组件替换了单个 Gateway 进程：使用 RW 锁定在共享内存区域上彼此独立运行的多线程信息和事务进程。 同时我们引入了调度和复制流程。
高频交易的影响
上述版本的架构一直存在到 2010 年。 与此同时，我们对HP Superdome服务器的性能不再满意。 此外，PA-RISC 架构实际上已经死亡；供应商没有提供任何重大更新。 因此，我们开始从 HP UX/PA RISC 转向 Linux/x86。 转变始于接入服务器的调整。
为什么我们必须再次改变架构？ 事实上，高频交易显着改变了系统核心的负载状况。
假设我们有一笔小额交易导致了重大的价格变化 - 有人购买了 XNUMX 亿美元。 几毫秒后，所有市场参与者都会注意到这一点并开始做出修正。 当然，请求会排成一个巨大的队列，系统需要很长时间才能清除。
在这 50 毫秒的间隔下，平均速度约为每秒 16 个事务。 如果我们将窗口减少到 20 毫秒，那么平均速度为每秒 90 万笔交易，峰值时为 200 万笔交易。 换句话说，负载不是恒定的，会突然爆发。 并且请求队列必须始终得到快速处理。
但为什么还要排队呢？ 因此，在我们的示例中，许多用户注意到价格变化并相应地发送了交易。 它们来到网关，网关将它们序列化，设置一定的顺序并将它们发送到网络。 路由器将数据包打乱并转发。 谁的包裹先到达，这笔交易就“赢了”。 结果，交易所客户开始注意到，如果同一笔交易从多个网关发送，那么快速处理的机会就会增加。 很快，交易机器人开始向 Gateway 发出请求，大量交易随之出现。
新一轮的进化
经过大量的测试和研究，我们转向了实时操作系统内核。 为此，我们选择了 RedHat Enterprise MRG Linux，其中 MRG 代表消息实时网格。 实时补丁的优点是它们优化了系统以尽可能快的执行：所有进程都排列在 FIFO 队列中，核心可以隔离，不会弹出，所有事务都按严格的顺序处理。
红色 - 在常规内核中使用队列，绿色 - 在实时内核中工作。
但在常规服务器上实现低延迟并不那么容易：
- SMI 模式在 x86 架构中是处理重要外设的基础，干扰很大。 各种硬件事件的处理以及组件和设备的管理都是由固件在所谓的透明SMI模式下执行的，在这种模式下操作系统根本看不到固件在做什么。 通常，所有主要供应商都为固件服务器提供特殊扩展，以减少 SMI 处理量。
- 不应该对处理器频率进行动态控制，这会导致额外的停机时间。
- 当刷新文件系统日志时，内核中会发生某些进程，从而导致不可预测的延迟。
- 您需要注意诸如 CPU 亲和性、中断亲和性、NUMA 之类的事情。
我必须说，为实时处理设置 Linux 硬件和内核的主题值得单独写一篇文章。 我们花了很多时间进行实验和研究，才取得了很好的结果。
当从 PA-RISC 服务器迁移到 x86 时，我们实际上不需要对系统代码进行太多更改，我们只需对其进行调整和重新配置即可。 同时，我们修复了多个错误。 例如，PA RISC 是 Big endian 系统，而 x86 是 Little endian 系统这一事实的后果很快就浮出水面：例如，数据读取不正确。 更棘手的错误是 PA RISC 使用 (）内存访问，而 x86 可以重新排序读取操作，因此在一个平台上绝对有效的代码在另一个平台上会被破坏。
切换到 x86 后，性能提高了近三倍，平均事务处理时间降低至 60 μs。
现在让我们仔细看看系统架构发生了哪些关键变化。
热备史诗
当切换到商品服务器时，我们意识到它们不太可靠。 因此，在创建新的架构时，我们先验地假设了一个或多个节点发生故障的可能性。 因此，需要一个能够非常快速地切换到备用机的热备系统。
此外，还有其他要求：
- 在任何情况下，您都不应丢失已处理的交易。
- 该系统必须对我们的基础设施绝对透明。
- 客户端不应看到连接断开。
- 预订不应造成明显的延误，因为这是交换的关键因素。
在创建双机热备系统时，我们没有考虑双重故障的场景（例如一台服务器网络停止工作，主服务器死机）； 没有考虑软件中出现错误的可能性，因为这些错误是在测试过程中发现的； 并且没有考虑硬件的错误操作。
结果，我们得出了以下方案：
- 主服务器直接与网关服务器交互。
- 主服务器上收到的所有交易都会通过单独的通道立即复制到备份服务器。 如果出现任何问题，仲裁者（州长）将协调切换。
- 主服务器处理每笔交易并等待备份服务器的确认。 为了将延迟降至最低，我们避免等待事务在备份服务器上完成。 由于事务在网络上传输所需的时间与执行时间相当，因此不会增加额外的延迟。
- 我们只能查看主备服务器上一个事务的处理状态，当前事务的处理状态未知。 由于我们仍然使用单线程进程，等待备份的响应会减慢整个处理流程，因此我们做出了合理的妥协：我们检查了上一个事务的结果。
该计划的工作原理如下。
假设主服务器停止响应，但网关继续通信。 备份服务器发生超时，它联系州长，州长为其分配主服务器的角色，并且所有网关都切换到新的主服务器。
如果主服务器重新上线，它也会触发内部超时，因为在一段时间内没有从网关对服务器进行调用。 然后他也向总督求助，并将他排除在该计划之外。 因此，交易所仅使用一台服务器工作，直到交易期结束。 由于服务器出现故障的概率相当低，因此该方案被认为是可以接受的；它不包含复杂的逻辑，并且易于测试。
要继续进行下去。
来源： habr.com