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