一種網絡編碼文件系統中基於數據溫度的重建方法
2023-05-08 20:27:01
一種網絡編碼文件系統中基於數據溫度的重建方法
【專利摘要】本發明公開了一種網絡編碼文件系統中基於數據溫度的重建方法，包括下述步驟：（1）數據溫度監控進程，負責監控數據區域訪問頻度的動態變化，統計訪問頻度；（2）重建任務調度進程，定義數據區域重建優先級為：該區域的數據溫度值/磁碟距離，數據溫度越高，與上一重建區域的距離越短，則該區域的重建優先級越高；（3）重建任務執行進程，從重建任務隊列中取出等待重建的任務，並進行相應的數據重建工作，直到所有數據區域重建工作完成。本發明通過優先重建熱點數據緩解了網絡編碼文件系統重建過程中用戶請求數據流與磁碟重建數據流爭用IO資源的矛盾，明顯地縮短了整個重建過程的耗時。
【專利說明】一種網絡編碼文件系統中基於數據溫度的重建方法
【技術領域】
[0001]本發明屬於計算機存儲【技術領域】，具體涉及了一種在網絡編碼文件系統中基於數據溫度的重建方法。
【背景技術】
[0002]在這個大數據的年代，數據量增長的速度是驚人的。據IDC報告顯示，預計到2020年全球數據總量將超過40ZB(相當於4萬億GB)，這一數據量是2011年的22倍。為了給海量數據提供有效的存儲及服務的能力，誕生了許多大規模數據存儲系統，比如GFS (谷歌文件系統)，Hadoop, OceanStore, Lustre, Gluster等。在這些大型存儲系統中，數據分布在一系列的節點(磁碟等物理介質)上，為了保證數據的可用性，系統必須能夠容忍節點失效。為了達到這一目的，分布式存儲系統弓I入了冗餘數據以提供容錯能力。
[0003]一般的容錯技術包括副本技術，糾刪碼技術和網絡編碼技術。副本技術對一個數據對象創建多個副本，併到這些副本分散到不同的節點上。當一個節點失效時，可以通過訪問其它節點的數據副本來重建新節點。比如GFS為每個數據塊提供了三個副本。糾刪碼技術是能夠容忍一個或多個節點同時失效的編碼技術，而且比副本技術有更高的空間存儲效率。常見的糾刪碼有Reed-Solomon碼，LDPC碼等。網絡編碼技術通過選擇特殊的編碼係數來構造生成矩陣，在節點修復時，把存儲在同一節點上的若干數據塊做線性運算，所以該節點傳輸一個數據塊就等於提供了做運算之前的若干個數據塊的信息，從而有效地節省了帶寬。
[0004]Dimakis等人於2007年首先在分布式存儲系統中引入網絡編碼思想，提出了一種稱為再生碼(regenerating code)的編碼技術。隨後，Rashmi等人提出了 exact minimumbandwidth regenerating (E-MBR)碼，突破了網絡編碼的理論階段給出了一個具體的最優帶寬再生碼方案。雖然網絡編碼在數據重建時的下載帶寬方面表現優越，但是其付出的運算開銷卻不可忽視。據NCFS研究表明，網絡編碼在退化模式下的表現明顯不如RAID5和RAID6。Lei Tian等人實現了以訪問頻度優先的數據重構優化方法來改善磁碟陣列中數據重建緩慢的問題，不過他們只限於對RAID5和RAIDlO的研究。基於此，本發明提出了一種在網絡編碼修復過程中利用數據溫度來加快數據重建過程的方法。
【發明內容】
[0005]本發明的主要目的是提供一種在網絡編碼文件系統中基於數據溫度的重建方法，本發明很好地解決了在網絡編碼文件系統中磁碟數據重建緩慢的問題，通過對訪問頻度高的數據區域優先重建，讓熱點數據的後續訪問請求能在磁碟上被命中，減少了重複的數據恢復解碼運算，另外，用戶請求數據流與磁碟重建數據流相互融合，能夠大幅度地縮短數據重建時間和用戶響應時間，提高存儲系統吞吐率。
[0006]本發明的目的通過下述技術方案實現:
[0007]一種網絡編碼文件系統中基於數據溫度的重建方法，包括下述步驟:[0008]( I)數據溫度監控進程，負責監控數據區域訪問頻度的動態變化，統計訪問頻度；
[0009](2)重建任務調度進程，定義數據區域重建優先級為:該區域的數據溫度值/磁碟距離，數據溫度越高，與上一重建區域的距離越短，則該區域的重建優先級越高。然後對數據區域的重建優先級按從高到低進行排序，選取優先級最高的數據區域作為當前任務，並把該任務放入重建任務隊列，直到所有數據區域的重建任務都已放入重建任務隊列；
[0010](3)重建任務執行進程，從重建任務隊列中取出等待重建的任務，並進行相應的數據重建工作，直到所有數據區域重建工作完成；
[0011](4)元數據對齊進程，新磁碟重建完成之後，把新磁碟的元數據上傳至上層文件系統集中管理，保持分布式存儲系統數據一致性。
[0012]優選的，當網絡編碼存儲系統中的某一個磁碟失效後，需要一個新磁碟來替代它，並且在新磁碟上面重建失效磁碟的原有數據信息；對於新磁碟，把它劃分成N個不重疊的連續區域，假如磁碟大小為M，數據區域大小為B，那麼N=M/B ;每個區域對應一個訪問頻度，用數組accessCount [N]表示,初始化為O ;用數組distance [N]來維護每個區域與當前重建區域的距離，初始化全為I ;用數組priority [N]來表示每個區域的重建優先級，初始化為O ;對於新磁碟上每個數據區域的重建狀態，用O代表未重建，I代表已重建，用數組constructed [N]表示，初始化為O ;啟動數據溫度監控進程，重建任務調度進程和重建任務執行進程。
[0013]優選的，步驟(I)中，數據溫度監控進程具體為:
[0014](1.U在文件系統的IO調度層註冊鉤子函數，監控每一個文件系統的對磁碟的IO請求，記錄IO請求的磁碟號及偏移地址Addr ；
[0015](1.2)如果磁碟號不是失效盤，則交給文件系統處理，否則計算該請求落入的區域號為 D=Addr/B ；
[0016](1.3)對訪問頻度數組作accessCount[D]做+1運算；
[0017](1.4)返回(1.3)。
[0018]優選的，步驟(2)中，重建任務調度進程具體為:
[0019](2.1)通過生產者-消費者模型，檢查重建任務隊列conQueue是否為空，如果不為空，則阻塞，否則轉到(2.2)；
[0020](2.2)計算重建優先級 priority[N],對於 i (O ?N-1),priority[i]=accessCount[i]/distance[i]ο 其中 accessCount[i]是數據溫度，distance [i]是i區域與上一個重建區域的區域號差的絕對值，如果i是上一個重建區域本身，那麼distance[i]取232 — I (理論上應取無窮大)；
[0021](2.3)遍歷數組priority [N],選取最大值priority [I],把I放入重建任務隊列conQueue,並把 accessCount [I]置為 _1 ；
[0022](2.4)返回(2.1)。
[0023]優選的，步驟(3)中，重建任務執行進程具體為:
[0024](3.1)檢查數組constructed [N]是否全為I,以判斷是否全部數據區域都已重建完成，如果是轉到(3.5)，否則轉到(3.2)；
[0025](3.2)通過生產者-消費者模型檢查重建任務隊列conQueue是否為空，如果為空，則阻塞，否則轉到(3.3)；[0026](3.3)獲取重建數據區域號I，執行以I為參數的數據重建函數，重建函數的過程與網絡編碼文件系統本身的重建過程一致；
[0027](3.4)修改表示數據區域是否已重建的狀態數組constructed [N]，置constructed [I]為 I ;返回(3.1)；
[0028](3.5)結束。
[0029]優選的，步驟(4)中，元數據對齊進程具體為:
[0030](4.1)收集新磁碟的元數據信息，包括磁碟設備號，磁碟容量大小，數據區域大小，數據重建的時間戳等；
[0031](4.2)把元數據信息寫入網絡編碼文件系統的元數據文件。
[0032]優選的，採用網絡編碼數據重建函數，無需連接所有存活節點，而只需要連接部分存活節點，利用生成矩陣來生成冗餘編碼塊，即可下載比原始信息少甚至和單個磁碟容量相等的冗餘信息來恢復數據。
[0033]優選的，所述網絡編碼為確定性最小帶寬再生碼E-MBR，所述E-MBR為一種準確性數據重建編碼，編碼時每個節點上的每個數據塊都在其餘節點中存在一個備份，每個節點的數據塊交集為I。
[0034]本發明相對於現有技術具有如下的優點及效果:
[0035](I)通過優先重建熱點數據緩解了重建過程中用戶請求數據流與磁碟重建數據流爭用IO資源的矛盾，明顯地縮短了整個重建過程的耗時。在存儲系統中，當磁碟失效之後，整個系統就處於退化模式。此時，用戶對失效磁碟的訪問由之前的直接訪問轉化成一系列複雜的流程，包括連接存活節點，從存活節點下載相應的冗餘信息，經過解碼得到原始信息，再從原始信息中提取失效磁碟存儲的那部分數據，以提供給用戶訪問。而另一方面，磁碟數據重建也需要從存活節點下載相應的數據信息，把經過解碼得到的數據寫到新的替代節點上。優先重建訪問頻度高的數據，可以把後續訪問該數據的請求直接引導到新磁碟節點上，從而避免了上述兩個過程的頻繁來回尋道，從而降低了磁碟重建的時間。
[0036](2)本發明通過優先重建熱點數據避免了反覆的數據恢復的編碼操作，使用戶請求的響應更加迅速。系統處於退化模式時，需從其它節點下載數據來恢復需要訪問的數據，再返回給用戶。如果該數據一直沒有被重建在新磁碟上，那麼每次這部分數據的訪問請求都會執行一遍數據恢復的編碼操作。優先重建熱點數據，讓熱點數據的訪問直接從新磁碟返回，加之熱點數據本身的訪問量大，從而避免了大量重複的編碼操作，加快了用戶請求的響應速度。。
[0037](3)本發明通過優先重建熱點數據提升了 I/O的效率，獲得了更高的吞吐率。磁碟完成一個I/O請求所花費的時間，由尋道時間、旋轉延遲和數據傳輸時間三部分構成，任何一部分時間的延遲都會使整個I/O請求的時間加長。本方法使得磁碟在某個時間段內，用戶請求數據和磁碟重建數據儘可能地重合，磁碟的讀寫儘量集中在某一片區域，從而減少了尋道的次數，縮短了旋轉延遲，每個I/O請求所花費的時間減少，獲得更高的吞吐率。。
【專利附圖】
【附圖說明】
[0038]圖1為本發明的網絡編碼文件系統中基於數據溫度的重建方法的系統架構示意圖；[0039]圖2為本發明的數據溫度監控進程工作流程圖；
[0040]圖3為本發明的重建任務調度進程工作流程圖；
[0041]圖4為本發明的重建任務執行進程工作流程圖。
【具體實施方式】
[0042]下面結合實施例及附圖對本發明作進一步詳細的描述，但本發明的實施方式不限於此。
[0043]實施例
[0044]如圖1所示，網絡編碼文件系統中基於數據溫度的重建方法的系統架構示意圖:
[0045]系統架構包括用戶、NCFS(Network Coding File System)和若干存儲節點。其中NCFS是基於FUSE，實現在用戶空間的網絡編碼文件系統。通過把物理節點掛載到當前的文件系統下面(如/mnt/ncfs)，就可以像訪問邏輯節點一樣訪問節點裡面的數據。NCFS主要由文件系統層，編碼層，存儲層組成。文件系統層負責文件系統的操作，比如文件讀、寫，刪除等；編碼層提供了 RAID5，RAID6, E-MBR的存儲編碼方式；存儲層提供訪問具體物理設備的接口。在實驗中，我們用Iinux作業系統的偽塊設備/dev/loop來模擬物理磁碟的存儲行為，用戶的讀、寫請求都是針對/dev/loopl，/dev/loop2等塊設備的讀寫。
[0046]另外，從用戶的角度，我們用帕雷託法則模擬了用戶請求的訪問行為。帕雷託法則又稱80-20法則，在計算機科學裡，80-20法則代表80%的資源只被20%的操作所使用。具體到文件系統的訪問行為，是指80%的請求往往集中在20%的文件上，從而導致某一部分數據被頻繁重複地訪問，而其它數據則相對訪問頻度較低。我們用該法則來產生用戶的請求，
以使數據訪問行為具有80-20特徵。具體公式為Px(j〕=長，其中
【權利要求】
1.一種網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，該方法基於網絡編碼文件系統，即以網絡編碼為存儲編碼的文件系統；方法包括下述步驟: (1)數據溫度監控進程，負責監控數據區域訪問頻度的動態變化，統計訪問頻度； (2)重建任務調度進程，定義數據區域重建優先級為:該區域的數據溫度值/磁碟距離，數據溫度越高，與上一重建區域的距離越短，則該區域的重建優先級越高；然後對數據區域的重建優先級按從高到低進行排序，選取優先級最高的數據區域作為當前任務，並把該任務放入重建任務隊列，直到所有數據區域的重建任務都已放入重建任務隊列； (3)重建任務執行進程，從重建任務隊列中取出等待重建的任務，並進行相應的數據重建工作，直到所有數據區域重建工作完成； (4)元數據對齊進程，新磁碟重建完成之後，把新磁碟的元數據上傳至上層文件系統集中管理，保持分布式存儲系統數據一致性。
2.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，當網絡編碼存儲系統中的某一個磁碟失效後，需要一個新磁碟來替代它，並且在新磁碟上面重建失效磁碟的原有數據信息；對於新磁碟，把它劃分成N個不重疊的連續區域，假如磁碟大小為M，數據區域大小為B，那麼N=M/B;每個區域對應一個訪問頻度，用數組accessCount[N]表示，初始化為O ;用數組distance[N]來維護每個區域與當前重建區域的距離，初始化全為I ;用數組priority [N]來表示每個區域的重建優先級,初始化為O ;對於新磁碟上每個數據區域的重建狀態，用O代表未重建，I代表已重建，用數組constructed [N]表示，初始化為O ;啟動數據溫度監控進程，重建任務調度進程和重建任務執行進程。
3.根據權利要求2所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，步驟(1)中，數據溫度監控進程具體為: (1.1)在文件系統的IO調度層註冊鉤子函數，監控每一個文件系統的對磁碟的IO請求，記錄IO請求的磁碟號及偏移地址Addr ； (1.2)如果磁碟號不是失效盤，則交給文件系統處理，否則計算該請求落入的區域號為D=Addr/B ； (1.3)對訪問頻度數組作accessCount[D]做+1運算；
(1.4)返回(1.3)。
4.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，步驟(2)中，重建任務調度進程具體為: (2.1)通過生產者-消費者模型，檢查重建任務隊列conQueue是否為空，如果不為空，則阻塞，否則轉到(2.2);
(2.2)計算重建優先級 priority [N],對於 i(0 ~N_1), priority [i] =accessCount [i] /distance [i];其中accessCount [i]是數據溫度,distance [i]是i區域與上一個重建區域的區域號差的絕對值，如果i是上一個重建區域本身，那麼distance[i]取232 — I ; (2.3)遍歷數組pri ority [N],選取最大值priority [I],把I放入重建任務隊列conQueue,並把 accessCount [I]置為 _1 ；
(2.4)返回(2.1)。
5.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，步驟(3)中，重建任務執行進程具體為: (3.1)檢查數組constructed [N]是否全為1，以判斷是否全部數據區域都已重建完成，如果是轉到(3.5)，否則轉到(3.2)； (3.2)通過生產者-消費者模型檢查重建任務隊列conQueue是否為空，如果為空，則阻塞，否則轉到(3.3)； (3.3)獲取重建數據區域號I，執行以I為參數的數據重建函數，重建函數的過程與網絡編碼文件系統本身的重建過程一致； (3.4)修改表示數據區域是否已重建的狀態數組constructed [N],置constructed [I]為I ;返回(3.1)； (3.5)結束。
6.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於，步驟(4)中，元數據對齊進程具體為: (4.1)收集新磁碟的元數據信息，包括磁碟設備號，磁碟容量大小，數據區域大小，數據重建的時間戳等； (4.2)把元數據信息寫入網絡編碼文件系統的元數據文件。
7.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於: 採用網絡編碼數據重建函數，無需連接所有存活節點，而只需要連接部分存活節點，利用生成矩陣來生成冗餘編碼塊，即可下載比原始信息少甚至和單個磁碟容量相等的冗餘信息來恢復數據。
8.根據權利要求1所述的網絡編碼文件系統中基於數據溫度的重建方法，其特徵在於: 所述網絡編碼為確定性最小帶寬再生碼E-MBR，所述E-MBR為一種準確性數據重建編碼，編碼時每個節點上的每個數據塊都在其餘節點中存在一個備份，每個節點的數據塊交集為I。
【文檔編號】G06F9/46GK103810027SQ201410037043
【公開日】2014年5月21日 申請日期:2014年1月24日 優先權日:2014年1月24日
【發明者】鄧玉輝, 李凱 申請人:暨南大學