基于排隊論的OLTP模型研究

柳晶晶

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

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

一、前言

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

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

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

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

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

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

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

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

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

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

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

M/M/c（c≥2）是多服務(wù)臺的等待制排隊系統(tǒng)，它的各種特征的規(guī)定和假設(shè)與M/M/1模型基本相同。假定c個服務(wù)臺并聯(lián)排列，各服務(wù)臺獨立工作，其平均服務(wù)率相同，即μ1=μ2=…=μc=μ。因此，當(dāng)n≥c時（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)達到N時，再來的顧客將被拒絕，其他條件與標(biāo)準(zhǔn)的M/M/c相同。

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

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

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

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

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

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

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

一個主控觸發(fā)后，主控依次讀取本地隊列中的所有消息，直到隊列中沒有消息為止。因為主控是同步調(diào)用消息處理程序（HNSV1000），所以在一個主控范圍內(nèi)，消息處理程序是串行的，沒有并發(fā)問題。

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

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

（三）模型假設(shè)

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

1.顧客的特性

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

（2）在同一時點上只能有一個顧客到達。

（3）顧客到達是相互獨立的。

（4）顧客到達的時間間隔是隨機的。

2.隊列的特性

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

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

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

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

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

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

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

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

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

4.輸出的特性

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

（四）排隊模型

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

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

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

2.服務(wù)臺的個數(shù)

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

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

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

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

（五）排隊模型的模擬試驗分析

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

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

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

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

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

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

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

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

四、結(jié)語

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

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

參考文獻

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

[2]林生.計算機通信網(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.