摘   要： 以電子商務(wù)網(wǎng)站為對(duì)象，提出一種改善其性能的調(diào)度算法和系統(tǒng)的體系機(jī)構(gòu)。通過(guò)大量的實(shí)驗(yàn)數(shù)據(jù)將算法與FIFO進(jìn)行性能比較。
關(guān)鍵詞： 電子商務(wù)  動(dòng)態(tài)加權(quán)公平服務(wù)  性能改善

　　目前改善Web Server性能的主要策略有：采用Web Server的復(fù)制策略[1]來(lái)達(dá)到負(fù)載均衡的效果；利用緩存(Cache)技術(shù)[2]來(lái)減少Web的延遲；通過(guò)短連接優(yōu)先調(diào)度[3]的策略來(lái)減少Web Server的響應(yīng)時(shí)間；從客戶(hù)端應(yīng)用程序的角度來(lái)提高應(yīng)用程序的自適應(yīng)性[4]并基于預(yù)測(cè)做出相應(yīng)的決策。
　　典型的購(gòu)物網(wǎng)站中，客戶(hù)的請(qǐng)求是基于會(huì)話(huà)(Session)[5]的。Session里包含了來(lái)自同一客戶(hù)端連續(xù)的請(qǐng)求序列。客戶(hù)能感受到的服務(wù)質(zhì)量就是響應(yīng)時(shí)間。對(duì)于這類(lèi)網(wǎng)站，Session里有瀏覽、查詢(xún)、訂單等不同的處理，這些不同的客戶(hù)行為對(duì)Web Server的需求也不相同。其中查詢(xún)處理會(huì)涉及訪(fǎng)問(wèn)數(shù)據(jù)庫(kù)，訂單處理要應(yīng)用程序進(jìn)行數(shù)據(jù)庫(kù)操作，瀏覽則不涉及復(fù)雜的操作。同時(shí)，客戶(hù)對(duì)不同行為的響應(yīng)時(shí)間的要求也不同，例如瀏覽客戶(hù)能忍受的延遲可能不超過(guò)1秒，而對(duì)于查詢(xún)操作客戶(hù)可忍受的延遲會(huì)較長(zhǎng)些。于是把請(qǐng)求分成4種：瀏覽首頁(yè)、購(gòu)物付賬、查詢(xún)和瀏覽靜態(tài)頁(yè)面。對(duì)于每個(gè)到達(dá)的請(qǐng)求依據(jù)其種類(lèi)進(jìn)入相應(yīng)的隊(duì)列，再動(dòng)態(tài)調(diào)整隊(duì)列權(quán)值，其依據(jù)就是使得效益函數(shù)取得最大值。然后采用動(dòng)態(tài)加權(quán)公平服務(wù)(Dynamic Weighted Fair Service，DWFS)算法，對(duì)不同類(lèi)型的請(qǐng)求提供有區(qū)別但相對(duì)權(quán)值來(lái)說(shuō)又是公平的服務(wù)。
1  相關(guān)工作
　　算法思想來(lái)源于一個(gè)理想的絕對(duì)公平的策略——處理機(jī)共享[6]。它先建立多個(gè)隊(duì)列，在每次循環(huán)中只發(fā)送1位。這樣，每個(gè)忙的源站都能夠得到完全相同的處理機(jī)容量，是絕對(duì)化公平的。特別是，如果有N個(gè)隊(duì)列，同時(shí)每個(gè)隊(duì)列永遠(yuǎn)都有1個(gè)分組要發(fā)送，則每個(gè)隊(duì)列就正好得到可用容量的1/N。這種處理稱(chēng)為處理機(jī)共享。下面定義一些術(shù)語(yǔ)。
　　R(t)：時(shí)間t內(nèi)，在處理機(jī)共享規(guī)則中發(fā)生的循環(huán)次數(shù)。
　　N(t)：t時(shí)刻的非空隊(duì)列數(shù)。
　　P_i：分組i的處理時(shí)間。
　　Z_i^a：在隊(duì)列a中分組i的到達(dá)時(shí)間。
　　S_i^a：隊(duì)列a中分組i的開(kāi)始被處理時(shí)R(t)的值。
　　F_i^a：在隊(duì)列a中分組i的結(jié)束處理時(shí)R(t)的值。
　　可以將R(t)想象成一個(gè)虛擬時(shí)間，記錄了在隊(duì)列頭部第1個(gè)分組所看到的服務(wù)速率。
下面的3個(gè)遞歸關(guān)系式歸納了處理機(jī)共享系統(tǒng)的基本思想：
　　　

2  Web Server性能改進(jìn)算法的基本原理
　　本文提出的體系結(jié)構(gòu)如圖1所示。其思想是：將顧客的請(qǐng)求根據(jù)所需要的服務(wù)器類(lèi)型分類(lèi)；對(duì)同一類(lèi)請(qǐng)求分配相同的權(quán)值；權(quán)值會(huì)隨著當(dāng)前的請(qǐng)求和Web服務(wù)器的處理情況調(diào)整；基于權(quán)值對(duì)請(qǐng)求進(jìn)行公平服務(wù)。

2.1 算法基本思想
　　為了使處理機(jī)能支持服務(wù)質(zhì)量，而有區(qū)別地分配容量，并且能夠發(fā)送整個(gè)分組，而不是單個(gè)位，就需要設(shè)計(jì)一個(gè)具有區(qū)別服務(wù)的可實(shí)現(xiàn)的處理機(jī)共享系統(tǒng)。
　　(1)考慮公平加權(quán)。為了考慮不同隊(duì)列的不同需求，應(yīng)將處理機(jī)共享規(guī)則廣義化，即允許分配任意的處理機(jī)容量。為每個(gè)隊(duì)列指派1個(gè)權(quán)值Φ_α，它確定了在每次循環(huán)中從該隊(duì)列可發(fā)送多少比特。假設(shè)只有3個(gè)隊(duì)列且均為非空，權(quán)值分別為0.8、0.1和0.1。對(duì)于隊(duì)列1中的請(qǐng)求i，P_i是全部處理機(jī)資源都在處理此請(qǐng)求時(shí)所需的時(shí)間，則請(qǐng)求i在這種情況下的實(shí)際處理時(shí)間就變?yōu)镻_i/0.8=5P_i/4，比原來(lái)大1/4倍。因?yàn)榉强贞?duì)列權(quán)值之和未必等于1，所以公式(1)中的Pi不能簡(jiǎn)單地變?yōu)镻_i/Φ_i，而應(yīng)變換為(P_i/Φ_i)*C₁，其中C1在給定的權(quán)值下為常數(shù)。因?yàn)殛?duì)列具有權(quán)值，不能同等對(duì)待，所以虛擬時(shí)間R(t)也要變化，不再是1/N(t)。非空隊(duì)列的權(quán)值之和越大，處理能力越分散，輪詢(xún)一遍所需的時(shí)間就越長(zhǎng)，虛擬時(shí)間的漲幅越小。即R(t)′與∑Φ_{非空隊(duì)列}成反比，記為R(t)′＝C2/∑Φ_{非空隊(duì)列}，其中C2在給定的權(quán)值下為常數(shù)。把以上2個(gè)結(jié)論分別代入公式(1)、(2)、(3)，就得到如下3個(gè)式子：
　　

　　(2)考慮具體實(shí)現(xiàn)。由于要處理的不是單個(gè)位，而是整個(gè)請(qǐng)求，屬0/1問(wèn)題，因此需進(jìn)一步完善。加權(quán)公平服務(wù)算法就是設(shè)計(jì)一個(gè)模擬逐位輪流的規(guī)則。實(shí)現(xiàn)此算法時(shí)要隨時(shí)計(jì)算虛擬開(kāi)始時(shí)間S_i與虛擬結(jié)束時(shí)間F_i，就好像正在運(yùn)行加權(quán)的處理機(jī)共享那樣。規(guī)定：只要一個(gè)請(qǐng)求的處理過(guò)程結(jié)束，下一個(gè)將被處理的請(qǐng)求就具有最小F_i值。為此建立了請(qǐng)求到達(dá)處理模型，且可以發(fā)現(xiàn)，隨著時(shí)間的推移，請(qǐng)求收到的平均響應(yīng)時(shí)間收斂于在逐位發(fā)送規(guī)則下的結(jié)果。

2.2 動(dòng)態(tài)調(diào)整權(quán)值
　　由于服務(wù)不同，賦予的初始權(quán)值也就不同。而且每個(gè)隊(duì)列長(zhǎng)度也在不斷變化，因此要防止擁塞，就需要每隔一定時(shí)間調(diào)用權(quán)值調(diào)整函數(shù)，根據(jù)隊(duì)列初始權(quán)值和當(dāng)前隊(duì)列長(zhǎng)度計(jì)算新的權(quán)值。
2.3 權(quán)值調(diào)整算法和加權(quán)公平服務(wù)算法
　　每隔一段時(shí)間調(diào)用一次權(quán)值調(diào)整方法：
　　

　　每次請(qǐng)求處理結(jié)束，調(diào)用加權(quán)公平服務(wù)方法，返回下一個(gè)應(yīng)處理的請(qǐng)求：
　

3  Web Server性能改進(jìn)算法具體實(shí)現(xiàn)
3.1 系統(tǒng)模擬環(huán)境
　　系統(tǒng)的程序?qū)崿F(xiàn)框圖如圖2所示。在真實(shí)的Web服務(wù)器前端實(shí)現(xiàn)一個(gè)代理(Proxy)，在Proxy中實(shí)現(xiàn)了FIFO和DWFS算法。為了產(chǎn)生較多的HTTP請(qǐng)求，用程序模擬了HTTP客戶(hù)端的實(shí)現(xiàn)。該客戶(hù)端能按照一定的時(shí)間間隔和規(guī)律來(lái)生成請(qǐng)求。

3.2 實(shí)驗(yàn)程序說(shuō)明
　　使用Java程序模擬Proxy的實(shí)現(xiàn)。其實(shí)現(xiàn)主要由以下類(lèi)組成。
　　(1)Http客戶(hù)端（HttpClient）：模擬客戶(hù)機(jī)發(fā)送Http請(qǐng)求。
　　(2)Http服務(wù)端（HttpServer）：模擬服務(wù)器，將Http請(qǐng)求進(jìn)行排隊(duì)處理。
　　(3)Http請(qǐng)求接收（HttpRequestRsv）：接收Http請(qǐng)求，根據(jù)訪(fǎng)問(wèn)頁(yè)面分類(lèi)進(jìn)入隊(duì)列。
　　(4)Http請(qǐng)求隊(duì)列(HttpRequestQueue)：隊(duì)列數(shù)據(jù)結(jié)構(gòu)。
　　(5)Http請(qǐng)求隊(duì)列處理（HttpRequestQueueHandler）：采取FIFO或DWFS進(jìn)行調(diào)度。
　　(6)Http請(qǐng)求處理（HttpRequestHandler）：調(diào)度后，發(fā)送真實(shí)Http請(qǐng)求，并進(jìn)行處理。
　　(7)數(shù)據(jù)日志（Datalog）：記錄實(shí)驗(yàn)數(shù)據(jù)寫(xiě)日志文件。
3.3 實(shí)驗(yàn)初始參數(shù)
　　服務(wù)器同時(shí)處理10個(gè)請(qǐng)求，選用了幾個(gè)有代表性的頁(yè)面，各頁(yè)面參數(shù)如表1所示。

4  實(shí)驗(yàn)結(jié)果數(shù)據(jù)分析
　　數(shù)據(jù)采集的參數(shù)包括：當(dāng)前請(qǐng)求響應(yīng)時(shí)間、各隊(duì)列當(dāng)前平均響應(yīng)時(shí)間、所有請(qǐng)求的平均響應(yīng)時(shí)間和各隊(duì)列當(dāng)前長(zhǎng)度。
　　(1)分別間隔300ms和200ms發(fā)送請(qǐng)求分析響應(yīng)時(shí)間。在每隔300ms發(fā)送請(qǐng)求時(shí)，2種算法下的系統(tǒng)性能幾乎相同。而且，隨著發(fā)送的請(qǐng)求個(gè)數(shù)越來(lái)越多，響應(yīng)時(shí)間并未增大。因?yàn)槊扛?00ms的時(shí)間發(fā)送一個(gè)請(qǐng)求的速度對(duì)于Web服務(wù)器來(lái)說(shuō)遠(yuǎn)沒(méi)有達(dá)到飽和，因此不論采用什么算法，都不會(huì)造成系統(tǒng)的擁塞，系統(tǒng)性能相對(duì)穩(wěn)定，2種算法沒(méi)有明顯區(qū)別。每隔200ms發(fā)送請(qǐng)求時(shí)，在前150個(gè)請(qǐng)求到來(lái)之前2種算法的系統(tǒng)性能幾乎相同。然而隨著請(qǐng)求的增多，應(yīng)用DWFS算法的請(qǐng)求響應(yīng)時(shí)間只是FIFO的一半。這說(shuō)明在系統(tǒng)負(fù)載接近飽和的情況下，DWFS算法會(huì)使系統(tǒng)性能明顯提高。
　　(2)分析間隔200ms發(fā)送請(qǐng)求時(shí)的隊(duì)列平均響應(yīng)時(shí)間和隊(duì)列長(zhǎng)度。在發(fā)送130個(gè)請(qǐng)求后，F(xiàn)IFO的各個(gè)隊(duì)列平均響應(yīng)時(shí)間和長(zhǎng)度均大于DWFS各隊(duì)列的響應(yīng)時(shí)間。此外，應(yīng)用FIFO的各隊(duì)列極不穩(wěn)定，不論“長(zhǎng)”請(qǐng)求隊(duì)列還是“短”請(qǐng)求隊(duì)列都可能得不到響應(yīng)，隊(duì)列會(huì)出現(xiàn)擁塞。而DWFS的各個(gè)隊(duì)列平均響應(yīng)時(shí)間和隊(duì)列長(zhǎng)度相對(duì)穩(wěn)定，但對(duì)于需要較長(zhǎng)處理時(shí)間的搜索頁(yè)面隊(duì)列通常的響應(yīng)時(shí)間也較長(zhǎng)，會(huì)有較多的請(qǐng)求排隊(duì)。
5  結(jié)論及展望
　　該體系結(jié)構(gòu)中仍然存在一些不足：請(qǐng)求的產(chǎn)生是均勻、依次的，而實(shí)際客戶(hù)訪(fǎng)問(wèn)各個(gè)頁(yè)面都是隨機(jī)的；僅在特定時(shí)刻根據(jù)隊(duì)列的長(zhǎng)度調(diào)整權(quán)值。針對(duì)以上不足可作進(jìn)一步的改善：在請(qǐng)求的產(chǎn)生上，引入概率轉(zhuǎn)移矩陣模型用于反映客戶(hù)在不同隊(duì)列間的轉(zhuǎn)移關(guān)系，以更客觀(guān)地模擬實(shí)際請(qǐng)求；根據(jù)客戶(hù)的優(yōu)先級(jí)調(diào)整權(quán)值。
參考文獻(xiàn)
1   Qiu L，Padmanabhan V，Voelker G.On the Placement of Web Server Replicas.In：Proceedings of IEEE Infocom，2001
2   Chandranmenon G，Varghese G.Reducing Web Latency Using Reference Point Caching.In：Proceedings of the IEEE Infocom，2001
3   Crovella M，F(xiàn)rangioso R，Harchol-Balte M.Connection Scheduling in Web Servers.In：USENIX Symposium on  Internet Technologies and Systems(USITS′99)，1999
4   Stemm M，Seshan S，Katz R H.A Network Measurement  Architecture for Adaptive Applications.In：Proceedings of  IEEE Infocom，2000
5   Chen H，Mohapatra P.Session-Based Overload Control for  QoS-Aware Web Servers.In：Proceedings of IEEE Infocom，2002
6   Stallings W著，齊望東譯.高速網(wǎng)絡(luò)：TCP/IP和ATM的設(shè)計(jì)原理.北京：電子工業(yè)出版社，1999