基于一致性哈希算法的云存儲服務(wù)器容錯性研究

摘 要：HDFS架構(gòu)下的云環(huán)境服務(wù)器擁有成本低、易擴(kuò)展、傳輸效率高等諸多優(yōu)點(diǎn)，但節(jié)點(diǎn)選擇策略易造成存儲負(fù)載不均，從而影響系統(tǒng)性能，針對這一問題，結(jié)合一致性哈希算法，綜合多個因素，提出了一種服務(wù)器改進(jìn)方案，用以緩解中小企業(yè)服務(wù)器端壓力。

關(guān)鍵詞：云存儲；負(fù)載均衡；節(jié)點(diǎn)分配；哈希環(huán)

中圖分類號：TP333

隨著近年來網(wǎng)絡(luò)應(yīng)用的不斷擴(kuò)充，網(wǎng)絡(luò)數(shù)據(jù)交換量正在迅猛增長，作為網(wǎng)絡(luò)服務(wù)提供方，Web服務(wù)器承受著龐大的數(shù)據(jù)流壓力。Web服務(wù)器和數(shù)據(jù)庫服務(wù)器的反應(yīng)速度一再成為阻礙網(wǎng)絡(luò)通信發(fā)展的難題，大量數(shù)據(jù)流請求使得數(shù)據(jù)庫服務(wù)器必須盡快提供數(shù)據(jù)處理服務(wù)。由于硬件和操作系統(tǒng)等軟件的原因，當(dāng)大量的訪問到達(dá)時，服務(wù)器不能夠及時處理所有的請求，造成應(yīng)答延遲。盡管計算機(jī)學(xué)術(shù)界已提出使用各項(xiàng)算法實(shí)現(xiàn)負(fù)載均衡（Load Balancing）與虛擬服務(wù)器集群等技術(shù)用以解決該問題，但仍存在諸多弊端，如DNS負(fù)載均衡技術(shù)無法按照Web服務(wù)器的處理能力分配負(fù)載，可靠性不強(qiáng)，集群服務(wù)器的高成本與能量消耗問題。隨著Google推出云計算[1]概念，大量云計算中心在各地落成，云存儲[2]成為一種新興的網(wǎng)絡(luò)服務(wù)器技術(shù)，在實(shí)際應(yīng)用中，結(jié)合云存儲的處理特點(diǎn)，使用Hadoop搭載平臺，合理利用一致性哈希算法（Consistent hashing），可以較好的解決上述問題。

1 云存儲與負(fù)載均衡機(jī)制

1.1 云存儲的特點(diǎn)

作為云計算的延伸，云存儲采用基于對象存儲[3-5]的分布式非對稱架構(gòu)，是一個具有高可靠性、高性能、高擴(kuò)展性的分布式存儲系統(tǒng)，能提供高吞吐量的數(shù)據(jù)訪問、在線存儲和在線備份。其應(yīng)用前景十分廣闊，云存儲系統(tǒng)的體系架構(gòu)如圖1所示。

圖1

除此之外，云存儲還擁有易操作性，后臺對用戶透明等特點(diǎn)，用戶只需通過Web-based應(yīng)用程序，即可上網(wǎng)直接存取數(shù)據(jù)，實(shí)時面對需求。從廣義講，任何基于Web的服務(wù)都可稱之為云服務(wù)。

由于云計算采用分布式存儲方式來存儲數(shù)據(jù)，需要將分布式應(yīng)用部署到大型廉價集群上，從而實(shí)現(xiàn)對海量數(shù)據(jù)信息的存儲，所以從本質(zhì)上講，云存儲仍是一種基于服務(wù)器集群模式的系統(tǒng)模型，稱之為云存儲模型[6]。

1.2 云存儲的負(fù)載均衡機(jī)制

在云存儲環(huán)境中，存儲設(shè)備數(shù)量龐大并多分布在不同的地域，如何實(shí)現(xiàn)多臺設(shè)備間的存儲虛擬化管理、最優(yōu)化利用存儲節(jié)點(diǎn)，使各服務(wù)器有效協(xié)同提供服務(wù)，便成了云存儲發(fā)展環(huán)節(jié)中的重中之重。

在云存儲模型中，云存儲可將工作量均勻分配到不同的存儲服務(wù)器上，避免個別存儲服務(wù)器因工作負(fù)荷過大造成瓶頸，使存儲系統(tǒng)能夠發(fā)揮最大效能。

2 一致性哈希算法在云存儲中的應(yīng)用

2.1 服務(wù)器分布式緩存問題

由于云存儲可以看做網(wǎng)格計算演化，可伸縮性強(qiáng)，所以能夠隨機(jī)應(yīng)變的提供資源與服務(wù)，利用這點(diǎn)構(gòu)建相對平衡的系統(tǒng)，需要每個節(jié)點(diǎn)參與管理，而如何才能結(jié)合現(xiàn)有算法，實(shí)現(xiàn)平衡穩(wěn)定的服務(wù)器模式呢？

舉例說明，假設(shè)有虛擬服務(wù)器M臺，需要映射對象OBJ至M臺存儲上，一般來講，我們會采用hash（OBJ）%M的方法計算OBJ的hash值，然后將其均勻映射給N個存儲，此為正常狀況。

而在實(shí)際應(yīng)用中，我們需要考慮，當(dāng)服務(wù)器訪問量加重時，需要添加存儲設(shè)備，此時公式演變?yōu)閔ash（OBJ）%（M-1）。

而當(dāng)其中一臺服務(wù)器N失效，此時映射至服務(wù)器N的對象失效，公式即演變?yōu)閔ash（OBJ）%（M-1）。

在實(shí)際應(yīng)用中，一旦出現(xiàn)如上情況，服務(wù)器的存儲分配機(jī)制就會全部失效，龐大的信息流將直接沖擊后臺服務(wù)器，造成嚴(yán)重后果。

為避免這種事故，需要hash結(jié)果保證原有已分配的內(nèi)容不被映射至舊緩沖集合中的其他緩沖區(qū)，上面提到的簡單hash算法顯然無法滿足單調(diào)性要求。

2.2 一致性哈希算法的應(yīng)用原理

一致性哈希算法（Consistent Hashing）最早在David Karger，Eric Lehman等人的論文中被提出，是當(dāng)前較主流的分布式哈希表協(xié)議之一，對簡單哈希算法進(jìn)行了修正。

透過一致性哈希，我們可以實(shí)現(xiàn)處理服務(wù)器的選擇不再僅僅依賴key的hash本身，而是將服務(wù)實(shí)例（節(jié)點(diǎn)）的配置也進(jìn)行hash運(yùn)算。

首先我們求出各服務(wù)節(jié)點(diǎn)的hash，將其配置到一個0～2^23的圓環(huán)（continuum）區(qū)間上。其次使用同樣的方法求出你所需要存儲的key的hash，也將其配置到這個圓環(huán)（continuum）上。然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的第一個服務(wù)節(jié)點(diǎn)上。如果超過2^32仍然找不到服務(wù)節(jié)點(diǎn)，將會保存至第一個memcached服務(wù)節(jié)點(diǎn)上，數(shù)據(jù)圖例如下：

圖2

當(dāng)服務(wù)節(jié)點(diǎn)增加時：

圖3

一致性哈希算法最大程度的避免了key在服務(wù)節(jié)點(diǎn)列表上的重新分布，其他附帶的改進(jìn)就是有的一致性哈希算法還增加了虛擬服務(wù)節(jié)點(diǎn)的方法，也就是一個服務(wù)節(jié)點(diǎn)在環(huán)上有多個映射點(diǎn)，這樣就能抑制分布不均勻，最大限度地減少服務(wù)節(jié)點(diǎn)增減時的緩存重新分布。實(shí)際應(yīng)用中能取得較好效果。

2.3 基于MD5調(diào)用hash部分的實(shí)現(xiàn)（Java版本）

/**

* Calculates the ketama hash value for a string

* @param s

* @return

*/

public static Long md5HashingAlg（String key） {

if（md5==1） {

try {

md5 = MessageDigest.getInstance（\"MD5\"）；

catch （NoSuchAlgorithmException e） {

log.error（ \"++++ no md5 algorythm found\" ）；

throw new IllegalStateException（ \"++++ no md5 algorythm found\"）；

md5.reset（）；

md5.update（key.getBytes（））；

byte[] bKey = md5.digest（）；

long res = （（long）（bKey[3]0xFF） << 24） | （（long）（bKey[2]0xFF） << 16） | （（long）（bKey[1]0xFF） << 8） | （long）（bKey[0]0xFF）；

return res；

3 結(jié)束語

本文針對云環(huán)境下服務(wù)器易發(fā)生的失效問題，運(yùn)用一致性哈希算法 ，將對象映射至哈?？臻g，從而使容錯性得到提升，使其在調(diào)用模式下，一旦一臺服務(wù)器失效，則受影響的數(shù)據(jù)僅僅是失效服務(wù)器與其環(huán)空間中前一臺服務(wù)器間數(shù)據(jù)，其余服務(wù)器不受影響。目前針對云存儲的研究仍處于起步階段，隨著研究的深入，傳統(tǒng)存儲技術(shù)勢必會被云存儲技術(shù)取代，云存儲的應(yīng)用將日益普遍。

參考文獻(xiàn)：

[1]趙培.云計算技術(shù)及其應(yīng)用[J].中興通訊技術(shù)，2010（04）：11.

[2]郭凌翔.淺談云存儲及其安全性[J].福建電腦，2010（05）：3.

[3]MesnierM，G anger G R，RidelE.Object based storage[J].IEEE Com，2003，15（04）：84.

[4]Sakar K.An analysis of object storage architecture[J].IEEE Comp，2003，2（03）：23.

[5]王紅艷，薛智峰.一種新型的面向?qū)ο蟠鎯ξ募到y(tǒng)[J].高性能計算技術(shù)，2006（02）：45.

[6]張建勛，古志民，鄭超.云計算研究進(jìn)展綜述[J].計算機(jī)應(yīng)用研究，2010，27（02）：429-433.

作者簡介：于亞舟（1993-），男，黑龍江人，學(xué)士學(xué)位，研究方向：物聯(lián)網(wǎng)云存儲技術(shù)方向；滕海坤（1983-），男，黑龍江人，講師，碩士研究生，研究方向：嵌入式系統(tǒng)。

作者單位：黑河學(xué)院計算機(jī)科學(xué)與信息工程系，黑龍江黑河 164300