分布式存儲系統(tǒng)需要完善的數(shù)據(jù)副本創(chuàng)建、部署、選擇、定位和一致性管理機制以保證分布式計算環(huán)境中的數(shù)據(jù)安全、可用、可靠、可擴展性和服務(wù)的高效、連續(xù)性。文中全面分析與研究了國內(nèi)外對分布式存儲系統(tǒng)中的副本管理機制研究現(xiàn)狀，重點對副本創(chuàng)建、副本定位、副本一致性維護和副本撤銷機制進行深入的研究，并從數(shù)據(jù)可用性、節(jié)點負載均衡、數(shù)據(jù)一致性和帶寬消耗等性能指標進行了分析。文中的研究成果對于分布式存儲系統(tǒng)的合理設(shè)計與構(gòu)建具有良好的參考價值。
分布式存儲系統(tǒng)(Distributed Storage Systems)是基于存儲服務(wù)器集群(Cluster)和分布式文件系統(tǒng)，將網(wǎng)絡(luò)中大量各種不同類型的存儲設(shè)備通過應(yīng)用軟件集合起來協(xié)同工作，并通過各種相應(yīng)的應(yīng)用軟件或應(yīng)用接口，共同為用戶提供高可用、高可靠的數(shù)據(jù)存儲和業(yè)務(wù)訪問功能的存儲資源系統(tǒng)。為了保證數(shù)據(jù)安全、可用、可靠、可擴展性和服務(wù)的高效、連續(xù)性，分布式存儲系統(tǒng)需要完善的數(shù)據(jù)多副本創(chuàng)建、部署、選擇、定位和一致性管理機制。隨著互聯(lián)網(wǎng)中的用戶對資源的需求量日益增多，如果僅有一份數(shù)據(jù)，則需要該數(shù)據(jù)的用戶都須到同一個節(jié)點上讀取它，網(wǎng)絡(luò)容易出現(xiàn)擁塞，而處理能力有限的節(jié)點也會因為訪問數(shù)量太大而宕機。然而，創(chuàng)建多份數(shù)據(jù)副本，并將它們合理分布在多個服務(wù)器節(jié)點上，分擔處理訪問請求的任務(wù)，可以有效降低節(jié)點失效率，減少用戶響應(yīng)時間。
文中詳細分析了目前國內(nèi)外對分布式存儲系統(tǒng)中的副本管理機制研究現(xiàn)狀，重點對副本創(chuàng)建、副本定位、副本一致性維護和副本撤銷機制進行深入的研究，并從數(shù)據(jù)可用性、節(jié)點負載均衡、數(shù)據(jù)一致性和帶寬消耗等性能指標進行了系統(tǒng)的分析。
1.副本創(chuàng)建
某一節(jié)點上的數(shù)據(jù)被頻繁訪問使得該服務(wù)器節(jié)點負載過重時，或出于提高可靠性的考慮時，可將數(shù)據(jù)復(fù)制一份或多份副本并存儲到其它節(jié)點上。
1.1 副本數(shù)量的設(shè)置
副本數(shù)量對分布式存儲系統(tǒng)的可用性的影響很大，創(chuàng)建太少容易產(chǎn)生數(shù)據(jù)熱點問題，延長訪問時間，太多則會造成無謂的存儲空間浪費。很多存儲系統(tǒng)復(fù)制的默認數(shù)據(jù)副本數(shù)是3份，即在數(shù)據(jù)投入使用時復(fù)制3份它的副本，之后根據(jù)具體情況來創(chuàng)建和撤銷副本。
文獻根據(jù)副本復(fù)制的數(shù)量可將副本復(fù)制方法分為3種:均勻復(fù)制，所有數(shù)據(jù)對象復(fù)制相同數(shù)量的副本；比例復(fù)制，復(fù)制數(shù)量與被訪問頻率成正比；方根復(fù)制，復(fù)制數(shù)量與被訪問頻率的方根成正比。方根復(fù)制在平均查詢距離和副本利用率方面具有較理想的性能表現(xiàn)。文獻經(jīng)模擬實驗得出當副本的生命周期較長和副本密度較高時更能體現(xiàn)方根復(fù)制方法的優(yōu)勢。雖然副本復(fù)制的數(shù)量一般被認為應(yīng)該正比于原數(shù)據(jù)大小的平方根，而文獻的研究結(jié)論表明，副本復(fù)制的數(shù)量應(yīng)該反比于原數(shù)據(jù)大小的平方根。
1.2 副本復(fù)制策略
副本復(fù)制策略分為路徑復(fù)制、源請求復(fù)制、鄰居節(jié)點復(fù)制、隨機復(fù)制和優(yōu)先級復(fù)制五種：
(1)路徑復(fù)制。發(fā)送副本給請求路徑上的所有節(jié)點。優(yōu)點是實現(xiàn)原理簡單，方便數(shù)據(jù)的查找；缺點是創(chuàng)建的副本數(shù)量供過于求，且增加了副本的一致性維護的開銷。
(2)源請求復(fù)制。只發(fā)送副本給請求節(jié)點。LAR(Lightweight Adaptive Replication，輕量級自適應(yīng)的復(fù)制方法)算法是美國馬里蘭大學(xué)研究人員提出的經(jīng)典源請求復(fù)制算法，其主要思想是:當訪問請求到達目的節(jié)點時，若目標節(jié)點未過載，則能讀取數(shù)據(jù)，若目標節(jié)點處理能力不夠，將創(chuàng)建一份新副本，而且如果請求節(jié)點未過載，才把新創(chuàng)建副本發(fā)給該請求節(jié)點，并告知請求路徑上所有節(jié)點該請求節(jié)點上也有該數(shù)據(jù)副本。優(yōu)點是對于目的節(jié)點來說，減少了副本的復(fù)制數(shù)量；缺點是請求路徑上有該副本且達到復(fù)制閾值的節(jié)點都存一份副本到請求節(jié)點上，易造成請求節(jié)點過載。
(3)鄰居節(jié)點復(fù)制。對網(wǎng)絡(luò)數(shù)據(jù)都保存訪問歷史記錄，節(jié)點將被頻繁訪問的副本新建一份發(fā)送給頻繁請求的節(jié)點的鄰節(jié)點，當請求節(jié)點再次訪問該數(shù)據(jù)時，可以到其鄰居節(jié)點直接讀取數(shù)據(jù)了，從而減少了請求的跳數(shù)。該方法缺點在于歷史記錄預(yù)測會有一定概率的失誤。
(4)隨機復(fù)制。隨機選擇一個或多個節(jié)點來存放副本，有隨機選擇的對象是請求路徑上的節(jié)點和整個網(wǎng)絡(luò)的節(jié)點兩種策略，后者主要運用多哈希函數(shù)和關(guān)聯(lián)哈希兩種方法。多哈希函數(shù)的優(yōu)點是可以動態(tài)調(diào)整副本的數(shù)目；副本被高度分散了，有益于負載均衡；缺點是管理多個哈希函數(shù)是個復(fù)雜的工作。關(guān)聯(lián)哈希的優(yōu)點是明顯減少了訪問時延；缺點是產(chǎn)生較大的副本數(shù)量和系統(tǒng)開銷。
(5)優(yōu)先級復(fù)制。請求發(fā)生就向已經(jīng)有副本的節(jié)點發(fā)送所需副本，直至飽和，再選擇別的節(jié)點來存儲副本。優(yōu)點是減少了存放副本的節(jié)點數(shù)，減低了節(jié)點的維護開銷；缺點是存放副本的節(jié)點易過載，容易出現(xiàn)新一輪的訪問熱點問題。
通過比較這5種副本分布方法，可以發(fā)現(xiàn)路徑復(fù)制和優(yōu)先級復(fù)制方法不夠靈活、效率相對較低，其它3種方法可以在大多數(shù)分布式網(wǎng)絡(luò)環(huán)境下使用并能解決熱點問題。
1.3 典型副本分布方法
文獻提出了一種漸進優(yōu)化的選舉和分區(qū)合并算法來存儲多個副本，以求得目標區(qū)域中的最佳存儲節(jié)點。方法假設(shè)要存儲n個副本，先將拓撲結(jié)構(gòu)劃分為多個區(qū)域，每個區(qū)域都有一個服務(wù)節(jié)點，即該區(qū)域內(nèi)最適合放置副本的節(jié)點，然后根據(jù)選舉法，選舉過程中，考慮了客戶的分布情況、訪問頻率、通信時延和節(jié)點的處理能力四個因素，每次淘汰一個區(qū)域，并有調(diào)整剩余區(qū)域的環(huán)節(jié)，經(jīng)過多次的選舉淘汰區(qū)域調(diào)整，最終將整個網(wǎng)格劃分為n個區(qū)域，這n個區(qū)域的服務(wù)節(jié)點就是最佳存儲節(jié)點。
文獻提出一種網(wǎng)格環(huán)境下的多副本后向預(yù)測調(diào)度的算法。方法與鄰居節(jié)點復(fù)制策略有些相似，也是根據(jù)已收集的歷史數(shù)據(jù)來預(yù)測合適的存儲節(jié)點，不同的是在發(fā)生負載失衡情況之前將副本直接存儲到選出的節(jié)點而不是它們的鄰居節(jié)點。
1.4 數(shù)據(jù)遷移方法
網(wǎng)絡(luò)系統(tǒng)的一個重點問題是如何實現(xiàn)負載均衡，通過新副本的添加或撤銷能達到這一目的，另外一種常用的方法則是數(shù)據(jù)遷移。虛擬節(jié)點技術(shù)的核心思想就是數(shù)據(jù)遷移。數(shù)據(jù)虛擬節(jié)點是存儲數(shù)據(jù)文件、路由定位的基本單元，一個物理節(jié)點可管理多個虛擬節(jié)點。若一個物理節(jié)點過載，則將其管理的部分虛擬節(jié)點轉(zhuǎn)移給其它物理節(jié)點管理，數(shù)據(jù)將隨之轉(zhuǎn)移。
虛擬節(jié)點技術(shù)有一對一、一對多和多對多這三種策略。虛擬節(jié)點策略的缺點在于實現(xiàn)復(fù)雜。由于復(fù)制技術(shù)本身已包含分布策略，且虛擬節(jié)點技術(shù)必須是在擁有足夠數(shù)量的副本才能實現(xiàn)，所以虛擬節(jié)點技術(shù)更適合于與復(fù)制技術(shù)結(jié)合使用。
2.副本定位
節(jié)點訪問數(shù)據(jù)性能表現(xiàn)的優(yōu)劣很大程度上受到數(shù)據(jù)定位策略的影響，即如何快速定位出目標數(shù)據(jù)所在節(jié)點的位置，然后讀取數(shù)據(jù)。
傳統(tǒng)的基于覆蓋網(wǎng)(Overlay network)的副本定位算法雖然在不同程度上解決了副本定位效率、負載均衡和可擴展性等問題，但目標節(jié)點不能很好地滿足特定應(yīng)用的服務(wù)質(zhì)量需求 。文獻提出一種多維度服務(wù)質(zhì)量約束的副本定位方法，通過采用分層和對等的混合定位機制，在高效定位的同時，還保證目標節(jié)點提供有效的服務(wù)質(zhì)量。方法基于區(qū)域內(nèi)分層、區(qū)域間對等的覆蓋網(wǎng)拓撲結(jié)構(gòu)，運用了區(qū)間路由算法、副本信息發(fā)布算法、站內(nèi)副本算法、區(qū)內(nèi)副本定位算法和區(qū)間副本定位算法等五個算法，使大量副本定位在本區(qū)域完成，從而有效降低了定位延遲，以滿足特定應(yīng)用的多維度服務(wù)質(zhì)量規(guī)約作為副定位標準，有效地保障了目標節(jié)點的服務(wù)質(zhì)量。
文獻提出了一種用于分布式系統(tǒng)多副本對象訪問控制的分層結(jié)構(gòu)分布式互斥實現(xiàn)方法，該方法利用了系統(tǒng)的自組織特性，對節(jié)點采取分層式管理方式，如圖1 所示。
圖1 25個節(jié)點分布式系統(tǒng)全活躍分層聚類邏輯圖
第1層每行只有一個節(jié)點，采用動態(tài)令牌控制方式，每行的第一個節(jié)點都帶領(lǐng)著此行的其它節(jié)點，以保證在出現(xiàn)節(jié)點間邏輯圖不一致時互斥操作的順利完成。
第2層為每行的多個節(jié)點，采用基于允許的分布式互斥算法。要求各節(jié)點采用相同的聚類規(guī)則和代表節(jié)點產(chǎn)生規(guī)則，系統(tǒng)中每個節(jié)點都保持一個系統(tǒng)分層結(jié)構(gòu)邏輯圖，并隨著系統(tǒng)運行而得到及時更新。對系統(tǒng)進行互斥訪問，需要得到各子系統(tǒng)代表節(jié)點所組成第2層所有節(jié)點的同意。當一個進程需要對系統(tǒng)中的對象進行互斥訪問時，該進程先讀取本節(jié)點保存的系統(tǒng)分層邏輯結(jié)構(gòu)圖，并向保存在數(shù)組中的表頭節(jié)點發(fā)送訪問請求。
3.數(shù)據(jù)一致性
數(shù)據(jù)一致性是指復(fù)制源相同的多個副本之間數(shù)據(jù)一致，分為弱數(shù)據(jù)一致性和強數(shù)據(jù)一致性。數(shù)據(jù)各副本最終達到一致即可滿足弱數(shù)據(jù)一致性，強數(shù)據(jù)一致性則要求數(shù)據(jù)各副本任何時候都要求致。由于多任務(wù)并行執(zhí)行、網(wǎng)絡(luò)延遲不可預(yù)測和修改對象的不確定性等原因，分布式系統(tǒng)中的數(shù)據(jù)一致性維護過程比較復(fù)雜。
3.1 Paxos 算法
Paxos 算法是由Leslie Lamport 提出的一種基于消息傳遞的數(shù)據(jù)一致性算法，用于解決分布式系統(tǒng)中的一致性問題，是目前為止公認最為有效的經(jīng)典數(shù)據(jù)一致性算法。
在Paxos 算法中，節(jié)點被分成了三種類型，Proposer、Acceptor 和Learner，且每個節(jié)點可以有多種角色。保證數(shù)據(jù)的一致性要滿足以下三個條件：
1、決議只有在被Proposer 提出后才能被批準；
2、每次只批準一個決議；
3、只有決議確定被批準后Learner 才能獲取這個決議。
為了達到這三個條件，需要滿足下面幾個約束條件：P1：每個Acceptor 只接受它得到的第一個決議；P2a：一旦某個決議v 得到通過，之后任何Acceptor 再批準的決議必須是v；P1 和P2a 有矛盾，主要體現(xiàn)在節(jié)點因失效參加不了決議，所以提出來第三個條件P2b；P2b：一旦某個決議v 得到通過，之后任何Proposer 再提出的決議必須是v；P2b 不易通過技術(shù)實現(xiàn)，所以提出蘊含P2b 的P2c；P2c：如果一個編號為k 的提案具有值v，那么存在一個“多數(shù)派”，它們中沒有誰批準過編號小于k 的任何提案，或者它們進行的最近一次批準具有值v。
在這些約束條件的基礎(chǔ)上，將一個決議的通過分為兩個階段：
1.準備階段：
a.Proposer 選擇一個提案編號k 并將prepare 請求發(fā)送給Acceptor 中的一個多數(shù)派；
b.Acceptor 收到prepare 消息后，如果提案的編號大于它已經(jīng)回復(fù)的所有prepare 消息，則Acceptor 將自己上次的批準回復(fù)給Proposer，并承諾不再批準編號小于k 的提案。
2.批準階段：
a.當一個Proposer 收到了多數(shù)Acceptor 對prepare的回復(fù)后，就進入批準階段。它要向回復(fù)prepare請求的Acceptor 發(fā)送accept請求，包括編號k和根據(jù)P2c 決定的value(如果根據(jù)P2c沒有決定value，那么它可以自由決定value)；
b.在不違背自己向其他Proposer 的承諾的前提下，Acceptor 收到accept 請求后即批準這個請求。為了減少決議發(fā)布過程中的消息量，Acceptor 將這個通過的決議發(fā)送給Learner 的一個子集，然后由該Learner 去通知所有其他的Learner，即所有副本都將執(zhí)行一樣的更新。
3.2 協(xié)同計算系統(tǒng)的副本一致性維護
協(xié)同計算環(huán)境由計算機網(wǎng)絡(luò)技術(shù)、通訊技術(shù)、多媒體技術(shù)和群件技術(shù)共同構(gòu)成，使不同地域、不同時間、不同文化背景的人們能夠協(xié)調(diào)一致地為某項任務(wù)共同工作。
文獻指出基于無結(jié)構(gòu)P2P 網(wǎng)絡(luò)的文件共享系統(tǒng)中的數(shù)據(jù)一般是靜態(tài)的，數(shù)據(jù)一致性維護的工作量較��；然而在基于無結(jié)構(gòu)P2P 網(wǎng)絡(luò)的新型協(xié)同計算系統(tǒng)中，數(shù)據(jù)具有較強的動態(tài)性，這種模式下的數(shù)據(jù)要求可被參與工作的人頻繁更改，同時保持強數(shù)據(jù)一致性。最簡便的方法是集中式方法：由一個或幾個副本節(jié)點保存所有成員信息，當發(fā)生更新時，就由這些節(jié)點來向其它節(jié)點發(fā)送更新信息。集中式方法的優(yōu)點在于發(fā)送更新快，但它的可擴展性差，易引起單點失效問題�；贕ossip 的組管理協(xié)議的容錯能力和擴展性較好，但基于Gossip 協(xié)議的數(shù)據(jù)一致性維護方法不能保證副本數(shù)據(jù)的強一致性，還會出現(xiàn)大量冗余數(shù)據(jù)。如以樹狀結(jié)構(gòu)組織節(jié)點，更新信息冗余較少且更新快，但容錯能力不高。
文獻結(jié)合以上三種方法的優(yōu)點，提出一種基于分割樹的無結(jié)構(gòu)P2P 網(wǎng)絡(luò)數(shù)據(jù)一致性維護方法。該方法采用Chord作為副本組管理協(xié)議，對Chord環(huán)所代表的ID 空間不斷分割，動態(tài)地建立更新消息傳播樹，從而達到副本數(shù)據(jù)的強一致性、更新信息冗余少、容錯性能高的目的。
4.副本撤銷
引起副本撤銷的原因通常有:副本的生命周期結(jié)束；副本被訪問的頻率很低；副本所在節(jié)點存儲空間不夠；副本所在節(jié)點的處理能力達到極限。
如果給節(jié)點所在副本制定生命周期，則在生命周期結(jié)束時就撤銷副本；當副本的需求不夠，即被訪問頻率很低，應(yīng)予以撤銷；如果節(jié)點需要接納一個新的副本，而本身存儲空間不夠，則會從已有副本中撤銷一個或多個副本，直到能夠存儲該副本；如果節(jié)點的處理能力已達到極限，有時會新建一份副本到其它節(jié)點上以分擔負載，有時會選擇撤銷副本。
4.1 周期保存法
文獻采用的是周期保存法:在副本創(chuàng)建時就給其一個初始值，每當計時周期到了就減1，到該值變?yōu)? 時，不論副本的訪問頻率或它所在節(jié)點的利用率的高低都撤銷該副本，在未變0之前，如果檢測到該副本幾乎未被訪問，則直接撤銷。
4.2 最久未訪問法
最久未訪問法(Least Recently Used，LRU)是一種比較簡單直接的撤銷方法:每個節(jié)點自己維護一個LRU 隊列，隊列中包含了節(jié)點上的所有文件。新產(chǎn)生的文件和副本被加到隊列的尾部。當一個文件被客戶端訪問時，它也被從LRU 隊列中抽取出來放到隊列的尾部。當需要刪除一個文件時，從隊列首部的文件開始，逐個刪除，直至磁盤剩余空間達到新文件的存儲要求。
文獻認為生成一個副本是代價比較高的一件事，所以建議盡量避免無謂地副本刪除。在撤銷副本時使用LRU 方法并結(jié)合考慮副本的重要程度來決定撤銷對象可以減少得不償失的副本撤銷。該文描述了當迎接新副本而節(jié)點存儲空間不夠時采取的撤銷策略。其過程是:將新副本與節(jié)點LRU 隊列中的第一個副本開始比較重要程度，第一個重要程度低于新副本的副本將會被撤銷，且將新副本放置在隊列的隊尾，如果比較完后無副本被撤銷，則取消新副本的存儲。
兩種撤銷方法中的周期保存方法在國外沒有被廣泛采用，其中的原因可能是:不同環(huán)境下數(shù)據(jù)的利用率不盡相同，有些數(shù)據(jù)的訪問頻率長期保持在一個波動不大的值上，而有些數(shù)據(jù)可能只是在短期被大量訪問，副本生命周期的制定會限制副本被有效地利用。而最久未訪問方法則顯得更加靈活，可以降低副本被誤刪的概率。
5. 結(jié)束語
副本管理問題是現(xiàn)在的研究熱點，通過對副本本身進行高效管理和一些相關(guān)技術(shù)的改進，使大眾所處的網(wǎng)絡(luò)環(huán)境能朝更高效率、更可用和更安全的方向發(fā)展。
副本是一群需要實際存儲空間的實體，能引發(fā)大量訪問請求，繼而影響網(wǎng)絡(luò)中節(jié)點的利用率、帶寬消耗和數(shù)據(jù)一致性維護等方面。如何為一個局域網(wǎng)乃至整個互聯(lián)網(wǎng)制定出一套實用的副本管理機制是一項重要任務(wù)。其中，數(shù)據(jù)的副本數(shù)量、副本的分布、副本的定位和副本的數(shù)據(jù)一致性對網(wǎng)絡(luò)的總體性能影響較大，因而是副本問題研究的重點。
核心關(guān)注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。
轉(zhuǎn)載請注明出處：拓步ERP資訊網(wǎng)http://www.oesoe.com/
本文標題：分布式存儲系統(tǒng)中數(shù)據(jù)副本管理機制
本文網(wǎng)址：http://www.oesoe.com/html/consultation/10839411368.html
相關(guān)文章
