基于排隊論的交易系統時延分析

黃寅飛 王 泊 白 碩

(上海證券交易所技術開發部 上海 200120)

?

基于排隊論的交易系統時延分析

黃寅飛 王 泊 白 碩

(上海證券交易所技術開發部 上海 200120)

低延遲是證券交易系統從小型機遷移到PC服務器過程中的主要挑戰，為此需要進行時延度量和分析。首先設計實現基于Redis和Python的時延數據采集監控框架。其次提出隊列級聯方法，分析分布式系統時延構成。最后通過參數試驗和數據分析，找到令吞吐量和時延最優的配置方法，并分析解決可擴展性和毛刺問題。將分布式系統建模為級聯隊列，在此基礎上通過量化分析、性能調優和流控保護等手段，令時延指標顯著提升。所提出的隊列級聯方法可為企業級關鍵業務實時系統的設計和調優提供參考。

時延度量 監控框架 低延遲 證券交易系統

0 引 言

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

本文建立交易時延模型，設計監控架構采集時延數據，在排隊論基礎上提出隊列級聯方法，以指導吞吐量和時延指標調優。

1 技術架構

證券處理的全業務流程如圖1所示。LTP關注的是業務流程中由交易所負責的部分，重點解決實時撮合處理的時延和吞吐量問題。LTP架構如圖2所示，主要包括通信網關CS和交易主機TC兩塊內容。LTP集成基于TCP協議的ZeroMQ消息中間件[2]作為通信層，以實現多對多的廣播訂閱通信方式。集群主機按照產品集合SET進行分區，以支持水平擴展。

圖1 證券處理業務流程示意圖

圖2中，CS上robot 進程負責模擬報單。TC上router 進程負責消息路由，matcher進程負責撮合處理，main為主撮合線程，csq為定序線程。從業務邏輯出發，也稱CS為報盤機，TC為撮合器。TC構成集群，基于Paxos算法[3]實現主備機訂單序號同步。

圖2 LTP進程通信數據流圖

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

圖3 LTP監控架構圖

2 時延建模

2.1 時延定義

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

圖4 時延指標定義

為進一步分析交易時延構成，設置N個采樣點t0,t1,…,tN-1，定義分段時延：

Ti,j=tj-ti

(1)

特別地，定義：

Ti=ti-ti-1

(2)

交易時延構成如下：

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

(3)

2.2 時延模型

LTP系統中訂單生命周期如圖5所示。設置8個采樣點，其中T1、T7為CS到TC間網絡時延，T2、T6為router到matcher 進程間通信時延，T3為主備機定序時延(包含兩跳網絡時延)，T4為撮合器中csq 到main線程間排隊時延，T5為撮合業務處理時延。LTP交易時延為：

T0,7=T1+T2+…+T7

(4)

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

(5)

圖5 LTP訂單生命周期圖

2.3 隊列級聯方法

單個撮合器對應單服務窗口的排隊系統，訂單依次進入撮合器的過程為一個排隊過程。訂單進入撮合器的事件流為泊松流，具備平穩性、無后效性和普通性[9]。

多報單機、多撮合器對應多事件流、多服務窗口的排隊系統。設報單機總數為m，主撮合器總數(即SET數)為n。每個報單機向n個撮合器發送訂單，每個撮合器接收來自m個報單機的訂單。每個報單機承擔的事件流強度為λ×n，每個撮合器承擔的事件流強度為λ×m。

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

以CS、TC多對多關聯構成的系統為例，包含兩個排隊點：CS發送隊列、TC撮合隊列。設報單機服務能力為μ0，撮合器服務能力為μ1。有如下公式：

(6)

(7)

綜合考慮報盤機和撮合器的服務能力，取事件流強度為min(λ0,λ1)可獲得吞吐量和時延的最優配置。

2.4 試驗設計

交易時延由通信時延、排隊時延和處理時延三部分構成，其中排隊時延受吞吐量影響最大，且二者關系并非線性關系。當吞吐量接近服務處理能力時，排隊時延將指數增長。

針對排隊模型中的事件流和服務窗調整參數，試驗不同的模型組合，找到系統中的不變量和隨事件流變化的變量。根據試驗結果，進一步細化模型，給出令時延最優和吞吐量可擴展的配置策略。

3 試驗與分析

3.1 環境準備

試驗環境為千兆以太網，三臺CS為HP DL380p(PC服務器，32核，128 GB內存)，四臺TC為IBM x3850(PC服務器，64核，128 GB內存)。設置8個SET，采取一主兩備配置，每臺TC上部署2個主SET、4個備SET。實際試驗可選取主機和SET的子集，如表1所示。

表1 環境配置表

為接近真實場景，使用工具生成由100萬賬戶和100支產品構成的一億條模擬持倉。使用工具圍繞40支產品和1萬賬戶生成480萬條模擬訂單，每臺CS對每個SET準備20萬條訂單。訂單價格和數量字段隨機生成。訂單消息長度為154字節。CS采取勻速報單方式，每隔固定間隔向TC發送1筆訂單。

3.2 模型試驗

分別使用1對1、3對1、1對4和3對4配置，試驗系統的服務能力，以及不同事件流強度下的性能表現，結果見表2至表5所示。表中λ用報單間隔推算，μ用處理時延推算。吞吐量取單個CS到所有SET的吞吐量總和。

表2 模型參數：1對1事件流

表3 模型參數：3對1事件流

表4 模型參數：1對4事件流

表5 模型參數：3對4事件流

通常起作用的是TC撮合隊列，對應于撮合器服務能力μ1，排隊時延取T4，處理時延取T5。1對4場景比較特殊，起作用的是CS發送隊列，因此表4中取報盤機服務能力μ0，排隊時延改取T1。μ0通過臨界點時的事件流強度推算。

3對8環境采用增加進程的辦法增加服務窗口。在單臺主機上部署多個撮合進程，可充分利用多核計算優勢，在基礎時延少量升高的同時令系統整體吞吐量翻倍，見表6所示。

表6 模型參數：3對8事件流

3.3 數據分析

3.3.1 時延折線圖

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

圖6 時延折線圖

可以看到，1v1曲線、3v1曲線拐點出現在ρ=0.9左右位置，且拐點處曲線變化陡峭；而3v4、3v8曲線拐點出現在ρ=0.7左右位置，且曲線變化較為平滑。隨著服務窗口增加，一方面基礎時延會增加，另一方面時延拐點會前移。

3.3.2 可擴展性分析

代碼不變，隊列μ值固定，從而決定了在該點的λ-時延曲線。在此基礎上可通過增加事件流和增加服務窗口來提升系統的整體吞吐量。

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

對比表2和表3數據，當系統瓶頸不在CS發送隊列時，擴展CS主機個數也能帶來一定收益。1對1場景下吞吐量為11 870筆/秒(用例1D，ρ=0.55)，3對1場景下單CS吞吐量為4610筆/秒(用例2D，ρ=0.57)，整體吞吐量為13 830筆/秒。吞吐量提升16.5%，代價是時延指標降低8.5%。

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

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

系統瓶頸主要在撮合器服務能力，通過增加TC主機和撮合器進程個數，可以線性提升整體吞吐量，但會損失一定的時延性能。

3.3.3 毛刺分析

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

圖7 時延曲線圖

圖8 時延分布圖

圖9 時延曲線局部放大

觀察出現毛刺的第107 395點，設為P點，該點時延DP=2898。發現DP-1為792，DP+1至DP+11為逐步減小的序列，說明毛刺是在特定點突然達到峰值，然后再逐步回歸到平均值。對P點觀察其時延分布，發現T1=T7=1277，即毛刺產生的原因是網絡通信。如能擴大網絡帶寬、升級網絡設備，應可降低毛刺出現頻度，進而改善整體時延性能。

3.4 總結和展望

3.4.1 分析方法

為突破單機性能瓶頸，需要采用多機分布式架構。然而多機系統架構上的復雜性，會帶來更多的交互延遲和隱藏阻塞點，從而加大系統調優代價。本文提出的隊列級聯方法，將系統抽象為一個個消息隊列的組合，系統時延由各個隊列的處理時延和排隊時延，再加上隊列間的通信時延構成。其中排隊時延是引發性能不確定性的主要因素，可以用libmoni庫測量排隊時延，并通過調節事件流壓力推算隊列服務能力參數μ。

受環境所限，文中只測量了TC撮合隊列和CS發送隊列的μ參數。節點規模擴大及部署云計算環境后，網絡帶寬、虛擬機等因素會帶來新的性能瓶頸點，仍可用隊列級聯方法加以分析。

3.4.2 調優和流控

將分布式系統視作消息隊列的組合，這些消息隊列的處理時延和通信時延加在一起，是整體時延的底線。消息隊列的服務能力，決定了不帶來過多排隊時延的合理事件流強度，也即系統吞吐量。性能調優包含兩個階段：第一個階段是盡量降低處理時延和通信時延，達到時延底線；第二個階段是在不引入過多排隊時延的基礎上，令吞吐量最大化。通過在排隊模型中增加事件流和服務窗口，可以突破μ參數的限制，達到通過增加節點線性提升性能的效果。

為使系統能按照設計的最優性能可靠運行，應引入用量化時延進行自適應流量控制的策略，以保證系統內每個隊列都不會受到高于服務能力的事件流沖擊。當事件流強度接近隊列臨界點時，時延會趨向無限大。此時應抑制系統中的重傳機制，避免重傳消息進一步增大隊列壓力，引發消息阻塞、丟失和振蕩，令系統不可用。

4 結 語

LTP為交易系統輕型化提供了試驗平臺，允許組合各種通信協議、主備策略和并行策略進行算法試驗。本文以輕型化交易系統為例，提出分布式系統時延的隊列級聯分析方法，并介紹相應的性能優化和流控策略。本文可為企業級關鍵業務實時系統的設計和調優提供參考。

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

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

[3] 黃曉東,張勇,邢春曉,等.一種基于Paxos算法的證券交易系統內存復制方法研究[J].計算機科學,2012,39(12):139-144,166.

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

[5] Wes McKinney.利用Python進行數據分析[M].唐學韜,等,譯.北京:機械工業出版社,2014.

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

[7] 徐廣斌,武劍鋒,白碩.低延遲證券交易系統關鍵技術研究[J].計算機工程,2011,37(18):28-31.

[8] 李波,張新有.單向時延測量的時鐘同步技術及測量方法[J].小型微型計算機系統,2013,34(8):1954-1958.

[9] 陸傳賚.排隊論[M].第2版.北京:北京郵電大學出版社,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。國家科技支撐計劃項目(2012BAH13F 04)。黃寅飛，高工，主研領域：證券交易與數據分析。王泊，工程師。白碩，研究員。

TP3

A

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