一種基于條帶的一致性散列數據放置算法

魏 征 竇 禹 高艷珍 馬 捷 孫凝暉 邢 晶

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學 北京 100190)

在大數據時代，數據因為其體現的價值而越來越多地受到重視.數據規模正呈爆發式地增長，根據互聯網數據中心(International Data Corporation, IDC)的統計預測，預計到2022年市場規模將達1 891億美元[1]，到2025年全球數據總量將達175 ZB[2].面對持續增長的海量數據，分布式存儲系統成為存儲研究方向的熱點之一.

分布式文件系統通常在數據中心中以存儲集群的方式來實現[3].在數據中心中包含了計算存儲、網絡、電力等眾多設備，各類設備故障都威脅著存儲數據的可靠性.各類出錯因素的積累，使得存儲服務器的失效成為常態[4].分布式存儲系統通過副本和糾刪碼機制提供數據可靠性存儲技術，保證當某個節點失效時不會對存儲的數據產生影響.其中糾刪碼能夠達到甚至超過3副本的可靠性[5-6].糾刪碼在Google的GFS[7]、Microsoft的Azure[8]以及Facebook的存儲系統[9]等商業系統中都有應用.糾刪碼與RAID類似，將數據分組組成條帶(stripe).每個條帶中有N塊數據，數據經過編碼矩陣編碼產生N個數據塊和M個校驗塊.N個數據塊和M個校驗塊構成一個糾刪碼條帶.糾刪碼條帶中的數據塊用于數據讀取.糾刪碼編碼產生的糾刪碼條帶具備最大距離可分碼(maximum distance separable, MDS)性質[10]，即任意不多于M塊數據丟失，都能恢復原始數據.

分布式文件系統從系統結構上可以分為有中心和無中心2種.有中心的分布式文件系統是在集群中選擇1個節點，負責管理整體集群，記錄每個數據塊的放置位置.其他節點通過與中心節點通信，確定數據的存放位置.在谷歌文件系統(Google file system, GFS)[11]、Hadoop分布式文件系統(Hadoop distri-buted file system, HDFS)[12]、百度文件系統(Baidu file system, BFS)[13]等文件系統中，均采用這類系統結構.有中心的分布式文件系統實現簡單，能夠收集全局信息，比較均衡地放置數據，并且數據放置的位置靈活可變.但存在單點故障，當中心節點失效時，可能導致整個系統進入不可用的狀態.同時每次獲取數據存放位置時，均需要與中心節點進行交互，中心節點負載壓力較大，不利于集群的擴展.面向EB(exabyte)級大規模分布式存儲機群，元數據管理成本較大，位置信息等元數據查詢效率影響了IO時延和吞吐量.有中心數據放置算法需要維護大量元數據信息，維護成本較高.文件信息、目錄信息、塊位置信息等元數據請求使得元數據服務器成為訪問熱點，不利于性能優化.

無中心的分布式文件系統是基于Hash算法實現的，即根據數據塊的某個或某些特征值，通過Hash函數等機制映射出實際存放的存儲節點，所以系統中不需要中心節點進行系統管理.在Ceph[14],Swift[15],Gluster[16]等存儲系統中，均采用這類系統結構.無中心的分布式文件系統不存在中心節點，避免了單點故障.在一般情況下，Hash函數取值呈均衡分布，各節點間負載均衡.同時每次查詢數據位置時，只要通過計算就能確定存儲節點，不存在單節點查詢的性能瓶頸，可擴展性好.因此，在集群規模較大、IO請求密集的情況下，無中心的分布式文件系統能夠在保證可靠性的同時，表現出更加優秀的性能，正被越來越多的分布式文件系統所采用.

在糾刪碼的存儲方式下，無中心的分布式文件系統在實現數據恢復的過程中，還面臨2個方面的挑戰:1)糾刪碼中將數據塊和校驗塊組成條帶，數據放置位置相對固定，需要保持放置規則，在節點恢復過程中易造成額外的數據塊遷移;2)糾刪碼條帶的恢復過程中涉及更多的并發IO操作，這些IO操作間相關度大，并行度低，恢復帶寬不高.為了獲得更高的性能和擴展性，本文采用了無中心的系統結構，針對基于糾刪碼的分布式文件系統恢復機制進行了研究，通過改進數據放置算法，減少恢復過程中變動的數據量，通過調度并發IO，提高恢復帶寬.

數據放置算法是分布式文件系統的核心問題，數據放置的方法決定了其他功能的實現，也影響著系統的整體性能.首先，數據需要均衡放置.數據放置不均衡導致某個節點的負載過高而崩潰，從而導致整體系統的不可用.其次，要保證數據的可靠存儲.針對糾刪碼而言就是要保證其MDS性質，即任意節點上同條帶內的塊不能超過M塊.再次，數據放置算法要使系統具備良好的擴展性.在系統擴展和數據恢復過程中，數據放置的位置會發生變化，需要依據數據放置算法，選擇新的位置存放數據.最后，數據放置算法應具有較高的查詢性能.在讀寫數據等操作中，都會包含查詢數據位置的操作，查詢的效率會對系統的性能產生較大影響.

糾刪碼的引入對于數據放置的可靠性、均衡性影響不大，但給擴展性和查詢性能帶來了挑戰.在糾刪碼的數據恢復過程中，條帶內的每個塊的內容并不相同，為了保證相同的讀取策略，需要依次遷移數據塊，產生了額外的數據遷移開銷.同時，在選擇數據放置位置時，還要考慮查詢的性能，不能帶來較高的查詢開銷.因此，本文提出了一種新的數據放置算法，既有較好的查詢性能，又能減少節點變動時的數據遷移量.

分布式文件系統的數據恢復過程，是從存活節點上讀取數據，然后寫入重建節點.整個恢復過程包含大量的數據IO操作，IO操作涉及到塊的讀寫數量是確定的，為數據恢復過程中進行精確地并發IO調度帶來了可能.糾刪碼數據恢復過程中，每個塊的恢復需要讀取N個塊，塊間存在約束關系，需要等待數據讀取IO的完成，再進行糾刪碼的恢復計算，才能執行寫入丟失塊的IO操作.同時，在數據恢復過程中，可能對條帶內沒有丟失的塊進行遷移，產生額外的遷移IO，遷移IO與恢復IO可能讀取同一個節點，影響IO的并行執行.所以，在糾刪碼中應該把一個條帶內的塊看做是一個整體，在條帶內統一調度包含恢復IO和遷移IO的所有并行IO操作.而對于條帶間的IO操作相互獨立，可以采用與數據塊調度類似的策略進行調度.因此，本文提出了基于條帶的并發IO調度恢復策略，將條帶內的恢復IO與遷移IO統一調度，提升數據恢復的速度.

本文的主要貢獻有3個方面:

1) 提出了一種基于條帶的一致性Hash數據放置算法(consistent Hash data placement algorithm based on stripe, SCHash).SCHash算法以條帶為單位放置數據，減少了節點變動過程中的數據遷移量，從而在恢復過程中降低了變動數據的比例，加快了恢復帶寬.同時，該算法還具有較好的均衡性和查詢性能.

3) 基于糾刪碼文件系統(erasure coded file system, ECFS)[17-18]實現了基于條帶的一致性Hash數據放置算法SCHash，并通過測試驗證了SCHash放置算法針對數據遷移和恢復的優化目的.

1 相關工作

本節首先介紹了糾刪碼文件系統中所采用的數據放置策略，及其對于數據恢復的影響.然后介紹了數據恢復過程中IO調度策略的相關研究工作.

1.1 采用糾刪碼的數據放置算法

數據放置算法是分布式文件系統中的核心算法，對于讀寫性能和恢復性能都會產生影響.分布式文件系統中的每次讀寫操作，都需要查詢數據的放置位置.在數據恢復時，需要依據數據放置算法，選擇重建節點恢復數據，并對其他數據放置的位置進行調整.所以數據放置算法應具備較高的查詢性能,還應減少數據恢復中變化的數據量.

1.1.1 APHash

APHash(Arash Partow Hash)[19]是一種類似順序放置的數據放置算法，該算法是先將數據塊映射為一個整數值，再根據當前節點的數目取模，得到實際存放的位置.APHash不同于其他Hash算法的地方在于，同一條帶上連續順序編號的數據塊，可以映射到一段連續的Hash值.從而使得同一條帶中的塊，在存儲節點上順序排列，保證了糾刪碼的MDS性質.APHash算法實現簡單，查詢效率高，并且數據分布基本均勻.但文件一旦寫入，每個數據塊對應的存儲位置也就唯一確定.當節點數據發生變化時，基本上所有的數據都要發生遷移.

1.1.2 一致性Hash算法

一致性Hash算法(consistent hashing)[20]將Hash空間分組映射到存儲節點上，從而在節點變化時，減少了數據的遷移.一致性Hash算法首先構造了一個環形的Hash空間，例如0～(232-1)的一個范圍.數據塊經過Hash算法，映射到該Hash空間上的某個位置，同樣，待存儲的節點也映射到這樣一個Hash空間上，從塊映射的位置開始，順時針選擇最近的節點映射值，對應的節點就是數據存放的節點.同樣，在增加節點時，也只需要遷移被分割區域內的塊即可.在頻繁地增減節點后，節點在Hash空間上的分布不一定均衡，最終就可能導致負載不均衡.因此，需要再增加數目固定的虛擬節點，替代物理節點映射到Hash空間上.虛擬節點可以看作是節點在Hash空間上的復制品，一個物理節點可以對應多個虛擬節點.當物理節點發生變化時，只需要更改虛擬節點到物理節點的映射關系即可.例如在文獻[21]中,通過動態調整虛節點優化數據布局.一致性Hash算法有效地解決了節點數目變化時數據大量遷移的問題.但對于糾刪碼存儲系統，并不能保證滿足MDS性質，即同一個條帶中的塊可能被映射到同一物理節點上，或者映射的虛節點被指向同一物理節點.

1.1.3 CRUSH算法

CRUSH(controlled scalable decentralized place-ment of replicated data)算法[14]是分布式文件系統Ceph中采用的數據放置算法，是對一致性Hash算法的進一步擴展，能夠支持更加復雜的集群結構.存儲文件首先被劃分為相同大小的對象(object)，每個對象可以由文件索引節點號(inode)與塊號(object number,ono)組成的對象號(object id,OID)唯一標示，即(inode,ono).然后對象號經過Hash取模映射到放置組(placement group, PG)中，PG相當于一致性Hash中的虛擬節點.PG再經過CRUSH算法，映射到存儲的對象存儲設備(object storage device, OSD)上.當節點數目變化時，只需要移動節點上存儲的PG即可.CRUSH算法選擇OSD的過程，是按照一定層次順序選擇存儲設備，然后在同一層次中，根據負載、可靠性、故障情況選擇最合適的設備.CRUSH算法能夠根據集群特點，分層逐步選取存儲設備，對于不同結構的存儲集群都能獲得較好的數據可靠性.

在糾刪碼環境中，同一層次選取設備的過程還需要考慮糾刪碼的MDS性質.假設需要選取6個存儲節點存儲1個條帶中的6個塊，依據一定的Hash算法，選取好6個存儲節點后，會檢查這6個存儲節點是否有重復，是否滿足糾刪碼MDS的約束條件.如果某個存儲節點不滿足條件，會將Key值增加條帶長度，重新Hash選取節點，直到選出的存儲節點間滿足負載、故障和糾刪碼的MDS性質.CRUSH算法相對比較復雜，在每個層次選取存儲設備的過程中，可能存在多次失敗重試的情況，對于資源相對緊張的中小集群，發生沖突的可能性比較高，會造成重復嘗試多次的問題.CRUSH算法本質上是隨機選取一些可行的節點組，再在這些節點組中依次存儲數據塊.當節點失效后，存儲節點的拓撲結構發生變化，同一塊的Hash結果難免不發生改變.雖然CRUSH算法給出了4種數據Hash方式，但并不能保證一定不發生額外的數據遷移，并且遷移數據量最小的Straw方式查詢效率比較低.

綜上所述，目前在分布式文件系統中所采用的數據放置策略，多是基于3副本存儲方式而設計的，并沒有針對糾刪碼做太多的優化適配.因此并不能完全適應于糾刪碼文件系統中數據放置的需要，在數據恢復中仍會帶來其他開銷.

1.2 采用糾刪碼的I/O調度策略

數據恢復是某些塊丟失后，通過仍然存在的其他塊，恢復丟失塊的過程.在糾刪碼環境下，恢復一個塊需要讀取N塊數據，包含了大量的并發IO操作.這些IO操作就會在系統內隨機執行，甚至可能導致恢復操作以串行的方式執行，降低系統的恢復效率.在(N,M)糾刪碼中，最多支持M個數據塊的丟失.依據Facebook統計的集群失效情況[22]，單塊丟失占據了98.09%以上的比例，并且多塊丟失主要是因為單塊丟失沒有及時恢復造成的.在調度過程中，應主要考慮對單塊丟失的情況進行調度.在分布式文件系統中，一般會有負載均衡策略，恢復中的IO操作與用戶讀寫IO操作相比較，涉及到的塊是確定的，具有一定的規律性，同時也具有較強的數據約束性.數據恢復過程中的IO操作，可以通過更加具體的策略進行調度.本節中將首先介紹文件系統中的數據IO調度策略，再說明針對糾刪碼的恢復調度策略.

1.2.2 基于數據位置的調度

Shen等人在文獻[28]中提出了最少跨機架傳輸(minimizing number of accessed racks)的方法.該方法依據數據塊所存儲的機架位置，在選取提供數據塊時，選取的數據塊盡量避免跨機架的數據遷移.假設每個機架上的節點連接同一個匯聚層交換機，同條帶中的數據塊會分布在不同機架的不同節點上，在選取同組數據塊時，選取的數據塊應盡量少地跨交換機傳輸，提高了傳輸速度.

1.2.3 基于網絡帶寬的調度

Li等人在文獻[29]中提出了樹型恢復方案(tree-structured regeneration scheme).該方法將每個存儲節點假設為圖中的頂點，節點間的網絡帶寬表示為節點間邊的權重，那么存儲系統中就可以用一個帶權無向圖，表示恢復時的網絡情況.當恢復IO在存活節點中選取同組節點時，就可以依據邊的權重，選取合適的網絡路徑.但在實際的恢復過程中，網絡帶寬不斷變化，無法準確判斷節點間的帶寬情況.并且樹型恢復過程中，恢復數據要經過一些節點的路由，會帶來額外的傳輸開銷.

2 基于條帶的一致性Hash數據放置算法SCHash

分布式文件系統中的數據恢復過程，是將丟失數據重新放置的過程，數據放置算法決定了數據與存儲節點之間的對應關系，因此數據放置算法是數據恢復過程中的關鍵問題之一.在數據恢復中，為了滿足糾刪碼數據塊間的約束關系，大部分情況下除了恢復丟失的數據塊外，還需要額外移動一些數據塊，造成不必要的開銷.因此構建遷移數據量小的數據放置算法，是分布式文件系統中數據恢復的基礎.

本文提出了一種基于條帶的一致性Hash數據放置算法SCHash.糾刪碼中的數據是以條帶為單位組織的，條帶間的數據并不存在約束關系.所以在糾刪碼環境下，應以條帶為單位進行數據放置.這樣就能通過一致性Hash算法，確定每個條帶的存儲位置.每個條帶要存儲到多個節點上，這就要把待存儲數據的節點組織成節點組，從而把數據塊到節點的映射過程轉化為從條帶到節點組的映射過程.因此，SCHash算法以條帶為單位放置數據，保證了節點間的約束關系，通過一致性Hash算法提高了數據放置算法的擴展性，減少了節點變動時的數據遷移量.

Fig. 1 SCHash algorithm圖1 SCHash算法

SCHash算法的數據放置過程如圖1所示.首先，依照一致性Hash算法的設計構造一個環形的Hash空間，生成一定數目的虛節點，這些虛節點均衡地分布到Hash空間上.例如圖1中構造了一個Hash空間并產生12個虛節點(用白色點表示，在工程實現中，虛節點數目與實際節點組數量成倍數或數量級關系，用于保證數據的均衡分布和節點的負載均衡)，虛節點均衡地分布在Hash空間上.每個虛節點對應一個節點組，每個節點組可以根據權重，分配不同數目的虛節點.通過inode,stripe_id(inode為文件的唯一標識號，stripe_id為當前數據的條帶號)可以唯一確定每個文件中的每個條帶.條帶以inode,stripe_id為Key可以根據Hash函數映射到Hash空間上的某個值.最后，從條帶映射的位置開始，在Hash空間上順序查找最近的虛節點，該虛節點對應的節點組，就作為存儲該條帶的節點組.在條帶與節點組之間，每個數據塊依次存儲在節點組中對應的節點上.

節點組的結構從根本上滿足了糾刪碼的MDS性質，只需要在構建節點組時，每個節點組內滿足約束條件，就能使任意條帶內的數據塊滿足MDS性質，保證了系統的可靠性.數據條帶到虛節點的映射是一個Hash的過程，可以認為數據均衡地分布在虛節點上.只需保證每個節點分配的虛節點數均衡，就能使系統均衡地存儲數據.在系統拓撲確定的前提下，整個查詢過程都是確定的計算過程，并且與系統中存儲節點的數目沒有關系，因此查詢效率為O(1).

NG=(n0,n1,…,nN+M-1).

(1)

(2)

節點組(node group,NG)根據式(1)定義，依據采用的糾刪碼編碼方案，由N+M個節點構成的N+M元組表示.節點組間的差異度(difference,Diff)由式(2)定義，表示節點組間對應位置上不同節點的數目.差異度越小，相同節點越多，節點組越相似，節點組間替換時遷移的數據量越小.在選取替換節點組時，就可以選取差異度最低的節點組.在理想情況下，總存在1個替換節點組，與原節點組的差異度為1.在數據從原節點組遷移到替換節點組時，只有對應位置上不同的節點需要遷移數據.因此，SCHash算法能夠提供較好的可靠性、均衡性、擴展性，具備良好的查詢效率.

2.1 構建節點組

SCHash算法，將數據條帶映射到節點組進行存儲.節點在節點組中的組織決定了數據存放的可靠性、均衡性和擴展性.節點組中的節點需滿足約束條件，即相同的節點數目小于M個，才能保證系統存儲數據的可靠性.為了達到數據均衡存儲的目的，存在3個基本原則：1)在節點同構的環境下(同構表示節點配置相同，反之為異構)，每個節點組對應的虛節點個數相同，構建的節點組應保證所有節點組中各節點的占比大體相同.2)在節點異構的環境下，需要調節節點組對應的虛節點數目，使數據按比例分布在各節點上.3)為了提升系統的擴展性，在增刪節點時，新產生節點組或減少節點組后，應選擇差異度較低的替換節點組，保證遷移的數據量在可以接受的范圍之中.綜合考慮這3個方面，本文提出了3種節點組的構建方式，供不同場景選擇.

為了方便說明節點組的構建過程，在本節中假設存儲系統中有S個同構的存儲節點，采用(N,M)的糾刪碼編碼方式，則每個條帶中有K(K=N+M)個數據塊.顯然，存儲節點的個數S與K滿足3個關系:

1) 當S≥K時，則可以選取任意K個存儲節點組成1個節點組.

2) 當K>S≥KM時，則每個存儲節點先放置KS個數據塊，再從S個存儲節點中選取(KmodS)個存儲節點，一同組成1個節點組.

3) 當KM>S時，則不可能滿足糾刪碼MDS性質.

我們以S=4,K=3,N=2,M=1為例，分別闡述排列法、組合法和單點冗余法在S≥K情況下的組合情況，通常在存儲系統的實際部署環境下，機群節點數量S遠大于條帶長度K.

2.1.1 排列法

1,2,3 1,3,2 2,1,3 2,3,4 3,1,2 3,2,4 4,1,2 4,2,3

1,2,4 1,4,2 2,1,4 2,4,1 3,1,4 3,4,1 4,1,3 4,3,1

1,3,4 1,4,3 2,3,1 2,4,3 3,2,1 3,4,2 4,2,1 4,3,2

2.1.2 組合法

1,2,3 1,2,4 1,3,4 2,3,4

2.1.3 單點冗余法

單點冗余法是選取K個節點組成一個節點組NG，然后再選取1個節點，依次替換節點組NG中的每個節點，從而再構建K個節點組，總共構建(S-K)×K+1個節點組.重復上述過程直到所有的節點都組成了節點組.本例中，從4個節點中選取3個節點組成節點組(1,2,3)，然后用剩余節點4依次替代節點組(1,2,3)，組成新的節點組，與節點組(1,2,3)一起組成4個節點組,NGi=(n0,n1,n2),i=1,2,3,4，即：

1,2,3 4,2,3 1,4,3 1,2,4

單點冗余法同樣選取了部分的節點組合方式，每個組合方式間的節點各不相同.在擴展性方面，同樣由于只選取了部分節點組，不能保證每個節點組在單節點丟失時，都存在差異度為1的替換節點組.但采用了替換的策略，在單點丟失時能盡可能小地減少遷移.單點冗余法僅構建了(S-K)×K+1個節點組，節點組數目較少且線性增加，需要存儲的元數據最少.

2.1.4 構建Hash空間

假設Hash空間大小為R(一般取值為232-1)，節點組個數為NG_Num，虛節點個數為V_Num，虛節點V_Num與節點組NG_Num成倍數關系(V_Num?NG_Num)，每個的權重為NG_W(權重默認為1，根據存儲空間設置，存儲空間越大，值越大，若100 GB存儲空間賦權重值為1，則200 GB節點為2.每個存儲節點組按權重分配的虛節點數目NG_V滿足關系:

(3)

1) 根據節點組編號對Hash空間R執行Hash取模映射，將節點組映射到Hash空間上的某個位置.

2) 順時針選取最近的虛節點.

3) 如果該虛節點已經分配了節點組，則執行步驟4，否則執行步驟5.

4) 順時針前進Step的長度，執行步驟2.

5) 如果查找到的虛節點沒有分配節點組，則將該虛節點分配給節點組.

6) 如果已經分配足夠的虛節點，則退出，否則順時針前進Step的長度，重復執行步驟2～6，直到分配足夠的虛節點后，退出.

2.2 節點變動

在節點發生變動時，待存儲數據的節點組成的節點組也會發生變化，但條帶到虛節點的映射關系保持不變，只需調節某些虛節點與節點組的對應關系，將虛節點從原節點組指向替換節點組即可.如圖2所示，當存儲機群添加存儲節點時，待添加節點與原有節點組織成為待添加節點組，待添加節點組在系統中查找差異度最小的節點組，然后調整與虛節點的對應關系，完成數據的遷移.

Fig. 2 The process of adding node group圖2 節點組的添加過程

具體實施步驟為：

1) 將待添加存儲節點與現存節點構建待添加節點組.

3) 將被替換的節點組中與添加節點組差異的節點進行數據的遷移.

如圖3所示，當系統中存在節點損壞或丟失時，該節點所在的所有節點組為待刪節點組，查找差異度最小的替換節點組，調整與虛節點的對應關系，完成數據的遷移.只有發生變動的虛節點上的數據會發生遷移，從而防止了整個Hash空間上的數據遷移.任意2個節點組中的對應位置上的節點會有不同，數據在節點組間遷移時，也可能會有比較大的數據遷移.因此在選擇替換節點時，應選擇與原節點組最相似的替換節點組，此時遷移的數據量最小.

Fig. 3 The process of replacing node group圖3 節點組的替換過程

2.3 節點分區

在實際部署的分布式存儲運行環境中，存儲節點的數目往往比較大，直接構建節點組的方法并不現實.需要先將存儲節點分區，再在區域內構建節點組.這樣一方面可以減少構建節點組的數目，從而減輕元數據存儲的壓力;另一方面也可以將恢復分區，在發生故障后，只有組內的節點進行數據恢復操作，其他分區的服務不受影響.

3 基于條帶的并發IO調度恢復策略

數據恢復是在數據丟失后，分布式文件系統通過未丟失數據主動恢復,從而得到丟失數據的過程.數據恢復的效率，對于分布式文件系統至關重要.在糾刪碼環境下，條帶內塊間存在較強的約束關系，數據恢復涉及到條帶中多個塊的并發讀寫.因此，在糾刪碼環境下，數據恢復與調度的單位是條帶與節點組，應從條帶和節點組的角度考慮數據恢復的過程.糾刪碼數據恢復就是選取重建節點組，進行數據恢復IO和數據遷移IO的過程.

3.1 重建節點組

SCHash算法以條帶為單位放置數據，提供了一種重建節點組的選擇策略.從條帶與節點組的角度看，任何糾刪碼的數據恢復過程中，為保證糾刪碼的MDS性質，都是將數據從原節點組恢復至重建節點組.假設存儲系統中有S個同構的存儲節點，采用(N,M)的糾刪碼編碼方式，則每個條帶中有K(K=N+M)個數據塊，需要K個不同節點存儲.那么:

4) 對于每一個失效節點組，擁有S-K個差異度為1的重建節點組.即僅將丟失節點替換為其他節點，不存在數據遷移IO.

3.2 條帶外節點重建的并發I/O調度

在數據恢復中，重建節點往往是條帶外的其他節點.如圖4所示，可以將存儲集群中的節點分為同組節點、重建節點和其他節點.其中只有同組節點上存儲條帶數據.那么恢復一個條帶時，存在2種IO:1)從同組節點到重建節點的數據恢復IO(圖4中實線);2)從同組節點到同組節點和其他節點的數據遷移IO(圖4中虛線).

Fig. 4 The concurrent IO during data reconstruction out of stripe圖4 條帶外節點重建時的并發IO情況

3.3 條帶內節點重建的并發I/O調度

Fig. 5 The concurrent IO during data reconstruction in stripe圖5 條帶內節點重建時的并發IO情況

在數據恢復時，如果可選的重建節點組比較少，就可能會出現重建節點是條帶內同組節點的情況.如圖5所示，同樣可以將存儲集群中的節點分為同組節點、重建節點和其他節點.其中重建節點、同組節點上都存儲條帶數據.因為每個節點上至多存儲1個數據塊，所以重建節點上必然存在1個遷移IO.那么恢復1個條帶時，與條帶外節點重建時相比，還額外存在從重建節點到同組節點和其他節點的數據遷移IO(圖5中點畫線).

通過分析，3.2節中采用的策略依然有效，同時可以再采取3個策略，使得重建節點上的恢復IO與遷移IO并發進行：1)選取重建節點作為一個恢復IO的讀節點，該策略可以減少1次IO.2)重建節點與同組節點同時讀取.在恢復IO讀操作時，重建節點處于空閑狀態，因此可以進行恢復IO的讀操作.3)重建節點與同組節點、其他節點同時寫入.由于每個節點上至多存儲一個數據塊.每個遷移IO的寫操作必然不在同一個節點上進行，因此可以并發寫入.

4 ECFS數據恢復模塊的設計與實現

為了評測基于條帶的一致性Hash數據放置算法SCHash和基于條帶的并發IO調度恢復策略的實際效果，本文在基于糾刪碼的分布式文件系統(ECFS)[17-18]中改進了數據放置算法，設計并實現了數據恢復模塊.

如圖6所示，ECFS包括文件系統客戶端(client)、元數據服務器(MDS)、存儲服務器(OSD).為了實現數據恢復的功能，在系統中增加了管理服務器(manager)和腳本接口(shell).所有節點之間通過TCPIP通信庫AMP連接.

Fig. 6 ECFS architecture圖6 ECFS系統架構圖

客戶端是基于用戶態文件系統(file system in userspace, FUSE)[30]構建的.通過數據放置算法，客戶端可以直接確定數據的存放位置，然后直接與存儲服務器進行交互，完成數據讀寫操作.元數據服務器主要提供文件系統命名空間的管理，為用戶提供對文件的按名訪問服務.有關元數據的IO操作占據了超過整個文件系統IO操作的50%.為了使得元數據服務器能夠提供更好的IO吞吐率，在分布式文件系統中，元數據服務逐漸從文件系統中獨立出來，由專門的元數據服務器完成[31].存儲服務器是實際存儲數據的節點，負責數據塊的存取工作.客戶端通過數據放置算法，將數據塊發送到存儲服務器，存儲服務器將數據塊和校驗塊以文件的方式存儲在本地磁盤上.在數據更新時，數據塊會直接更新存儲的文件.

管理服務器中的信息均從系統中統計而來，當管理服務器丟失時，可以重新從系統中統計相關信息，重建管理服務器.因此，管理服務器并不會成為系統中的單點.為了增強系統的可靠性，可以同時部署多臺管理服務器，再通過選主協議保證多活管理服務器的可靠性.該方式與單臺管理服務器提供服務的方式并無區別，本節中通過單臺管理服務器說明系統設計.

5 測評與分析

本節基于分布式文件系統ECFS評測了基于條帶的一致性Hash數據放置算法SCHash的均衡性、擴展性和查詢性能，同時評測了基于條帶的并發IO調度恢復策略的調度效果.

5.1 測試環境

本節的相關測試是在一個擁有10個節點的機群上完成的，該機群中的所有節點采用星形網絡連接到同一個核心交換機上.為了減少操作系統IO的影響，操作系統與ECFS的數據分別存儲在不同的硬盤上.每個節點的軟硬件配置如表1所示:

Table 1 The Configuration of Machine表1 測試節點配置表

ECFS的部署方案為:選取一個物理節點同時作為元數據服務器和管理服務器，其他物理節點同時作為客戶端和存儲服務器，從而避免元數據操作與數據操作之間相互影響.所有評測中對糾刪碼的編碼方式并無特殊要求，所以在測試中如無特殊說明，均采用RS(4,2)編碼方式，每個數據塊大小為1 MB.為了消除測試過程中操作系統緩存的影響，每次測試前需清空系統緩存.

5.2 數據放置算法的測試

本節主要測試SCHash算法的查詢性能、擴展性和均衡性.假定每個寫入文件的大小為1 GB，inode號隨機產生，條帶號和塊號通過計算產生.逐漸向ECFS中寫入數據，測試數據放置算法的各項性能.

5.2.1 數據放置算法的查詢效率

APHash是一種類似順序放置的數據放置算法，同一條帶上連續順序編號的數據塊存放到連續的節點，且APHash實現簡單，查詢效率高效.SCHash以條帶為單位管理數據的放置關系，保證了條帶的連續存放，與APHash算法類似，同時SCHash針對APHash在數據節點發生變化時需要遷移的問題進行了優化.

Fig. 7 Read and write performance of SCHash and APHash圖7 不同數據放置算法的讀寫性能

5.2.2 節點變動時的遷移數據比

通過計算節點變動時的遷移數據比來反應節點變動時的遷移數據量.在節點變動后，存儲位置發生變化的數據塊數目，即為實際的遷移數據量.數據放置算法中數據存放的位置與糾刪碼編碼、數據傳輸等步驟無關.因此本測試采用模擬的方式，分別計算不同節點變化的模式下，節點變動前后數據塊的存儲位置，并統計存儲位置發生變化的數目，然后計算遷移數據的占比情況.

隨著系統存儲數據量的增長，在節點增加時遷移的數據量也會增長，這就可能對遷移數據比造成波動.如圖8所示，通過從6個節點增加到7個節點和12個節點，反映了不同節點增加情況下的遷移數據比與數據總量的關系.隨著數據總量的增加，遷移數據的比例基本不變，說明SCHash算法與APHash算法的遷移數據比均與總數據量的大小無關，SCHash算法遷移數據的數目要明顯少于APHash算法.

Fig. 8 Relationship between migration data ratio and total data when increasing the number of nodes圖8 增加節點時遷移數據比與數據總量的關系

5.2.3 數據放置算法的均衡性

通過計算每個存儲服務器中，存儲數據的相對標準差來反映數據放置的均衡性.與遷移數據比的測試相同，本測試采用模擬的方式，分別統計8,12,16個節點的集群，在數據放置的過程中，每個存儲服務器編號出現的次數，即可反映出實際存儲的數據塊數.

Fig. 9 Relationship between standard deviation and total data圖9 數據放置的相對標準差與數據總量的關系

如圖9所示，當數據量較少時，Hash算法的Hash值只分布于部分Hash空間上，SCHash算法與APHash算法的相對標準差都比較大，數據存儲不太均衡.但隨著存儲數據量的增大，相對均方差快速下降.當總數據量達到32 GB時，相對均方差降到0.5%以下且波動不大，說明各存儲服務器間存儲數據量的差異小于0.5%.一般來說，隨著數據量的增加，隨機放置算法放置的數據越均衡，相關測試基本反映出該趨勢.比較2種數據放置算法的均衡性，SCHash算法相對較差，但隨著數據量的增加差異逐漸減小，可以忽略不計.

5.3 系統恢復性能測試

數據恢復的性能受到網絡、磁盤、調度等多種因素的影響，應在分布式文件系統中測試實際的恢復帶寬.本節測試中采用7個節點作為存儲服務器，通過將某個節點的網卡關閉，模擬節點丟失的情況.統計從數據恢復任務開始到全部數據恢復結束中各部分操作的時間，并記錄期間恢復IO和遷移IO的數量，計算出恢復帶寬，從而反映系統的恢復性能.

如圖10所示，測試了采用不同的節點組構建方式時，系統恢復帶寬與總數據量的關系.其中，排列法構建的系統平均恢復帶寬為308.06 MBps，遷移數據比為21.65%；組合法構建的系統平均恢復帶寬為65.06 MBps，遷移數據比為59.59%；單點冗余法構建的系統平均恢復帶寬為61.57 MBps，遷移數據比為39.37%.排列法構建的系統，在節點丟失時，遷移的數據最少，同時能夠在多個節點上并發恢復數據，因此擁有較高的恢復性能.組合法與單點冗余法的恢復性能都相對較低.組合法遷移的數據量遠大于排列法，因此恢復性能較差.單點冗余法雖然遷移的數據量比較少，但主要在一個節點上重建數據，IO的并發度比較低，所以恢復性能也不高.通過對不同節點組構建方式的分析可知，恢復過程中的遷移數據量和IO的并發度，對于系統的恢復性能都有較大的影響.

Fig. 10 Influence of node group construction on recovery performance圖10 節點組構建方法對恢復性能的影響

5.4 并發I/O調度的測試

本節測試與系統恢復性能的測試方法相同，同樣模擬節點故障，通過測試系統的恢復帶寬，反應實際的恢復性能.在測試數據恢復之前，首先在恢復過程中，只執行恢復IO操作，不執行遷移IO操作，此時的恢復帶寬可以認為是基準恢復帶寬.然后再在恢復中加入遷移IO，分別測試有無調度時的恢復帶寬.通過對比有無調度時的恢復帶寬，計算恢復帶寬與基準恢復帶寬的比值，反映出并發IO調度的實際效果.在測試過程中，同時記錄每秒執行的IO數目.通過對比有無調度時單位之間的IO數目，反映出恢復過程中IO的并發度.

在組合法構建的系統中，當單個節點丟失時，不能保證每個丟失的節點組都存在差異度為1的重建節點組，這時選取的重建節點就可能在條帶以外，并產生同組節點間和同組節點到其他節點的遷移IO.因此本節測試采用組合法構建節點組，測試在8個節點中丟失1個節點時，條帶外節點重建的數據恢復中，并發IO調度的效果.

如圖11所示，測試了在32～256 GB存儲容量下有無調度時的恢復帶寬.首先測試了基準恢復帶寬，在圖11中以實線方形表示，平均值為73.54 MBps.然后分別測試了有無調度時的恢復帶寬.圖11中虛線圓形表示沒有調度時的恢復帶寬，平均值為27.73 MBps.實線圓形表示有調度時的恢復帶寬，平均值為66.11 MBps.通過測試可見，通過對并發IO的調度，恢復帶寬提升了138.44%，達到了基準恢復帶寬的89.93%(圖11中實線三角表示).

Fig. 11 The relationship between concurrent IO scheduling and data volume during data reconstruction out of stripe圖11 條帶外節點重建時并發IO調度與數據總量的關系

如圖12所示，測試了128 GB存儲容量下，在數據恢復過程中，每秒執行的IO數目.深色區域表示有調度時每秒的IO數目.淺色表示無調度時每秒的IO數目.通過調度，減少了遷移IO與恢復IO在同組節點上的競爭，每秒執行的IO數目普遍多于無調度的情況，并且執行數據恢復的時間更短.說明通過IO調度，提高了恢復IO與遷移IO的并發度，單位時間可以執行更多的IO操作.在有調度的情況下，隨著IO操作的逐步執行，IO操作的執行越來越呈現隨機性，最終導致調度失效.因此在調度過程中增加了同步操作，保證恢復IO與遷移IO能夠依照調度規則執行.所以從圖12中可見，在有調度的情況下，每執行一定數目的IO后會產生一次波動，執行的IO數目降為0，此時正在執行同步操作.

Fig. 12 The IOPS during data reconstruction out of stripe圖12 條帶外節點重建時每秒的IO總量

在單點冗余法構建的系統中，當單個節點丟失時，會在冗余的節點上恢復丟失的數據，冗余的節點同時也是條帶內的節點，這時就會產生從重建節點到同組節點的遷移IO.因此本節測試采用單點冗余法構建節點組，測試在7個節點中丟失1個節點時，條帶內節點重建的數據恢復中并發IO調度的效果.

Fig. 13 The relationship between concurrent IO scheduling and data volume during data reconstruction in stripe圖13 條帶內節點重建時并發IO調度與數據總量的關系

如圖13所示，測試了在32～256 GB存儲容量下有無調度時的恢復帶寬.首先測試了基準恢復帶寬，在圖13中以實線方形表示，平均值為71.96 MBps.然后分別測試了有無調度時的恢復帶寬.圖13中虛線表示沒有調度時的恢復帶寬，平均值為41.56 MBps；實線圓形表示有調度時的恢復帶寬，平均值為61.57 MBps.通過測試可見，通過對并發IO的調度，恢復帶寬提升了48.16%，達到了基準恢復帶寬的85.57%(圖13中實線三角表示).

如圖14所示，測試了128 GB存儲容量下，在數據恢復過程中，每秒執行的IO數目.深色區域表示有調度時每秒的IO數目.淺色表示無調度時每秒的IO數目.通過調度，重建節點上的遷移IO與恢復IO可以同步執行，每秒執行的IO數目普遍多于無調度的情況.并且執行數據恢復的時間更短.說明通過IO調度，提高了恢復IO與遷移IO的并發度，單位時間可以執行更多的IO操作.與條帶外節點重建的情況相同，在有調度的情況下，同樣存在同步操作產生的波動.

Fig. 14 The IOPS during data reconstruction in stripe圖14 條帶內節點重建時的IO總量

條帶內節點重建與條帶外節點重建相比較，在恢復相同數據塊時，條帶內節點重建涉及到的節點比較少，IO操作之間更容易發生沖突.因此，在條帶內節點重建時，IO調度所帶來的恢復帶寬的提升，小于條帶外節點重建時恢復帶寬的提升.

6 總 結

本文主要研究了糾刪碼分布式文件系統的恢復機制.糾刪碼作為一種數據存儲方式，既具有較高的空間利用效率，又能保證存儲數據的可靠性.但糾刪碼的引入給數據恢復帶來了新的挑戰.一方面，糾刪碼中將數據塊組成條帶，數據塊間放置位置的約束增強，在節點恢復中易造成額外的數據塊遷移;另一方面，糾刪碼的恢復過程中涉及更多的并發IO操作，這些IO操作間相關度大、并行度低，恢復帶寬不高.本文從條帶的角度出發，分析研究了糾刪碼在數據放置和恢復調度方面的特點，將文件系統中的處理單位從數據塊與節點，變化為條帶與節點組，從而解決了糾刪碼所引入的問題.