分布式存儲中數(shù)據(jù)分布策略的分析與研究

龐 慧 陳艷君

(1.河北建筑工程學(xué)院，河北張家口075000;2.北京交通大學(xué)計算機(jī)與信息技術(shù)學(xué)院，北京100000)

0 論文所要解決的問題

分布式存儲系統(tǒng)，就是將數(shù)據(jù)分散存儲在多臺獨(dú)立的設(shè)備上.傳統(tǒng)的網(wǎng)絡(luò)存儲系統(tǒng)采用集中的存儲服務(wù)器存放所有數(shù)據(jù)，存儲服務(wù)器成為系統(tǒng)性能的瓶頸，也是可靠性和安全性的焦點(diǎn)，不能滿足大規(guī)模存儲應(yīng)用的需要.分布式網(wǎng)絡(luò)存儲系統(tǒng)采用可擴(kuò)展的系統(tǒng)結(jié)構(gòu)，利用多臺存儲服務(wù)器分擔(dān)存儲負(fù)荷，利用位置服務(wù)器定位存儲信息，它不但提高了系統(tǒng)的可靠性、可用性和存取效率，還易于擴(kuò)展.

如何才能最大限度地提高分布式存儲系統(tǒng)的容量、可靠性、安全性、數(shù)據(jù)分布、負(fù)載均衡性、可移植性，在數(shù)據(jù)存儲領(lǐng)域中已成為一個急需解決的迫切問題.本課題主要研究合理的分布式存儲管理系統(tǒng)的體系結(jié)構(gòu)，分布式數(shù)據(jù)存儲的數(shù)據(jù)流向與數(shù)據(jù)負(fù)載均衡和系統(tǒng)優(yōu)化等各方面的關(guān)鍵技術(shù).所得結(jié)論使得分布式存儲系統(tǒng)更能適應(yīng)網(wǎng)絡(luò)存儲數(shù)據(jù)的動態(tài)變化，可以更加合理地利用存儲設(shè)備的磁盤資源.有效地調(diào)度系統(tǒng)資源，使服務(wù)器的負(fù)載趨于平衡，使存儲設(shè)備的性能得到充分利用.

1 分布式存儲中數(shù)據(jù)分布策略的分析

1.1 分布式存儲架構(gòu)模型:

整個存儲架構(gòu)可以分成三部分:存儲客戶端、元數(shù)據(jù)服務(wù)器集群以及存儲資源池.其中客戶端內(nèi)嵌入用戶或者存儲應(yīng)用系統(tǒng)內(nèi)部，提供與元數(shù)據(jù)服務(wù)器以及存儲資源池通信的應(yīng)用接口，完成客戶端與存儲系統(tǒng)之間的數(shù)據(jù)交互功能.由于原型系統(tǒng)對于存儲應(yīng)用接口進(jìn)行了封裝，元數(shù)據(jù)服務(wù)器集群以及存儲資源池的底層架構(gòu)以及工作方式對抗上層客戶端是完全透明的，這使得用戶無需考慮底層復(fù)雜的結(jié)構(gòu)特征，利用簡單的接口輕松使用存儲資源，開發(fā)數(shù)據(jù)服務(wù)應(yīng)用.元數(shù)據(jù)服務(wù)器集群用來管理用戶數(shù)據(jù)的元數(shù)據(jù)信息，并且管理數(shù)據(jù)的存放位置以及冗余策略.元數(shù)據(jù)服務(wù)器對用戶提供文件IO，處理來自客戶端的文件級操作，并保存關(guān)鍵的元數(shù)據(jù)信息.存儲資源池由多個存儲節(jié)點(diǎn)構(gòu)成，主要采用對象存儲技術(shù)和分布式的架構(gòu)，完成客戶數(shù)據(jù)的保存，并提供數(shù)據(jù)的容錯，容災(zāi)功能.

海量的網(wǎng)絡(luò)存儲系統(tǒng)必須支持在底層存儲池變動的情況下保持?jǐn)?shù)據(jù)負(fù)載的均衡，數(shù)據(jù)尋址的高效.特別是隨著數(shù)據(jù)量不斷增加，網(wǎng)絡(luò)存儲系統(tǒng)面臨著不斷擴(kuò)展的壓力，對系統(tǒng)的可擴(kuò)展性提出了要求.所以，為了滿足這些技術(shù)需求，網(wǎng)絡(luò)存儲系統(tǒng)需要靈活高效的數(shù)據(jù)分布策略來確保性能.數(shù)據(jù)分配策略是在數(shù)據(jù)與存儲地址之間建立起高效映射關(guān)系的方法，換言之，是將數(shù)據(jù)合理的分配到存儲設(shè)備中，并最大限度地簡化尋址過程，同時確保存儲資源和網(wǎng)絡(luò)資源的合理分配.

1.2 分布式緩存的問題

假設(shè)我們有一個網(wǎng)站，最近發(fā)現(xiàn)隨著流量增加，服務(wù)器壓力越來越大，之前直接讀寫數(shù)據(jù)庫的方式不太合適了，于是我們想引入一種高性能的分布式內(nèi)存對象緩存系統(tǒng)作為緩存機(jī)制.現(xiàn)在我們有兩臺機(jī)器可以作為服務(wù)器，如圖2所示.

很顯然，最簡單的策略是將每一次緩存請求隨機(jī)發(fā)送到一臺服務(wù)器，但是這種策略可能會帶來兩個問題:一是同一份數(shù)據(jù)可能被存在不同的機(jī)器上而造成數(shù)據(jù)冗余，二是有可能某數(shù)據(jù)已經(jīng)被緩存但是訪問卻沒有命中，因?yàn)闊o法保證對相同key的所有訪問都被發(fā)送到相同的服務(wù)器.因此，隨機(jī)策略無論是時間效率還是空間效率都非常不好.

要解決上述問題只需做到如下一點(diǎn):保證對相同key的訪問會被發(fā)送到相同的服務(wù)器.很多方法可以實(shí)現(xiàn)這一點(diǎn)，最常用的方法是計算哈希.例如對于每次訪問，可以按如下算法計算其哈希值:h=Hash(key)%2其中Hash是一個從字符串到正整數(shù)的哈希映射函數(shù).這樣，如果我們將服務(wù)器分別編號為0、1，那么就可以根據(jù)上式和key計算出服務(wù)器編號h，然后去訪問.

這個方法雖然解決了上面提到的兩個問題，但是存在一些其它的問題.如果將上述方法抽象，可以認(rèn)為通過:h=Hash(key)%N這個算式計算每個key的請求應(yīng)該被發(fā)送到哪臺服務(wù)器，其中N為服務(wù)器的臺數(shù)，并且服務(wù)器按照0–(N－1)編號.

這個算法的問題在于容錯性和擴(kuò)展性不好.所謂容錯性是指當(dāng)系統(tǒng)中某一個或幾個服務(wù)器變得不可用時，整個系統(tǒng)是否可以正確高效運(yùn)行;而擴(kuò)展性是指當(dāng)加入新的服務(wù)器后，整個系統(tǒng)是否可以正確高效運(yùn)行.

現(xiàn)假設(shè)有一臺服務(wù)器壞了，那么為了填補(bǔ)空缺，要將壞的服務(wù)器從編號列表中移除，后面的服務(wù)器按順序前移一位并將其編號值減一，此時每個key就要按h=Hash(key)%(N－1)重新計算;同樣，如果新增了一臺服務(wù)器，雖然原有服務(wù)器編號不用改變，但是要按h=Hash(key)%(N+1)重新計算哈希值.因此系統(tǒng)中一旦有服務(wù)器變更，大量的key會被重定位到不同的服務(wù)器從而造成大量的緩存不命中.而這種情況在分布式系統(tǒng)中是非常糟糕的.

一個設(shè)計良好的分布式哈希方案應(yīng)該具有良好的單調(diào)性，即服務(wù)節(jié)點(diǎn)的增減不會造成大量哈希重定位.

1.3 一種改進(jìn)的哈希方案

如果將整個哈希值空間假想成一個虛擬的圓環(huán)，然后將各個服務(wù)器使用H進(jìn)行一個哈希，具體可以選擇服務(wù)器的IP或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中兩臺服務(wù)器使用IP地址哈希后在環(huán)空間的位置如圖3所示:

接下來使用如下算法定位數(shù)據(jù)訪問到相應(yīng)服務(wù)器:將數(shù)據(jù)key使用相同的函數(shù)H計算出哈希值h，通根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時針“行走”，第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器.

例如我們有a、b、c三個數(shù)據(jù)對象，經(jīng)過哈希計算后，在環(huán)空間上的位置如圖4所示:

根據(jù)算法，數(shù)據(jù)a，b會被定為到服務(wù)器1上，c被定為到服務(wù)器2上.現(xiàn)假設(shè)服務(wù)器1壞了:

可以看到此時c不會受到影響，只有a，b節(jié)點(diǎn)被重定位到服務(wù)器2.一般的，在該算法中，如果一臺服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺服務(wù)器之間數(shù)據(jù)，其它不會受到影響.如果我們在系統(tǒng)中增加一臺服務(wù)器3:

此時b，c不受影響，只有a需要重定位到新的服務(wù)器3.一般的，在一致性哈希算法中，如果增加一臺服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺服務(wù)器之間數(shù)據(jù)，其它不會受到影響.

綜上所述，該算法對于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯性和可擴(kuò)展性.但是在服務(wù)器節(jié)點(diǎn)太少時，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問題.例如我們的系統(tǒng)中有兩臺服務(wù)器，其環(huán)分布如圖7所示:

此時必然造成大量數(shù)據(jù)集中到服務(wù)器2上，而只有極少量會定位到服務(wù)器1上.為了解決這種數(shù)據(jù)傾斜問題，上述算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對每一個服務(wù)節(jié)點(diǎn)計算多個哈希，每個計算結(jié)果位置都放置一個此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn).具體做法可以在服務(wù)器IP或主機(jī)名的后面增加編號來實(shí)現(xiàn).例如上面的情況，我們決定為每臺服務(wù)器計算三個虛擬節(jié)點(diǎn)，于是可以分別計算“服務(wù)器1.1”、“服務(wù)器1.2”、“服務(wù)器 1.3”、“服務(wù)器 2.1”、“服務(wù)器 2.2”、“服務(wù)器2.3”的哈希值，于是形成六個虛擬節(jié)點(diǎn):

同時數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射，例如定位到“服務(wù)器1.1”、“服務(wù)器1.2”、“服務(wù)器1.3”三個虛擬節(jié)點(diǎn)的數(shù)據(jù)均定位到服務(wù)器1上.這樣就解決了服務(wù)節(jié)點(diǎn)少時數(shù)據(jù)傾斜的問題.在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為32甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對均勻的數(shù)據(jù)分布.

1.4 基于節(jié)點(diǎn)容量感知的負(fù)載均衡策略

在大多數(shù)的存儲系統(tǒng)中，隨著系統(tǒng)存儲設(shè)備的更新升級，新加入的節(jié)點(diǎn)往往具有更高的帶寬，更大的存儲空間.而基本的一致性哈希算法所有節(jié)點(diǎn)默認(rèn)為資源對等，地址分配的結(jié)果只是滿足統(tǒng)計學(xué)意義上的均勻分配.所以基本算法的使用環(huán)境默認(rèn)為由同構(gòu)存儲節(jié)點(diǎn)構(gòu)成的存儲池，無法再存儲資源分配過程中體現(xiàn)存儲節(jié)點(diǎn)之間的性能差異.

所以，針對該問題，本文在虛擬節(jié)點(diǎn)分配方法的基礎(chǔ)上，提出了基于節(jié)點(diǎn)容量感知負(fù)載均衡策略，對分配方法進(jìn)行優(yōu)化，提高系統(tǒng)數(shù)據(jù)分布策略的靈活性，從而提高系統(tǒng)的整體性能.該優(yōu)化方法的實(shí)現(xiàn)基于以下假設(shè):存儲對象的哈希值成均勻分布，并且各個存儲地址段的存儲開銷呈均勻分布.優(yōu)化的基本思想是對每個物理節(jié)點(diǎn)的資源進(jìn)行估計量化，根據(jù)整個系統(tǒng)的節(jié)點(diǎn)資源情況，對物理節(jié)點(diǎn)分配的虛擬節(jié)點(diǎn)數(shù)進(jìn)行調(diào)整，從而進(jìn)一步優(yōu)化物理節(jié)點(diǎn)間的負(fù)載均衡.對于每個物理節(jié)點(diǎn)分配調(diào)節(jié)因子w，該參數(shù)表示該物理節(jié)點(diǎn)的資源分配權(quán)值，可表示節(jié)點(diǎn)的容量或者帶寬等，原型系統(tǒng)設(shè)計中采用的是對容量資源的量化權(quán)值.然后，統(tǒng)計每個物理節(jié)點(diǎn)的所分配地址空間的大小s.基于前提假設(shè)，s值可以表示該節(jié)點(diǎn)所分配存儲開銷;設(shè)P=s/w，作為物理節(jié)點(diǎn)資源利用率量化值.系統(tǒng)通過統(tǒng)計計算，獲取P的均值，并設(shè)定門限值Pmax和Plow，當(dāng)節(jié)點(diǎn)超過門限范圍時，采用增加或減少虛擬節(jié)點(diǎn)的方法，均衡整個系統(tǒng)負(fù)載.圖9為該策略具體的實(shí)現(xiàn)流程:

基于節(jié)點(diǎn)容量感知的分配策略采用分布式的方式完成，存儲資源節(jié)點(diǎn)通過主控端獲得相關(guān)門限值，并計算自身的相關(guān)參數(shù)，實(shí)時比較.當(dāng)本節(jié)點(diǎn)的參數(shù)P值小于下限值Plow時，進(jìn)行申請?zhí)摂M節(jié)點(diǎn)操作，請求信息被發(fā)送到控制端，調(diào)用函數(shù)完成操作;同理，當(dāng)本節(jié)的參數(shù)P值大于上限值Phigh時，進(jìn)行退出虛擬節(jié)點(diǎn)操作.此外，在主控端保存著節(jié)點(diǎn)的信息，很容易獲得理論均值.門限值的設(shè)定采用如下公式:

其中:Plev時P的均值;N為物理節(jié)點(diǎn)數(shù);S為物理節(jié)點(diǎn)所有虛擬節(jié)點(diǎn)地址范圍之和;W為存儲資源標(biāo)準(zhǔn)化權(quán)值(例如采用50GB為單位，200GB的節(jié)點(diǎn)W值為4，100GB的節(jié)點(diǎn)W值為2.值得注意的是:當(dāng)K過大時，會影響到負(fù)載平衡的效果;當(dāng)K值過小時，會造成虛擬節(jié)點(diǎn)的頻繁增減操作，甚至造成某些物理節(jié)點(diǎn)的虛擬節(jié)點(diǎn)數(shù)出現(xiàn)“顫動”(頻繁來回增減虛擬節(jié)點(diǎn))，造成極大地系統(tǒng)開銷.此外，K值的極限值與物理節(jié)點(diǎn)的個數(shù)有一定關(guān)系，當(dāng)物理節(jié)點(diǎn)數(shù)越多時，k值可以設(shè)得越小.

以上便是基于接點(diǎn)容量感知分配策略的實(shí)現(xiàn)方法，在前提假設(shè)成立的情況下，該方法為系統(tǒng)存儲資源的合理利用提供了更加靈活的機(jī)制，確保了系統(tǒng)存儲資源的負(fù)載均衡.

2 結(jié)論

本文對分布式存儲領(lǐng)域的技術(shù)展開了研究，介紹了一種分布式存儲的基本架構(gòu).該策略以一致性哈希數(shù)據(jù)分布策略為基礎(chǔ)，引入了虛擬化設(shè)計思路，采用虛擬節(jié)點(diǎn)的分配策略，并分析研究了一種基于節(jié)點(diǎn)容量感知的負(fù)載均衡方法，有效優(yōu)化了系統(tǒng)的性能，提高了系統(tǒng)的可擴(kuò)展性.但是上述負(fù)載均衡策略由于算法的缺陷帶來過大的負(fù)載轉(zhuǎn)移開銷，如:由于需要實(shí)時比較，主控端必須不停的獲取并計算理論均值，并調(diào)用函數(shù)進(jìn)行比較，這就必將增加系統(tǒng)的負(fù)荷.

既然靜態(tài)負(fù)載均衡策略具有簡單易行的優(yōu)點(diǎn)，動態(tài)負(fù)載均衡策略具有較好的時間和空間效率，而二者又都具有其弊端，故單獨(dú)使用某個策略并不能滿足所有網(wǎng)絡(luò)系統(tǒng)的需求.因此我們可以試著動靜結(jié)合，將這兩種策略互相配合使用，或許可以達(dá)到更好的效果.下面是一個新的算法設(shè)想:

在沒有節(jié)點(diǎn)加入或退出系統(tǒng)時，我們可以采用普通的靜態(tài)負(fù)載分配算法，在靜態(tài)負(fù)載分配算法中，利用特殊的ID生成算法可有效地為節(jié)點(diǎn)均衡分配負(fù)載;同時，當(dāng)網(wǎng)絡(luò)發(fā)生動蕩時，即有節(jié)點(diǎn)加入或退出系統(tǒng)時，采用特殊的動態(tài)負(fù)載分配方法來對其進(jìn)行調(diào)整，以最快的速度和最小的轉(zhuǎn)移開銷可保證系統(tǒng)負(fù)載重新均衡.設(shè)想中提出的策略雖有待改進(jìn)和細(xì)化，但我相信在不久的將來必將出現(xiàn)與之相符的詳細(xì)實(shí)用的算法.

［1］(美)特尼博姆等著，辛春生等譯.分布式系統(tǒng)原理與范型(第2版).清華大學(xué)出版社，2008，6

［2］肖迎元.分布式實(shí)時數(shù)據(jù)庫技術(shù).科技出版社，2009，6

［3］陸嘉恒.分布式系統(tǒng)及云計算概論.清華大學(xué)出版社，2011，5

［4］李明.認(rèn)識 Linux的磁盤配額.http://blog.chinaunix.net/u3/93755/showart－187

［5］Andrew S.Tanenbaum著，陳向群，馬洪兵譯.現(xiàn)代操作系統(tǒng).北京機(jī)械工業(yè)出版社，2009，7

［6］韋理，周悅芝，夏楠。用于網(wǎng)絡(luò)存儲系統(tǒng)的存儲空間動態(tài)分配方法.計算機(jī)工程，2008(5)

［7］田穎.2003.分布式文件系統(tǒng)中的負(fù)載平衡技術(shù)研究［D］:［碩士學(xué)位論文］北京:中國科學(xué)院計算技術(shù)研究所

［8］楊德志，許魯，張建剛.2008.藍(lán)鯨分布式文件系統(tǒng)元數(shù)據(jù)服務(wù)［J］.計算機(jī)工程:4～9

［9］肖培棕.2009.分布式文件系統(tǒng)元數(shù)據(jù)負(fù)載均衡技術(shù)研究與實(shí)現(xiàn)［D］［碩士學(xué)位論文］合肥中國科學(xué)技術(shù)大學(xué)

［10］馮幼樂.2010.分布式文件系統(tǒng)元數(shù)據(jù)管理技術(shù)研究與實(shí)現(xiàn)［D］:［碩士學(xué)位論文］.合肥:中國科學(xué)技術(shù)大學(xué)