开发常用业务逻辑算法-撮合交易

撮合系统设计

01

概述

随着信息技术的日新月异和金融业务的快速发展,金融交易领域对于核心技术的求也在不断增强,国内外金融交易模式已经从传统的人工叫价的方式变成了由高度电子化交易系统撮合订单的方式。传统的金融交易主要发生在有型金融市场中,金融交易的买卖双方通过叫价进行价格协商等方式最终达成一致,从而形成一笔交易,同时按照交易订单到指定的交割地点进行实物交割的交易方式。由于交易的整个过程主要依靠人来执行,传统的金融交易缺点主要有:效率低速度慢、交易时间限制大、交易空间限制大、交易成本非常髙、容易有内幕交易、交易扩展性差、交易容易出错、资金安全性差等一系列的缺点。

通过了解熟悉电子交易市场中订单的下单流程、交易所的订单处理机制、以及从订单下达到交易所形成交易价格的过程,深入了解交易所撮合订单的方式与机制,从而总结出交易撮合系统的需求,对系统进行分析建模与设计系统架构。根据真实市场机制采用多层分布式体系和内存撮合的数据存储模式,构建出了一个较为完善的交易撮合系统。

02

系统总体设计

2.1

系统设计

交易撮合系统中包括以下几个核心模块:

  • 交易层:最终用户可以通过终端进行撮合委托、委托查询、出入金等操作
  • 接口层:用户的商品查询、下单等请求派发给业务层,并把产生的行情反馈给交易层。
  • 业务层:交易系统中的核心部分,用于接收订单并根据业务逻辑实现订 单撮合同时生成交易记录,随后给予用户交易结果反馈。
  • 数据层:用来存储商品信息、交易信息、资金信息、用户信息进行持久化,同时,缓存会对行情就行存储,减轻数据库的压力。

此外,根据不同类型的金融交易展品将撮合模块划分为若干业务分区,每个分区独立进行撮合,彼此不受影响。对于单个业务分区而言,撮合系统整体架构设计如图所示,本章的总体设计围绕撮合引擎层以及撮合引擎与网关层、数据库层的交互方式的总体设计。

2.2

撮合算法设计

撮合引擎核心业务模块就是撮合交易算法撮合交易算法的任务一方面是完成对客户所下订单进行公平合理的排列和撮合功能,也要保证撮合算法的公平性、高效性以及扩展性等。由于不同金融交易系统的撮合业务各有不同,因此本节对通用的撮合交易算法进行概括性描述。

订单队列

撮合交易的重要组成部分就是买卖订单,通过对买卖订单进行撮合最后形成交易记录。所以对无法立刻完成撮合的订单,需要有买入队列和卖出队列保存订单。队列按照“价格优先、同价格下时间优先”的原则。买入队列按照委托价格从低到高的顺序,卖出队列则按照委托价格从低到高的顺序排列,如图

撮合有如下四种情况:

  • 新进的是买入市价委托: 如果卖出队列中有市价委托,则对它们进行撮合; 而如果卖队列中的市价委托全部撮合后,该买入委托还有可交易数量,则和卖出队列中的限价委托撮合。如果卖出队列中没有市价委托,则直接和卖出队列中的限价委托进行撮合。如果卖出队列为空,则只是将该买入委托插入买入队列。
  • 新进的是买入限价委托: 如果卖出队列中有市委托,则先对它们进行撮合; 如果市价委托全部撮合完毕后该买入委托还存在可交易数量且价格大于等于卖出队列中的卖一最低价格,则继续跟限价委托撮合。如果卖出队列中只有限价委托且该买入委托的价格大于等于卖出队列中卖一的最低价格,则 对它们进行撮合,否则只能将该买入委托按照撮合 原则插入到买入队列。如果卖出队列为空,则直接 将该买入委托按照撮合原则插入到买入队列。
  • 新进的是卖出市价委托: 如果买入队列有市价委托,则进行撮合; 如果撮合后该卖出队列还有未成 交量,则和买入队列中限价委托撮合。如果买入队列中仅有限价委托,则和限价委托撮合。如果买入队列为空,则将该卖委托插入到卖出队列中。
  • 新进的是卖出限价委托: 如果买入队列中有市价委托,则先对它们进行撮合; 如果市价委托全部撮合完毕后该卖出委托还存在可交易数量且价格小于等于买入队列中的买一最高价格,则继续跟限价委托撮合。如果买入队列中只有限价委托且该卖出委托的价格小于等于买入队列中买一的最高价格,则进行撮合,否则只能将该卖出委托按照撮合原则插入到卖出队列。如果买入队列为空,则直接将该卖出委托按照撮合原则插入到卖出队列。

撮合顺序

撮合引擎接收到新的买入订单,则会到卖出队列的头部查找是否存在符合价格规则的卖出订单,如果存在卖出价格小于或等于买入价格的订单,则从队列中取出此订单并撮合成一笔交易;如果卖出队列为空或队列头部不满足价格关系,则将买入订单插入买入队列中,由于买入队列是按照价格与时间先后进行排序,所以新插入的订单会经过一次排序插入到买入队列。

相同的,当撮合引擎接收到新的卖出订单,则会到买入队列的头部査找是否存在符合价格规则的买入订单,如果存在买入价格大于或等于卖出价格的订单,则从订单队列中取出此订单并撮合成一笔交易;如果买入队列为空或队列头部不满足价格关系,则将卖出订单插入到卖出队列中,由于卖出队列也是按照价格与时间先后进行排序的所以新插入的订单会经过一次排序插入到卖出队。

结合买卖订单情况,撮合算法流程如图所示。从图所示的撮合顺序可知,买卖队列的有序性是保证撮合顺序的确定性的基础,并且撮合过程中每笔订单都可以撮合出当前最优交易。

2.3

基于内存撮合

当前的数据库撮合技术的性能低下的原因在于过多与数据库交互,使得I/O很多,系统整体处理速度同时受数据库事务逻辑约束。

本文釆用内存撮合技术,通过最大程度去除与数据库的交互过程,将整个撮和逻辑放在内存中进行(如图所示)。因此比数据库撮合技术少了许多I/O交互,在性能上可以大幅提升撮合速度;例是内存撮合的弊端就是由于内存的易失性服务器出现故障停机时,所有的交易数据将会丢失,系统的可靠性以及一致性都相应降低。因此本文在提高内存撮合技术可靠性的方面采用了多机热备份及分布式一致性技术作为补充,从而获得内存撮合技术的高性能以及数据库撮合技术的数据持久性。

2.4

灾备的多机设计

由于内存撮合技术在撮合引攀出现异常时的可靠性和一致性非常差,而金融交场系统因为其业务特性,对服务小断以及数据丢失的容忍度非常低,提高容错性,一般多采取的是多机热条份技术。采用多机热备份技术,将一组撮合引擎部署成互为备份的撮合引擎集群,并且在同一时间内只有一台撮合引擎提供服务。

当-其中运行这的一台撮六引擎出现故障无法继续正常工作 ,撮合引擎集群会迅速检测到这个故障,并选举出一个备份撮合引擎接管故障撮合引擎的任务从而保证整个撮合系统的正常运行多机热备份技术的本质就足针对服务器临时故障所做的一种备份技术,本文迎过采用多机热备份技术,来避免长 间的撮合服务中断,保证撮合系统长期、可靠的服务。如图所示,通过将多台撮合引擎进行热格份,从而保证在撮合引擎出现故障时,会在可以接受的时间内完成主机和备机之间的切换,由备份机提供无缝连续服务。

通过釆用多机热备份技术,降低了单一内存撮合引擎故障时系统不可用的问题,但仍旧无法提供100%的可用性,因为当出现大规模服务器集群故障时,仍旧存在服务不可用的可能性,但在实际生产环境中,三台互为备份的服务器就可以提供较高的可以用于生产环境的可靠性。

2.5

状态机复制

由于多机热备份技术引入了多台互为热备份的撮合引擎,根据撮合系统设计以及撮合逻辑要求,需要保证服务器之间的数据一致,这就需要保证多服务器之间一致性,这也是该系统的难点之一。

在设计中提出一种内存状态机复制方案,即将撮合算法视作一个确定性状态机,将其复制多份并部署到撮合系统中的多台撮合引擎中。每个撮合引擎副本从相同的初始状态开始运行,当撮合系统收到网关发来的订单时,系统中的每个撮合引擎都会撮合这个订单,并依次产生交易记录,同时更新确定性撮合算法状态机的独立状态。通过这样的方式,当撮合系统正常运转时,每个撮合引擎副本都会具有相同的结果状态;当撮合系统出现故障或异常时,撮合引擎就会出现状态的不一致情况,换句话说一旦撮合系统的结果或状态出现了不一致的情况就可以断定系统出现了异常

关键技术点

系统为了实现这样的内存状态机复制撮合系统,将撮合系统划分为以下组成关键技术点

  1. 将确定性撮合算法状态机服务部署到多个独立撮合引擎
  2. 接收网关订单,并作为确定性撮合算法状态机的输入
  3. 根据撮合算法需求,选择一种订单排序方式
  4. 每个撮合引擎对按照排序方式排序过的订单进行撮合
  5. 将确定性撮合算法状态机输出的交易记录作为给用户或数据库的响应
  6. 监控撮合引擎副本的状态或输出的差别

具体实现

为实现基于内存状态机复制的撮合系统,系统主要通过以下方案实现状态机复制的关键技术点:

  1. 采用原子多播解决撮合引擎订单的可靠多播与全局有序性
  2. 采用基于无锁订单队列的流水线撮合技术提供快速的订单撮合
  3. 采用异步一致性持久化技术实现与数据库的交互
  4. 采用失效备援技术对撮合引擎集群进行状态监控并保证系统的容错能
  5. 采用进度追赶技术解决将故障撮合引擎的恢复或新撮合引擎的加入

数据库优化

撮合系统中对数据库的查询操作是很重要的一环,查询过程的性能对是否能够拥有高效的撮合效率有很大的影响力。为此对数据库进行查询优化必不可少。每个查询都会有许多可供选择的执行策略和操作算法,查询优化就是选择一个高效执行的查询处理策略。查询的执行开销主要包括磁盘存取块数(I/O代价),处理机时间(CPU代价),查询的内存开销。其中I/O代价是最主要的。为此可以充分利用索引方法,减少表扫描的I/O代价,尽量避免表搜索的发生。例如可以在订单表中对orderID或是itemID建立索引提高查询效率。利用好索引可以极大地提高数据库的检索性能,但是不能在经常修改变动列建立索引,这只会增加系统搜索代价。而且由于撮合系统每秒钟都需要处理大量的数据,因此为了提高系统效率,可以尽量建立单索引提高查找效率。

2.6

系统架构

系统硬件体系架构

典型的高可靠高性能撮合模型硬件架构如图1.6所示,系统由n台客户端、N台网关、X个产品集群(每个集群由2至3台撮合引擎组成,负责响应产品订单的处理)、一个交易记录数据库和可选的监视系统组成。其中客户端连接到相应网关,网关负责接收客户端提交的订单,并根据订单相关的金融产品类别,转发到相对应的产品集群。产品集群中所有撮合引擎均接收网关发送的订单,根据撮合业务规则,将其撮合并回馈消息给网关和客户端,同时将撮合生成的交易记录持久化到交易记录数据库中。

通过对产品集群进行扩充,增加撮合引擎数量,可以增强产品集群的可靠性,将不同金融产品转发到不同的撮合产品集群中可以实现多产品高效并行撮合。

系统软件体系架构

如图所示,高可靠高性能撮合模型主要由表示层、转发层、业务层和数据层组成。其核心部分业务层主要由撮合引擎集群组成,每个撮合引擎采用原子多播将订单定序后进行撮合处理,并结合无锁订单队列实现高效流水线撮合,最后结果写入本地日志。整个业务流程由消息传递总线将消息反馈给转发层。转发层则根据产品转发规则将订单转发给相应撮合引擎集群;而撮合引擎将本地日志中的交易记录读取到异步持久化代理进程中,并进而与数据层的异步持久化写入进程通信,并最终持久化到数据库中。本地日志增强了撮合系统数据的可靠性,在出现故障后,数据仍就可以从本地日志中恢复;而界步的持久化机制则提高了数据的持久化吞吐率。

撮合系统架构

为了使系统可扩展易维护,撮合引擎由原子多播订单定序模块、撮合处理器模块、交易记录日志模块和内存数据组成,每个模块根据功能业务划分。其中各部分主要有以下功能:

  • 交易订单接收线程:负责从网关接收订单,并完成原子多播定序流程。
  • 交易订单发送线程:将定序完成的订单发送给相关撮合业务线程。
  • 交易信息发送线程:将订单交易状态反馈给网关。
  • 外围业务逻辑线程:进行撮合数据的准备处理,更新内存订单数据。
  • 撮合业务逻辑线程: 运用撮合算法对委托接收队列和撮合队列中的委托进行撮合,并及时更新产品信息、客户信息、委托信息和行情信息,产生交易记录存储到交易记录中。。
  • 交易行情发布线程: 从行情信息中获得行情并发布给网关。
  • 同步日志写线程:将订单撮合产生的交易记录同步持久化到本地日志文件。
  • 异步持久化代理进程:异步将日志文件中的数据读取并持久化到数据库。
  • 订单信息:存储订单的相关价格、数量、用户、限制、类型和状态等信息交
  • 易行情信息:撮合交易过程中的交易行情信息。

网关设计

撮合系统主要为使用者提供订单的下单和查询服务、交易行情的实时反馈功能以及系统状态的监控查看服务。因此系统需要实现预留的接口主要包括:下单接口、订单查询接口、行情查询接口、系统控制接口和运行状态查询接口等。

03

总结

通过了解现行电子商品交易市场的交易制度和交易流程,熟悉电子商品交易市场撮合订单的方式与机制,并将其转换为详细的流程框图,为撮合系统提供设计基础。从交易机制中抽象出撮合系统的需求,将系统分为多个功能模块进行详细架构和设计。同时为了构建一个高性能、高可靠性和高扩展性的交易撮合系统,本文提出了基于多层分布式体系,利用J2EE技术进行设计和实现。采用最新的内存撮合技术,利用多级存储模式提高系统运行效率。随着电子商品交易市场的日益扩大以及股民对系统性能要求越来越高,如何构建一个高性能的撮合交易系统是电子商品交易市场需要进一步研究。本文通过构建一个基于多层分布式体系的电子商品交易交易撮合系统来模拟仿真电子商品交易市场,借此充分了解电子商品交易市场的交易运作模式,为进一步深入研究市场提供基础。

转载之:微信公众号:技术方舟

阅读剩余
THE END