分布式存儲系統中改進的一致性哈希算法

王 康，李東靜，陳海光

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

分布式存儲系統中改進的一致性哈希算法

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

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

隨著網絡存儲系統的發展，分布式存儲中的數據均勻分布和高效定位的問題越來越備受關注。現存的關于分布式系統的數據分布的可靠性和可用性等方面并不能得到有效的保證。文中提出了一種改進的一致性哈希算法，通過對Redis存儲節點進行邏輯劃分成一個組，組內采用主從的模式提高了分布式存儲的一致性和可靠性，并分析了同一個組內不同讀寫策略的數據一致性。經過實驗比較，該算法能有效地降低系統平均響應時間，提高系統吞吐量，使分布式存儲系統負載更為均衡。當組內主節點宕機時，利用從節點的備份數據以及主從切換可以及時對外提供集群服務，這一點有助于實際的研發分布式存儲。

分布式存儲；數據讀寫策略；Redis；一致性哈希

0 引 言

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

如何最大限度地提高分布式存儲系統的存儲能力、可靠性，使數據均勻分布，在分布式存儲領域已經成為一個急需解決的問題。

文中主要以Redis內存數據庫為例，針對分布式存儲系統對一致性哈希算法展開研究。主要是對已有的一致性哈希算法進行改進，通過將Redis存儲節點進行邏輯劃分成一個組，組內采用主從模式可以提高分布式存儲的一致性和可靠性，并分析了同一個組內不同讀寫策略的數據一致性。

1 基礎知識

1.1 相關工作

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

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

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

1.2 內存數據庫Redis

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

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

2 算法的基本思想與提出

2.1 問題描述

在分布式存儲系統中，往往將一臺服務器或者服務器上運行的一個進程稱為一個節點[11-13]。如果有N個數據存儲節點，那么如何將一個鍵(key)映射到N個存儲節點(按0～N-1編號)上，通用方法是計算對象的Hash值，然后均勻地映射到N個存儲節點。

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

(1)一個存儲節點m宕機了(在實際應用中必須要考慮這種情況)，則所有映射到節點m的鍵都會失效。因此需要把存儲節點m移除,此時節點個數為N-1，映射公式變成了Hash(key)%(N-1)。

(2)由于數據量增大訪問加重，需要添加服務器存儲節點，此時服務器是N+1臺，映射公式變成了Hash(key)%(N+1)。

在上面兩種情況下，突然之間幾乎所有的服務器存儲節點都失效了，對于服務器而言這是一場災難。整個系統數據對象的映射位置都需要重新進行計算，系統無法對外界訪問進行正常響應，導致系統處于崩潰狀態，那么系統的可靠性和可用性就降低了。增刪存儲節點會導致同一個key，在讀寫操作時分配不到數據真正存儲的存儲節點，命中率會急劇下降。

一個設計良好的分布式哈希策略應該具有良好的單調性和可靠性、可用性，即服務器存儲節點的增刪或宕機不會造成大量哈希重定位?；谝陨显颍闹刑岢隽艘环N改進的一致性哈希算法來有效解決單調性和可靠性、可用性等問題。

2.2 改進的一致性哈希算法

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

首先求出每個存儲節點的哈希值，并將其配置到一個0～232-1(哈希值是一個32位的無符號整型)的圓環區間上。其次使用同樣的方法求出所需要存儲的鍵的哈希，也將其配置到這個圓環上。然后從數據映射到的位置開始順時針查找，將數據映射到找到的第一個存儲節點上。如果超過232仍然找不到存儲節點，就會映射到第一個存儲節點上。

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

改進后的一致性哈希算法具體實現過程如下：

(1)圓環、Group數據結構選擇及初始化。以Java語言為例，圓環可以用TreeMap數據結構來模擬，因為TreeMap中所有的元素都保持著某種固定的順序，而且在這個環中節點之間是存在順序關系的，所以TreeMap的key必須實現Comparator接口，這樣易于讀取指定哈希值范圍的子環。Group的定義為：

publicclassGroup{privateNodemaster;privateListslaves;}

其中，Node表示一個存儲節點：publicclassNode{privateStringhost;privateintport= 6379;//redis默認端口privateJedisPoolpool;//Jedis連接池，通過JedisAPI鏈接Redis數據庫}。

為此，定義TreeMapketamaNodes。在這個MAP中，鍵存節點組的哈希值，值存節點組的信息對象。例如，有4個節點組GroupA、B、C、D在圓環ketamaNodes初始化。

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

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

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

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

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

if(!ketamaNodes.containsKey(key)) {//如果找到這個節點，直接取節點，返回

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

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

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

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

圖1 k1～k9經過哈希計算后的空間示意圖

2.2.1 存儲節點增刪

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

(a)增加一個Group E后的圓環空間 (b)刪除一個Group B后的圓環空間

2.2.2 數據傾斜問題

一致性哈希算法具有隨機性。當存儲節點組數量較少時節點在環上分布不夠均勻，會使得部分節點組分布的數據量較少，部分節點組分布的數據明顯增多的情況[14]。為解決這個問題，提出了基于虛擬節點的改進算法。其核心思路是引入虛擬節點，每個虛擬節點都有一個對應的物理存儲節點，而每個物理存儲節點可以對應若干個虛擬節點。引入“虛擬節點”后，映射關系就從對{數據->節點}轉換到了{數據->虛擬節點}。

下面介紹引入虛擬機節點之后，圓環TreeMap的初始化算法過程，如算法2所示。

首先定義存儲節點組列表的集合nodes，虛擬節點個數numReps初始化為160，定義一個TreeMap類型的圓環ketamaNodes。對于所有Group，生成numReps個虛擬組節點，將16字節的數組每四個字節一組,分別對應一個虛擬節點，計算節點組的信息摘要。對于每四個字節，組成一個long值數值，作為這個虛擬節點在環中的唯一key。然后計算這個存儲節點列表中每個節點組的信息摘要對應哈希值Hash，將這個節點對應的哈希值及Group放入圓環中，最后返回這個圓環的ketamaNodes。

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

publicTreeMapKetamaGroupLocator(Listnodes,intnumReps) {//Group列表及虛擬節點個數

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

for(Groupnode:nodes) {//對于所有Group，生成numReps個虛擬組節點

for(inti=0;i

byte[]digest=computeMd5(node.getGroupName() +i)//計算節點組的信息摘要

for(inth=0;h<4;h++) { //對于每四個字節，組成一個long值數值，作為這個虛擬節點的在環中的唯一key.

longm=hash(digest,h);//計算這個節點組信息摘要的哈希值

ketamaNodes.put(m,node);}} //這個節點對應的哈希值及Group放入圓環中

returnketamaNodes}//返回這個圓環ketamaNodes

2.2.3Group內數據讀寫策略

當一個客戶端請求的key經過改進的一致性哈希映射到一個Group，由于同一個Group內是采用主從復制的方式來保證可用性。在讀寫策略中，使用master和slaves來表達主從關系。于是就產生了同一個Group內主存儲節點與從存儲節點之間讀寫策略方式：

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

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

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

3 實 驗

3.1 實驗環境

服務器配置為內存64 G、硬盤7 T、CPU為4核*4線程1 596 MHz、網絡為1個1 000 M網卡，所用的操作系統為CentOS 6.4。在4臺服務器上，分別部署2～4個Redis節點組，在組內采用1主1從結構,啟用Redis數據庫自有的復制Replication機制(需要配置節點間的主從關系)。

3.2 實驗結果與分析

3.2.1 可靠性測試

通過對1 000萬條KV數據進行客戶端讀寫操作，在不同場景下進行節點故障測試來驗證。分布式Redis集群的可靠性實驗結果如表1所示。

結果表明，有讀寫請求下，由于主從切換有一定的延遲，主節點故障會丟失部分數據，以及沒有從節點的節點組也會丟失數據，重啟后恢復正常，因此需要一主多從的模式來保障整個Redis集群的可靠性。

表1 Group組內存儲節點的可靠性測試結果匯總

3.2.2 性能測試

衡量系統性能好壞的一個重要指標就是系統的吞吐量，有時候人們也常稱為TPS(Transactions Per Second，單位時間內系統發生的事務數)。在研究一致性哈希算法的過程中，通過性能測試來測試分布式存儲系統的TPS峰值。

圖3 不同Group組數集群TPS性能對比圖

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

圖4 不同Group組數集群數據讀寫操作平均響應時間對比

3.2.3 分布平均性測試

當集群的節點組數為2個或3個，進行寫操作1 000萬次時，進行數據庫寫操作驗證，測試結果如圖5所示。

圖5 數據均勻性分布

當采用2個節點組時，Group內寫入的數據量分別占51%、49%，采用3個節點組時，Group內寫入的數據量分別占36%、32%、32%。節點組之間數據分布相對比較均勻，避免了數據傾斜問題的發生。

4 結束語

文中對分布式存儲領域的技術展開了研究，簡單介紹了Redis數據庫及分布式系統的CAP理論，詳細說明了普通哈希算法的不足之處。提出基于Group方式對物理上的存儲節點進行邏輯劃分，改進的一致性哈希算法提高了分布式存儲系統的可靠性、可用性，并以Redis數據為例進行實驗驗證，通過增加存儲節點組大大提高了集群的系統負載。

[1] 陸嘉恒.分布式系統及云計算概論[M].北京:清華大學出版社,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函數的設計和安全性分析[D].北京:北京郵電大學,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] 余秦勇,陳 林,童 斌.一種無中心的云存儲架構分析[J].通信技術,2012,45(8):123-126.

[9] 李 正.雜湊函數結構研究現狀及新的結構設計[D].濟南:山東大學,2010.

[10] 姜大光,奚加鵬.分布式存儲系統(OceanStore)的復制策略[J].計算機工程與科學,2008,30(8):144-146.

[11] 楊彧劍,林 波.分布式存儲系統中一致性哈希算法的研究[J].電腦知識與技術,2011,7(22):5295-5296.

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

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

[14] 周 瑜.一種基于一致性hash算法存儲資源的方法: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

時間：2016-06-22

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

王 康(1988-)，男，碩士研究生，研究方向為數據挖掘；陳海光，副教授，碩導，研究方向為數據挖掘。

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