一種改進(jìn)的分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)動(dòng)態(tài)擴(kuò)展策略*

裴　沛,黃　勇,盧　晨

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

?

一種改進(jìn)的分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)動(dòng)態(tài)擴(kuò)展策略*

裴沛,黃勇,盧晨

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

分布式存儲(chǔ)系統(tǒng)經(jīng)常面臨數(shù)據(jù)的均衡分布和擴(kuò)容問(wèn)題，針對(duì)現(xiàn)有一致性哈希動(dòng)態(tài)擴(kuò)展算法的不足，提出一種基于訪問(wèn)概率的動(dòng)態(tài)擴(kuò)展策略.該策略基于熱點(diǎn)數(shù)據(jù)訪問(wèn)概率大的思想改進(jìn)原算法虛擬節(jié)點(diǎn)的分配方法，能夠有效改善擴(kuò)容后造成請(qǐng)求命中率下降和負(fù)載均衡的問(wèn)題.實(shí)驗(yàn)結(jié)果表明，在系統(tǒng)添加新存儲(chǔ)節(jié)點(diǎn)時(shí)，改進(jìn)策略有效地優(yōu)化了系統(tǒng)的性能，縮短了系統(tǒng)到達(dá)新的負(fù)載平衡狀態(tài)的時(shí)間.

一致性哈希；數(shù)據(jù)存儲(chǔ)；虛擬節(jié)點(diǎn)；概率；負(fù)載均衡

0　引言

隨著互聯(lián)網(wǎng)中數(shù)據(jù)的不斷擴(kuò)大，存儲(chǔ)系統(tǒng)為了滿足業(yè)務(wù)需求必須不斷地動(dòng)態(tài)擴(kuò)展存儲(chǔ)的空間，同時(shí)，還要考慮存儲(chǔ)節(jié)點(diǎn)的突然宕機(jī)或網(wǎng)絡(luò)故障等突發(fā)情況下造成的節(jié)點(diǎn)脫離，可靠的系統(tǒng)設(shè)計(jì)需要確保數(shù)據(jù)在各個(gè)存儲(chǔ)節(jié)點(diǎn)中重新均衡分布，達(dá)到負(fù)載均衡[1].此外，在這些海量數(shù)據(jù)中，存儲(chǔ)系統(tǒng)還需要能夠高效地查找定位到目標(biāo)數(shù)據(jù)或文件，最大限度地縮短平均響應(yīng)時(shí)間，提高系統(tǒng)的吞吐量，也是提高系統(tǒng)性能的關(guān)鍵.學(xué)術(shù)界對(duì)存儲(chǔ)系統(tǒng)的數(shù)據(jù)分布式存儲(chǔ)策略等問(wèn)題已經(jīng)展開(kāi)了深入的研究，如LH*[2]、Consistent Hashing[3]等早期提出的經(jīng)典算法.

一致性哈希算法最初是由麻省理工學(xué)院的Karger等人于1997年提出，設(shè)計(jì)的目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)問(wèn)題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用[3].而隨著互聯(lián)網(wǎng)的快速發(fā)展，分布式存儲(chǔ)系統(tǒng)也得到了更加普及的應(yīng)用，隨后一致性哈希算法也在分布式存儲(chǔ)系統(tǒng)，包括云計(jì)算等平臺(tái)中得到了廣泛的應(yīng)用，如Amazon在2007年發(fā)布的Dynamo[4-5]，Google推出的BigTable和OpenStack中的Swift存儲(chǔ)模塊等.

在分析現(xiàn)有一致性哈希動(dòng)態(tài)擴(kuò)展算法不足的基礎(chǔ)上，筆者提出了一種基于概率的分布式存儲(chǔ)空間擴(kuò)展策略.該策略基于熱點(diǎn)數(shù)據(jù)訪問(wèn)概率大的思想改進(jìn)原算法虛擬節(jié)點(diǎn)的分配方法，能夠有效改善分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)容量擴(kuò)充后造成請(qǐng)求命中率下降的問(wèn)題，同時(shí)也能夠快速地調(diào)整各個(gè)節(jié)點(diǎn)的負(fù)載，提高了系統(tǒng)處理請(qǐng)求的性能.最后利用當(dāng)前主流的分布式緩存系統(tǒng)Memcached[6]進(jìn)行相關(guān)的測(cè)試模擬，驗(yàn)證了該策略的可行性和性能優(yōu)勢(shì).

1　一致性哈希在分布式存儲(chǔ)系統(tǒng)中的應(yīng)用

1.1基本一致性哈希算法的設(shè)計(jì)方案

一致性哈希算法是一種哈希算法，在添加或移除一個(gè)存儲(chǔ)節(jié)點(diǎn)時(shí)，它能夠盡可能小地改變已存在的key映射關(guān)系，盡可能地滿足單調(diào)性的要求.

在該算法中，考慮到通常的哈希算法都是將value映射到一個(gè)32位的key值，也即是0～(232-1)次方的數(shù)值空間，將這個(gè)空間想象成一個(gè)首(0)尾(232-1)相接的圓環(huán)，并把存儲(chǔ)服務(wù)器節(jié)點(diǎn)的某一特殊標(biāo)識(shí)符(唯一即可)通過(guò)hash函數(shù)計(jì)算出的值分布在這個(gè)環(huán)上，如圖1所示：

圖1　一致性哈希算法思想

在執(zhí)行每一次的存儲(chǔ)命令時(shí)，系統(tǒng)將key值通過(guò)相同的hash函數(shù)計(jì)算，將計(jì)算后的哈希值映射到這個(gè)環(huán)上，沿著順時(shí)針的方向查找，找到的第一個(gè)存儲(chǔ)節(jié)點(diǎn)，即為負(fù)責(zé)存儲(chǔ)該條信息的存儲(chǔ)節(jié)點(diǎn).之后，當(dāng)需要獲取該條數(shù)據(jù)時(shí)，由于采用相同的hash函數(shù)，計(jì)算后的哈希值一定也相同，通過(guò)同樣的方法可以找到存儲(chǔ)這條數(shù)據(jù)的節(jié)點(diǎn).

當(dāng)添加存儲(chǔ)服務(wù)器節(jié)點(diǎn)時(shí)，根據(jù)上面講到的映射方法，這時(shí)受影響的將僅僅是新加入的節(jié)點(diǎn)和逆時(shí)針?lè)较蛘业降牡谝粋€(gè)節(jié)點(diǎn)之間的對(duì)象，如圖2，假設(shè)節(jié)點(diǎn)Node5是新加入的存儲(chǔ)服務(wù)器，通過(guò)hash(key1)原本是會(huì)到節(jié)點(diǎn)Node2上取得object1，加入新節(jié)點(diǎn)后沿順時(shí)針?lè)较蛘业降牡谝粋€(gè)存儲(chǔ)節(jié)點(diǎn)變成了節(jié)點(diǎn)Node5，即只有通過(guò)hash函數(shù)映射到節(jié)點(diǎn)Node4和節(jié)點(diǎn)Node5之間的這些數(shù)據(jù)會(huì)受到影響.同理，刪減存儲(chǔ)節(jié)點(diǎn)的情況下也只會(huì)影響到映射在環(huán)上某一段的數(shù)據(jù).

雖然一致性哈希算法盡可能地保證存儲(chǔ)空間發(fā)生變化時(shí)造成的數(shù)據(jù)單調(diào)性，但仍然存在如下問(wèn)題：

1)無(wú)法適應(yīng)節(jié)點(diǎn)的異質(zhì)性.因?yàn)閔ash函數(shù)的隨機(jī)性，存儲(chǔ)節(jié)點(diǎn)和數(shù)據(jù)是隨機(jī)映射在這個(gè)環(huán)上，而各存儲(chǔ)節(jié)點(diǎn)的存儲(chǔ)空間和帶寬等物理因素不盡相同，所以各存儲(chǔ)節(jié)點(diǎn)的負(fù)載可能會(huì)不均衡.

2)當(dāng)存儲(chǔ)節(jié)點(diǎn)比較少時(shí)，新增節(jié)點(diǎn)或刪除節(jié)點(diǎn)時(shí)，受影響的數(shù)據(jù)依然很多.為了解決這些問(wèn)題，引入了虛擬節(jié)點(diǎn)的思想來(lái)彌補(bǔ)這些不足.

圖2　新增加存儲(chǔ)節(jié)點(diǎn)后的變化

1.2基于虛擬節(jié)點(diǎn)的改進(jìn)方案

虛擬節(jié)點(diǎn)的核心思想，即是將環(huán)分成若干等份，每一份對(duì)應(yīng)一個(gè)虛擬節(jié)點(diǎn)，再將虛擬節(jié)點(diǎn)和物理存儲(chǔ)服務(wù)器之間采用多對(duì)一的方式映射關(guān)聯(lián)起來(lái)，這樣就把每個(gè)物理存儲(chǔ)節(jié)點(diǎn)映射分配到了哈希環(huán)的多個(gè)位置上，如圖3所示.

圖3　新增節(jié)點(diǎn)時(shí)虛擬節(jié)點(diǎn)配置的變化

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

2　動(dòng)態(tài)擴(kuò)展存儲(chǔ)空間策略的研究

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

將哈希環(huán)等分成s份.假設(shè)現(xiàn)在有n臺(tái)物理存儲(chǔ)節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)的權(quán)重為wi，則總比重為

那么各個(gè)節(jié)點(diǎn)數(shù)據(jù)負(fù)載的比重為

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

圖4　虛擬節(jié)點(diǎn)同時(shí)映射到兩個(gè)存儲(chǔ)節(jié)點(diǎn)

處理GET請(qǐng)求的部分偽代碼如下：

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　實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)方案

在Java環(huán)境下模擬了采用一致性哈希算法的緩存系統(tǒng)，并依據(jù)筆者提出的策略對(duì)其在存儲(chǔ)節(jié)點(diǎn)列表發(fā)生變化的情況進(jìn)行了測(cè)試.整個(gè)實(shí)驗(yàn)過(guò)程中，初始狀態(tài)設(shè)定的是5個(gè)存儲(chǔ)節(jié)點(diǎn)，10000個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)依據(jù)各個(gè)存儲(chǔ)節(jié)點(diǎn)的權(quán)重分配.通過(guò)隨機(jī)生成100000條字符串作為存儲(chǔ)的數(shù)據(jù)，暫不考慮緩存過(guò)期的問(wèn)題.實(shí)驗(yàn)采用多線程模擬50個(gè)客戶端的并發(fā)訪問(wèn)，在系統(tǒng)穩(wěn)定后，動(dòng)態(tài)加入新的存儲(chǔ)節(jié)點(diǎn)，監(jiān)測(cè)系統(tǒng)對(duì)請(qǐng)求的響應(yīng)情況進(jìn)行分析.

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

實(shí)驗(yàn)結(jié)果如圖5所示，實(shí)線表示的是本文所介紹的算法在動(dòng)態(tài)擴(kuò)展存儲(chǔ)節(jié)點(diǎn)后系統(tǒng)處理請(qǐng)求的數(shù)量，虛線是文中提到的WSDRA算法單位時(shí)間內(nèi)處理響應(yīng)的情況.

圖5　新增節(jié)點(diǎn)后重新平衡性能測(cè)試

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

4　總結(jié)與展望

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

[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] 巴子言, 吳軍, 馬嚴(yán). 基于虛節(jié)點(diǎn)的一致性哈希算法的優(yōu)化[J]. 軟件, 2014, 35(12): 26-29.

[責(zé)任編輯蘇琴]

[責(zé)任校對(duì)黃招揚(yáng)]

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.

廣西高校科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目.

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

TP301.6

A

1673-8462(2016)02-0085-04