王 康，李東靜，陳海光

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234；2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

分布式存儲(chǔ)系統(tǒng)中改進(jìn)的一致性哈希算法

王 康1，李東靜2，陳海光1

(1.上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海 200234；2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

隨著網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)的發(fā)展，分布式存儲(chǔ)中的數(shù)據(jù)均勻分布和高效定位的問題越來越備受關(guān)注?，F(xiàn)存的關(guān)于分布式系統(tǒng)的數(shù)據(jù)分布的可靠性和可用性等方面并不能得到有效的保證。文中提出了一種改進(jìn)的一致性哈希算法，通過對Redis存儲(chǔ)節(jié)點(diǎn)進(jìn)行邏輯劃分成一個(gè)組，組內(nèi)采用主從的模式提高了分布式存儲(chǔ)的一致性和可靠性，并分析了同一個(gè)組內(nèi)不同讀寫策略的數(shù)據(jù)一致性。經(jīng)過實(shí)驗(yàn)比較，該算法能有效地降低系統(tǒng)平均響應(yīng)時(shí)間，提高系統(tǒng)吞吐量，使分布式存儲(chǔ)系統(tǒng)負(fù)載更為均衡。當(dāng)組內(nèi)主節(jié)點(diǎn)宕機(jī)時(shí)，利用從節(jié)點(diǎn)的備份數(shù)據(jù)以及主從切換可以及時(shí)對外提供集群服務(wù)，這一點(diǎn)有助于實(shí)際的研發(fā)分布式存儲(chǔ)。

分布式存儲(chǔ)；數(shù)據(jù)讀寫策略；Redis；一致性哈希

0 引 言

所謂分布式存儲(chǔ)系統(tǒng)[1]，就是將數(shù)據(jù)分散存儲(chǔ)在多臺(tái)獨(dú)立的設(shè)備上。隨著網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展，個(gè)人用戶、互聯(lián)網(wǎng)應(yīng)用等產(chǎn)生了海量的數(shù)據(jù)。爆炸式增長的數(shù)據(jù)已經(jīng)從PB級向EB級邁進(jìn)，這些數(shù)據(jù)的存儲(chǔ)和高速訪問對分布式存儲(chǔ)系統(tǒng)在可用性、可擴(kuò)展性以及IO訪問性能上提出了新的挑戰(zhàn)。隨著數(shù)據(jù)規(guī)模的擴(kuò)大，使得存儲(chǔ)系統(tǒng)需要不斷動(dòng)態(tài)擴(kuò)大存儲(chǔ)規(guī)模，并且存儲(chǔ)系統(tǒng)必須能夠支持新的存儲(chǔ)節(jié)點(diǎn)不斷加入，保證數(shù)據(jù)在各個(gè)存儲(chǔ)節(jié)點(diǎn)的均勻分布。然而這些數(shù)據(jù)目前集中部署在單節(jié)點(diǎn)存儲(chǔ)設(shè)備上，隨著數(shù)據(jù)規(guī)模的擴(kuò)大，將會(huì)導(dǎo)致單臺(tái)主機(jī)的資源(如內(nèi)存、磁盤IO)不能很好地滿足海量級數(shù)據(jù)。由于后續(xù)擴(kuò)容成本非常昂貴，因此迫切需要引入分布式存儲(chǔ)系統(tǒng)來解決大數(shù)據(jù)的存放和訪問問題。

如何最大限度地提高分布式存儲(chǔ)系統(tǒng)的存儲(chǔ)能力、可靠性，使數(shù)據(jù)均勻分布，在分布式存儲(chǔ)領(lǐng)域已經(jīng)成為一個(gè)急需解決的問題。

文中主要以Redis內(nèi)存數(shù)據(jù)庫為例，針對分布式存儲(chǔ)系統(tǒng)對一致性哈希算法展開研究。主要是對已有的一致性哈希算法進(jìn)行改進(jìn)，通過將Redis存儲(chǔ)節(jié)點(diǎn)進(jìn)行邏輯劃分成一個(gè)組，組內(nèi)采用主從模式可以提高分布式存儲(chǔ)的一致性和可靠性，并分析了同一個(gè)組內(nèi)不同讀寫策略的數(shù)據(jù)一致性。

1 基礎(chǔ)知識(shí)

1.1 相關(guān)工作

哈希的英文名字為Hash，意思為散列，它將任意長度的輸入值通過散列算法，變換成固定長度的輸出值。這個(gè)值就是散列值，即哈希值。哈希算法的方式有很多，在分布式存儲(chǔ)系統(tǒng)中主要是對文件名和路徑進(jìn)行哈希，決定數(shù)據(jù)的分布策略。目前廣為流行的有經(jīng)典的一致性哈希算法、字符串哈希算法、MD4、MD5、SHA-1、Davies-Meyer等。

文獻(xiàn)[2]提出了一致性哈希算法，現(xiàn)在在分布式系統(tǒng)中應(yīng)用非常廣泛。一致性哈希算法在移除或者添加一個(gè)服務(wù)器時(shí)，能夠盡可能小地改變已存在的服務(wù)請求與處理請求服務(wù)器之間的映射關(guān)系。常用的字符串哈希算法有BKDRHash[3]、APHash、DJBHash、JSHash等。MD4算法是哈希算法中較為成熟的算法之一。MD4算法[4]可以對任意長度不超過264的消息進(jìn)行處理，生成一個(gè)128 bit的哈希值。消息在處理前，首先要進(jìn)行填充，保證MD填充后的bit位長度是512 bit的整數(shù)倍。填充結(jié)束后，利用迭代結(jié)構(gòu)和壓縮函數(shù)來順序處理每個(gè)512 bit的消息分組。MD5算法[5]是MD4算法的升級版。在MD5算法中，原始消息的預(yù)處理操作和MD4是完全相同的，都需要進(jìn)行補(bǔ)位、補(bǔ)位長度操作，它們的信息摘要的大小都是128 bit。MD5在MD4的基礎(chǔ)上加入了第四輪的計(jì)算模式，每一步驟都是一一對應(yīng)的固定值，改進(jìn)了MD4在第二輪、第三輪計(jì)算中的漏洞，完善了訪問輸入分組的次序，從而減小其對稱性和相同性。

SHA-1算法[6]是在MD5算法基礎(chǔ)上發(fā)展而來的，其主要功能是從輸入長度不大于264bit的明文消息中得到長度為160 bit的摘要值。該算法通過計(jì)算明文信息得到固定長度的信息摘要，只要原始信息改變，摘要也隨之發(fā)生改變，而且變化很大。這種發(fā)散性可以檢測數(shù)據(jù)的完整性，因此SHA-1算法在數(shù)字簽名中有著廣泛的應(yīng)用。Davies-Meyer算法[7-9]是基于對稱分組算法的單向散列算法。分組算法在設(shè)計(jì)和實(shí)現(xiàn)上成本較低，可以構(gòu)建一個(gè)基于該分組密碼的哈希函數(shù)。

1.2 內(nèi)存數(shù)據(jù)庫Redis

Redis是一個(gè)開源的key-value存儲(chǔ)系統(tǒng)，它通常被稱為數(shù)據(jù)結(jié)構(gòu)服務(wù)器，因?yàn)閗ey可以包含字符串、哈希、鏈表、集合和有序集合。Redis支持存儲(chǔ)的Value類型很多，包括string(字符串)、list(鏈表)、set(集合)、sorted set(有序集合)。這些數(shù)據(jù)類型都支持push/pop、add/remove以及取交集和并集及更豐富的操作，Redis支持各種不同方式的排序。為了保證效率，數(shù)據(jù)都是緩存在內(nèi)存中，它也可以周期性地把更新的數(shù)據(jù)寫入磁盤或者把修改操作寫入追加的記錄文件(相當(dāng)于log文件)。

Redis對不同數(shù)據(jù)類型的操作是自動(dòng)的，因此設(shè)置或增加key值，從一個(gè)集合中增加或者刪除一個(gè)元素都能安全的操作。其支持簡單而快速的主從復(fù)制，官網(wǎng)提供了一個(gè)數(shù)據(jù)，slave在21 s即完成了對Amazon網(wǎng)站10 G key set的復(fù)制[10]。目前全球最大的Redis用戶是新浪微博。在新浪有200多臺(tái)物理機(jī)，400多個(gè)端口正在運(yùn)行著Redis，有超過4G的數(shù)據(jù)在Redis上來為微博用戶提供服務(wù)。Redis的應(yīng)用場景有很多，例如取最新N個(gè)數(shù)據(jù)操作、取TopN操作、需要精確設(shè)定過期時(shí)間的應(yīng)用、計(jì)數(shù)器應(yīng)用、獲取某段時(shí)間所有數(shù)據(jù)排重值、實(shí)時(shí)系統(tǒng)、反垃圾系統(tǒng)等等。Redis具有速度快、持久化等特點(diǎn)，因此在文中用Redis存儲(chǔ)節(jié)點(diǎn)作為實(shí)驗(yàn)部分的環(huán)境。

2 算法的基本思想與提出

2.1 問題描述

在分布式存儲(chǔ)系統(tǒng)中，往往將一臺(tái)服務(wù)器或者服務(wù)器上運(yùn)行的一個(gè)進(jìn)程稱為一個(gè)節(jié)點(diǎn)[11-13]。如果有N個(gè)數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，那么如何將一個(gè)鍵(key)映射到N個(gè)存儲(chǔ)節(jié)點(diǎn)(按0～N-1編號(hào))上，通用方法是計(jì)算對象的Hash值，然后均勻地映射到N個(gè)存儲(chǔ)節(jié)點(diǎn)。

Hash(key)%N一切都運(yùn)行正常，但是要考慮兩種情況：

(1)一個(gè)存儲(chǔ)節(jié)點(diǎn)m宕機(jī)了(在實(shí)際應(yīng)用中必須要考慮這種情況)，則所有映射到節(jié)點(diǎn)m的鍵都會(huì)失效。因此需要把存儲(chǔ)節(jié)點(diǎn)m移除,此時(shí)節(jié)點(diǎn)個(gè)數(shù)為N-1，映射公式變成了Hash(key)%(N-1)。

(2)由于數(shù)據(jù)量增大訪問加重，需要添加服務(wù)器存儲(chǔ)節(jié)點(diǎn)，此時(shí)服務(wù)器是N+1臺(tái)，映射公式變成了Hash(key)%(N+1)。

在上面兩種情況下，突然之間幾乎所有的服務(wù)器存儲(chǔ)節(jié)點(diǎn)都失效了，對于服務(wù)器而言這是一場災(zāi)難。整個(gè)系統(tǒng)數(shù)據(jù)對象的映射位置都需要重新進(jìn)行計(jì)算，系統(tǒng)無法對外界訪問進(jìn)行正常響應(yīng)，導(dǎo)致系統(tǒng)處于崩潰狀態(tài)，那么系統(tǒng)的可靠性和可用性就降低了。增刪存儲(chǔ)節(jié)點(diǎn)會(huì)導(dǎo)致同一個(gè)key，在讀寫操作時(shí)分配不到數(shù)據(jù)真正存儲(chǔ)的存儲(chǔ)節(jié)點(diǎn)，命中率會(huì)急劇下降。

一個(gè)設(shè)計(jì)良好的分布式哈希策略應(yīng)該具有良好的單調(diào)性和可靠性、可用性，即服務(wù)器存儲(chǔ)節(jié)點(diǎn)的增刪或宕機(jī)不會(huì)造成大量哈希重定位。基于以上原因，文中提出了一種改進(jìn)的一致性哈希算法來有效解決單調(diào)性和可靠性、可用性等問題。

2.2 改進(jìn)的一致性哈希算法

一致性哈希算法是一種分布式算法，在分布式存儲(chǔ)中做數(shù)據(jù)分布時(shí)比較常用，Memcached client也選擇這種算法，解決將key-value均勻分布到眾多Memcached server上的問題。該算法實(shí)現(xiàn)思路如下：

首先求出每個(gè)存儲(chǔ)節(jié)點(diǎn)的哈希值，并將其配置到一個(gè)0～232-1(哈希值是一個(gè)32位的無符號(hào)整型)的圓環(huán)區(qū)間上。其次使用同樣的方法求出所需要存儲(chǔ)的鍵的哈希，也將其配置到這個(gè)圓環(huán)上。然后從數(shù)據(jù)映射到的位置開始順時(shí)針查找，將數(shù)據(jù)映射到找到的第一個(gè)存儲(chǔ)節(jié)點(diǎn)上。如果超過232仍然找不到存儲(chǔ)節(jié)點(diǎn)，就會(huì)映射到第一個(gè)存儲(chǔ)節(jié)點(diǎn)上。

當(dāng)該存儲(chǔ)節(jié)點(diǎn)所在的服務(wù)器宕機(jī)或者網(wǎng)絡(luò)異常時(shí)，客戶端將無法連接，導(dǎo)致系統(tǒng)服務(wù)處于不可用狀態(tài)。一種改進(jìn)性方案是采用Master-Slave的方式對存儲(chǔ)節(jié)點(diǎn)邏輯劃分成一個(gè)存儲(chǔ)節(jié)點(diǎn)Group組，對應(yīng)于物理上的一個(gè)主存儲(chǔ)節(jié)點(diǎn)和N個(gè)從存儲(chǔ)節(jié)點(diǎn)，其中從節(jié)點(diǎn)是對主節(jié)點(diǎn)的數(shù)據(jù)復(fù)制。以Redis存儲(chǔ)節(jié)點(diǎn)為例，改進(jìn)后哈希存儲(chǔ)方案就會(huì)變成主從方式，節(jié)點(diǎn)映射時(shí)將映射至邏輯上的Group。例如，當(dāng)在同一個(gè)Group內(nèi)配置一個(gè)master節(jié)點(diǎn)、一個(gè)slave節(jié)點(diǎn)，這時(shí)當(dāng)master節(jié)點(diǎn)宕機(jī)時(shí)，通過Redis哨兵(Sentinel)檢測到并及時(shí)進(jìn)行故障恢復(fù)(failover)，將slave節(jié)點(diǎn)替換為master節(jié)點(diǎn)及時(shí)對外提供不間斷服務(wù)。

改進(jìn)后的一致性哈希算法具體實(shí)現(xiàn)過程如下：

(1)圓環(huán)、Group數(shù)據(jù)結(jié)構(gòu)選擇及初始化。以Java語言為例，圓環(huán)可以用TreeMap數(shù)據(jù)結(jié)構(gòu)來模擬，因?yàn)門reeMap中所有的元素都保持著某種固定的順序，而且在這個(gè)環(huán)中節(jié)點(diǎn)之間是存在順序關(guān)系的，所以TreeMap的key必須實(shí)現(xiàn)Comparator接口，這樣易于讀取指定哈希值范圍的子環(huán)。Group的定義為：

publicclassGroup{privateNodemaster;privateListslaves;}

其中，Node表示一個(gè)存儲(chǔ)節(jié)點(diǎn)：publicclassNode{privateStringhost;privateintport= 6379;//redis默認(rèn)端口privateJedisPoolpool;//Jedis連接池，通過JedisAPI鏈接Redis數(shù)據(jù)庫}。

為此，定義TreeMapketamaNodes。在這個(gè)MAP中，鍵存節(jié)點(diǎn)組的哈希值，值存節(jié)點(diǎn)組的信息對象。例如，有4個(gè)節(jié)點(diǎn)組GroupA、B、C、D在圓環(huán)ketamaNodes初始化。

(2)通過鍵的哈希值獲取Group算法實(shí)現(xiàn)。首先定義一個(gè)字節(jié)數(shù)組digest，其存放key的MD5信息摘要以及一個(gè)Long類型的鍵key。然后計(jì)算這個(gè)digest摘要的哈希值Hash，判斷圓環(huán)ketamaNodes中是否存在這個(gè)哈希值Hash，如果存在則key的值為Hash，返回key的Croup，否則返回大于這個(gè)哈希值Hash的子MaptailMap。如果tailMap為空，則key為圓環(huán)的第一個(gè)key，否則返回key的值為ailMap的第一個(gè)key。過程如算法1所示。要存儲(chǔ)鍵k1～k9經(jīng)過哈希計(jì)算后在環(huán)空間上的位置如圖1所示：k1～k2映射至GroupA,k3～k4映射至GroupB，k5～k8映射至GroupC,k9映射至GroupD。

算法1：通過鍵的哈希值獲取Group算法實(shí)現(xiàn)(Java版本)

publicGroupgetPrimary(finalStringk) {/* 通過鍵獲取Group*/

byte[]digest=computeMD5(k);//計(jì)算這個(gè)key的MD5信息摘要

longhash=hash(digest);//得到這個(gè)摘要的哈希值

if(!ketamaNodes.containsKey(key)) {//如果找到這個(gè)節(jié)點(diǎn)，直接取節(jié)點(diǎn)，返回

SortedMaptailMap=ketamaNodes.tailMap(key);//得到大于當(dāng)前key的那個(gè)子Map

if(tailMap.isEmpty()){key=ketamaNodes.firstKey();}//如果子Map為空，則返回圓環(huán)的第一個(gè)key

else{key=tailMap.firstKey();}}//然后從中取出第一個(gè)key，就是大于且離它最近的那個(gè)key

returnketamaNodes.get(key);}//返回這個(gè)key的Group

圖1 k1～k9經(jīng)過哈希計(jì)算后的空間示意圖

2.2.1 存儲(chǔ)節(jié)點(diǎn)增刪

如果只是在同一個(gè)Group內(nèi)增加或刪除一個(gè)從存儲(chǔ)節(jié)點(diǎn)，則不需要做任何變動(dòng)，只是同一個(gè)Group內(nèi)節(jié)點(diǎn)數(shù)增多了，還是正常讀寫。如果是主存儲(chǔ)節(jié)點(diǎn)宕機(jī)(刪除)則通過故障轉(zhuǎn)移機(jī)制(如Redis的failover)選舉出一個(gè)主節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的讀寫。如果增加或刪除一個(gè)存儲(chǔ)節(jié)點(diǎn)組，則受影響的數(shù)據(jù)僅僅是新存儲(chǔ)節(jié)點(diǎn)組到其環(huán)空間中前一個(gè)存儲(chǔ)節(jié)點(diǎn)組之間的數(shù)據(jù)，其他不會(huì)受到影響。增加一個(gè)GroupE之后，之前的9個(gè)數(shù)據(jù)k1～k9受影響的有k5、k6，如圖2(a)所示，刪除一個(gè)GroupB之后受影響的只有節(jié)點(diǎn)組k3、k4，如圖2(b)所示。

(a)增加一個(gè)Group E后的圓環(huán)空間 (b)刪除一個(gè)Group B后的圓環(huán)空間

2.2.2 數(shù)據(jù)傾斜問題

一致性哈希算法具有隨機(jī)性。當(dāng)存儲(chǔ)節(jié)點(diǎn)組數(shù)量較少時(shí)節(jié)點(diǎn)在環(huán)上分布不夠均勻，會(huì)使得部分節(jié)點(diǎn)組分布的數(shù)據(jù)量較少，部分節(jié)點(diǎn)組分布的數(shù)據(jù)明顯增多的情況[14]。為解決這個(gè)問題，提出了基于虛擬節(jié)點(diǎn)的改進(jìn)算法。其核心思路是引入虛擬節(jié)點(diǎn)，每個(gè)虛擬節(jié)點(diǎn)都有一個(gè)對應(yīng)的物理存儲(chǔ)節(jié)點(diǎn)，而每個(gè)物理存儲(chǔ)節(jié)點(diǎn)可以對應(yīng)若干個(gè)虛擬節(jié)點(diǎn)。引入“虛擬節(jié)點(diǎn)”后，映射關(guān)系就從對{數(shù)據(jù)->節(jié)點(diǎn)}轉(zhuǎn)換到了{(lán)數(shù)據(jù)->虛擬節(jié)點(diǎn)}。

下面介紹引入虛擬機(jī)節(jié)點(diǎn)之后，圓環(huán)TreeMap的初始化算法過程，如算法2所示。

首先定義存儲(chǔ)節(jié)點(diǎn)組列表的集合nodes，虛擬節(jié)點(diǎn)個(gè)數(shù)numReps初始化為160，定義一個(gè)TreeMap類型的圓環(huán)ketamaNodes。對于所有Group，生成numReps個(gè)虛擬組節(jié)點(diǎn)，將16字節(jié)的數(shù)組每四個(gè)字節(jié)一組,分別對應(yīng)一個(gè)虛擬節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)組的信息摘要。對于每四個(gè)字節(jié)，組成一個(gè)long值數(shù)值，作為這個(gè)虛擬節(jié)點(diǎn)在環(huán)中的唯一key。然后計(jì)算這個(gè)存儲(chǔ)節(jié)點(diǎn)列表中每個(gè)節(jié)點(diǎn)組的信息摘要對應(yīng)哈希值Hash，將這個(gè)節(jié)點(diǎn)對應(yīng)的哈希值及Group放入圓環(huán)中，最后返回這個(gè)圓環(huán)的ketamaNodes。

算法2：Group在環(huán)形上的初始化過程(Java版本)

publicTreeMapKetamaGroupLocator(Listnodes,intnumReps) {//Group列表及虛擬節(jié)點(diǎn)個(gè)數(shù)

privateTreeMapketamaNodes=newTreeMap();//定義圓環(huán)ketamaNodes

for(Groupnode:nodes) {//對于所有Group，生成numReps個(gè)虛擬組節(jié)點(diǎn)

for(inti=0;i

byte[]digest=computeMd5(node.getGroupName() +i)//計(jì)算節(jié)點(diǎn)組的信息摘要

for(inth=0;h<4;h++) { //對于每四個(gè)字節(jié)，組成一個(gè)long值數(shù)值，作為這個(gè)虛擬節(jié)點(diǎn)的在環(huán)中的唯一key.

longm=hash(digest,h);//計(jì)算這個(gè)節(jié)點(diǎn)組信息摘要的哈希值

ketamaNodes.put(m,node);}} //這個(gè)節(jié)點(diǎn)對應(yīng)的哈希值及Group放入圓環(huán)中

returnketamaNodes}//返回這個(gè)圓環(huán)ketamaNodes

2.2.3Group內(nèi)數(shù)據(jù)讀寫策略

當(dāng)一個(gè)客戶端請求的key經(jīng)過改進(jìn)的一致性哈希映射到一個(gè)Group，由于同一個(gè)Group內(nèi)是采用主從復(fù)制的方式來保證可用性。在讀寫策略中，使用master和slaves來表達(dá)主從關(guān)系。于是就產(chǎn)生了同一個(gè)Group內(nèi)主存儲(chǔ)節(jié)點(diǎn)與從存儲(chǔ)節(jié)點(diǎn)之間讀寫策略方式：

方式1：master-only策略。讀寫操作都在主節(jié)點(diǎn)，毫無疑問，這種方式一致性無法得以保證。

方式2：master-first-slaves-async策略。寫策略：先寫主節(jié)點(diǎn)，然后異步同步到從節(jié)點(diǎn)。讀策略：可以讀取任何節(jié)點(diǎn)。這種策略是弱一致性的體現(xiàn)，在從節(jié)點(diǎn)未及時(shí)同步時(shí)也會(huì)無法保證數(shù)據(jù)一致性，一般適合寫操作頻繁的服務(wù)，節(jié)點(diǎn)掛掉時(shí)最近的數(shù)據(jù)容易丟失。數(shù)據(jù)可靠性中，主備切換可能丟失數(shù)據(jù)，對于一個(gè)key可能存在不同值。

方式3：master-first-slaves-sync策略。先主節(jié)點(diǎn)然后同步更新到從節(jié)點(diǎn)。寫策略：多數(shù)節(jié)點(diǎn)寫入成功。讀策略：讀取多數(shù)節(jié)點(diǎn)，并進(jìn)行一致性驗(yàn)證。寫入時(shí)在半數(shù)以上拷貝寫成功時(shí)即返回請求。讀寫數(shù)據(jù)時(shí)都有特定提供服務(wù)的備份。備份掛掉半數(shù)以下時(shí)不會(huì)發(fā)生數(shù)據(jù)丟失，掛掉半數(shù)以上一般集群會(huì)選擇進(jìn)入安全模式(如NameNode的安全模式一樣，進(jìn)入后進(jìn)行數(shù)據(jù)復(fù)制檢查)。容災(zāi)時(shí)，需要各備份間互補(bǔ)數(shù)據(jù)，以防止不一致性，這個(gè)流程會(huì)花費(fèi)一定時(shí)間，可根據(jù)需求決定彼此間是否繼續(xù)提供服務(wù)，容災(zāi)結(jié)束后保證數(shù)據(jù)一致。這種方式數(shù)據(jù)可靠性高，主備切換不丟失數(shù)據(jù)。

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

3.1 實(shí)驗(yàn)環(huán)境

服務(wù)器配置為內(nèi)存64 G、硬盤7 T、CPU為4核*4線程1 596 MHz、網(wǎng)絡(luò)為1個(gè)1 000 M網(wǎng)卡，所用的操作系統(tǒng)為CentOS 6.4。在4臺(tái)服務(wù)器上，分別部署2～4個(gè)Redis節(jié)點(diǎn)組，在組內(nèi)采用1主1從結(jié)構(gòu),啟用Redis數(shù)據(jù)庫自有的復(fù)制Replication機(jī)制(需要配置節(jié)點(diǎn)間的主從關(guān)系)。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 可靠性測試

通過對1 000萬條KV數(shù)據(jù)進(jìn)行客戶端讀寫操作，在不同場景下進(jìn)行節(jié)點(diǎn)故障測試來驗(yàn)證。分布式Redis集群的可靠性實(shí)驗(yàn)結(jié)果如表1所示。

結(jié)果表明，有讀寫請求下，由于主從切換有一定的延遲，主節(jié)點(diǎn)故障會(huì)丟失部分?jǐn)?shù)據(jù)，以及沒有從節(jié)點(diǎn)的節(jié)點(diǎn)組也會(huì)丟失數(shù)據(jù)，重啟后恢復(fù)正常，因此需要一主多從的模式來保障整個(gè)Redis集群的可靠性。

表1 Group組內(nèi)存儲(chǔ)節(jié)點(diǎn)的可靠性測試結(jié)果匯總

3.2.2 性能測試

衡量系統(tǒng)性能好壞的一個(gè)重要指標(biāo)就是系統(tǒng)的吞吐量，有時(shí)候人們也常稱為TPS(Transactions Per Second，單位時(shí)間內(nèi)系統(tǒng)發(fā)生的事務(wù)數(shù))。在研究一致性哈希算法的過程中，通過性能測試來測試分布式存儲(chǔ)系統(tǒng)的TPS峰值。

圖3 不同Group組數(shù)集群TPS性能對比圖

1 000萬個(gè)請求,數(shù)據(jù)大小為32 B時(shí)進(jìn)行高并發(fā)測試。當(dāng)進(jìn)行set操作，增加一個(gè)節(jié)點(diǎn)時(shí)，寫操作的吞吐量提升了30%、讀操作的吞吐量提升了50%。通過集群節(jié)點(diǎn)的增加，讀寫性能都有提升。另外，讀操作的性能要明顯好于寫操作，結(jié)果如圖3所示。同樣，可以明顯看出，當(dāng)集群內(nèi)增加節(jié)點(diǎn)組時(shí)，讀寫操作的平均響應(yīng)時(shí)間都有所縮短，在10 ms以內(nèi)符合預(yù)期，結(jié)果如圖4所示。

圖4 不同Group組數(shù)集群數(shù)據(jù)讀寫操作平均響應(yīng)時(shí)間對比

3.2.3 分布平均性測試

當(dāng)集群的節(jié)點(diǎn)組數(shù)為2個(gè)或3個(gè)，進(jìn)行寫操作1 000萬次時(shí)，進(jìn)行數(shù)據(jù)庫寫操作驗(yàn)證，測試結(jié)果如圖5所示。

圖5 數(shù)據(jù)均勻性分布

當(dāng)采用2個(gè)節(jié)點(diǎn)組時(shí)，Group內(nèi)寫入的數(shù)據(jù)量分別占51%、49%，采用3個(gè)節(jié)點(diǎn)組時(shí)，Group內(nèi)寫入的數(shù)據(jù)量分別占36%、32%、32%。節(jié)點(diǎn)組之間數(shù)據(jù)分布相對比較均勻，避免了數(shù)據(jù)傾斜問題的發(fā)生。

4 結(jié)束語

文中對分布式存儲(chǔ)領(lǐng)域的技術(shù)展開了研究，簡單介紹了Redis數(shù)據(jù)庫及分布式系統(tǒng)的CAP理論，詳細(xì)說明了普通哈希算法的不足之處。提出基于Group方式對物理上的存儲(chǔ)節(jié)點(diǎn)進(jìn)行邏輯劃分，改進(jìn)的一致性哈希算法提高了分布式存儲(chǔ)系統(tǒng)的可靠性、可用性，并以Redis數(shù)據(jù)為例進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過增加存儲(chǔ)節(jié)點(diǎn)組大大提高了集群的系統(tǒng)負(fù)載。

[1] 陸嘉恒.分布式系統(tǒng)及云計(jì)算概論[M].北京:清華大學(xué)出版社,2013.

[2] Devine R.Design and implementation of DDH:a distributed dynamic hashing algorithm[M]//Foundations of data organization and algorithms.Berlin:Springer,1993:101-114.

[3] Kernighan B W,Ritchie D M.The C programming language[M].[s.l.]:Prentice Hall,1988:36-40.

[4] Rivest R L.The MD4 message digest algorithm[C]//Proc of CRYPT0’90.[s.l.]:[s.n.],1991:303-311.

[5] Rivest R.The MD5 message-digest algorithm[S].[s.l.]:IETF,1992.

[6] 張紹蘭.幾類密碼Hash函數(shù)的設(shè)計(jì)和安全性分析[D].北京:北京郵電大學(xué),2011.

[7] Winternitz R S.A secure one-way hash function built from DES[C]//Proc of IEEE symposium on security and privacy.[s.l.]:IEEE Computer Society,1984:88-88.

[8] 余秦勇,陳 林,童 斌.一種無中心的云存儲(chǔ)架構(gòu)分析[J].通信技術(shù),2012,45(8):123-126.

[9] 李 正.雜湊函數(shù)結(jié)構(gòu)研究現(xiàn)狀及新的結(jié)構(gòu)設(shè)計(jì)[D].濟(jì)南:山東大學(xué),2010.

[10] 姜大光,奚加鵬.分布式存儲(chǔ)系統(tǒng)(OceanStore)的復(fù)制策略[J].計(jì)算機(jī)工程與科學(xué),2008,30(8):144-146.

[11] 楊彧?jiǎng)?林 波.分布式存儲(chǔ)系統(tǒng)中一致性哈希算法的研究[J].電腦知識(shí)與技術(shù),2011,7(22):5295-5296.

[12] 趙 飛,蘇 忠.一致性哈希算法在數(shù)據(jù)庫集群上的拓展應(yīng)用[J].成都信息工程學(xué)院學(xué)報(bào),2015,30(1):52-58.

[13] 郭 寧，張 新.一致性哈希算法在多處理機(jī)進(jìn)程分配的應(yīng)用[J].計(jì)算機(jī)與現(xiàn)代化,2013(9):71-74.

[14] 周 瑜.一種基于一致性hash算法存儲(chǔ)資源的方法:CN,CN 103281358 A[P].2013.

An Improved Consistent Hashing Algorithm in Distributed Storage System

WANG Kang1,LI Dong-jing2,CHEN Hai-guang1

(1.College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China;2.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

With the development of the network storage system,the problem of normal distribution and efficient locating in the distributed storage is more concerned.The existing reliability and availability of distributed data distribution cannot be effectively guaranteed,therefore an improved consistency hash algorithm is presented.By dividing the nodes into a group,the Redis storage can improve the consistency and reliability of the distributed storage,and analyze the data consistency of different reading and writing strategies in the same group.It is verified in the experiment the algorithm can decrease the average response time effectively and raise the throughput,which makes the distributed storage system more balanced.When the group in the main node downtime,the slave node data backup and master-slave switching can timely provide the cluster service to external,which is helpful for the actual development of distributed storage.

distributed storage;data reading and writing strategy;Redis;consistent hashing

2015-11-03

2016-03-04

時(shí)間：2016-06-22

國家自然科學(xué)基金青年基金(41301407)；上海市教育創(chuàng)新項(xiàng)目(09YZ154，09YZ247)；上海師范大學(xué)基金項(xiàng)目(A-3101-12-004005)；南京航空航天大學(xué)研究生創(chuàng)新基地開放基金(kfjj20151607)

王 康(1988-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘；陳海光，副教授，碩導(dǎo)，研究方向?yàn)閿?shù)據(jù)挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0845.046.html

TP301

A

1673-629X(2016)07-0024-06

10.3969/j.issn.1673-629X.2016.07.006