任樂樂,何靈敏

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

一種改進(jìn)的主從節(jié)點(diǎn)選舉算法用于實(shí)現(xiàn)集群負(fù)載均衡

任樂樂,何靈敏

(中國(guó)計(jì)量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

隨著數(shù)據(jù)量的不斷增長(zhǎng),分布式搜索引擎的出現(xiàn)滿足了大數(shù)據(jù)量的檢索性能.現(xiàn)有的主從節(jié)點(diǎn)選舉策略往往會(huì)導(dǎo)致主從節(jié)點(diǎn)分配不均而使得查詢性能不均衡.現(xiàn)提出一種搜索引擎集群的主從節(jié)點(diǎn)選舉策略,能保證正常情況下節(jié)點(diǎn)的分布均衡.當(dāng)出現(xiàn)宕機(jī)時(shí)能重新切換主節(jié)點(diǎn),保證檢索功能有效;當(dāng)宕機(jī)的服務(wù)器重新上線時(shí),主從節(jié)點(diǎn)分布恢復(fù)正常,避免了負(fù)載不平衡的缺陷,達(dá)到合理利用每臺(tái)服務(wù)器的性能并充分發(fā)揮集群的性能優(yōu)勢(shì)的目的.

集群;主從節(jié)點(diǎn)選舉;負(fù)載均衡;容災(zāi)恢復(fù)

分布式算法不但能夠?qū)⒍嗯_(tái)服務(wù)器的資源綜合利用,而且可以通過備份機(jī)制避免由于單個(gè)節(jié)點(diǎn)失效而影響數(shù)據(jù)查詢結(jié)果的風(fēng)險(xiǎn)[1].分布式算法往往使用主從模式實(shí)現(xiàn)數(shù)據(jù)的備份和容災(zāi)功能.如何均衡地利用每臺(tái)搜索引擎的性能并且如何實(shí)現(xiàn)容災(zāi)恢復(fù)策略是分布式算法的關(guān)鍵[2-3].

現(xiàn)有的主從節(jié)點(diǎn)選舉算法中的主從節(jié)點(diǎn)分配不合理,往往會(huì)出現(xiàn)1臺(tái)服務(wù)器存在2個(gè)主節(jié)點(diǎn),而另外1臺(tái)服務(wù)器存在2個(gè)從節(jié)點(diǎn)的情況.當(dāng)用戶進(jìn)行查詢時(shí)集群只會(huì)向主節(jié)點(diǎn)發(fā)送查詢請(qǐng)求,導(dǎo)致1臺(tái)服務(wù)器需要完成2個(gè)分片的查詢工作,而另一臺(tái)服務(wù)器處于完全空閑的狀態(tài).查詢性能不均衡[4].

該缺點(diǎn)主要由兩個(gè)原因?qū)е?

1)因?yàn)槊總€(gè)分片的注冊(cè)線程是完全獨(dú)立的,每臺(tái)服務(wù)器上有兩個(gè)不同的分片需要注冊(cè),而由于服務(wù)器的啟動(dòng)速度和網(wǎng)路情況都不相同,往往會(huì)出現(xiàn)一臺(tái)服務(wù)器上的兩個(gè)分片都首先注冊(cè)到zookeeper[5]的分片管理目錄下而成為主節(jié)點(diǎn),而注冊(cè)速度慢的服務(wù)器上的兩個(gè)節(jié)點(diǎn)都會(huì)成為從節(jié)點(diǎn).

2)即使首次創(chuàng)建時(shí)主節(jié)點(diǎn)的分配是均衡的,即每臺(tái)服務(wù)器上有一個(gè)主節(jié)點(diǎn)和一個(gè)從節(jié)點(diǎn),但是當(dāng)某個(gè)服務(wù)器出現(xiàn)宕機(jī)情況時(shí),該服務(wù)器上的主節(jié)點(diǎn)就會(huì)被其他服務(wù)器上的從節(jié)點(diǎn)取代,等到宕機(jī)的服務(wù)器重新上線時(shí),曾經(jīng)的主節(jié)點(diǎn)也會(huì)成為從節(jié)點(diǎn),導(dǎo)致負(fù)載不均衡情況的出現(xiàn).現(xiàn)有的主從節(jié)點(diǎn)選舉算法流程圖如圖1.

Zookeeper[6]作為Hadoop的子項(xiàng)目,為分布式系統(tǒng)提供可靠的協(xié)調(diào)功能.提供包括配置維護(hù)、分布式同步、事件觸發(fā)器等功能,是當(dāng)前分布式系統(tǒng)最常用的協(xié)調(diào)管理系統(tǒng)[7].當(dāng)前的搜索引擎集群選擇zookeeper來實(shí)現(xiàn)協(xié)調(diào)功能.現(xiàn)有的搜索引擎服務(wù)器集群的zookeeper管理目錄如圖2.

1 改進(jìn)優(yōu)化

本文提出一種搜索引擎集群的主從節(jié)點(diǎn)選舉策略[8],能保證正常情況下節(jié)點(diǎn)的分布均衡,當(dāng)出現(xiàn)宕機(jī)時(shí)能重新切換主節(jié)點(diǎn),保證檢索功能有效,當(dāng)宕機(jī)的服務(wù)器重新上線時(shí),主從節(jié)點(diǎn)分布恢復(fù)正常,避免了負(fù)載均衡不平衡的缺陷.

根據(jù)分片個(gè)數(shù)和備份個(gè)數(shù),指定合理的分片策略.每個(gè)分片首先向服務(wù)器管理目錄注冊(cè),并等待同一個(gè)服務(wù)器的其他分片注冊(cè)成功(如有某分片未注冊(cè),則認(rèn)為該服務(wù)器啟動(dòng)不正常).每個(gè)分片根據(jù)自身所在服務(wù)器所有注冊(cè)分片的信息以及分片和備份個(gè)數(shù),可以確定自身是否為主節(jié)點(diǎn).最

圖1 現(xiàn)有的搜索引擎服務(wù)器集群的zookeeper管理目錄Figure 1 Existing directory of search engine cluster’s zookeeper management

圖2 現(xiàn)有的主從節(jié)點(diǎn)選舉算法流程圖

后每個(gè)分片獨(dú)立向分片管理目錄注冊(cè),根據(jù)注冊(cè)順序和自身是否是主節(jié)點(diǎn)來確定當(dāng)前分片的主從關(guān)系.

假設(shè)搜索引擎集群共有N臺(tái)服務(wù)器,并做M個(gè)備份.

1)利用合理的分片策略[9]保證任意(M,N)組合下存在固定的分片模式.

分片策略主要有兩種,第一種M

本方法確定第X(1≤X≤N)臺(tái)服務(wù)器的分片策略:如果((N-X)≥M),則該服務(wù)器為分片X到分片(X+M);否則該服務(wù)器為分片X到分片N,加上分片1到分片(M-(N-X)).并且確定分片X為主節(jié)點(diǎn).服務(wù)器分片策略舉例如表1所示:N=5,M=3.

表1 服務(wù)器分片策略舉例

可以發(fā)現(xiàn),除了M=N的特殊情況外,每臺(tái)服務(wù)器的分片情況都是唯一的,在已知分片數(shù)和備份數(shù)的情況下,每個(gè)分片根據(jù)自身所在的服務(wù)器上所有分片的信息,即可確定自身是否是確定的主節(jié)點(diǎn).所以當(dāng)M

圖3 搜索引擎集群主從節(jié)點(diǎn)選舉(M

2)針對(duì)M=N的情況,通過按大小順序搶占式注冊(cè)模式確定主從節(jié)點(diǎn)的方法.

考慮M=N的特殊情況:此時(shí)所有服務(wù)器的分片情況都是分片1到分片N.分片無法根據(jù)所在服務(wù)器所有分片的信息來確定自身是否是主節(jié)點(diǎn),本方法指定選舉策略.

根據(jù)每個(gè)分片的注冊(cè)順序以及該服務(wù)器中其他先注冊(cè)的分片的主從情況來確定自身是否是主節(jié)點(diǎn).具體選舉策略如圖4.

該策略中每臺(tái)服務(wù)器的各個(gè)分片按名字大小依次進(jìn)行注冊(cè)式選舉[10],如果之前完成注冊(cè)的分

片中沒有已經(jīng)確定了的主節(jié)點(diǎn),則自身可以成為確定主節(jié)點(diǎn);否則,僅能成為暫時(shí)主節(jié)點(diǎn),允許其他服務(wù)器對(duì)應(yīng)的分片進(jìn)行主節(jié)點(diǎn)的替換.各分片類型說明如表2.

圖4 搜索引擎集群主從節(jié)點(diǎn)選舉(M=N)流程圖Figure 4 Election of master-slave node for search engine cluster flowchart (M=N)

通過在zookeeper上增加服務(wù)器管理目錄,保證每個(gè)分片在M

改進(jìn)后的zookeeper管理目錄如圖5.

表2 各分片類型說明

圖5 改進(jìn)后的zookeeper管理目錄

2 實(shí) 驗(yàn)

本實(shí)驗(yàn)選擇的平臺(tái)為一個(gè)服務(wù)器集群,hadoop版本為2.6,節(jié)點(diǎn)數(shù)為從3個(gè)連續(xù)地增加到15;其中一個(gè)節(jié)點(diǎn)為namenode(Active)節(jié)點(diǎn),另外一個(gè)namenode為Standby狀態(tài),并且設(shè)置一個(gè)節(jié)點(diǎn)作為resourcemanager,整體上實(shí)現(xiàn)高可用HA(High Availability).同時(shí)為了減少因?yàn)橥ㄐ抛枞鴰淼挠绊?所有的節(jié)點(diǎn)都部署在一個(gè)機(jī)架內(nèi).

下面給出了在運(yùn)用主從節(jié)點(diǎn)選舉算法進(jìn)行控制集群的情況,展示其在HA和容災(zāi)恢復(fù)時(shí)的使用效果.在本zookeeper的集群中,設(shè)置一個(gè)leader節(jié)點(diǎn),其他的節(jié)點(diǎn)均為follower;停掉leader,然后從follower中選舉出一個(gè)新的leader.在測(cè)試過程中,以復(fù)制模式運(yùn)行zookeeper,每次測(cè)試時(shí),人為地宕掉leader節(jié)點(diǎn),通過測(cè)試其恢復(fù)時(shí)間以展示本算法的性能.一臺(tái)服務(wù)器宕機(jī)后,容災(zāi)重建的時(shí)間對(duì)比如圖6.

圖6 容災(zāi)重建時(shí)間對(duì)比示意圖Figure 6 Comparison time of schematic disaster reconstruction

從實(shí)驗(yàn)結(jié)果可以看出,在follower節(jié)點(diǎn)數(shù)較少的情況下,傳統(tǒng)的主從節(jié)點(diǎn)選舉算法重建時(shí)間較短;但是,隨著集群規(guī)模的不斷擴(kuò)大,改進(jìn)后的算法優(yōu)勢(shì)突出.這是由于改進(jìn)后的zookeeper管理目錄增加了服務(wù)器向zookeeper注冊(cè)的步驟,導(dǎo)致額外的通信時(shí)間.總的時(shí)間損耗包括注冊(cè)時(shí)間和選舉時(shí)間,在節(jié)點(diǎn)數(shù)少時(shí)注冊(cè)時(shí)間對(duì)總體性能影響較明顯.但是在大規(guī)模節(jié)點(diǎn)場(chǎng)景下,這些注冊(cè)損耗跟選舉時(shí)間相比,幾乎可以忽略不計(jì).結(jié)果證明,本算法在大規(guī)模集群具有很好的適應(yīng)性,符合現(xiàn)在生產(chǎn)環(huán)境的現(xiàn)實(shí)需求.

3 結(jié) 語

本方法通過提出一種主從節(jié)點(diǎn)選舉算法,保證了搜索引擎服務(wù)器集群的性能負(fù)載盡量處于均衡狀態(tài).當(dāng)出現(xiàn)集群中某臺(tái)服務(wù)器宕機(jī)的情況時(shí)能自動(dòng)實(shí)現(xiàn)主從節(jié)點(diǎn)的切換,并且在該服務(wù)器恢復(fù)正常工作時(shí)恢復(fù)負(fù)載均衡，同時(shí)達(dá)到合理利用每臺(tái)服務(wù)器的性能,充分發(fā)揮集群的性能優(yōu)勢(shì)[11]的目的.

[1] 廖鋒,成靜靜.大數(shù)據(jù)環(huán)境下Hadoop分布式系統(tǒng)的研究與設(shè)計(jì)[J].廣東通信技術(shù),2013(10):22-27. LIAO Feng, CHENG Jingjing. Research and design of hadoop in the big data environment of distributed systems[J].Guangdong Communication Technology,2013(10):22-27.

[2] 王俊生,施運(yùn)梅,張仰森.基于Hadoop的分布式搜索引擎關(guān)鍵技術(shù)[J].北京信息科技大學(xué)學(xué)報(bào):自然科學(xué)版,2011(4):53-56. WANG Junsheng, SHI Yunmei, ZHANG Yangsen. Key technologies of distributed search engine based on hadoop[J].Journal of Beijing Information Science and Technology University: Natural Science Edtion,2011(4):53-56.

[3] LI Yong, FENG Dan, SHI Zhan, et al. A probability based load balancing algorithm for parallel file systems[J].Journal of the Chinese Institute of Engineers,2015,38(6):811-820.

[4] AHN T, SANDU A, WATSON L,et al. A framework to analyze the performance of load balancing schemes for Ensembles of stochastic simulations[J].International Journal of Parallel Programming,2015,43(4):597-630.

[5] SKEIRIK S, BOBBA RB, MESEGUER J. Formal analysis of fault-tolerant group key management using zookeeper[C]//Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing(CCGrid). Delft, Nederland: IEEE,2013:636-641.

[6] CANINO W, POWELL D. Formal behavioral evaluation of enrichment programs on a zookeeper’s schedule:a case study with a polar bear(Ursus Maritimus) at the Bronx Zoo[J].Zoo Biology,2010,29(4): 503-508.

[7] 離汝光,趙俊.基于ZooKeeper的分布式緩存的設(shè)計(jì)與實(shí)現(xiàn)[J].綿陽師范學(xué)院學(xué)報(bào),2011(11):116-119. LI Ruguang, ZHAO Jun. Design and implementation of distributed caching based zookeeper[J].Journal of Mianyang Normal University,2011(11):116-119.

[8] 杜麗娟,余鎮(zhèn)危.分布式超級(jí)節(jié)點(diǎn)選舉算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(14):4-6. DU Lijuan, YU Zhenwei. Algorithm for distributed super-node election[J].Computer Engineering and Applications,2011,47(14):4-6.

[9] 張洪,路松峰,趙友橋,等.數(shù)據(jù)安全存儲(chǔ)的分片策略模型研究[J].計(jì)算機(jī)工程與應(yīng)用,2012(18):66-70. ZHANG Hong, LU Songfeng, ZHAO Youqiao, et al. Research on file-slice model for data security storage[J].Computer Engineering and Applications,2012,48(18):66-70.

[10] 王濟(jì)勇,林濤,王金東,等.EDF調(diào)度算法搶占行為的研究及其改進(jìn)[J].電子學(xué)報(bào),2004(1):64-68. WANG Jiyong, LIN Tao, WANG Jindong, et al. Research on preemptions of preemptive EDF and improvement on its performance[J].Acta Electionica Sinica,2004(1):64-68.

[11] 諶超,強(qiáng)保華,石龍.基于Hadoop MapReduce的大規(guī)模數(shù)據(jù)索引構(gòu)建與集群性能分析[J].桂林電子科技大學(xué)學(xué)報(bào),2012(4):307-312. CHEN Chao, QIANG Baohua, SHI Lon. Large scale data index construction and cluster efficiency analysis based on Hadoop MapReduce[J].Journal of Guilin University of Electronic Technology,2012(4):307-312.

A master-slave election algorithm for load balancing clusters

REN Lele, HE Lingmin

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

With the increasing amount of data, distributed search engines appeared to meet the need of big data retrieval performance. The existing master-slave node election strategy leaded to the imbalance of query performance due to uneven node distributions. To solve this problem, we proposed a master-slave election strategy based on search engine clusters.When a server was down,a main node was switched to guarantee the effectiveness of the retrieval. And when the broken server was back online again, the distribution of the master-slave node also came to normal.Thus,the defect of load unbalance was avoided.At the same time,every server was used reasonably and we could take full advantage of the clusters.

cluster; master-slave algorithm; load balancing; disaster recovery

1004-1540(2015)03-0341-06

10.3969/j.issn.1004-1540.2015.03.017

2015-05-19 《中國(guó)計(jì)量學(xué)院學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

任樂樂(1993- )，女，山西省長(zhǎng)治人，碩士研究生，主要研究方向?yàn)榇髷?shù)據(jù).E-mail:1192695818@qq.com 通訊聯(lián)系人：何靈敏，男，副教授.E-mail:helm@cjlu.edu.cn

TP317

A