一種改進的分布式存儲系統節點動態擴展策略*

裴　沛,黃　勇,盧　晨

(廣西民族大學，信息科學與工程學院，廣西 南寧　530006)

?

一種改進的分布式存儲系統節點動態擴展策略*

裴沛,黃勇,盧晨

(廣西民族大學，信息科學與工程學院，廣西 南寧530006)

分布式存儲系統經常面臨數據的均衡分布和擴容問題，針對現有一致性哈希動態擴展算法的不足，提出一種基于訪問概率的動態擴展策略.該策略基于熱點數據訪問概率大的思想改進原算法虛擬節點的分配方法，能夠有效改善擴容后造成請求命中率下降和負載均衡的問題.實驗結果表明，在系統添加新存儲節點時，改進策略有效地優化了系統的性能，縮短了系統到達新的負載平衡狀態的時間.

一致性哈希；數據存儲；虛擬節點；概率；負載均衡

0　引言

隨著互聯網中數據的不斷擴大，存儲系統為了滿足業務需求必須不斷地動態擴展存儲的空間，同時，還要考慮存儲節點的突然宕機或網絡故障等突發情況下造成的節點脫離，可靠的系統設計需要確保數據在各個存儲節點中重新均衡分布，達到負載均衡[1].此外，在這些海量數據中，存儲系統還需要能夠高效地查找定位到目標數據或文件，最大限度地縮短平均響應時間，提高系統的吞吐量，也是提高系統性能的關鍵.學術界對存儲系統的數據分布式存儲策略等問題已經展開了深入的研究，如LH*[2]、Consistent Hashing[3]等早期提出的經典算法.

一致性哈希算法最初是由麻省理工學院的Karger等人于1997年提出，設計的目標是為了解決因特網中的熱點問題，使得DHT可以在P2P環境中真正得到應用[3].而隨著互聯網的快速發展，分布式存儲系統也得到了更加普及的應用，隨后一致性哈希算法也在分布式存儲系統，包括云計算等平臺中得到了廣泛的應用，如Amazon在2007年發布的Dynamo[4-5]，Google推出的BigTable和OpenStack中的Swift存儲模塊等.

在分析現有一致性哈希動態擴展算法不足的基礎上，筆者提出了一種基于概率的分布式存儲空間擴展策略.該策略基于熱點數據訪問概率大的思想改進原算法虛擬節點的分配方法，能夠有效改善分布式存儲系統的節點容量擴充后造成請求命中率下降的問題，同時也能夠快速地調整各個節點的負載，提高了系統處理請求的性能.最后利用當前主流的分布式緩存系統Memcached[6]進行相關的測試模擬，驗證了該策略的可行性和性能優勢.

1　一致性哈希在分布式存儲系統中的應用

1.1基本一致性哈希算法的設計方案

一致性哈希算法是一種哈希算法，在添加或移除一個存儲節點時，它能夠盡可能小地改變已存在的key映射關系，盡可能地滿足單調性的要求.

在該算法中，考慮到通常的哈希算法都是將value映射到一個32位的key值，也即是0～(232-1)次方的數值空間，將這個空間想象成一個首(0)尾(232-1)相接的圓環，并把存儲服務器節點的某一特殊標識符(唯一即可)通過hash函數計算出的值分布在這個環上，如圖1所示：

圖1　一致性哈希算法思想

在執行每一次的存儲命令時，系統將key值通過相同的hash函數計算，將計算后的哈希值映射到這個環上，沿著順時針的方向查找，找到的第一個存儲節點，即為負責存儲該條信息的存儲節點.之后，當需要獲取該條數據時，由于采用相同的hash函數，計算后的哈希值一定也相同，通過同樣的方法可以找到存儲這條數據的節點.

當添加存儲服務器節點時，根據上面講到的映射方法，這時受影響的將僅僅是新加入的節點和逆時針方向找到的第一個節點之間的對象，如圖2，假設節點Node5是新加入的存儲服務器，通過hash(key1)原本是會到節點Node2上取得object1，加入新節點后沿順時針方向找到的第一個存儲節點變成了節點Node5，即只有通過hash函數映射到節點Node4和節點Node5之間的這些數據會受到影響.同理，刪減存儲節點的情況下也只會影響到映射在環上某一段的數據.

雖然一致性哈希算法盡可能地保證存儲空間發生變化時造成的數據單調性，但仍然存在如下問題：

1)無法適應節點的異質性.因為hash函數的隨機性，存儲節點和數據是隨機映射在這個環上，而各存儲節點的存儲空間和帶寬等物理因素不盡相同，所以各存儲節點的負載可能會不均衡.

2)當存儲節點比較少時，新增節點或刪除節點時，受影響的數據依然很多.為了解決這些問題，引入了虛擬節點的思想來彌補這些不足.

圖2　新增加存儲節點后的變化

1.2基于虛擬節點的改進方案

虛擬節點的核心思想，即是將環分成若干等份，每一份對應一個虛擬節點，再將虛擬節點和物理存儲服務器之間采用多對一的方式映射關聯起來，這樣就把每個物理存儲節點映射分配到了哈希環的多個位置上，如圖3所示.

圖3　新增節點時虛擬節點配置的變化

由于各個存儲服務器的存儲空間，機器性能，網絡帶寬等資源可能是不同的，所以存儲節點負載也是有差異的 .在分配虛擬節點和物理節點的映射關系時，文獻[7]引入了權重.存儲容量和性能較好的節點權重較大，這樣分配的虛擬節點也就越多，相應的，負載的數據也就越多，圖3中Node1與Node3配置相當，Node2次之，Node4最差所分得的虛擬節點也最少.此外，當系統負載不均衡時，可以通過調配虛擬節點與物理節點的映射來達到新的平衡狀態.同理，當添加或刪除物理存儲節點時，根據權重的變化，獲取或釋放虛擬節點即可快速達到負載均衡，如新加入節點時，只需從其他各個節點將部分虛擬節點指向新的節點即可，受影響的只會是映射在這些虛擬節點上的數據，如圖3中新增的Node5節點，配置與Node4相當，從Node1、Node2和Node3中選出虛擬節點M、Q和S指向新節點Node5.

2　動態擴展存儲空間策略的研究

當有新的存儲節點加入或退出時，如果改變節點的分布，將會對現有數據的重新分布造成較大的影響，尤其是數據的遷移工作.所以，一般情況下虛擬節點的數量不會發生變化，主要改變的是虛擬節點和物理存儲服務器的映射關系，這樣對系統整體的改變是最小的，擴展存儲空間時，新加入的物理存儲服務器分配好虛擬節點后，當系統的一個讀請求hash(key)后找到了某個虛擬節點，而該虛擬節點現在指向的是新加入的物理存儲節點，這樣就造成了命中率的下降，所以還需要將映射在這些虛擬節點上的數據從之前的存儲節點遷移到新的物理存儲節點.為了改善系統的命中率和保證系統的數據均衡，筆者提出了一種分布式緩存動態擴展的方法，具體方案如下：

將哈希環等分成s份.假設現在有n臺物理存儲節點，各個節點的權重為wi，則總比重為

那么各個節點數據負載的比重為

雖然理論上數據是隨機映射在哈希環上的，但由于一些具體的實際情況，比如會有部分的熱點數據，對應的虛擬節點的訪問量就會比較高.為了盡量減少對系統響應速度的影響，對這n個物理節點的虛擬節點分別進行排序，優先將熱度較低的虛擬節點釋放給新加入的物理節點，同時保持該虛擬節點與新舊兩個物理存儲節點的映射關系，如圖4所示.當hash(key)后的結果指向了該虛擬節點時，如果是SET請求，將統一把數據SET進新加入的物理節點，如果是GET請求時，通過產生一個隨機數，來判斷具體要到哪個物理存儲節點中獲取數據，評判的標準以這兩個物理節點的比重關系來判斷.當新的節點剛加入時，其所承載的數據比重為0，即GET請求100%的要到之前的節點中獲取數據，并且命中率是100%.獲取數據后返回給客戶端，同時將這條數據遷移到新節點中去，這樣通過概率來判斷存儲節點查找數據的過程最多為兩跳，并且一跳的概率會逐漸增長.而隨著數據的遷移和新數據的SET，新節點中的數據比重在不斷增長，當增長到一定的閥值后再完全釋放掉虛擬節點與舊物理存儲節點之間的映射關系.當所有的虛擬節點都指向一個物理存儲節點時，即系統達到了新的平衡狀態.

圖4　虛擬節點同時映射到兩個存儲節點

處理GET請求的部分偽代碼如下：

if(virtualNode.currentNode.weight>W)

virtualNode.fomerNode=null;

if(virtualNode.fomerNode==null)

return virtualNode.currentNode.get(key);

random=Random(0,1);

if(random

if(virtualNode.currentNode.hasItem(key))

return virtualNode.currentNode.get(key);

}

transList.add(virtualNode,key);

return virtualNode.fomerNode.get(key);

3　實驗結果與分析

3.1實驗方案

在Java環境下模擬了采用一致性哈希算法的緩存系統，并依據筆者提出的策略對其在存儲節點列表發生變化的情況進行了測試.整個實驗過程中，初始狀態設定的是5個存儲節點，10000個虛擬節點，虛擬節點依據各個存儲節點的權重分配.通過隨機生成100000條字符串作為存儲的數據，暫不考慮緩存過期的問題.實驗采用多線程模擬50個客戶端的并發訪問，在系統穩定后，動態加入新的存儲節點，監測系統對請求的響應情況進行分析.

3.2實驗結果分析

實驗結果如圖5所示，實線表示的是本文所介紹的算法在動態擴展存儲節點后系統處理請求的數量，虛線是文中提到的WSDRA算法單位時間內處理響應的情況.

圖5　新增節點后重新平衡性能測試

開始時，系統中包含5個存儲節點，在系統穩定時，動態添加一個新的節點后，由于虛擬節點與存儲節點之間的映射關系發生了變動，直接通過Hash(key)后找到的虛擬節點可能指向了與之前SET數據時不同的存儲節點，兩種算法單位時間內處理的請求數量急劇下滑，然后又都逐漸回升至穩定狀態.由于該算法中動態擴展存儲節點時，虛擬節點映射給新的節點的同時，仍保留與之前節點的映射關系，而隨著新數據的存入和從之前節點轉移過來的數據越來越多，新節點的比重也逐漸增大，所以單位時間內處理的響應請求會逐漸加速回升到之前的穩定狀態，新加入節點和之前的節點達到新的平衡.從圖中可得出結論，該策略較之每次獲取失敗時去查找之前映射關系再來獲取數據的策略具有更好的效果.經過測試，隨著寫數據速度的增加，本文的策略效果會更好.

4　總結與展望

當前，一致性哈希算法已廣泛應用在分布式存儲系統中，而系統存儲節點動態擴展時常常面臨著數據重均衡問題，不少學者也提出了自己的改進策略，文獻[7]提出了虛擬節點的概念，存儲節點的增加或退出只需要修改虛擬節點和物理節點的映射關系.而實際項目中往往都存在有熱點數據，對應的虛擬節點的訪問量就會比較高，筆者提出一種基于訪問概率的適用于異構環境的數據重均衡和遷移的策略.最后通過模擬測試了該方法與WSDRA算法在動態擴展時的表現，驗證了新方法的可行性.如何進一步優化虛擬節點的分配策略和盡可能小的影響到系統對熱點數據的響應情況將是下一步工作的主要內容.

[1] ZENG WENYING, ZHAO YUELONG, OU KAIRI, et al. Research on cloud storage architecture and key technologies [C]// ICIS 09:Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human. New York: ACM, 2009: 1044-1048.

[2] LEWIN W, NEIMAT M-A, SCHNEIDER D A. LH*-A scalable, distributed data structure[J]. ACM Transactions on Database Systems. 1996, 21(4): 480-525

[3] David Karger, Eric Lehman, Tom Leighton, etc. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web[C]∥ In Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), 1997.

[4] Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007[Z].

[5] D. Hastorun, M. Jampani, G. Kakulapati, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. [C]∥In Proceedings of ACM Symposium on Operating Systems Principles (SOSP '07). 2007.

[6] https://github.com/memcached/memcached/wiki[EB/OL].

[7] 巴子言, 吳軍, 馬嚴. 基于虛節點的一致性哈希算法的優化[J]. 軟件, 2014, 35(12): 26-29.

[責任編輯蘇琴]

[責任校對黃招揚]

An Improved Distributed Storage System Dynamic Expansion Strategy

PEI Pei, HUANG Yong, LU Chen

(CollegeofInformationScienceandEngineering,GuangxiUniversityforNationalities,Nanning530006,China)

Distributed storage system often has the problems of balanced distribution and capacity of data. Aiming at the shortcomings of the existing consistency dynamic extension hash algorithm, we proposed a dynamic extension strategy based on access probability. The strategy based on the idea of hot data access probability to improve the distribution method of the original algorithm. And it can effectively improve the problems request shooting falling and load balancing after expansion. Our experiment shows that when the new storage nodes are added in the system, the improvement strategy effectively optimize the performance of the system and shorten the time of rebalancing.

Consistent hashing；Data storage；Virtual node；Probability；Load balancing

2016-03-02.

廣西高校科學技術研究重點項目.

裴沛(1988-)，男，河南洛陽人，廣西民族大學碩士研究生，研究方向：高性能分布式系統.

TP301.6

A

1673-8462(2016)02-0085-04