[發明專利]一種基于N-Code的RAID6磁盤陣列擴容方法及數據填充方法

有效

• 申請號: 202110288850.6
• 申請日: 2021-03-18
• 公開（公告）號: CN112799604B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 劉靖宇;李蕭言;牛秋霞;李浩鵬;顏鈺瑩;曹興旺;武優西
• 申請（專利權）人: 河北工業大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 天津翰林知識產權代理事務所(普通合伙) 12210
• 代理人: 王瑞

1.一種基于N-Code的RAID6磁盤陣列擴容方法，其特征在于，該擴容方法包括以下步驟：

第一步、在磁盤陣列中添加新磁盤：

基于N-Code的RAID6磁盤陣列中，每個磁盤分成C個大小相同的塊，具有相同塊號的塊組成一個條帶，若干個條帶組成一個編碼陣列；N-Code的編碼陣列滿足(p_k-1)×(p_k+1)的布局，其中p_k為磁盤陣列第k次擴容時的參數，k為正整數，p_k為大于3的質數，p_k-1為條帶數量，p_k+1為磁盤數量；一個編碼陣列中共有(p_k-1)×(p_k+1)個塊，RAID6磁盤陣列有(p_k-1)²個數據塊和2×(p_k-1)個校驗塊；校驗塊分為對角校驗塊和水平校驗塊；

增加的新磁盤數n＝p_k-p_k-1；舊磁盤陣列中共有m個磁盤，m＝p_k+1，舊磁盤的磁盤號為d_i(0≤i≤m-1)；將新磁盤插入舊磁盤陣列的中間位置處，則第j(0≤j≤n-1)塊新磁盤的磁盤號d_j＝(p_k-1+1)/2+j；

新磁盤添加后，根據式(1)將舊磁盤的磁盤號d_i調整為d_i’，得到新磁盤陣列；

第二步、調整編碼陣列；

檢測并記錄新磁盤陣列中每個磁盤的空白塊數量B_i并存儲在數組中，遍歷數組，找到新磁盤陣列中空白塊數量最少的磁盤d_min，磁盤d_min的空白塊數記為B_min；

采用式(2)計算擴容閾值CT；若每個磁盤的空白塊數均超過CT，則說明新磁盤陣列有超過CT條空白條帶；

式(2)中，C為單個磁盤中的塊總數；S_ad為添加新磁盤后每個編碼陣列增加的條帶數；S_k為添加新磁盤后每個編碼陣列的條帶總數；

情況一、當0≤B_min≤CT時，調整編碼陣列的具體步驟如下：

步驟1、編碼陣列標準化：將新磁盤陣列的一個操作單位的最后(L/S_k-1)-(L/S_k)個條帶集中的每n個條帶分為一組得到拼接條帶組，這些被分組拼接到其它條帶集中的條帶為拼接條帶；將每個拼接條帶組分別邏輯拼接到同一個操作單位的前L/S_k個條帶集的第(m-2)/2個條帶之后；

一個操作單位中包含L個條帶；添加新磁盤前一個操作單位有L/S_k-1個條帶集，添加新磁盤后一個操作單位有L/S_k個條帶集；L為S_k-1和S_k的最小公倍數；S_k-1表示添加新磁盤前每個編碼陣列的條帶總數；

步驟2、數據遷移：數據遷移分為校驗塊遷移和數據塊遷移；新磁盤將添加新磁盤前的編碼陣列分為左側遷移區域和右側遷移區域；

對于校驗塊，對角校驗塊在編碼陣列標準化時已經移動到相應位置，因此不需要遷移；需要遷移的水平校驗塊為拼接條帶中的n個水平校驗塊；遷移時，將拼接條帶中的n個水平校驗塊分別水平移動，使得拼接后的條帶集中的水平校驗塊位于同一對角線上；在同一校驗鏈中遷移不需要重新計算校驗值，塊號不變，只改變磁盤號；

對于數據塊，需要遷移的數據塊為左側遷移區域和右側遷移區域中邊長為min＝MIN[n,(m-2)/2]的等腰三角形區域中的數據塊；遷移時，數據遷移按照水平遷移規則和數據遷移量最小規則，將被選擇的遷移數據塊向新磁盤方向水平移動n個磁盤，塊號不變，僅改變磁盤號；

所述水平遷移規則是：數據遷移始終保持在同一行中進行；所述數據遷移量最小規則是：盡可能多地將遷移的數據塊移動到原對角校驗鏈中，并保證數據只從舊磁盤移動到新磁盤，使得一個條帶集中維持2×min條原校驗鏈；

步驟3、負載均衡：先從左側遷移區域和右側遷移區域分別選擇n/2條對角校驗鏈作為犧牲對角校驗鏈；再按照磁盤號的順序依次為犧牲對角校驗鏈中的數據塊尋找寫入位置，使數據塊當前所在的磁盤號與目標磁盤的距離最小，進而實現負載均衡；距離通過取余函數計算得到；

犧牲對角校驗鏈的選取原則是：按照各個對角校驗鏈中包含的空白塊的數量，將所有對角校驗鏈從多至少順序排列，并從包含最多空白塊的對角校驗鏈開始選擇，直至達到需要的對角校驗鏈條數；

情況二、當CT＜B_min≤C時，調整編碼陣列的具體步驟如下：

步驟1、編碼陣列標準化：條帶拼接時，從d_min中的第一個空白塊所在的條帶開始，將新磁盤陣列中每n條空白條帶分為一組，邏輯拼接到前面每個條帶集的第(m-2)/2個條帶之后；

步驟2、數據遷移：新磁盤將添加新磁盤前的編碼陣列分為左側遷移區域和右側遷移區域，需要遷移的數據塊為左側遷移區域和右側遷移區域中邊長為(m-2)/2的等腰三角形區域中的數據塊；

遷移時，將左側遷移區域和右側遷移區域中的數據塊向新磁盤方向水平移動n個磁盤，即塊號不變，只改變磁盤號；數據遷移之后水平校驗鏈和對角校驗鏈都保持原鏈。