柳晶晶

摘要：聯(lián)機(jī)交易（OLTP）系統(tǒng)是一種典型的計(jì)算機(jī)應(yīng)用系統(tǒng)，雖然使用數(shù)量眾多，但其系統(tǒng)設(shè)計(jì)一般停留在感性階段，多是通過試驗(yàn)和測(cè)試手段考查其設(shè)計(jì)的有效性，性能調(diào)優(yōu)基本依靠技術(shù)人員的經(jīng)驗(yàn)，缺乏系統(tǒng)性的理論指導(dǎo)。為了提高OLTP系統(tǒng)設(shè)計(jì)的可靠性和穩(wěn)定性，從排隊(duì)理論的角度進(jìn)行了抽象和分析，并以大額支付系統(tǒng)為例給出了OLTP系統(tǒng)的處理模型，形成理解和討論OLTP系統(tǒng)內(nèi)部處理機(jī)制的基礎(chǔ)，有助于實(shí)現(xiàn)從知道怎么做到知道為什么這么做的轉(zhuǎn)變。

關(guān)鍵詞：聯(lián)機(jī)交易系統(tǒng)；排隊(duì)論；隨機(jī)過程

一、前言

排隊(duì)論[1]是一門專門研究排隊(duì)問題的運(yùn)籌學(xué)分支。排隊(duì)論的起源可以追溯到1909年愛爾朗（A. K. Erlang）的論文，該論文的發(fā)表為后來排隊(duì)論的發(fā)展奠定了堅(jiān)實(shí)的基礎(chǔ)。在絕大多數(shù)的排隊(duì)系統(tǒng)中，顧客到達(dá)和服務(wù)時(shí)間都是隨機(jī)的。排隊(duì)過程通常是一個(gè)隨機(jī)過程，排隊(duì)論又稱“隨機(jī)服務(wù)系統(tǒng)理論”。排隊(duì)論在計(jì)算機(jī)性能分析和通信網(wǎng)的定量分析方面占有極重要的地位。一個(gè)計(jì)算機(jī)或網(wǎng)絡(luò)實(shí)際可看成一個(gè)復(fù)雜的排隊(duì)系統(tǒng)[2]。

二、OLTP系統(tǒng)的排隊(duì)模型

排隊(duì)模型需要確定排隊(duì)系統(tǒng)的各項(xiàng)特征，如平均等待時(shí)間、平均隊(duì)長(zhǎng)等，或是構(gòu)建某個(gè)服務(wù)系統(tǒng)以滿足特定的顧客服務(wù)水平。

（一）排隊(duì)系統(tǒng)的基本構(gòu)成

排隊(duì)系統(tǒng)通常由輸入、隊(duì)列、服務(wù)臺(tái)和輸出四部分構(gòu)成，可以用圖1來加以描述。

（二）排隊(duì)系統(tǒng)的分類描述

肯達(dá)爾（Kendall）通過由斜線分割開的6項(xiàng)代碼來表示排隊(duì)模型。前兩項(xiàng)為字符碼，分別表示到達(dá)過程和服務(wù)過程的分布形式。第三、四、五項(xiàng)是數(shù)字，分別代表服務(wù)臺(tái)數(shù)目、系統(tǒng)的容量和顧客總量。最后一項(xiàng)表示排隊(duì)規(guī)則。

（三）單服務(wù)器排隊(duì)系統(tǒng)模型

泊松到達(dá)過程、負(fù)指數(shù)服務(wù)時(shí)間分布、只有一個(gè)服務(wù)員的排隊(duì)系統(tǒng)模型為M/G/1。其中，M代表泊松輸入或服務(wù)時(shí)間服從負(fù)指數(shù)分布，G代表一般的服務(wù)時(shí)間。對(duì)于M/G/1模型，服務(wù)時(shí)間 的分布是一般的（但要求期望值E[T]和方差Var[T]都存在）。為了達(dá)到穩(wěn)態(tài)，ρ<1這一條件是必要的，其中ρ=μ/λ。對(duì)于M/G/1排隊(duì)系統(tǒng)，系統(tǒng)中逗留的平均顧客數(shù)和平均逗留時(shí)間僅與顧客平均到達(dá)率λ、平均服務(wù)時(shí)間1/μ及服務(wù)時(shí)間的方差Var[T]有關(guān)，而不需知道服務(wù)時(shí)間的分布情況。

（四）多服務(wù)器排隊(duì)系統(tǒng)模型

1.M/M/c/∞/∞模型

M/M/c（c≥2）是多服務(wù)臺(tái)的等待制排隊(duì)系統(tǒng)，它的各種特征的規(guī)定和假設(shè)與M/M/1模型基本相同。假定c個(gè)服務(wù)臺(tái)并聯(lián)排列，各服務(wù)臺(tái)獨(dú)立工作，其平均服務(wù)率相同，即μ1=μ2=…=μc=μ。因此，當(dāng)n≥c時(shí)（n為系統(tǒng)中的顧客數(shù)量），該系統(tǒng)的平均服務(wù)率為cμ；當(dāng)n

2.M/M/c/N/∞模型

該系統(tǒng)的容量最大限制為N（≥c），當(dāng)系統(tǒng)中顧客數(shù)n已經(jīng)達(dá)到N時(shí)，再來的顧客將被拒絕，其他條件與標(biāo)準(zhǔn)的M/M/c相同。

三、OLTP系統(tǒng)的排隊(duì)模型實(shí)例

從OLTP系統(tǒng)的角度看，大額支付系統(tǒng)是典型的OLTP系統(tǒng)。下面將以大額支付系統(tǒng)在國(guó)家處理中心（NPC）節(jié)點(diǎn)的處理為例，在分析現(xiàn)有處理流程的基礎(chǔ)上，整理并抽象其排隊(duì)模型。

（一）大額支付系統(tǒng)的處理流程

大額支付系統(tǒng)NPC使用CICS交易中間件保證交易的完整性；使用MQ傳輸中間件實(shí)現(xiàn)報(bào)文的傳輸；在開放和主機(jī)平臺(tái)上分別使用ORACLE和DB2，負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)和管理。MCTL是大額支付系統(tǒng)應(yīng)用的主控程序。當(dāng)CICS啟動(dòng)時(shí)同時(shí)啟動(dòng)MCTL。在CICS活動(dòng)期間MCTL一直處于活動(dòng)狀態(tài)。大額支付系統(tǒng)城市處理中心（CCPC）向NPC的MQ網(wǎng)關(guān)（MQGW）發(fā)送報(bào)文。MQGW收到CCPC發(fā)來的報(bào)文，進(jìn)行報(bào)文分配，并將報(bào)文轉(zhuǎn)發(fā)給大額應(yīng)用服務(wù)器。大額應(yīng)用服務(wù)器MQ本地隊(duì)列收到CCPC發(fā)來的CMT100報(bào)文，觸發(fā)MCTL。MCTL根據(jù)報(bào)文的種類，調(diào)用相應(yīng)交易服務(wù)程序。大額支付系統(tǒng)一般大額業(yè)務(wù)（CMT100）報(bào)文的并發(fā)主要處理體現(xiàn)在以下幾個(gè)方面（忽略了應(yīng)用服務(wù)器的并發(fā)處理）：

1.主控程序的并發(fā)

主控程序的最大并發(fā)數(shù)：主控程序MAINSVR是CMT100報(bào)文處理的入口。MAINSVR服務(wù)程序在CICS中的交易名是MCTL。MCTL采用MQ觸發(fā)機(jī)制，其基本功能是讀取NPC本地隊(duì)列里的報(bào)文，并調(diào)用相應(yīng)的程序進(jìn)行處理。在大額CICS REGION中，通過RD中的MINSERFER和MAXSERVER定義了總的程序并發(fā)處理能力。MCTL作為CICS REGION中由TCLASS定義的其中一類交易，在RD中進(jìn)一步定義了MCTL可以并發(fā)的最大個(gè)數(shù)（由ClassMaxTasks參數(shù)確定）。在大額支付系統(tǒng)中，MCTL的最大并發(fā)數(shù)為20。主控程序?qū)嶋H的并發(fā)數(shù)：主控程序由MQ觸發(fā)。大額支付系統(tǒng)采用的是MQ First（trigdpth 1，trigint 500）觸發(fā)方式。在該交易調(diào)用機(jī)制下，MQ隊(duì)列觸發(fā)器類型設(shè)置為First，當(dāng)隊(duì)列中滿足條件的消息從0變到非0時(shí)會(huì)產(chǎn)生一條觸發(fā)消息，MQ 隊(duì)列的Monitor會(huì)調(diào)起主控處理程序處理隊(duì)列中的消息，直到隊(duì)列為空為止。在某些情況下，當(dāng)隊(duì)列不為空時(shí)，MQ系統(tǒng)隔trigint時(shí)間后也會(huì)產(chǎn)生一條新的觸發(fā)消息。每一個(gè)觸發(fā)消息都會(huì)觸發(fā)一個(gè)主控，由于CMT100報(bào)文達(dá)到的隨機(jī)性，可能會(huì)啟動(dòng)多個(gè)主控，但實(shí)際并發(fā)的主控個(gè)數(shù)小于等于主控的最大并發(fā)數(shù)。

2.消息服務(wù)的并發(fā)

一個(gè)主控觸發(fā)后，主控依次讀取本地隊(duì)列中的所有消息，直到隊(duì)列中沒有消息為止。因?yàn)橹骺厥峭秸{(diào)用消息處理程序（HNSV1000），所以在一個(gè)主控范圍內(nèi)，消息處理程序是串行的，沒有并發(fā)問題。

（二）排隊(duì)系統(tǒng)表述

如果將CMT100報(bào)文視為排隊(duì)系統(tǒng)中的顧客，將NPC節(jié)點(diǎn)本地隊(duì)列視為排隊(duì)系統(tǒng)中的隊(duì)列，將主控視為排隊(duì)系統(tǒng)中的服務(wù)臺(tái)，CMT100的排隊(duì)系統(tǒng)流程圖見圖2。

（三）模型假設(shè)

按照排隊(duì)理論和以上的分析，做出如下假設(shè)：

1.顧客的特性

（1）由于OLTP系統(tǒng)一般處理的交易是巨量的，因此可以近似認(rèn)為顧客總體是無限的。

（2）在同一時(shí)點(diǎn)上只能有一個(gè)顧客到達(dá)。

（3）顧客到達(dá)是相互獨(dú)立的。

（4）顧客到達(dá)的時(shí)間間隔是隨機(jī)的。

2.隊(duì)列的特性

（1）CMT100排隊(duì)系統(tǒng)中，只有一個(gè)隊(duì)列。

（2）如果所有服務(wù)臺(tái)都正在被占用，顧客不會(huì)選擇隨即離去，而是排隊(duì)等待。

（3）生產(chǎn)系統(tǒng)中隊(duì)列的深度是固定的，因此是有限隊(duì)列。

3.服務(wù)臺(tái)的特性

（1）主控程序可以并發(fā)。排隊(duì)系統(tǒng)中可以有一個(gè)或多個(gè)服務(wù)臺(tái)。如果是多服務(wù)臺(tái)，各服務(wù)臺(tái)可以串聯(lián)、并聯(lián)或混聯(lián)。實(shí)際并發(fā)的主控個(gè)數(shù)具有一定的隨機(jī)性。

（2）主控服務(wù)一次只能處理一個(gè)報(bào)文。

（3）主控服務(wù)的處理時(shí)間是隨機(jī)的。

（4）如果主控服務(wù)的服務(wù)時(shí)間分布和特征參數(shù)不隨時(shí)間的變化而變化，即是平穩(wěn)的。

（5）CMT100的服務(wù)規(guī)則是先到先服務(wù)（FIFO）。

4.輸出的特性

CMT100處理完成后，即刻轉(zhuǎn)發(fā)CCPC，因此以上排隊(duì)系統(tǒng)是一個(gè)開環(huán)系統(tǒng)。

（四）排隊(duì)模型

要建立排隊(duì)模型，除了以上的假設(shè)，還需明確以下三個(gè)問題：

1.顧客到達(dá)的規(guī)則

顧客到達(dá)是隨機(jī)的，因此需要確定單位時(shí)間的顧客到達(dá)數(shù)或相繼到達(dá)時(shí)間間隔的概率分布。假設(shè)顧客到達(dá)是符合泊松分布的隨機(jī)過程，（嚴(yán)格意義上，應(yīng)根據(jù)實(shí)際生產(chǎn)數(shù)據(jù)，進(jìn)行x2假設(shè)檢驗(yàn)）。

2.服務(wù)臺(tái)的個(gè)數(shù)

服務(wù)臺(tái)數(shù)即為MCTL最大并發(fā)個(gè)數(shù)，實(shí)際上可以得出此OLTP系統(tǒng)業(yè)務(wù)處理的最高效率，包括吞吐量、平均等待時(shí)間、平均隊(duì)列長(zhǎng)度等技術(shù)指標(biāo)。

3.服務(wù)的規(guī)則

最簡(jiǎn)單的服務(wù)時(shí)間分布是負(fù)指數(shù)分布（嚴(yán)格意義上應(yīng)根據(jù)實(shí)際生產(chǎn)數(shù)據(jù)，進(jìn)行x2假設(shè)檢驗(yàn)），這種情況下，平均服務(wù)率一個(gè)參數(shù)就完全描述了整個(gè)服務(wù)過程。平均服務(wù)率μ可以用測(cè)試的方法確定，即單個(gè)主控的處理速率。

因此，以上OLTP系統(tǒng)的排隊(duì)模型可以確定為M/M/c/N/∞/FIFO，其中c為MCTL的最大并發(fā)個(gè)數(shù)，N為本地隊(duì)列的最大長(zhǎng)度與c之和。

（五）排隊(duì)模型的模擬試驗(yàn)分析

除了以上給出的解析方法，下面以模擬試驗(yàn)的方法對(duì)其進(jìn)行分析。假設(shè)在λ＝156筆/秒，μ=50筆/秒的情況下，當(dāng)n<4時(shí)，由于nμ<λ，即ρ>1，因此隊(duì)列長(zhǎng)度會(huì)不斷增大，以至于造成隊(duì)列滿的情況。在模擬時(shí)，僅模擬n=4，6，8，10，20的情況，此時(shí)ρ<1，不會(huì)形成無限隊(duì)列，由此得出排隊(duì)系統(tǒng)的統(tǒng)計(jì)平均指標(biāo)如表1所示。

在n=4時(shí)系統(tǒng)狀態(tài)（pn）的概率分布見圖3。

在n=20時(shí)系統(tǒng)狀態(tài)（pn）的概率分布見圖4。

在假定CMT100報(bào)文平均到達(dá)率λ＝156筆/秒以及NPC服務(wù)器平均服務(wù)率μ＝50筆/秒不變的情況下，隨著并發(fā)服務(wù)臺(tái)的個(gè)數(shù)增加，有如下結(jié)論：

1.大額支付系統(tǒng)平均隊(duì)長(zhǎng)近似為零。也就是說，在假定的業(yè)務(wù)量和系統(tǒng)設(shè)計(jì)處理容量的條件下，業(yè)務(wù)一旦到達(dá)，可即刻處理，幾乎不需排隊(duì)等待。由于幾乎不存在業(yè)務(wù)排隊(duì)，因此業(yè)務(wù)排隊(duì)撤銷也是沒有必要的。大額支付系統(tǒng)的這種設(shè)計(jì)，實(shí)際上是通過增加系統(tǒng)處理容量，以較低的設(shè)備使用效率代價(jià)換取了業(yè)務(wù)處理的最大實(shí)時(shí)性。

2.當(dāng)并發(fā)服務(wù)臺(tái)的個(gè)數(shù)n≧4后，系統(tǒng)的平均排隊(duì)等待時(shí)間幾乎可以忽略，平均處理時(shí)間也基本相同，不會(huì)隨著并發(fā)服務(wù)臺(tái)的個(gè)數(shù)增加而明顯增加。因此在不考慮資源瓶頸（如CPU、內(nèi)存、CICS并發(fā)進(jìn)程、清算賬戶等）的限制和并發(fā)服務(wù)臺(tái)之間同步和沖突開銷的前提下，大額支付系統(tǒng)理想的吞吐量峰值（吞吐量峰值＝n×1/W）會(huì)隨著并發(fā)服務(wù)臺(tái)的個(gè)數(shù)增加而近似線性的增加。

3.n≧4時(shí)，大額支付系統(tǒng)的系統(tǒng)狀態(tài)趨于穩(wěn)定，不會(huì)隨并發(fā)服務(wù)臺(tái)個(gè)數(shù)的增加而有明顯的改善。

4.由于CCPC的處理邏輯不涉及清算賬戶資源瓶頸，因此其處理模型可以用無沖突的M/M/c/N/∞/FIFO模型很好地刻畫，此時(shí)實(shí)際并發(fā)的主控進(jìn)程數(shù)就可以近似認(rèn)為是n，提高CCPC處理容量的有效方法之一就是提高并發(fā)主控進(jìn)程數(shù)量，從排隊(duì)系統(tǒng)的角度，也很容易解釋為什么CCPC的處理性能可能遠(yuǎn)遠(yuǎn)大于NPC的原因。

四、結(jié)語(yǔ)

排隊(duì)模型是目前計(jì)算機(jī)系統(tǒng)性能評(píng)價(jià)中應(yīng)用最廣的一種分析模型?；诮?jīng)典隨機(jī)過程假設(shè)的排隊(duì)理論通常被稱為“馬爾可夫排隊(duì)網(wǎng)絡(luò)”。盡管這些假設(shè)有時(shí)是不成立的，例如參數(shù)是隨時(shí)間變化的、作業(yè)是相關(guān)的等，但是Buzen[3]和Denning[4]研究證明，馬爾可夫排隊(duì)模型的結(jié)果可以從一組完全不同的假設(shè)推導(dǎo)出來，這些假設(shè)能夠直接檢驗(yàn)，而且實(shí)際系統(tǒng)多半滿足這些假定。因此也就解釋了即便經(jīng)典排隊(duì)理論的大部分假設(shè)與實(shí)際情況不符，但排隊(duì)模型刻畫的實(shí)際系統(tǒng)還可以得到比較滿意的結(jié)果的原因。

本文通過引入排隊(duì)理論，以大額支付系統(tǒng)為例給出了聯(lián)機(jī)交易系統(tǒng)的處理模型。排隊(duì)模型給出了一種排隊(duì)系統(tǒng)的解析方法，特別是那些符合馬爾可夫排隊(duì)網(wǎng)絡(luò)假設(shè)的排隊(duì)系統(tǒng)，其關(guān)鍵性統(tǒng)計(jì)指標(biāo)是能夠解析得出的，這些指標(biāo)比較全面地、量化地描述了排隊(duì)系統(tǒng)的特征，也給出了可能影響系統(tǒng)性能的關(guān)鍵要素。

參考文獻(xiàn)

[1]《運(yùn)籌學(xué)教材》編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，1990.

[2]林生.計(jì)算機(jī)通信網(wǎng)原理[M].西安：西安電子科技大學(xué)出版社，1997.

[3]Buzen， Jeffrey P .Computational algorithms for closed queueing networks with exponential servers[J].Communications of the ACM， 1973， 16（9）：527-531.

[4] Denning P J ， Buzen J P .The Operational Analysis of Queueing Network Models[J].Acm Computing Surveys， 1978， 10（3）：225-261.