[發(fā)明專利]一種基于N-Code的RAID6磁盤(pán)陣列擴(kuò)容方法及數(shù)據(jù)填充方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110288850.6
• 申請(qǐng)日: 2021-03-18
• 公開(kāi)（公告）號(hào): CN112799604B
• 公開(kāi)（公告）日: 2022-06-17
• 發(fā)明（設(shè)計(jì)）人: 劉靖宇;李蕭言;牛秋霞;李浩鵬;顏鈺瑩;曹興旺;武優(yōu)西
• 申請(qǐng)（專利權(quán)）人: 河北工業(yè)大學(xué)
• 主分類號(hào): G06F3/06
• 分類號(hào): G06F3/06
• 代理公司: 天津翰林知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 12210
• 代理人: 王瑞

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

第一步、在磁盤(pán)陣列中添加新磁盤(pán)：

基于N-Code的RAID6磁盤(pán)陣列中，每個(gè)磁盤(pán)分成C個(gè)大小相同的塊，具有相同塊號(hào)的塊組成一個(gè)條帶，若干個(gè)條帶組成一個(gè)編碼陣列；N-Code的編碼陣列滿足(p_k-1)×(p_k+1)的布局，其中p_k為磁盤(pán)陣列第k次擴(kuò)容時(shí)的參數(shù)，k為正整數(shù)，p_k為大于3的質(zhì)數(shù)，p_k-1為條帶數(shù)量，p_k+1為磁盤(pán)數(shù)量；一個(gè)編碼陣列中共有(p_k-1)×(p_k+1)個(gè)塊，RAID6磁盤(pán)陣列有(p_k-1)²個(gè)數(shù)據(jù)塊和2×(p_k-1)個(gè)校驗(yàn)塊；校驗(yàn)塊分為對(duì)角校驗(yàn)塊和水平校驗(yàn)塊；

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

新磁盤(pán)添加后，根據(jù)式(1)將舊磁盤(pán)的磁盤(pán)號(hào)d_i調(diào)整為d_i’，得到新磁盤(pán)陣列；

第二步、調(diào)整編碼陣列；

檢測(cè)并記錄新磁盤(pán)陣列中每個(gè)磁盤(pán)的空白塊數(shù)量B_i并存儲(chǔ)在數(shù)組中，遍歷數(shù)組，找到新磁盤(pán)陣列中空白塊數(shù)量最少的磁盤(pán)d_min，磁盤(pán)d_min的空白塊數(shù)記為B_min；

采用式(2)計(jì)算擴(kuò)容閾值CT；若每個(gè)磁盤(pán)的空白塊數(shù)均超過(guò)CT，則說(shuō)明新磁盤(pán)陣列有超過(guò)CT條空白條帶；

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

情況一、當(dāng)0≤B_min≤CT時(shí)，調(diào)整編碼陣列的具體步驟如下：

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

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

步驟2、數(shù)據(jù)遷移：數(shù)據(jù)遷移分為校驗(yàn)塊遷移和數(shù)據(jù)塊遷移；新磁盤(pán)將添加新磁盤(pán)前的編碼陣列分為左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域；

對(duì)于校驗(yàn)塊，對(duì)角校驗(yàn)塊在編碼陣列標(biāo)準(zhǔn)化時(shí)已經(jīng)移動(dòng)到相應(yīng)位置，因此不需要遷移；需要遷移的水平校驗(yàn)塊為拼接條帶中的n個(gè)水平校驗(yàn)塊；遷移時(shí)，將拼接條帶中的n個(gè)水平校驗(yàn)塊分別水平移動(dòng)，使得拼接后的條帶集中的水平校驗(yàn)塊位于同一對(duì)角線上；在同一校驗(yàn)鏈中遷移不需要重新計(jì)算校驗(yàn)值，塊號(hào)不變，只改變磁盤(pán)號(hào)；

對(duì)于數(shù)據(jù)塊，需要遷移的數(shù)據(jù)塊為左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域中邊長(zhǎng)為min＝MIN[n,(m-2)/2]的等腰三角形區(qū)域中的數(shù)據(jù)塊；遷移時(shí)，數(shù)據(jù)遷移按照水平遷移規(guī)則和數(shù)據(jù)遷移量最小規(guī)則，將被選擇的遷移數(shù)據(jù)塊向新磁盤(pán)方向水平移動(dòng)n個(gè)磁盤(pán)，塊號(hào)不變，僅改變磁盤(pán)號(hào)；

所述水平遷移規(guī)則是：數(shù)據(jù)遷移始終保持在同一行中進(jìn)行；所述數(shù)據(jù)遷移量最小規(guī)則是：盡可能多地將遷移的數(shù)據(jù)塊移動(dòng)到原對(duì)角校驗(yàn)鏈中，并保證數(shù)據(jù)只從舊磁盤(pán)移動(dòng)到新磁盤(pán)，使得一個(gè)條帶集中維持2×min條原校驗(yàn)鏈；

步驟3、負(fù)載均衡：先從左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域分別選擇n/2條對(duì)角校驗(yàn)鏈作為犧牲對(duì)角校驗(yàn)鏈；再按照磁盤(pán)號(hào)的順序依次為犧牲對(duì)角校驗(yàn)鏈中的數(shù)據(jù)塊尋找寫(xiě)入位置，使數(shù)據(jù)塊當(dāng)前所在的磁盤(pán)號(hào)與目標(biāo)磁盤(pán)的距離最小，進(jìn)而實(shí)現(xiàn)負(fù)載均衡；距離通過(guò)取余函數(shù)計(jì)算得到；

犧牲對(duì)角校驗(yàn)鏈的選取原則是：按照各個(gè)對(duì)角校驗(yàn)鏈中包含的空白塊的數(shù)量，將所有對(duì)角校驗(yàn)鏈從多至少順序排列，并從包含最多空白塊的對(duì)角校驗(yàn)鏈開(kāi)始選擇，直至達(dá)到需要的對(duì)角校驗(yàn)鏈條數(shù)；

情況二、當(dāng)CT＜B_min≤C時(shí)，調(diào)整編碼陣列的具體步驟如下：

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

步驟2、數(shù)據(jù)遷移：新磁盤(pán)將添加新磁盤(pán)前的編碼陣列分為左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域，需要遷移的數(shù)據(jù)塊為左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域中邊長(zhǎng)為(m-2)/2的等腰三角形區(qū)域中的數(shù)據(jù)塊；

遷移時(shí)，將左側(cè)遷移區(qū)域和右側(cè)遷移區(qū)域中的數(shù)據(jù)塊向新磁盤(pán)方向水平移動(dòng)n個(gè)磁盤(pán)，即塊號(hào)不變，只改變磁盤(pán)號(hào)；數(shù)據(jù)遷移之后水平校驗(yàn)鏈和對(duì)角校驗(yàn)鏈都保持原鏈。