分布式時空數據庫去中心化負載均衡方法

胡 珂，李成名，沈建明

(1.中國測繪科學研究院，北京 100036; 2.江蘇省地質測繪院，江蘇 南京 211100)

近年來，云計算技術的興起[1-3]，解決了大數據的存儲及處理問題[4]，特別是對于結構化及半結構化[5]數據，分布式數據庫成為一種有效、經濟、安全的存儲方式[6]，并且提供近乎實時的查詢效率[7-8]，滿足了線上系統的應用需要。但是分布式存儲系統中的數據量非常龐大，節點存儲的信息也很多[9-10]，當集群中的某些節點利用率不高時，就會影響存儲系統的性能，浪費存儲空間。另外，在多用戶高并發訪問節點時，用戶不了解每個節點的負載情況會導致節點的負載分配不均[11]。以上問題嚴重影響了系統整體的性能和服務效率，因此提出一種負載均衡方法來解決上述問題顯得尤為重要。

在分布式系統中，常用的負載均衡策略[12]分為中心化控制策略和去中心化控制策略。其中，中心化的控制策略采用單一負載均衡器來收集系統負載情況，但是對于海量時空數據，負載均衡器承載的任務量大，易出現宕機問題；去中心化控制策略則是由每個服務器都參與到收集負載信息和分配客戶請求中，這種模式沒有中心節點，自組織能力強，可擴展性高，更適合存儲時空數據。因此去中心化的存儲策略[13]成為存儲時空數據的主流。

針對以上海量時空數據存儲問題及高并發讀寫能力問題，本文首次使用在分布式時空數據庫去中心化動態負載均衡下的環狀模型作為解決方案。該方案采用一致性哈希算法建立環狀模型，可以有效地保證集群的穩定性與可靠性，實現整體的負載均衡。

1 一致性哈希算法

1.1 算法簡介

一致性哈希算法(consistent hash)由麻省理工學院David Karger等在1997年提出[17]，其設計初衷是應對互聯網中的熱點問題，解決了簡單哈希算法在分布式哈希表(distributed hash table,DHT)中存在的動態伸縮等問題，對簡單的哈希算法進行了修正。由于分布式環境是不斷變化的，哈希算法相比于其他算法的優勢在于平衡性、單調性和分散性上，具體如下：

(1) 平衡性：每個節點都等量分配了hash結果。

(2) 單調性：無論是增加還是刪除節點，系統依舊可以繼續運作。

(3) 分散性：分布式集群里每個節點都存儲了數據的一部分(節點自身可備份)，而不需要冗余存儲。

1.2 算法原理

一致性哈希算法[18]屬于傳統的哈希算法，特點是無論節點的增刪,都能以最小的影響處理好已經存在的節點與增刪節點的映射關系[19],盡可能滿足單調性的需求。

一致性哈希算法首先將哈希空間進行映射,如同一個圓圈一般，哈希空間在0～232-1中取值。然后按順時針方向排列。0和232-1在零點方向重合，如圖1所示。

這種定制改裝賦予了越野車一種硬朗的都市感，我們聯系了當地的影像資料館，資料館建議把Dean Lane滑板公園作為外景地。那里充滿涂鴉的環境十分完美，所以我們預訂了兩個小時的包場，在當地滑板運動愛好者到達之前的清晨進行拍攝。

圖1 環形哈希空間

接著將服務器節點使用統一算法計算出對應的hash值,順時針映射到hash環上,然后根據hash值的位置沿圓環順時針方向映射到環上。每增加一臺新的服務器時,只有新增服務器的逆時針方向上碰到的第一臺服務器的數據受到影響，其他均不會受到影響。由于節點的增刪帶來的重定位數據很小，因此系統的運行效率和容錯率會高很多。

1.3 DHT算法原理

DHT屬于一種網絡中很流行的分布式數據保存算法，其通過分布式哈希算法解決數據的相關存儲問題。DHT的核心思想是把需要存儲的資源相關屬性通過哈希運算,得到相關鍵值(hash key),需要存儲的資源信息根據鍵值進行存儲。具體來講,大致有以下步驟：

(1) 將需要存儲的資源相關屬性通過哈希運算,得到鍵值，即可將所有資源的信息歸結在同一個數值區域內。

(2) 整個網絡中每一個節點只管理某一個特定數值區域。如A節點管理鍵值2000～2999的資源，B節點管理3000～3999的資源。通過該方式,就有規律性地將所有資源存儲到整個網絡中每一個節點上面。

2 分布式時空數據去中心化的負載均衡方法

整體路線分為兩個部分：服務器和負載均衡。其中，服務器部分經過多項比較選擇了分布式集群架構PostgreSQL-XL。它包括了以下3個部分:全局事務管理器(GTM)控制全局事物分配，確保事務一致性；協調器(coordinator)管理用戶會話，并與GTM和數據節點進行交互，將操作指令發送到各數據節點；數據節點(data node)負責實際存儲。

負載均衡部分通過Chord算法來維護和管理網絡結構，通過Gossip協議(一種在P2P網絡分布式環境中廣播自己信息及獲取其他節點信息的協議)來廣播節點的負載信息到全局。Chord是一致性哈希的一種實現，是構建結構化P2P的分布式哈希表系統中比較重要的一個算法。一致性哈希保證了整體架構，將服務器的節點通過hash之后平均分布到整個哈希環上，并且使得節點與關鍵字均生成了m位的標識符。節點的后繼節點successor(k)來保存每個關鍵字，其中后繼節點是指從k節點沿順時針方向最近的一個節點。

另外，每個節點都維護了一張最多m個表項的Finger-Table表，該表提供了所有節點對整個網絡的“全局視圖”，由于本身是用來做類二分的節點查找的，因此可以把它當作一個路由表，用戶通過訪問一個節點就能迅速找到自己落在環上的位置，同時Gossip通信也通過路由表來傳遞各節點信息。負載均衡指標作為各個節點的信息廣播到全局，經過比較篩選負載低的節點進行存儲。最后，通過不斷地比較負載指標從而實現負載均衡。

增加新的節點n時分為以下3步：

(1) 初始化節點n的Finger-Table表，同時將已知的某節點為它查找Finger-Table表中各個表項。

(2) 更新原有其他節點的Finger-Table表，其他節點使用更新函數來更新自身的Finger-Table表。

(3) 從后繼節點把關鍵字傳遞到節點n。

如果節點n發生故障，根據Chord環的特性，由n的后繼節點n+1替換故障的n節點，并將指針指向n+1。同時為了不影響系統查詢，每個節點都維護一張r個最近后繼節點的路由表，這樣使得集群穩定性大大提高。設計路線如圖2所示。

圖2 集群設計方案

3 對比試驗

本文在PostgreSQL-XL分布式集群環境下，利用上述方法搭建了基于Chord算法的負載均衡方法，網絡帶寬環境是100 MB的局域網。整個分布式時空數據系統采用4層結構，包括客戶端、通信層、協調器層、分布式時空數據庫層，如圖3所示。

集群搭建在5臺相同配置的服務器(CPU 8核2.4 GHz、16 GB內存、100 MB以太網卡)下進行測試，使用1臺Windows 7計算機(CPU 8核3.6 GHz、4 GB內存、100 MB以太網卡)遠程搭建PostgreSQL-XL服務器集群。其中，1臺服務器作為GTM(global transaction monitor)來確保集群范圍內的事務一致性，另外4臺服務器配置協調器(coordinator)和數據節點(data node)。Chord算法及負載指標所在的通信層通過Java實現。

圖3 系統結構

由于集群系統節點的異構性，服務器的不同硬件參數對性能的影響程度也有不同[20]。因此，參考文獻[20]，本文采用了5種硬件參數加權求和來評價節點的性能C(Ti)，分別為服務器的網絡帶寬使用率C(Bi)、存儲空間的使用率C(Si)、磁盤I/O的訪問率C(IOi)、CPU利用率C(Ci)和內存利用率C(Mi)

(1)

啟動負載均衡服務以后，通過Jmeter工具進行性能測試。測試數據是20世紀70年代1∶100萬柵格世界地圖數據集，在PostGIS數據庫中以blob字段進行分塊存儲。在客戶端用Jmeter向PostgreSQL-XL集群發送地圖服務請求，然后從最初的250個虛擬并發用戶依次增加到3000用戶數并且設置用戶的迭代次數為5次，總共進行兩次測試。第一次使用中心化負載均衡模型(以HaProxy為例)與環狀模型進行測試，在2000并發用戶數時刪除一個節點繼續測試，結果如圖4所示。

圖4 系統響應時間對比

如圖4所示，虛擬的并發用戶越多，兩個模型的響應時間也越長。任務數量較少時時間相當，但是隨著并發用戶數越來越多，環狀模型的性能更好，與HaProxy相比提升了6.2%；在2000用戶數關閉一個節點時，HaProxy停止運行，環狀模型重新計算導致響應時間較長，之后又穩定下來，保證了集群的穩定性與有效性。

第二次在鏈狀模型、網狀模型、鏈網模型及本文環狀模型4種狀態下分別進行測試，所獲得的系統性能對比情況如圖5所示。

圖5 系統響應時間對比

從圖5可以看出，虛擬的并發用戶個數不多的情況下4種方式的相應時間相差不多，但是用戶個數超過1000之后差距開始逐漸顯現出來，節點的負載加重對集群性能的影響也越來越大。通過對4種負載均衡方式的比較，鏈狀模型與網狀模型的響應時間變長，鏈網模型與環狀模型系統性能較為穩定，環狀模型比鏈狀模型性能提升了20%，比網狀模型提升了17%，比鏈網模型提升了3%，算法的負載均衡效果較為顯著。由于環狀模型的靈活性更強，在后期的效果略好于鏈網模型。

4 結 語

與傳統的去中心化動態負載均衡算法相比，在多用戶高并發的情況下存儲時空大數據，環狀模型的性能有明顯的提升，在任務數增大的情況下尤為顯著。將這種負載均衡方法應用在存儲時空數據上具有一定的參考價值。但是本文沒有考慮到路由效率問題，這是進一步研究中需要解決的問題。