龐 慧 陳艷君

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

0 論文所要解決的問(wèn)題

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

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

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

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

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

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

1.2 分布式緩存的問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)論

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

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

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

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

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

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

［4］李明.認(rèn)識(shí) 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ò)存儲(chǔ)系統(tǒng)的存儲(chǔ)空間動(dòng)態(tài)分配方法.計(jì)算機(jī)工程，2008(5)

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

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

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

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