首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >撮合引擎开发:数据结构设计

撮合引擎开发:数据结构设计

作者头像
Keegan小钢
发布2019-11-20 15:05:01
1.7K0
发布2019-11-20 15:05:01
举报
文章被收录于专栏:Keegan小钢Keegan小钢

交易委托账本

交易委托账本(OrderBook)是整个撮合引擎里最核心也是最复杂的数据结构,每个交易对都需要维护一份交易委托账本,账本里保存着指定交易对所有待撮合的委托单。每份账本都有两个队列,一个卖单队列和一个买单队列,两个队列都需要按照价格优先、时间优先的原则进行排序。

所谓价格优先、时间优先,即是说:卖单队列的委托单是按价格由低到高排序,买单队列则相反,按价格由高到低排序;相同价格的委托单,则是按下单时间的先后来排序。

如上图,每个小方格表示一个委托单,标 H 的是排在头部的委托单,N 则是与 H 同价格但下单时间上排在 H 后面的委托单,S 则是下一档位价格的第一个委托单。可以从图中明显看出,横向上,委托单是按时间排序的,竖向上,又是按价格排序的。

撮合的时候,都是先取出 H 委托单与新委托单进行匹配。如果新委托单是买单,则获取卖单队列的 H 单出来匹配;如果新委托单是卖单,则获取买单队列的 H 单。如果 H 单全部匹配成交了,那标识为 N 的委托单就变成了新的 H 单。如果第一排的全部委托单都匹配完了,那就 S 单会变成新的 H 单。

交易委托账本可支持一些操作方法,包括初始化、增加买卖委托单、移除买卖委托单、获取头部委托单等。交易委托账本的类图大概如下:

其中,getHeadpopHead 方法的区别是:get 只读头部委托单但不会移除它,而 pop 会将头部委托单从队列中移除。

订单队列

买单队列和卖单队列可以设计为使用统一的订单队列类型,两者只有价格排序方向不同,那订单队列就可以用一个属性来表示排序方向。队列里的所有订单可以采用二维数组或二维链表来保存,考虑到主要操作是插入和删除,用链表比用数组效率更高。如果想让操作效率更高,那就需要使用更复杂的数据结构了,比如再结合跳表。目前版本为了简单,采用简单的二维链表即可。

使用二维链表的话,那链表中的每个元素保存的就是横向上按时间排序的订单链表,这些订单链表又组成了竖向上按价格排序的链表。

另外,还可以保存一个 Map,将价格作为 Key,将同价格的订单链表作为 Value,这样就能加快同价格订单的查询。

订单队列可支持的操作方法也很简单,包括初始化、新增订单、移除订单、获取头部订单等。其类图大概如下:

sortBy 指定价格排序的方向,parentList 保存整个二维链表,第一维以价格排序,第二维以时间排序,elementMap 则是 Key 为价格、Value 为第二维订单链表的键值对。

委托单

委托单则是撮合引擎里最基本的数据结构了,其数据主要是从上游服务传输过来的,其类图大概如下:

action 声明对委托单要进行哪种操作,我们只需支持两种操作:下单(create)撤单(cancel)symbol 指定该委托单所属的交易对,orderId 是该委托单的唯一标识,side 指明是买入(buy)还是卖出(sell)type **表示交易类型,即限价交易(limit)市价交易(market)等,我们的 MVP 版本只支持限价交易。amount 是购买数量,price** 是购买价格,timestamp 则是订单时间。

toJson()fromJson() 方法是为了支持订单数据传输时的序列化和反序列化。

成交记录

撮合成交的委托单就会生成对应的成交记录,成交记录需要发布到 MQ 给下游服务消费。成交记录的数据结构如下图:

maker 指挂单,是本来挂在交易委托账本里的订单,而 taker 则是吃单,是指吃掉 maker 的订单。makerIdtakerId 就是挂单和吃单的订单 ID。takerSide 就是吃单的买卖方向,我们在行情软件里看到的成交记录会有不同颜色,就是由这个 takerSide 决定的。amount 就是成交数量,price 指成交价格,timestamp 是成交时间。

Redis缓存

我们需要用 Redis 缓存委托单数据和撮合中的交易对数据,主要有两个作用,一是可以对请求做去重处理,二是程序重启后可以恢复数据。

由于网络中断或延迟,或其他异常情况,上游服务有可能会重复发送相同请求给到撮合引擎,因此,程序是需要做去重处理的,有了数据缓存就可以解决去重问题了。另外,由于我们采用的是内存撮合,撮合时的数据都是直接保存在程序内存里的,一旦程序退出了,那所有数据也都消失了,重启后就需要从其他地方重新加载数据,采用Redis缓存就可以很快速地缓存数据和加载数据。

开启一个交易对引擎时需要将交易对缓存,关闭时则从缓存中删除,保证缓存的都是运行中的交易对,当重启时,就可以重新启动这些交易对的撮合引擎了。需要缓存的交易对数据包括两个:symbolprice,即标识和价格。关于价格,每次产生新的成交记录时,价格也需要同步更新,因此价格的更新会非常频繁。而标识基本无需更新,因此两者最好分开缓存。

所有交易对的 symbol 可以统一缓存到一个 set 里。我们可以将 key 值设置为 matching:symbols,用 Redis 的 saddsrem 命令将不同的 symbol 缓存到该 key 值里或从 key 中删除。而 price 则可以保存为 string 类型,为不同交易对的价格设置不同的 key,key 值可以设置为 matching:price:{symbol},{symbol} 为具体交易对的 symbol 值。

每个委托单也需要缓存和更新,为了能够从缓存中最快地读取和更新委托单数据,最好为每个委托单都设置一个单独的 key,key 值可以设置为 matching:order:{symbol}:{orderId}:{action},而 value 值建议设置为 hash 类型,因为 hash 类型特别适合存储结构化的对象。

交易对和委托单数据都缓存了,就能够解决去重问题和程序重启后重新启动各交易对的撮合引擎了,但其实还有一个问题,撮合引擎里的交易委托账本如何恢复?该问题先留给大伙去思考,后续章节我再来讲解我的方案。

小结

撮合引擎里涉及到的数据结构其实并不多,最复杂的也只有交易委托账本,其设计还会直接关系到撮合的速度。Redis 缓存的设计也有些学问在里面,设计得不好也一样会影响整体的撮合性能。本小节完成了数据结构的设计,下一小节我们就开始深入到代码实现。

最后,请抽时间研究下遗留的思考题:撮合引擎里的交易委托账本如何恢复?

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-11-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Keegan小钢 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 交易委托账本
  • 订单队列
  • 委托单
  • 成交记录
  • Redis缓存
  • 小结
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档