基于排隊論的信息存儲配置分析

孫紅鶯

(1.杭州師范大學 理學院，浙江 杭州 310036；2.浙江大學 公共管理學院，浙江 杭州 310027)

0 引 言

由于計算機技術多方面的發(fā)展和應用，人們對數據存儲容量和速度的要求越來越高，對存儲系統(tǒng)的容量提出了前所未有的需求.原有的以服務器為中心的存儲技術已經不適應今天的存儲需求,而以網絡為中心的存儲技術得到快速發(fā)展.

存儲結構的發(fā)展經歷幾個階段，大致包括DAS、NAS和SAN，其中的網絡存儲技術能夠有效地管理一定范圍內的數據存儲，將存儲系統(tǒng)從傳統(tǒng)的集成計算機系統(tǒng)中獨立出來，使得存儲與計算脫離，這對存儲系統(tǒng)各方面特性的研究開辟了更大的空間；同時，高速網絡的迅猛發(fā)展和普及也為網絡存儲提供了底層支持，使大規(guī)模遠距離的網絡存儲系統(tǒng)成為可能.網絡存儲技術為解決海量存儲中存儲設備的分散性、I/O的并行性以及協議的高效性提供了一種很好的手段[1].

對存儲網絡系統(tǒng)I/O請求響應時間的分析和建模，國內外研究者作了大量的工作，但是這些研究大都是定性的[2-4]，而定量研究模型不多，如：曹強是從網絡存儲的存取過程入手，分析影響網絡存儲性能的各種因素，提出針對網絡存儲系統(tǒng)中I/O響應時間的性能評估模型并進行了驗證[5]；崔寶江通過分析建立網絡RAID存儲系統(tǒng)的閉合排隊網絡模型，研究的是網絡RAID存儲系統(tǒng)的I/O響應時間的性能邊界[6]；周薇是基于使用光纖通道的磁盤陣列構建的存儲區(qū)域，利用排隊模型評估的是不同預取策略對于存儲系統(tǒng)性能的影響[7].但他們僅僅是對網絡存儲系統(tǒng)性能的分析，而沒有再進一步，比如可以探討訪問模式和具體配置優(yōu)化的相關性等等.

在此對SAN存儲系統(tǒng)中請求I/O的平均響應時間進行分析并建立排隊論數學模型，由此推導出存儲級中每一存儲陣列個數的最佳數量范圍，據此可以組成優(yōu)化配置.

1 信息存儲架構比較

1.1 海量信息存儲的基礎設備——RAID技術

RAID是redundant array of inexpensive disks的縮寫，簡稱“磁盤陣列”，這種磁盤陣列在提高存儲系統(tǒng)的容量、速度的同時，也提高了數據可靠性和數據管理，成為存儲系統(tǒng)的基礎存儲設備之一.

RAID可以將離散的磁盤變成RAID子系統(tǒng).由于不同磁盤上的數據可以同時讀取，提高磁盤的帶寬，因此具有較高的性能；所有的磁盤可以并行執(zhí)行尋道工作，減少尋道時間，提高整體性能；還能保證一定程度的容錯性.

1.2 DAS存儲

圖1 DAS存儲架構圖

DAS(Direct Attached Storage)是服務器直接連接存儲的縮寫，是一種傳統(tǒng)的基本存儲結構，存儲設備直接連接在主機上.在中小型系統(tǒng)中，存儲設備和處理器是處在同一個機箱中的；在大型系統(tǒng)中，存儲設備和服務器分別處在不同的單元中，通過SCSI電纜、光纜或其他的纜線進行連接.具體如圖1所示.

但是，當用戶進行大量數據訪問時還是容易造成“瓶頸”效應，而且多個服務器之間各有各的存儲設備，不能實現存儲空間的共享，無法實現統(tǒng)一的管理軟件，在系統(tǒng)的管理上增加很大的難度和維護成本.

1.3 NAS存儲

圖2 NAS存儲架構圖

NAS(Network Attached Storage)是附網存儲的縮寫，源于基于以太網的數據訪問技術，并以網絡服務器為模型.NAS在物理連接上是將存儲器直接連到網絡，是一種專用的數據存儲設備，可以向網絡用戶提供跨平臺的文件級海量數據信息共享.如圖2所示.

但是，NAS存儲的缺點是帶寬消耗大，在進行數據備份時，由于多個存儲設備在同一個TCP/IP網絡上，備份時會占用大量的LAN資源.

1.4 SAN存儲

圖3 SAN存儲架構圖

SAN(Storage Area Network)是存儲區(qū)域網絡的縮寫，它是將存儲設備從網絡分離出來，通過專用存儲交換設備再連接到一群計算機上，采用高速光纖通道作為傳輸媒體[8].SAN存儲由3個主要部分組成：計算機主機、光纖通道(Fiber Channel,FC)交換機和存儲設備，如圖3所示.

從圖3可以看到，由于SAN提供多主機的連接，使得網絡中的任何服務器都可以連接到任何的存儲陣列，于是不管數據存放在哪里，服務器都可以直接存取所需的數據，實現數據共享.并且隨著存儲容量的劇增，用戶只需增加磁盤陣列中的磁盤或是增加新的磁盤陣列就可以擴充企業(yè)或單位所需的存儲容量.

1.5 iSCSI-SAN存儲

圖4 iSCSI的協議棧

iSCSI的工作原理如圖4所示.iSCSI協議是推動存儲區(qū)域網絡(SAN)技術快速發(fā)展的關鍵技術之一，因為它使數據存儲的傳送更加快捷.

iSCSI-SAN真正實現了系統(tǒng)中服務器端和存儲設備的分離.用戶可以根據需要在存儲網絡中增加服務器和存儲設備，而不改變現有的網絡結構以及當前應用的運行[9].

通過以上比較，知道SAN能提供許多存儲設備和服務器之間的連接，具有結構靈活、性能高、可擴展性好等特點.高性能的光纖通道交換機和網絡協議能確保設備連接的可靠性和高效性.SAN可以通過最優(yōu)化處理來達到服務器和存儲設備之間快速傳輸數據塊.

2 排隊論模型

圖5 排隊系統(tǒng)一般模型圖

排隊論(Queuing Theory)是研究排隊現象的理論和應用的學科，專門研究由于隨機因素的影響而產生擁擠現象的科學，也稱為隨機服務系統(tǒng).排隊分析是計算機和網絡人員的重要工具之一[10].排隊系統(tǒng)由輸入過程、排隊規(guī)則、服務機構3部分組成，具體如圖5所示.最簡單的輸入過程是服從參數為λ的泊松分布，服務過程一般是服從參數為μ的負指數分布.

2.1 M/M/1排隊模型

當系統(tǒng)中只有一個服務臺，顧客按參數為λ的泊松分布到達，并且任務到達的時間間隔與服務系統(tǒng)為每個顧客服務的時間均為負指數分布，這樣的排隊系統(tǒng)構成了M/M/1排隊模型.

當淤土層厚度較簿時，可采用將淤土層挖除，換填砂壤土、石灰土、粗砂、水泥土等辦法進行地基處理，考慮到砂墊層滲透性強，且造價較高，水利工程一般就地取材，以換填水泥土為多。換土法要回填有較好壓密特性土進行壓實或夯實，形成良好的持力層，從而改變地基承載力特性，提高抗變形和穩(wěn)定能力，施工時應注意坑邊穩(wěn)定，保證填料質量，填料應分層夯實。

其穩(wěn)定分布為：

(1)

(2)

(3)

其中，Ls為在系統(tǒng)中的平均顧客數(隊長期望值);Lq為在隊列中等待的平均顧客數(隊列期望值);Ws為在系統(tǒng)中顧客逗留時間的期望值;Wq為在隊列中顧客等待時間的期望值.

2.2 M/M/L排隊模型

(4)

此時，平均等待時間逗留時間為：

(5)

2.3 一般服務時間M/G/1排隊模型

如果服務臺為顧客服務的時間是一般分布G，系統(tǒng)就構成M/G/1排隊模型.它的平均排隊等待時間為：

(6)

在存儲系統(tǒng)中最常用到的排隊模型就是上述這幾類.

3 SAN存儲的排隊論模型分析

3.1 SAN存儲中的I/O路徑分析

如果SAN存儲是建立在光纖通道協議(FC)技術基礎上的,那么整個存儲系統(tǒng)就成了FC-SAN網絡系統(tǒng).在SAN存儲中傳輸的是數據塊的I/O，所以，當客戶端發(fā)出的請求I/O后，經過文件系統(tǒng)轉化為對邏輯數據塊的請求,傳遞到SCSI驅動程序，將其轉化為對存儲設備的I/O請求(如SCSI命令)，再傳到FCP驅動程序，根據SCSI命令的SCSI地址定位對應的光纖通道設備和LUN，包裝轉化后在光纖通道(FC)網絡上傳播；SAN存儲的目標器設備接收后，交給FCP驅動程序進行處理，解包還原出SCSI命令轉發(fā)給SCSI目標器中間驅動程序，從SCSI命令中得到SCSI CDB，在SAN存儲設備的I/O子系統(tǒng)上進行具體的數據處理，之后再將數據按相反路徑返回[11].

在SAN中的I/O的存取過程有一個特別點，就是當客戶端提出I/O請求，要經過本地的文件系統(tǒng)轉化為對邏輯數據塊的請求，在目標端再轉化為對存儲設備的I/O請求(SCSI命令).當系統(tǒng)發(fā)現所需的存儲設備是位于SAN內，系統(tǒng)就會把I/O請求通過光纖通道卡以及光纖通道交換機傳到具體的存儲設備上.

3.2 SAN存儲中的排隊過程的分析和數學建模

在SAN存儲中，按互連協議不同，可分為光纖通道互連存儲(FC-SAN)，IP互連存儲(IP-SAN)以及iSCSI互連存儲(iSCSI-SAN)，按連接方式不同，又有點對點連接、仲載環(huán)連接以及交換網連接，所以，SAN存儲就比較復雜.如圖6所示.

圖6 SAN存儲的實例結構圖

經過3.1節(jié)對SAN存儲的I/O的路徑分析，知道當客戶主機服務器發(fā)出的I/O經總線適配器后，將數據包發(fā)送到光纖交換機完成數據交換后，發(fā)送到具體的存儲設備上.

因此，在FC-SAN存儲中，可考慮將系統(tǒng)分為2個基本的串行排隊模型，即服務器級的交換傳輸隊列和存儲級的調度服務隊列.在排隊系統(tǒng)中，串行的多個排隊子系統(tǒng)的任務，在系統(tǒng)中的響應時間可以分別計算，最后將各個滯留時間進行累計相加就是任務在系統(tǒng)中的總響應時間[12]，即：

TSAN=TSEVER+TRAID

(7)

其中，TSERVER為I/O請求在服務器級中的響應時間，TRAID為I/O請求在存儲級中的響應時間.具體如圖7所示.

圖7 SAN存儲的排隊模型

3.3 隊列轉換方法求解優(yōu)化配置

依照第2節(jié)對請求獨立性和服務規(guī)則的假設，即到達過程為泊松分布，可用排隊理論進行分析.

首先要對圖7所示的模型作假設：在服務器級中的每個服務器有相同的到達率；在存儲服務中的每個磁盤陣列有相同的到達率、服務率等；排隊規(guī)則是先到服務(FCFS)，即客戶按系統(tǒng)的次序到達，也按相同的次序接受服務；在同一級中，所有服務器和存儲系統(tǒng)有相同的平均服務率，并以平均達到率λ到達服務器級后被均等分配到每個服務器.由于系統(tǒng)的限制，有一部分客戶的請求被拒絕，拒絕率為λPK,服務器的到達率λ′=λ(1-PK).

在圖7中，一個服務器和一個存儲陣列之間構成的多線程進程是，一個到達入口，一個有限的等待隊列和一個出口，并且一次能同時執(zhí)行多個任務，所以符合排隊理論的M/M/L/k模型，用一個這樣的模型來模擬.L代表SAN存儲系統(tǒng)所含的有線程數，k代表這個存儲系統(tǒng)中的客戶請求的最大數量.

從圖7的二級隊列模型中，通過模型轉換(見圖8)，不僅可以算出I/O請求的平均響應時間，而且可以估算出磁盤陣列的最佳數量.估算過程如下.

圖8 SAN存儲轉換的隊列圖

3.3.1 在服務器級中的轉換

客戶請求以到達率λ′=λ(1-PK)到達服務器級，其中的每一個服務器可看作一個M/M/L模型(L代表每一個服務器中服務臺的數量)，而數量為Y的服務器級則構成數量為Y的M/M//L排隊系統(tǒng).如果先把其中的每個M/M/L轉換成為數量L的M/M/1隊列，那么整個排隊系統(tǒng)就變成數量為L×Y的M/M/1排隊系統(tǒng)；接著再把數量為L×Y的M/M/1轉換成一個M/M/LY的排隊系統(tǒng)，具體的過程如圖9所示[13].

圖9 由Y個M/M/L模型到1個M/M/LY模型的轉換

在整個的轉換過程中，每一步驟中的平均等待時間相等，即W0=W1=W2，需要調整服務率μ0、μ1、μ2.M/M/L模型中的平均等待時間用公式(5)，即：

1)當一個M/M/L轉換到L個M/M/1隊列(目標排隊系統(tǒng))時，設定在：

2)當L個M/M/1隊列轉換成一個M/M/L(目標排隊系統(tǒng))時，設定有：

3.3.2 在存儲級中的轉換

由前面對服務器級中轉換的分析，知道在M/M/L1隊列中，到達率為λ′=λ(1-PK),其中PK為拒絕率，服務率為μ1，

在存儲級中，符合模型為M/M/L2，到達率為λ2，λ2=Pi·λ′=Pi·λ·(1-PK)，其中Pi為存儲陣列中到達率的概率，服務率為μ2，因為后面存儲級中的總服務率不能大于前面服務器級中的總服務率，就有：

(8)

(9)

由式(1)(2)可得L2的范圍：

(10)

由上面的轉換分析得知：L2=C2×Y2，其中，C2為存儲級中的線程數量，Y2為存儲級中每一存儲陣列的個數，因此：

(11)

這樣，在理論上求得存儲配置的最佳數量范圍，據此可以組成優(yōu)化配置.

4 結 論

通過對存儲技術中請求I/O在SAN存儲中的平均響應時間分析，利用排隊論對其訪問模式和具體配置最優(yōu)化的相關性研究，提出存儲配置的最佳數量范圍，從而能幫助系統(tǒng)管理員預先了解每種存儲應用的訪問模式，更合理地進行預配置存儲資源.

[1] 張江陵,馮丹.海量信息存儲[M].北京:科學出版社,2003:22-24.

[2] Luyp David. Performance study of Iscsi-based storage subsystems[J]. IEEE Communications Magazine,2003,41(8):76-82.

[3] Hexb, Beedanagari, Zhou D. Performance evaluation of distributed iSCSI RAID[C]//Proceedings of the 2003 IEEE/ACM International Workshop on Storage Network Architecture and Parallel I/O(SNAPI’03). New Orleans:2003.

[4] Weetn, Hillyer, Shriver E. Obtaining high performance for storage outsourcing[C]//Procee-dings of Conference on File and Storage Technologies (FAST’02). Monterey, California:2002：145-158.

[5] 曹強,謝長生.網絡存儲系統(tǒng)中I/O請求時間的研究[J].計算機研究與發(fā)展,2003,40(8):1271-1275.

[6] 崔寶江,劉軍,王剛,等.網絡存儲系統(tǒng)I/O響應時間邊界性能研究[J].通信學報,2006,27(1):70-74.

[7] 周薇,羅榮桂,田磊,等.排隊論在計算機存儲系統(tǒng)性能中的應用和分析[J].微計算機信息,2006,22(21):271-296.

[8] Marc Farley.SAN存儲區(qū)域網絡[M]:2版.孫功星,蔣文保,范勇，等譯.北京:機械工業(yè)出版社,2002:12-34.

[9] Phillips B. Have storage area networks come of age. Computer[J].1998,31(7):10-12.

[10] 徐玖平,胡知能,李軍.運籌學Ⅱ類[M].北京:科學出版社,2004:247-275.

[11] O’Sullivan M, Walker C, Allard J. Improving Optimal Storage Area Network Design[C]//ORSNZ Conference Twenty Naught Two. New Zealand,2002:119-128.

[12] 張江陵.高性能磁盤陣列I/O服務時間分析[J].小型微型計算機系統(tǒng),2000,21(3):235-237.

[13] 崔夢天,張世祿,趙海軍.基于排隊的方法解決分布式系統(tǒng)中信息資源的問題[J].情報雜志,2005(3),46-47.