郭明強，黃穎，謝忠

（1.中國地質(zhì)大學（武漢）信息工程學院，湖北 武漢 430074；2.教育部GIS軟件與應(yīng)用工程研究中心，湖北 武漢 430074）

0 引言

現(xiàn)有WebGIS主要從硬件和軟件兩個方面解決負載均衡問題。硬件上通過專用的負載均衡器或提高地圖服務(wù)器的CPU處理速度、增加內(nèi)存容量等方法提高系統(tǒng)性能，但代價昂貴［1］。傳統(tǒng)的軟件方法提供了廉價而有效的負載均衡機制，目前已有相關(guān)探索，如最小負載法、網(wǎng)絡(luò)輪詢法、最少連接數(shù)法以及相應(yīng)的加權(quán)算法等。但是這些算法要么未考慮系統(tǒng)特征信息，僅適用于小規(guī)模網(wǎng)絡(luò)地理信息服務(wù)系統(tǒng)；要么過度使用和監(jiān)測服務(wù)器實時狀態(tài)信息，信息收集本身及其準確性影響了系統(tǒng)的快速響應(yīng)與決策，因此均不能達到理想的負載均衡效果［2－5］。文獻［5－7］方法雖然能在一定程度上起到負載均衡的作用，但是由于沒有同時考慮并發(fā)用戶任務(wù)等待時間和執(zhí)行時間，對于后提交的任務(wù)，其等待時間長，如果其要求的執(zhí)行時間短，優(yōu)先級高，則會產(chǎn)生響應(yīng)滯后現(xiàn)象，隨著并發(fā)用戶的增多，這種滯后現(xiàn)象會越發(fā)嚴重。

為了縮短所有并發(fā)用戶的響應(yīng)時間，解決并發(fā)訪問時產(chǎn)生的響應(yīng)滯后問題，本文提出了基于響應(yīng)比優(yōu)先調(diào)度的 WebGIS動態(tài)負載均衡算法（RRPSA）。本算法同時考慮了并發(fā)用戶請求在任務(wù)隊列中的等待時間、任務(wù)要求的標準執(zhí)行時間、集群中各應(yīng)用服務(wù)器的當前負載狀態(tài)，使執(zhí)行時間越短、等待時間越長的任務(wù)優(yōu)先被分配到當前負載最輕的服務(wù)器上。實驗結(jié)果表明，本算法有效縮短了服務(wù)器的平均響應(yīng)時間，充分考慮了所有并發(fā)用戶的使用，讓所有并發(fā)用戶都能在理想的時間內(nèi)得到響應(yīng)，實現(xiàn)了良好的全局負載均衡效果。

1 基于RRPSA的WebGIS負載均衡模型

WebGIS是一種用戶交互性很強的網(wǎng)絡(luò)地圖服務(wù)應(yīng)用，包含兩大要素：GIS數(shù)據(jù)與GIS計算。一個高效的WebGIS的最終目標是實現(xiàn)Internet上高效的GIS數(shù)據(jù)分布和GIS計算分布。對GIS計算的策略不同，WebGIS實現(xiàn)的技術(shù)方案也就不同［1］。

目前已有的對WebGIS中負載均衡的研究大多是針對單任務(wù)、順序性任務(wù)。單任務(wù)、順序性任務(wù)是WebGIS空間計算任務(wù)的簡單形式，解決的問題比較簡單。隨著WebGIS應(yīng)用的不斷深入，空間計算已從單任務(wù)向并行性、協(xié)作性任務(wù)發(fā)展，如何提升系統(tǒng)并發(fā)訪問能力和響應(yīng)速度已成為其迫切需要解決的問題［8］。顯然，一個能夠綜合描述上述各種因素的調(diào)度模型和基于該模型的高效的求解方法是提升系統(tǒng)并發(fā)訪問能力和響應(yīng)速度的關(guān)鍵。

為了解決以上問題，本文提出了一種可自由按需擴展的網(wǎng)絡(luò)地圖服務(wù)集群負載均衡模型（圖1），綜合考慮任務(wù)的請求等待時間、任務(wù)標準執(zhí)行時間兩方面因素及資源的負載能力、資源之間的網(wǎng)絡(luò)狀況。

總控模塊啟動請求監(jiān)聽器，負責監(jiān)聽來自 Web服務(wù)器的請求，將請求按序排列，加入請求等待隊列，同時通過負載監(jiān)視器定時檢測集群中各個地圖服務(wù)器的網(wǎng)絡(luò)狀況和實時處理能力。RRPSA算法計算請求等待隊列中任務(wù)的響應(yīng)比（RRP），按RRP從高到低進行排序，選擇RRP最高的任務(wù)作為當前待分配任務(wù)，根據(jù)負載監(jiān)視器的檢測結(jié)果和各地圖服務(wù)器的硬件配置計算各地圖服務(wù)器的負載權(quán)值，將負載最低的地圖服務(wù)器作為當前目標服務(wù)器，讓其處理當前RRP最高的待分配任務(wù)。地圖服務(wù)器處理完請求后將結(jié)果反饋給Web服務(wù)器，最終返回給客戶端。RRPSA重新計算請求等待隊列中任務(wù)的RRP，選擇下一個RRP最高的任務(wù)進行處理。

圖1 基于RRPSA的WebGIS模型Fig.1 WebGIS model based on RRPSA

在大用戶量并發(fā)訪問的情況下，請求等待隊列會隨著用戶數(shù)的增加而增加，本算法使得并發(fā)訪問的所有用戶都能在比較理想的時間內(nèi)得到響應(yīng)，并能均衡的使用集群中的各個地圖服務(wù)器，提高系統(tǒng)的并發(fā)處理能力。

2 RRPSA算法

2.1 服務(wù)器狀態(tài)權(quán)值收集

負載均衡調(diào)度器初始化集群中設(shè)有各地圖服務(wù)器負載權(quán)值列表、服務(wù)結(jié)點信息表以及服務(wù)器狀態(tài)列表。

各地圖服務(wù)器負載權(quán)值主要由3方面決定：地圖服務(wù)器的軟硬件性能線性綜合參數(shù)Hi，其權(quán)值為W（h）；負載均衡調(diào)度器與地圖服務(wù)器集群之間的網(wǎng)絡(luò)狀況參數(shù)Ti，用來衡量負載均衡調(diào)度器與集群中各個地圖服務(wù)器之間的數(shù)據(jù)傳輸速度，其權(quán)值為W（t）；地圖服務(wù)器即時處理能力Pi（是指各個地圖服務(wù)器執(zhí)行一項相同的標準任務(wù)的快慢），權(quán)值為W（p），設(shè)：

負載權(quán)值算法計算流程如下：

（1）根據(jù)地圖服務(wù)器軟硬件配置信息計算地圖服務(wù)器軟硬件配置所占權(quán)值。各個硬件配置的性能值和權(quán)值參數(shù)定義如表1所示。

表1 性能值、權(quán)值參數(shù)定義Table 1 Parameters definition of performance and weight

其中：Ci、Mi、Di、Xi、Ni、Oi＜1，W （c）＋W （m）＋W（d）＋W（x）＋W（n）＋W（o）＝1。

根據(jù)上述參數(shù)和服務(wù)器軟硬件配置權(quán)值計算地圖服務(wù)器軟硬件性能線性綜合參數(shù)：

（2）計算出軟硬件性能線性綜合參數(shù)后，再根據(jù)地圖服務(wù)器的網(wǎng)絡(luò)延時計算出各個地圖服務(wù)器的網(wǎng)絡(luò)狀況參數(shù)，其公式如下：

其中：ti是各個地圖服務(wù)器與負載均衡調(diào)度器之間的網(wǎng)絡(luò)延時，n為地圖服務(wù)器的數(shù)目。

（3）計算各個地圖服務(wù)器即時處理能力權(quán)值Pi，其公式如下：

其中：n同上，pi為地圖服務(wù)器執(zhí)行標準運算任務(wù)所花的時間。

（4）通過式（1）、式（2）、式（3），可得出各個地圖服務(wù)器的負載權(quán)值：

計算出地圖服務(wù)器的負載權(quán)值后，負載均衡調(diào)度器啟動服務(wù)，開始監(jiān)聽服務(wù)端口，準備接收 Web服務(wù)器的地圖服務(wù)請求；同時啟動負載均衡調(diào)度器監(jiān)控線程，定時監(jiān)控各個地圖服務(wù)器狀態(tài)。

2.2 RRP計算及動態(tài)調(diào)度

WebGIS應(yīng)用復(fù)雜，包括矢量地圖顯示、瓦片地圖顯示、要素查詢、空間分析等功能，每個功能應(yīng)用需要的標準執(zhí)行時間均不相同，以矢量地圖顯示功能為例，每個用戶每次請求的矢量地圖的范圍均不相同，范圍越大，生成圖像越慢。在這種復(fù)雜的應(yīng)用場景下，為了使大多數(shù)并發(fā)用戶滿意，首先要考慮請求預(yù)計的標準執(zhí)行時間，執(zhí)行時間越小，應(yīng)該優(yōu)先被執(zhí)行，其次要考慮并發(fā)用戶的等待時間，等待時間越長，優(yōu)先級越高，應(yīng)該優(yōu)先被執(zhí)行，這樣才能使等待時間長的用戶優(yōu)先得到響應(yīng)，避免用戶無限的排隊等待。RRPSA基于使平均響應(yīng)時間盡可能低且讓大多數(shù)并發(fā)用戶滿意的原則對任務(wù)進行動態(tài)分配。

設(shè)ts為任務(wù)提交時間，tb為任務(wù)實際開始執(zhí)行時間，tc為任務(wù)實際執(zhí)行完成時間，tp為任務(wù)要求的標準執(zhí)行時間，T為所有并發(fā)任務(wù)平均周轉(zhuǎn)時間。如果只考慮任務(wù)在隊列中的等待時間，即只考慮tb－ts這個時間段而不考慮tp，則會出現(xiàn)tp小等待時間長的任務(wù)的響應(yīng)延遲現(xiàn)象。RRPSA算法的目標是綜合考慮任務(wù)等待時間和執(zhí)行時間，讓T最小，即讓所有并發(fā)用戶的平均響應(yīng)時間最短，使等待時間長、要求執(zhí)行時間短的任務(wù)優(yōu)先執(zhí)行，T計算公式如下：

計算任務(wù)標準執(zhí)行時間tp：以矢量地圖請求為例，可采用空間范圍來衡量一個請求內(nèi)容的大小，根據(jù)請求范圍計算出等待任務(wù)隊列中各任務(wù)要求的標準執(zhí)行時間tp，定義xmin、ymin、xmax、ymax為當前矢量地圖請求隊列中最大的外包矩形范圍，每個請求的范圍為xmini、ymini、xmaxi、ymaxi。

計算任務(wù)等待隊列中的各任務(wù)的響應(yīng)優(yōu)先級，設(shè)當前計算時間為t，則當前計算任務(wù)的響應(yīng)優(yōu)先級R：

負載均衡調(diào)度器中的負載監(jiān)視線程定期搜集服務(wù)器狀態(tài)信息，計算負載權(quán)值，選擇R最高的任務(wù)分配給負載最低的服務(wù)器執(zhí)行，同時從等待隊列中刪除已分配的任務(wù)。

3 實驗分析

本文使用位于高速局域網(wǎng)內(nèi)的刀片中心構(gòu)建試驗床，對本文提出的響應(yīng)比優(yōu)先調(diào)度動態(tài)負載均衡算法進行仿真實驗，并與傳統(tǒng)集群服務(wù)器負載均衡算法進行對比。圖2為實驗環(huán)境的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，表2為系統(tǒng)仿真參數(shù)。

圖2 實驗環(huán)境網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig.2 The network topology of simulation

通過LoadRunner對系統(tǒng)進行壓力負載測試。測試數(shù)據(jù)：國土地類圖斑矢量數(shù)據(jù)（矢量要素個數(shù)為4 023 175），每個用戶每次隨機請求一個地圖范圍。在WebGIS應(yīng)用系統(tǒng)中，數(shù)據(jù)請求的響應(yīng)時間至關(guān)重要，負載均衡的重要指標就是最小化請求平均響應(yīng)時間。特別是在地圖漫游響應(yīng)時間方面，響應(yīng)時間越短，表示W(wǎng)ebGIS應(yīng)用系統(tǒng)的地圖漫游越流暢，用戶所感受到的漫游體驗或者說服務(wù)質(zhì)量越高。

表2 系統(tǒng)仿真參數(shù)Table 2 Simulation parameters of the system

圖3是在相同的用戶數(shù)（100個虛擬客戶端）并發(fā)訪問的情況下，本文算法和其它常見的幾種負載均衡算法在仿真過程中的平均響應(yīng)時間波動對比。從圖中可以分析得出：1）本文中RRPSA算法的平均響應(yīng)時間在整個仿真過程中波動較小，原因是RRPSA算法綜合考慮了請求的等待時間和執(zhí)行時間以及服務(wù)器的負載狀況。2）最小負載算法和最少連接算法的平均響應(yīng)時間波動較大，其原因是這兩種算法都未考慮請求的執(zhí)行時間，仿真過程中如果隊列中有執(zhí)行時間較長的任務(wù)，則會導致隊列中后面的請求的響應(yīng)時間增大，導致產(chǎn)生波動。3）輪詢算法的平均響應(yīng)時間波動最大，分析其原因是該算法既未考慮服務(wù)器的負載狀況，也未考慮任務(wù)的執(zhí)行時間，導致服務(wù)器的負載不均衡，使得所有并發(fā)用戶的平均響應(yīng)時間產(chǎn)生較大波動。

圖3 100用戶并發(fā)訪問平均響應(yīng)時間波動Fig.3 The average response time fluctuations of 100 concurrent users

圖4是在不同的并發(fā)用戶數(shù)并發(fā)訪問情況下，采用不同的負載均衡算法服務(wù)的平均響應(yīng)時間的對比。從圖中可以看出，本文提出的算法總能更快地返回用戶請求的數(shù)據(jù)，因為它同時考慮了服務(wù)器負載狀態(tài)和請求的等待時間及執(zhí)行時間，隨著并發(fā)用戶數(shù)的增大，本算法的效果更加明顯。

圖4 不同并發(fā)用戶訪問平均響應(yīng)時間Fig.4 The average response time of different concurrent users

由以上測試結(jié)果可見，使用RRPSA算法可以明顯的縮短系統(tǒng)響應(yīng)時間，減小大用戶量并發(fā)訪問下服務(wù)平均響應(yīng)時間的波動，提高地圖服務(wù)器場的并發(fā)處理能力，具有較好的穩(wěn)定性、并發(fā)性和抗負載能力。

4 結(jié)論

本文分析了傳統(tǒng)負載均衡算法的缺點，針對大用戶量并發(fā)訪問的情況進行分析，提出了一種基于任務(wù)響應(yīng)比優(yōu)先調(diào)度的WebGIS動態(tài)負載均衡算法，解決了目前WebGIS負載均衡算法并發(fā)處理能力低、不能平衡并發(fā)訪問情況下所有用戶的響應(yīng)時間的問題；并通過建立測試環(huán)境，對算法的穩(wěn)定性和并發(fā)性能進行了壓力測試，測試結(jié)果驗證了本算法的穩(wěn)定性和高效性都優(yōu)于傳統(tǒng)的負載均衡算法。

［1］ 江飛，周保群，王惠芳.一種有效負載均衡的分布式 WebGIS體系結(jié)構(gòu)模型［J］.微計算機信息，2006，22（28）：215－217.

［2］ 章文嵩.可伸縮網(wǎng)絡(luò)服務(wù)的研究與實現(xiàn)［D］.長沙：國防科學技術(shù)大學，2000.1－15.

［3］ IQBAL S，CAREY G F.Performance analysis of dynamic load balancing algorithms with variable［J］.Parallel and Distributed Computing，2005，65：934.

［4］ DOWN D G，LEWIS M E.Dynamic load balancing in parallel queueing systems：Stability and optimal control［J］.European Journal of Operational Research，2006，168：509.

［5］ 朱江，張立立，曾志明，等.WebGIS服務(wù)器場的負載平衡算法設(shè)計［J］.計算機工程，2006，32（9）：94－95.

［6］ 李忠民，喻占武，朱莉，基于空間數(shù)據(jù)內(nèi)容的動態(tài)負載均衡方法［J］.武漢大學學報（信息科學版），2009，34（5）：622－624.

［7］ 郭明強，黃穎，謝忠.一種基于服務(wù)器場的分布式 WebGIS計算模型設(shè)計與實現(xiàn)［J］.地理與地理信息科學，2008，24（6）：12－15.

［8］ 黃穎，謝忠，吳亮，等.基于聚類調(diào)度負載均衡的 WebGIS模型［J］.中國地質(zhì)大學學報（地球科學），2010，35（3）：407－414.