基于二次映射的哈希負(fù)載均衡方法

王永亮

（華為軟件技術(shù)有限公司南京研究所江蘇南京 210012）

1 引言

在互聯(lián)網(wǎng)應(yīng)用中，面對(duì)海量的數(shù)據(jù)，通常采用分布式集群服務(wù)器進(jìn)行數(shù)據(jù)存儲(chǔ)，不可避免的面臨集群服務(wù)器之間的負(fù)載均衡問(wèn)題。同時(shí)集群服務(wù)器之間可能是異構(gòu)的，更是增加了負(fù)載均衡的難度，本文描述一種基于二次映射的哈希(Hash)負(fù)載均衡方法，能夠很好的支持同構(gòu)或者異構(gòu)的存儲(chǔ)服務(wù)器集群的負(fù)載均衡。

2 基于二次映射的哈希負(fù)載均衡設(shè)計(jì)

負(fù)載均衡策略分為靜態(tài)負(fù)載均衡策略和動(dòng)態(tài)負(fù)載均衡策略，靜態(tài)負(fù)載均衡策略實(shí)現(xiàn)簡(jiǎn)單、方便，如果規(guī)劃設(shè)計(jì)合理就能達(dá)到良好的效果；動(dòng)態(tài)負(fù)載均衡策略根據(jù)系統(tǒng)的負(fù)載情況動(dòng)態(tài)的進(jìn)行調(diào)整，較靈活，但是實(shí)現(xiàn)復(fù)雜。

由于存儲(chǔ)系統(tǒng)涉及到數(shù)據(jù)的增刪改查，服務(wù)器集群各個(gè)節(jié)點(diǎn)有狀態(tài)、不對(duì)等，因此存儲(chǔ)系統(tǒng)的負(fù)載均衡算法和普通的無(wú)狀態(tài)的集群負(fù)載均衡算法不同；在存儲(chǔ)系統(tǒng)中，較廣泛使用哈希算法對(duì)數(shù)據(jù)請(qǐng)求進(jìn)行靜態(tài)負(fù)載均衡，這種方式能解決大多數(shù)的問(wèn)題，但是在服務(wù)器集群擴(kuò)容或者縮容時(shí)，通常需要進(jìn)行大量的數(shù)據(jù)遷移；并且難以適應(yīng)服務(wù)器異構(gòu)的情況；一致性哈希算法是對(duì)普通哈希算法的改進(jìn)，在擴(kuò)容或者縮容時(shí)能較少的進(jìn)行數(shù)據(jù)遷移，但是并不能方便的對(duì)熱點(diǎn)數(shù)據(jù)進(jìn)行精準(zhǔn)的控制，并且如果前期規(guī)劃的數(shù)據(jù)槽位或者哈希函數(shù)的選擇不合理，針對(duì)熱點(diǎn)數(shù)據(jù)的處理會(huì)有極限。

在基于二次映射的哈希負(fù)載均衡算法中，所有的數(shù)據(jù)請(qǐng)求根據(jù)一級(jí)哈希函數(shù)映射到不同的分區(qū)Section，然后對(duì)分區(qū)Section再次進(jìn)行二級(jí)哈希映射，將映射到同一分區(qū)Section的數(shù)據(jù)關(guān)鍵字映射到不同的槽位Slot上；槽位Slot和服務(wù)器Node之間通過(guò)Map表進(jìn)行關(guān)聯(lián)；將數(shù)據(jù)進(jìn)行分區(qū)，各個(gè)分區(qū)互不影響；將同一分區(qū)中的數(shù)據(jù)進(jìn)行分槽位映射，可以針對(duì)數(shù)據(jù)熱點(diǎn)分區(qū)增加槽位；槽位和服務(wù)器節(jié)點(diǎn)進(jìn)行Map映射，可以控制各個(gè)服務(wù)器節(jié)點(diǎn)分配的槽位和槽位數(shù)量。因此此算法可以方便的處理數(shù)據(jù)熱點(diǎn)和負(fù)載不均的問(wèn)題。

2.1 數(shù)據(jù)模型

此算法的數(shù)據(jù)模型如圖2-1所示。

圖2-1 數(shù)據(jù)模型

所有的數(shù)據(jù)請(qǐng)求的key∈U，U=[k1,k2,ki,…,km]，其中m為不同的key的個(gè)數(shù)；請(qǐng)求數(shù)據(jù)key與分區(qū)Section的關(guān)系為：j=H1(ki)，其中j∈[0,n]，i∈[0,m]，H1為選定的一級(jí)Hash函數(shù)，j為第j個(gè)分區(qū)Section，ki為第i個(gè)key；

每個(gè)分區(qū)映射到多個(gè)槽位Slot，設(shè)第j個(gè)分區(qū)section映射到p個(gè)槽位上，數(shù)據(jù)key與槽位Slot的關(guān)系為：u=H2j(Kij)其中u為第j個(gè)分區(qū)的第u個(gè)槽位Slot，kij滿足j = H1(kii)，H2j為分區(qū)j選定的二級(jí)Hash函數(shù)；

一級(jí)Hash函數(shù)和各個(gè)分區(qū)的二級(jí)Hash可以從某一全域Hash函數(shù)族中隨機(jī)選擇，這樣可以確保在二級(jí)Hash后減少Hash沖突。

服務(wù)器節(jié)點(diǎn)Node與槽位Slot的關(guān)系為Map表映射，可人為配置或者自動(dòng)配置，類(lèi)似如表2-1所示。不同分區(qū)的槽位可以映射到相同的服務(wù)器節(jié)點(diǎn)。

表2-1 數(shù)據(jù)槽位和服務(wù)器節(jié)點(diǎn)配置樣例表

2.2 服務(wù)器節(jié)點(diǎn)的擴(kuò)容和縮容

在系統(tǒng)設(shè)計(jì)完成并上線運(yùn)行后，隨著在線數(shù)據(jù)量及業(yè)務(wù)請(qǐng)求量的增加或者減少，根據(jù)服務(wù)器負(fù)載情況，需要對(duì)服務(wù)器集群進(jìn)行擴(kuò)容或者縮容。

數(shù)據(jù)單個(gè)分區(qū)對(duì)應(yīng)的槽位在系統(tǒng)設(shè)計(jì)時(shí)可能無(wú)法準(zhǔn)確的進(jìn)行評(píng)估，隨著系統(tǒng)數(shù)據(jù)量的增多和數(shù)據(jù)請(qǐng)求量的不均衡，在服務(wù)器節(jié)點(diǎn)之間會(huì)出現(xiàn)負(fù)載不均衡的問(wèn)題；此時(shí)需要對(duì)高負(fù)載的服務(wù)器節(jié)點(diǎn)進(jìn)行數(shù)據(jù)槽位遷出，將多余的槽位遷出都其他負(fù)載低的服務(wù)器節(jié)點(diǎn)或新增服務(wù)器節(jié)點(diǎn)上；在遷移數(shù)據(jù)槽位都無(wú)法均衡各個(gè)服務(wù)器的負(fù)載的時(shí)候，就需要增加熱點(diǎn)數(shù)據(jù)對(duì)應(yīng)分區(qū)的槽位個(gè)數(shù)；由于各個(gè)分區(qū)獨(dú)立，因此單個(gè)分區(qū)槽位的增加并不會(huì)影響其他分區(qū)的數(shù)據(jù)，達(dá)到了較少遷移數(shù)據(jù)的目的。

服務(wù)器存儲(chǔ)的數(shù)據(jù)減少后，為了節(jié)省成本通常會(huì)選擇對(duì)服務(wù)器集群進(jìn)行縮容；此時(shí)針對(duì)數(shù)據(jù)減少的分區(qū)，減少服務(wù)器節(jié)點(diǎn)數(shù)量，將減少的服務(wù)器節(jié)點(diǎn)上的對(duì)應(yīng)的槽位遷移到剩余的對(duì)應(yīng)分區(qū)的服務(wù)器節(jié)點(diǎn)上即可。不會(huì)影響到其他數(shù)據(jù)槽位和其他分區(qū)。

3 實(shí)驗(yàn)結(jié)果

采用此負(fù)載均衡算法進(jìn)行了模擬實(shí)驗(yàn)，實(shí)驗(yàn)場(chǎng)景如下：

（1）使用隨機(jī)數(shù)產(chǎn)生負(fù)載請(qǐng)求數(shù)據(jù)；

（2）從全域Hash函數(shù)族中選擇一個(gè)一次Hash函數(shù)作為從數(shù)據(jù)key到分區(qū)Section的映射；

（3）從全域Hash函數(shù)族中選擇一個(gè)二次Hash函數(shù)作為各個(gè)分區(qū)數(shù)據(jù)到對(duì)應(yīng)分區(qū)槽位Slot的映射；

（4）配置各個(gè)分區(qū)Section的槽位Slot到服務(wù)器節(jié)點(diǎn)Node的對(duì)應(yīng)關(guān)系。

實(shí)驗(yàn)?zāi)M結(jié)束后，各個(gè)數(shù)據(jù)的分布如圖3-1所示；各個(gè)服務(wù)器節(jié)點(diǎn)的數(shù)據(jù)負(fù)載分布如圖3-2所示。

圖3-1 數(shù)據(jù)分布

圖3-2 服務(wù)器節(jié)點(diǎn)數(shù)據(jù)負(fù)載分布

從實(shí)驗(yàn)結(jié)果可以得出，基于二級(jí)映射的哈希負(fù)載均衡算法可以較好的完成服務(wù)器節(jié)點(diǎn)間的負(fù)載均衡。

4 總結(jié)

在海量存儲(chǔ)系統(tǒng)中，通常需要集群服務(wù)器進(jìn)行存儲(chǔ)，為了均衡各個(gè)服務(wù)器之間的負(fù)載，需要考慮選擇對(duì)應(yīng)的負(fù)載均衡算法，本文提出了一種基于二次映射的哈希負(fù)載均衡算法，能夠很好的完成在服務(wù)器節(jié)點(diǎn)間的負(fù)載均衡，并能方便的解決數(shù)據(jù)熱點(diǎn)和服務(wù)器的擴(kuò)容、縮容，為存儲(chǔ)系統(tǒng)的負(fù)載均衡提供了新的思路和方法。