分布式時(shí)空數(shù)據(jù)庫去中心化負(fù)載均衡方法

胡 珂，李成名，沈建明

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

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

在分布式系統(tǒng)中，常用的負(fù)載均衡策略[12]分為中心化控制策略和去中心化控制策略。其中，中心化的控制策略采用單一負(fù)載均衡器來收集系統(tǒng)負(fù)載情況，但是對于海量時(shí)空數(shù)據(jù)，負(fù)載均衡器承載的任務(wù)量大，易出現(xiàn)宕機(jī)問題；去中心化控制策略則是由每個(gè)服務(wù)器都參與到收集負(fù)載信息和分配客戶請求中，這種模式?jīng)]有中心節(jié)點(diǎn)，自組織能力強(qiáng)，可擴(kuò)展性高，更適合存儲時(shí)空數(shù)據(jù)。因此去中心化的存儲策略[13]成為存儲時(shí)空數(shù)據(jù)的主流。

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

1 一致性哈希算法

1.1 算法簡介

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

(1) 平衡性：每個(gè)節(jié)點(diǎn)都等量分配了hash結(jié)果。

(2) 單調(diào)性：無論是增加還是刪除節(jié)點(diǎn)，系統(tǒng)依舊可以繼續(xù)運(yùn)作。

(3) 分散性：分布式集群里每個(gè)節(jié)點(diǎn)都存儲了數(shù)據(jù)的一部分(節(jié)點(diǎn)自身可備份)，而不需要冗余存儲。

1.2 算法原理

一致性哈希算法[18]屬于傳統(tǒng)的哈希算法，特點(diǎn)是無論節(jié)點(diǎn)的增刪,都能以最小的影響處理好已經(jīng)存在的節(jié)點(diǎn)與增刪節(jié)點(diǎn)的映射關(guān)系[19],盡可能滿足單調(diào)性的需求。

一致性哈希算法首先將哈?？臻g進(jìn)行映射,如同一個(gè)圓圈一般，哈?？臻g在0～232-1中取值。然后按順時(shí)針方向排列。0和232-1在零點(diǎn)方向重合，如圖1所示。

這種定制改裝賦予了越野車一種硬朗的都市感，我們聯(lián)系了當(dāng)?shù)氐挠跋褓Y料館，資料館建議把Dean Lane滑板公園作為外景地。那里充滿涂鴉的環(huán)境十分完美，所以我們預(yù)訂了兩個(gè)小時(shí)的包場，在當(dāng)?shù)鼗暹\(yùn)動愛好者到達(dá)之前的清晨進(jìn)行拍攝。

圖1 環(huán)形哈希空間

接著將服務(wù)器節(jié)點(diǎn)使用統(tǒng)一算法計(jì)算出對應(yīng)的hash值,順時(shí)針映射到hash環(huán)上,然后根據(jù)hash值的位置沿圓環(huán)順時(shí)針方向映射到環(huán)上。每增加一臺新的服務(wù)器時(shí),只有新增服務(wù)器的逆時(shí)針方向上碰到的第一臺服務(wù)器的數(shù)據(jù)受到影響，其他均不會受到影響。由于節(jié)點(diǎn)的增刪帶來的重定位數(shù)據(jù)很小，因此系統(tǒng)的運(yùn)行效率和容錯(cuò)率會高很多。

1.3 DHT算法原理

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

(1) 將需要存儲的資源相關(guān)屬性通過哈希運(yùn)算,得到鍵值，即可將所有資源的信息歸結(jié)在同一個(gè)數(shù)值區(qū)域內(nèi)。

(2) 整個(gè)網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)只管理某一個(gè)特定數(shù)值區(qū)域。如A節(jié)點(diǎn)管理鍵值2000～2999的資源，B節(jié)點(diǎn)管理3000～3999的資源。通過該方式,就有規(guī)律性地將所有資源存儲到整個(gè)網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)上面。

2 分布式時(shí)空數(shù)據(jù)去中心化的負(fù)載均衡方法

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

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

另外，每個(gè)節(jié)點(diǎn)都維護(hù)了一張最多m個(gè)表項(xiàng)的Finger-Table表，該表提供了所有節(jié)點(diǎn)對整個(gè)網(wǎng)絡(luò)的“全局視圖”，由于本身是用來做類二分的節(jié)點(diǎn)查找的，因此可以把它當(dāng)作一個(gè)路由表，用戶通過訪問一個(gè)節(jié)點(diǎn)就能迅速找到自己落在環(huán)上的位置，同時(shí)Gossip通信也通過路由表來傳遞各節(jié)點(diǎn)信息。負(fù)載均衡指標(biāo)作為各個(gè)節(jié)點(diǎn)的信息廣播到全局，經(jīng)過比較篩選負(fù)載低的節(jié)點(diǎn)進(jìn)行存儲。最后，通過不斷地比較負(fù)載指標(biāo)從而實(shí)現(xiàn)負(fù)載均衡。

增加新的節(jié)點(diǎn)n時(shí)分為以下3步：

(1) 初始化節(jié)點(diǎn)n的Finger-Table表，同時(shí)將已知的某節(jié)點(diǎn)為它查找Finger-Table表中各個(gè)表項(xiàng)。

(2) 更新原有其他節(jié)點(diǎn)的Finger-Table表，其他節(jié)點(diǎn)使用更新函數(shù)來更新自身的Finger-Table表。

(3) 從后繼節(jié)點(diǎn)把關(guān)鍵字傳遞到節(jié)點(diǎn)n。

如果節(jié)點(diǎn)n發(fā)生故障，根據(jù)Chord環(huán)的特性，由n的后繼節(jié)點(diǎn)n+1替換故障的n節(jié)點(diǎn)，并將指針指向n+1。同時(shí)為了不影響系統(tǒng)查詢，每個(gè)節(jié)點(diǎn)都維護(hù)一張r個(gè)最近后繼節(jié)點(diǎn)的路由表，這樣使得集群穩(wěn)定性大大提高。設(shè)計(jì)路線如圖2所示。

圖2 集群設(shè)計(jì)方案

3 對比試驗(yàn)

本文在PostgreSQL-XL分布式集群環(huán)境下，利用上述方法搭建了基于Chord算法的負(fù)載均衡方法，網(wǎng)絡(luò)帶寬環(huán)境是100 MB的局域網(wǎng)。整個(gè)分布式時(shí)空數(shù)據(jù)系統(tǒng)采用4層結(jié)構(gòu)，包括客戶端、通信層、協(xié)調(diào)器層、分布式時(shí)空數(shù)據(jù)庫層，如圖3所示。

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

圖3 系統(tǒng)結(jié)構(gòu)

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

(1)

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

圖4 系統(tǒng)響應(yīng)時(shí)間對比

如圖4所示，虛擬的并發(fā)用戶越多，兩個(gè)模型的響應(yīng)時(shí)間也越長。任務(wù)數(shù)量較少時(shí)時(shí)間相當(dāng)，但是隨著并發(fā)用戶數(shù)越來越多，環(huán)狀模型的性能更好，與HaProxy相比提升了6.2%；在2000用戶數(shù)關(guān)閉一個(gè)節(jié)點(diǎn)時(shí)，HaProxy停止運(yùn)行，環(huán)狀模型重新計(jì)算導(dǎo)致響應(yīng)時(shí)間較長，之后又穩(wěn)定下來，保證了集群的穩(wěn)定性與有效性。

第二次在鏈狀模型、網(wǎng)狀模型、鏈網(wǎng)模型及本文環(huán)狀模型4種狀態(tài)下分別進(jìn)行測試，所獲得的系統(tǒng)性能對比情況如圖5所示。

圖5 系統(tǒng)響應(yīng)時(shí)間對比

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

4 結(jié) 語

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