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

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

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

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

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

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

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

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

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

4  實驗結(jié)果數(shù)據(jù)分析
　　數(shù)據(jù)采集的參數(shù)包括：當(dāng)前請求響應(yīng)時間、各隊列當(dāng)前平均響應(yīng)時間、所有請求的平均響應(yīng)時間和各隊列當(dāng)前長度。
　　(1)分別間隔300ms和200ms發(fā)送請求分析響應(yīng)時間。在每隔300ms發(fā)送請求時，2種算法下的系統(tǒng)性能幾乎相同。而且，隨著發(fā)送的請求個數(shù)越來越多，響應(yīng)時間并未增大。因為每隔300ms的時間發(fā)送一個請求的速度對于Web服務(wù)器來說遠(yuǎn)沒有達(dá)到飽和，因此不論采用什么算法，都不會造成系統(tǒng)的擁塞，系統(tǒng)性能相對穩(wěn)定，2種算法沒有明顯區(qū)別。每隔200ms發(fā)送請求時，在前150個請求到來之前2種算法的系統(tǒng)性能幾乎相同。然而隨著請求的增多，應(yīng)用DWFS算法的請求響應(yīng)時間只是FIFO的一半。這說明在系統(tǒng)負(fù)載接近飽和的情況下，DWFS算法會使系統(tǒng)性能明顯提高。
　　(2)分析間隔200ms發(fā)送請求時的隊列平均響應(yīng)時間和隊列長度。在發(fā)送130個請求后，F(xiàn)IFO的各個隊列平均響應(yīng)時間和長度均大于DWFS各隊列的響應(yīng)時間。此外，應(yīng)用FIFO的各隊列極不穩(wěn)定，不論“長”請求隊列還是“短”請求隊列都可能得不到響應(yīng)，隊列會出現(xiàn)擁塞。而DWFS的各個隊列平均響應(yīng)時間和隊列長度相對穩(wěn)定，但對于需要較長處理時間的搜索頁面隊列通常的響應(yīng)時間也較長，會有較多的請求排隊。
5  結(jié)論及展望
　　該體系結(jié)構(gòu)中仍然存在一些不足：請求的產(chǎn)生是均勻、依次的，而實際客戶訪問各個頁面都是隨機的；僅在特定時刻根據(jù)隊列的長度調(diào)整權(quán)值。針對以上不足可作進一步的改善：在請求的產(chǎn)生上，引入概率轉(zhuǎn)移矩陣模型用于反映客戶在不同隊列間的轉(zhuǎn)移關(guān)系，以更客觀地模擬實際請求；根據(jù)客戶的優(yōu)先級調(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è)計原理.北京：電子工業(yè)出版社，1999