基于響應比優先調度的WebGIS動態負載均衡算法

郭明強，黃穎，謝忠

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

0 引言

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

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

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

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

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

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

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

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

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

2 RRPSA算法

2.1 服務器狀態權值收集

負載均衡調度器初始化集群中設有各地圖服務器負載權值列表、服務結點信息表以及服務器狀態列表。

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

負載權值算法計算流程如下：

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

表1 性能值、權值參數定義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。

根據上述參數和服務器軟硬件配置權值計算地圖服務器軟硬件性能線性綜合參數：

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

其中：ti是各個地圖服務器與負載均衡調度器之間的網絡延時，n為地圖服務器的數目。

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

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

（4）通過式（1）、式（2）、式（3），可得出各個地圖服務器的負載權值：

計算出地圖服務器的負載權值后，負載均衡調度器啟動服務，開始監聽服務端口，準備接收 Web服務器的地圖服務請求；同時啟動負載均衡調度器監控線程，定時監控各個地圖服務器狀態。

2.2 RRP計算及動態調度

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

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

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

計算任務等待隊列中的各任務的響應優先級，設當前計算時間為t，則當前計算任務的響應優先級R：

負載均衡調度器中的負載監視線程定期搜集服務器狀態信息，計算負載權值，選擇R最高的任務分配給負載最低的服務器執行，同時從等待隊列中刪除已分配的任務。

3 實驗分析

本文使用位于高速局域網內的刀片中心構建試驗床，對本文提出的響應比優先調度動態負載均衡算法進行仿真實驗，并與傳統集群服務器負載均衡算法進行對比。圖2為實驗環境的網絡拓撲結構，表2為系統仿真參數。

圖2 實驗環境網絡拓撲結構Fig.2 The network topology of simulation

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

表2 系統仿真參數Table 2 Simulation parameters of the system

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

圖3 100用戶并發訪問平均響應時間波動Fig.3 The average response time fluctuations of 100 concurrent users

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

圖4 不同并發用戶訪問平均響應時間Fig.4 The average response time of different concurrent users

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

4 結論

本文分析了傳統負載均衡算法的缺點，針對大用戶量并發訪問的情況進行分析，提出了一種基于任務響應比優先調度的WebGIS動態負載均衡算法，解決了目前WebGIS負載均衡算法并發處理能力低、不能平衡并發訪問情況下所有用戶的響應時間的問題；并通過建立測試環境，對算法的穩定性和并發性能進行了壓力測試，測試結果驗證了本算法的穩定性和高效性都優于傳統的負載均衡算法。

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

［2］ 章文嵩.可伸縮網絡服務的研究與實現［D］.長沙：國防科學技術大學，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服務器場的負載平衡算法設計［J］.計算機工程，2006，32（9）：94－95.

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

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

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