基于排隊(duì)論的交易系統(tǒng)時(shí)延分析

黃寅飛 王 泊 白 碩

(上海證券交易所技術(shù)開發(fā)部 上海 200120)

?

基于排隊(duì)論的交易系統(tǒng)時(shí)延分析

黃寅飛 王 泊 白 碩

(上海證券交易所技術(shù)開發(fā)部 上海 200120)

低延遲是證券交易系統(tǒng)從小型機(jī)遷移到PC服務(wù)器過程中的主要挑戰(zhàn)，為此需要進(jìn)行時(shí)延度量和分析。首先設(shè)計(jì)實(shí)現(xiàn)基于Redis和Python的時(shí)延數(shù)據(jù)采集監(jiān)控框架。其次提出隊(duì)列級(jí)聯(lián)方法，分析分布式系統(tǒng)時(shí)延構(gòu)成。最后通過參數(shù)試驗(yàn)和數(shù)據(jù)分析，找到令吞吐量和時(shí)延最優(yōu)的配置方法，并分析解決可擴(kuò)展性和毛刺問題。將分布式系統(tǒng)建模為級(jí)聯(lián)隊(duì)列，在此基礎(chǔ)上通過量化分析、性能調(diào)優(yōu)和流控保護(hù)等手段，令時(shí)延指標(biāo)顯著提升。所提出的隊(duì)列級(jí)聯(lián)方法可為企業(yè)級(jí)關(guān)鍵業(yè)務(wù)實(shí)時(shí)系統(tǒng)的設(shè)計(jì)和調(diào)優(yōu)提供參考。

時(shí)延度量 監(jiān)控框架 低延遲 證券交易系統(tǒng)

0 引 言

輕便高效交易系統(tǒng)LTP(Light Trading Platform)是國家科技支撐計(jì)劃《證券核心交易系統(tǒng)研發(fā)》課題(2012BAH13F04)的交付成果，于2015年4月通過國家驗(yàn)收，達(dá)到吞吐量10萬筆/秒、交易時(shí)延小于1毫秒的技術(shù)指標(biāo)。LTP基于PC服務(wù)器集群搭建，選用Linux操作系統(tǒng)(RHEL 6.3，64位)。LTP引入內(nèi)存復(fù)制技術(shù)，在保證高吞吐和高可用性的基礎(chǔ)上，時(shí)延指標(biāo)相比現(xiàn)有系統(tǒng)[1]提升兩個(gè)數(shù)量級(jí)。

本文建立交易時(shí)延模型，設(shè)計(jì)監(jiān)控架構(gòu)采集時(shí)延數(shù)據(jù)，在排隊(duì)論基礎(chǔ)上提出隊(duì)列級(jí)聯(lián)方法，以指導(dǎo)吞吐量和時(shí)延指標(biāo)調(diào)優(yōu)。

1 技術(shù)架構(gòu)

證券處理的全業(yè)務(wù)流程如圖1所示。LTP關(guān)注的是業(yè)務(wù)流程中由交易所負(fù)責(zé)的部分，重點(diǎn)解決實(shí)時(shí)撮合處理的時(shí)延和吞吐量問題。LTP架構(gòu)如圖2所示，主要包括通信網(wǎng)關(guān)CS和交易主機(jī)TC兩塊內(nèi)容。LTP集成基于TCP協(xié)議的ZeroMQ消息中間件[2]作為通信層，以實(shí)現(xiàn)多對(duì)多的廣播訂閱通信方式。集群主機(jī)按照產(chǎn)品集合SET進(jìn)行分區(qū)，以支持水平擴(kuò)展。

圖1 證券處理業(yè)務(wù)流程示意圖

圖2中，CS上robot 進(jìn)程負(fù)責(zé)模擬報(bào)單。TC上router 進(jìn)程負(fù)責(zé)消息路由，matcher進(jìn)程負(fù)責(zé)撮合處理，main為主撮合線程，csq為定序線程。從業(yè)務(wù)邏輯出發(fā)，也稱CS為報(bào)盤機(jī)，TC為撮合器。TC構(gòu)成集群，基于Paxos算法[3]實(shí)現(xiàn)主備機(jī)訂單序號(hào)同步。

圖2 LTP進(jìn)程通信數(shù)據(jù)流圖

LTP監(jiān)控架構(gòu)與交易架構(gòu)通過libmoni監(jiān)控探針庫以低耦合方式相連接，見圖3所示。每臺(tái)TC和CS上均安裝有Redis數(shù)據(jù)庫[4]，用以存放實(shí)時(shí)監(jiān)控?cái)?shù)據(jù)。監(jiān)控主機(jī)上開發(fā)有PyShow監(jiān)控工具包，通過 Redis客戶端離線抓取各臺(tái)主機(jī)的監(jiān)控?cái)?shù)據(jù)。使用NumPy庫[5]在內(nèi)存中整合形成矩陣以利高速處理，使用Pickle庫持久化以便數(shù)據(jù)重用，使用MatplotLib庫進(jìn)行可視化展示。

圖3 LTP監(jiān)控架構(gòu)圖

2 時(shí)延建模

2.1 時(shí)延定義

交易時(shí)延指的是交易訂單從發(fā)出到收到響應(yīng)之間的時(shí)間間隔。參照Cinobber公司白皮書[6]，定義端到端、門到門和撮合器三個(gè)時(shí)延指標(biāo)，見圖4所示。交易所關(guān)注的交易時(shí)延指的是門到門時(shí)延，即消息從CS到TC再回到CS的處理時(shí)延[7]。

圖4 時(shí)延指標(biāo)定義

為進(jìn)一步分析交易時(shí)延構(gòu)成，設(shè)置N個(gè)采樣點(diǎn)t0,t1,…,tN-1，定義分段時(shí)延：

Ti,j=tj-ti

(1)

特別地，定義：

Ti=ti-ti-1

(2)

交易時(shí)延構(gòu)成如下：

T0,N-1=T1+T2+…+TN-1

(3)

2.2 時(shí)延模型

LTP系統(tǒng)中訂單生命周期如圖5所示。設(shè)置8個(gè)采樣點(diǎn)，其中T1、T7為CS到TC間網(wǎng)絡(luò)時(shí)延，T2、T6為router到matcher 進(jìn)程間通信時(shí)延，T3為主備機(jī)定序時(shí)延(包含兩跳網(wǎng)絡(luò)時(shí)延)，T4為撮合器中csq 到main線程間排隊(duì)時(shí)延，T5為撮合業(yè)務(wù)處理時(shí)延。LTP交易時(shí)延為：

T0,7=T1+T2+…+T7

(4)

因t0、t7采樣點(diǎn)位于CS主機(jī)，t1到t6采樣點(diǎn)位于TC主機(jī)，不同主機(jī)上的時(shí)鐘難以做到微秒級(jí)同步[8]。T1、T7兩段時(shí)延無法直接計(jì)算，而需采用間接計(jì)算公式，如下：

(5)

圖5 LTP訂單生命周期圖

2.3 隊(duì)列級(jí)聯(lián)方法

單個(gè)撮合器對(duì)應(yīng)單服務(wù)窗口的排隊(duì)系統(tǒng)，訂單依次進(jìn)入撮合器的過程為一個(gè)排隊(duì)過程。訂單進(jìn)入撮合器的事件流為泊松流，具備平穩(wěn)性、無后效性和普通性[9]。

多報(bào)單機(jī)、多撮合器對(duì)應(yīng)多事件流、多服務(wù)窗口的排隊(duì)系統(tǒng)。設(shè)報(bào)單機(jī)總數(shù)為m，主撮合器總數(shù)(即SET數(shù))為n。每個(gè)報(bào)單機(jī)向n個(gè)撮合器發(fā)送訂單，每個(gè)撮合器接收來自m個(gè)報(bào)單機(jī)的訂單。每個(gè)報(bào)單機(jī)承擔(dān)的事件流強(qiáng)度為λ×n，每個(gè)撮合器承擔(dān)的事件流強(qiáng)度為λ×m。

針對(duì)系統(tǒng)中包含多個(gè)隊(duì)列的情況，提出隊(duì)列級(jí)聯(lián)方法。將分布式系統(tǒng)視作若干隊(duì)列組的串聯(lián)，其中每個(gè)隊(duì)列組又可由多個(gè)并聯(lián)的隊(duì)列組成。為保證平穩(wěn)服務(wù)，可設(shè)定系統(tǒng)負(fù)荷水平ρ(通常在0.5到0.6之間)。根據(jù)隊(duì)列級(jí)聯(lián)關(guān)系，計(jì)算所有隊(duì)列的服務(wù)能力并取最小值，即為整個(gè)系統(tǒng)能穩(wěn)定支持的最大事件流強(qiáng)度。

以CS、TC多對(duì)多關(guān)聯(lián)構(gòu)成的系統(tǒng)為例，包含兩個(gè)排隊(duì)點(diǎn)：CS發(fā)送隊(duì)列、TC撮合隊(duì)列。設(shè)報(bào)單機(jī)服務(wù)能力為μ0，撮合器服務(wù)能力為μ1。有如下公式：

(6)

(7)

綜合考慮報(bào)盤機(jī)和撮合器的服務(wù)能力，取事件流強(qiáng)度為min(λ0,λ1)可獲得吞吐量和時(shí)延的最優(yōu)配置。

2.4 試驗(yàn)設(shè)計(jì)

交易時(shí)延由通信時(shí)延、排隊(duì)時(shí)延和處理時(shí)延三部分構(gòu)成，其中排隊(duì)時(shí)延受吞吐量影響最大，且二者關(guān)系并非線性關(guān)系。當(dāng)吞吐量接近服務(wù)處理能力時(shí)，排隊(duì)時(shí)延將指數(shù)增長。

針對(duì)排隊(duì)模型中的事件流和服務(wù)窗調(diào)整參數(shù)，試驗(yàn)不同的模型組合，找到系統(tǒng)中的不變量和隨事件流變化的變量。根據(jù)試驗(yàn)結(jié)果，進(jìn)一步細(xì)化模型，給出令時(shí)延最優(yōu)和吞吐量可擴(kuò)展的配置策略。

3 試驗(yàn)與分析

3.1 環(huán)境準(zhǔn)備

試驗(yàn)環(huán)境為千兆以太網(wǎng)，三臺(tái)CS為HP DL380p(PC服務(wù)器，32核，128 GB內(nèi)存)，四臺(tái)TC為IBM x3850(PC服務(wù)器，64核，128 GB內(nèi)存)。設(shè)置8個(gè)SET，采取一主兩備配置，每臺(tái)TC上部署2個(gè)主SET、4個(gè)備SET。實(shí)際試驗(yàn)可選取主機(jī)和SET的子集，如表1所示。

表1 環(huán)境配置表

為接近真實(shí)場景，使用工具生成由100萬賬戶和100支產(chǎn)品構(gòu)成的一億條模擬持倉。使用工具圍繞40支產(chǎn)品和1萬賬戶生成480萬條模擬訂單，每臺(tái)CS對(duì)每個(gè)SET準(zhǔn)備20萬條訂單。訂單價(jià)格和數(shù)量字段隨機(jī)生成。訂單消息長度為154字節(jié)。CS采取勻速報(bào)單方式，每隔固定間隔向TC發(fā)送1筆訂單。

3.2 模型試驗(yàn)

分別使用1對(duì)1、3對(duì)1、1對(duì)4和3對(duì)4配置，試驗(yàn)系統(tǒng)的服務(wù)能力，以及不同事件流強(qiáng)度下的性能表現(xiàn)，結(jié)果見表2至表5所示。表中λ用報(bào)單間隔推算，μ用處理時(shí)延推算。吞吐量取單個(gè)CS到所有SET的吞吐量總和。

表2 模型參數(shù)：1對(duì)1事件流

表3 模型參數(shù)：3對(duì)1事件流

表4 模型參數(shù)：1對(duì)4事件流

表5 模型參數(shù)：3對(duì)4事件流

通常起作用的是TC撮合隊(duì)列，對(duì)應(yīng)于撮合器服務(wù)能力μ1，排隊(duì)時(shí)延取T4，處理時(shí)延取T5。1對(duì)4場景比較特殊，起作用的是CS發(fā)送隊(duì)列，因此表4中取報(bào)盤機(jī)服務(wù)能力μ0，排隊(duì)時(shí)延改取T1。μ0通過臨界點(diǎn)時(shí)的事件流強(qiáng)度推算。

3對(duì)8環(huán)境采用增加進(jìn)程的辦法增加服務(wù)窗口。在單臺(tái)主機(jī)上部署多個(gè)撮合進(jìn)程，可充分利用多核計(jì)算優(yōu)勢(shì)，在基礎(chǔ)時(shí)延少量升高的同時(shí)令系統(tǒng)整體吞吐量翻倍，見表6所示。

表6 模型參數(shù)：3對(duì)8事件流

3.3 數(shù)據(jù)分析

3.3.1 時(shí)延折線圖

綜合不同配置下的λ和排隊(duì)時(shí)延間變化關(guān)系繪制折線圖，見圖6所示。從變化曲線可以看到，一開始時(shí)延隨著λ增大而緩慢增加，當(dāng)λ達(dá)到特定拐點(diǎn)后時(shí)延會(huì)迅速上升，最終在λ趨近于臨界點(diǎn)μ時(shí)趨向無窮大。其中1v4曲線臨界點(diǎn)為μ0/4， 其他曲線臨界點(diǎn)為μ1。

圖6 時(shí)延折線圖

可以看到，1v1曲線、3v1曲線拐點(diǎn)出現(xiàn)在ρ=0.9左右位置，且拐點(diǎn)處曲線變化陡峭；而3v4、3v8曲線拐點(diǎn)出現(xiàn)在ρ=0.7左右位置，且曲線變化較為平滑。隨著服務(wù)窗口增加，一方面基礎(chǔ)時(shí)延會(huì)增加，另一方面時(shí)延拐點(diǎn)會(huì)前移。

3.3.2 可擴(kuò)展性分析

代碼不變，隊(duì)列μ值固定，從而決定了在該點(diǎn)的λ-時(shí)延曲線。在此基礎(chǔ)上可通過增加事件流和增加服務(wù)窗口來提升系統(tǒng)的整體吞吐量。

對(duì)比表4和表5數(shù)據(jù)可以看到，擴(kuò)展CS主機(jī)個(gè)數(shù)可用來增加事件流強(qiáng)度，以突破CS發(fā)送隊(duì)列瓶頸的束縛。1對(duì)4場景下，吞吐量受限于μ0參數(shù)，為 44 894筆/秒(用例3D，ρ=0.58)。3對(duì)4場景下，單CS吞吐量為24 823筆/秒(用例4C，ρ=0.55)，整體吞吐量最大達(dá)到74 469筆/秒。吞吐量提升65.9%，代價(jià)是時(shí)延指標(biāo)微降6.6%。

對(duì)比表2和表3數(shù)據(jù)，當(dāng)系統(tǒng)瓶頸不在CS發(fā)送隊(duì)列時(shí)，擴(kuò)展CS主機(jī)個(gè)數(shù)也能帶來一定收益。1對(duì)1場景下吞吐量為11 870筆/秒(用例1D，ρ=0.55)，3對(duì)1場景下單CS吞吐量為4610筆/秒(用例2D，ρ=0.57)，整體吞吐量為13 830筆/秒。吞吐量提升16.5%，代價(jià)是時(shí)延指標(biāo)降低8.5%。

對(duì)比表3和表5數(shù)據(jù)可以看到，擴(kuò)展TC主機(jī)個(gè)數(shù)可用來增加服務(wù)窗口，以突破TC撮合隊(duì)列瓶頸的束縛。3對(duì)1場景下整體吞吐量為13 830筆/秒(用例2D)，3對(duì)4場景下整體吞吐量為74 469筆/秒(用例4C)。吞吐量提升5.38倍，代價(jià)是時(shí)延指標(biāo)降低34.6%。注意到撮合器服務(wù)能力μ1在不同場景下存在差異。

對(duì)比表5和表6數(shù)據(jù)可以看到，擴(kuò)展撮合進(jìn)程個(gè)數(shù)可用來增加服務(wù)窗口。3對(duì)4場景下整體吞吐量為74 469筆/秒(用例4C)，3對(duì)8場景中單場景下單CS吞吐量為48 967筆/秒(用例5C，ρ=0.51)，整體吞吐量為146 901筆/秒。吞吐量提升1.97倍，代價(jià)是時(shí)延指標(biāo)降低33.6%。

系統(tǒng)瓶頸主要在撮合器服務(wù)能力，通過增加TC主機(jī)和撮合器進(jìn)程個(gè)數(shù)，可以線性提升整體吞吐量，但會(huì)損失一定的時(shí)延性能。

3.3.3 毛刺分析

3對(duì)8場景，輸入480萬條訂單，打單時(shí)長約31秒。取從CS1到SET1的數(shù)據(jù)進(jìn)行分析，λ×3為0.0214，μ1為0.0350，ρ為0.61。整體吞吐量15.6萬筆/秒，平均時(shí)延848.9 μs，其中95%的訂單時(shí)延在1359 μs以內(nèi)，99%的訂單時(shí)延在1719 μs以內(nèi)，100%的訂單時(shí)延在2898 μs以內(nèi)。時(shí)延曲線見圖7所示，時(shí)延分布圖見圖8所示，局部放大見圖9所示。

圖7 時(shí)延曲線圖

圖8 時(shí)延分布圖

圖9 時(shí)延曲線局部放大

觀察出現(xiàn)毛刺的第107 395點(diǎn)，設(shè)為P點(diǎn)，該點(diǎn)時(shí)延DP=2898。發(fā)現(xiàn)DP-1為792，DP+1至DP+11為逐步減小的序列，說明毛刺是在特定點(diǎn)突然達(dá)到峰值，然后再逐步回歸到平均值。對(duì)P點(diǎn)觀察其時(shí)延分布，發(fā)現(xiàn)T1=T7=1277，即毛刺產(chǎn)生的原因是網(wǎng)絡(luò)通信。如能擴(kuò)大網(wǎng)絡(luò)帶寬、升級(jí)網(wǎng)絡(luò)設(shè)備，應(yīng)可降低毛刺出現(xiàn)頻度，進(jìn)而改善整體時(shí)延性能。

3.4 總結(jié)和展望

3.4.1 分析方法

為突破單機(jī)性能瓶頸，需要采用多機(jī)分布式架構(gòu)。然而多機(jī)系統(tǒng)架構(gòu)上的復(fù)雜性，會(huì)帶來更多的交互延遲和隱藏阻塞點(diǎn)，從而加大系統(tǒng)調(diào)優(yōu)代價(jià)。本文提出的隊(duì)列級(jí)聯(lián)方法，將系統(tǒng)抽象為一個(gè)個(gè)消息隊(duì)列的組合，系統(tǒng)時(shí)延由各個(gè)隊(duì)列的處理時(shí)延和排隊(duì)時(shí)延，再加上隊(duì)列間的通信時(shí)延構(gòu)成。其中排隊(duì)時(shí)延是引發(fā)性能不確定性的主要因素，可以用libmoni庫測(cè)量排隊(duì)時(shí)延，并通過調(diào)節(jié)事件流壓力推算隊(duì)列服務(wù)能力參數(shù)μ。

受環(huán)境所限，文中只測(cè)量了TC撮合隊(duì)列和CS發(fā)送隊(duì)列的μ參數(shù)。節(jié)點(diǎn)規(guī)模擴(kuò)大及部署云計(jì)算環(huán)境后，網(wǎng)絡(luò)帶寬、虛擬機(jī)等因素會(huì)帶來新的性能瓶頸點(diǎn)，仍可用隊(duì)列級(jí)聯(lián)方法加以分析。

3.4.2 調(diào)優(yōu)和流控

將分布式系統(tǒng)視作消息隊(duì)列的組合，這些消息隊(duì)列的處理時(shí)延和通信時(shí)延加在一起，是整體時(shí)延的底線。消息隊(duì)列的服務(wù)能力，決定了不帶來過多排隊(duì)時(shí)延的合理事件流強(qiáng)度，也即系統(tǒng)吞吐量。性能調(diào)優(yōu)包含兩個(gè)階段：第一個(gè)階段是盡量降低處理時(shí)延和通信時(shí)延，達(dá)到時(shí)延底線；第二個(gè)階段是在不引入過多排隊(duì)時(shí)延的基礎(chǔ)上，令吞吐量最大化。通過在排隊(duì)模型中增加事件流和服務(wù)窗口，可以突破μ參數(shù)的限制，達(dá)到通過增加節(jié)點(diǎn)線性提升性能的效果。

為使系統(tǒng)能按照設(shè)計(jì)的最優(yōu)性能可靠運(yùn)行，應(yīng)引入用量化時(shí)延進(jìn)行自適應(yīng)流量控制的策略，以保證系統(tǒng)內(nèi)每個(gè)隊(duì)列都不會(huì)受到高于服務(wù)能力的事件流沖擊。當(dāng)事件流強(qiáng)度接近隊(duì)列臨界點(diǎn)時(shí)，時(shí)延會(huì)趨向無限大。此時(shí)應(yīng)抑制系統(tǒng)中的重傳機(jī)制，避免重傳消息進(jìn)一步增大隊(duì)列壓力，引發(fā)消息阻塞、丟失和振蕩，令系統(tǒng)不可用。

4 結(jié) 語

LTP為交易系統(tǒng)輕型化提供了試驗(yàn)平臺(tái)，允許組合各種通信協(xié)議、主備策略和并行策略進(jìn)行算法試驗(yàn)。本文以輕型化交易系統(tǒng)為例，提出分布式系統(tǒng)時(shí)延的隊(duì)列級(jí)聯(lián)分析方法，并介紹相應(yīng)的性能優(yōu)化和流控策略。本文可為企業(yè)級(jí)關(guān)鍵業(yè)務(wù)實(shí)時(shí)系統(tǒng)的設(shè)計(jì)和調(diào)優(yōu)提供參考。

[1] 黃寅飛,黃俊杰,王泊,等.證券交易系統(tǒng)中的事務(wù)恢復(fù)方法[J].計(jì)算機(jī)工程,2010,36(24):241-243.

[2] Pieter Hintjens.ZeroMQ:云時(shí)代極速消息通信庫[M].盧濤,等,譯.北京:電子工業(yè)出版社,2015.

[3] 黃曉東,張勇,邢春曉,等.一種基于Paxos算法的證券交易系統(tǒng)內(nèi)存復(fù)制方法研究[J].計(jì)算機(jī)科學(xué),2012,39(12):139-144,166.

[4] 李子驊.Redis入門指南[M].北京:人民郵電出版社,2013.

[5] Wes McKinney.利用Python進(jìn)行數(shù)據(jù)分析[M].唐學(xué)韜,等,譯.北京:機(jī)械工業(yè)出版社,2014.

[6] Cinnober公司.A Cinnober white paper on: latency[EB/OL].http://www.cinnober.com/whitepapers.

[7] 徐廣斌,武劍鋒,白碩.低延遲證券交易系統(tǒng)關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)工程,2011,37(18):28-31.

[8] 李波,張新有.單向時(shí)延測(cè)量的時(shí)鐘同步技術(shù)及測(cè)量方法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(8):1954-1958.

[9] 陸傳賚.排隊(duì)論[M].第2版.北京:北京郵電大學(xué)出版社,2009.

QUEUING THEORY-BASED LATENCY ANALYSIS ON TRADING SYSTEMS

Huang Yinfei Wang Bo Bai Shuo

(Technology Development Department,Shanghai Stock Exchange,Shanghai 200120,China)

Low latency is the major challenge of stock-trading system when to be moved from minicomputers to PC servers, with regard to this it requires the latency measurement and analysis. First we designed the Redis and Python-based latency data collecting and monitoring framework and implemented it. Then we proposed the cascading queues method to analyse the latency composition in distributed systems. Finally we found the configuration way enabling the optimisation of throughput and latency through parameters test and data analyses, and studied the solutions for extensibility and microburst problems. In this paper we model the distributed systems as cascading queues, on this basis, we make a significant improvement in latency index by the means of quantitative analysis, performance tuning and flow control protection, etc. The cascading queues method proposed in the paper can provide references for design and tuning of enterprise-level mission-critical real-time systems.

Latency measurement Monitoring framework Low latency Stock-trading system

2015-08-31。國家科技支撐計(jì)劃項(xiàng)目(2012BAH13F 04)。黃寅飛，高工，主研領(lǐng)域：證券交易與數(shù)據(jù)分析。王泊，工程師。白碩，研究員。

TP3

A

10.3969/j.issn.1000-386x.2016.11.074