[发明专利]一种基于纠删码的数据块重建方法

摘要

一种基于纠删码的数据块重建方法，属于计算机存储技术领域，解决现有数据块修复方法需要传输大量数据的问题，以减少重建数据的传输量。本发明包括数据分块步骤、构造生成矩阵G步骤、生成校验块步骤、检查数据块状态步骤、构造修复矩阵步骤和修复数据块步骤。本发明将原始文件分为k个数据块，将每个数据块继续等分为r个数据片；k个数据块编码为m个校验块，每个校验块也包含r个校验片。重建任意一个数据块时，从剩余的每个数据块的r个数据片和校验块的r个校验片中取r/m片(该方法保证r被m整除)，从而重建一个数据块只需要总量(m+k‑1)r/m的数据片，相对里德‑所罗门编码重建一个数据块的数据量，有了明显的减少。

主权项

一种基于纠删码的数据块重建方法，包括数据分块步骤、构造生成矩阵G步骤、生成校验块步骤、检查数据块状态步骤、构造修复矩阵步骤和修复数据块步骤，其特征在于：(1)数据分块步骤：将数据量为M的原始文件等分为k个数据块Dj，j＝0、…、k‑1，再将k个数据块分别保存在k个数据节点上，进而将各数据节点上的数据块Dj等分为r个数据片Dj,p，p＝0、…、r‑1，r＝mk‑1，k≥2，m≥2；等分过程中不足部分用0补齐并记录不足数据块或数据片的长度；对所有数据片赋予序号，数据片Dj,p为第j×r+p+1个数据片；(2)构造生成矩阵G步骤：生成矩阵G是m行、k列的分块矩阵，包括m×k个子矩阵Gi,j：G0,0G0,1LG0,k-1G1,0G1,1LG1,k-1LLLLGm-1,0Gm-1,1LGm-1,k-1,]]>其中，每个子矩阵Gi,j为一个r行、r列的方阵，满足下面等式：Gi,j=(Imi+)⊗j⊗(Im)⊗(k-1-j)gαi,j,i=0~m-1,j=0~k-1;]]>其中，表示矩阵的张量乘(也称为Kronecker乘)，Im表示m行、m列的单位矩阵，表示单位矩阵Im所有元素循环左移i位后的结果，当i＝0时，表示j个连续张量乘的结果，αi,j是(m+k,k)‑里德‑所罗门编码生成矩阵中第i行第j列元素；(3)生成校验块步骤：分别计算生成矩阵G中各行子矩阵和所有数据块的乘积，得到m个校验块Ci，i＝0～m‑1,再将m个校验块分别保存在m个数据节点上，第i个校验块Ci为生成矩阵G的第i行子矩阵与k个数据块的乘积：Ci=Ci,0Ci,1MCi,r-1=Gi,0Gi,1LGi,k-1gD0D1MDk-1;]]>校验块Ci再等分为r个校验片Ci,p，p＝0～r‑1；对所有校验片赋予序号，校验片Ci,p为第i×r+p+1个校验片；(4)检查数据块状态步骤：定期依次检查各数据节点上的数据块是否出错或丢失，是则转步骤(5)；否则不作处理；(5)构造修复矩阵步骤，包括下述子步骤：(5.1)当第i个数据节点上的数据块Di出错或丢失，将生成矩阵G中第i列的子矩阵全设置为0，构成第一中间矩阵GA；(5.2)在第一中间矩阵GA中选取任意一个非零子矩阵，在该非零子矩阵中选取任意一个非零矩阵元素作为种子，在第一中间矩阵GA中标记该非零矩阵元素所在的行向量与列向量；(5.3)对所标记的行向量与列向量中的每个非零矩阵元素，在第一中间矩阵GA中标记该非零矩阵元素所在的行向量和列向量；(5.4)判断是否有新的行向量和列向量被标记，是则转子步骤(5.3)，否则进行子步骤(5.5)；(5.5)构成修复矩阵Mr：首先生成一个k×r行，k×r列的单位矩阵GB；将第一中间矩阵GA标记的列向量序号作为行向量序号，从单位矩阵GB中选取对应的行向量，作为第一行向量组；将第一中间矩阵GA标记的行向量序号作为行向量序号，从生成矩阵G中选取对应的行向量，作为第二行向量组；将所述第一行向量组置于第二行向量组之上，构成第二中间矩阵Gc，将第二中间矩阵Gc中全零列删除得到正方矩阵Gd，然后从正方矩阵Gd的逆矩阵中选择从i×r/m开始的r个行向量，构成r行、(k+m－1)×r/m列的修复矩阵Mr；(6)修复数据块步骤：选取第一中间矩阵GA标记的列向量的列序号作为数据片序号，其所对应的各数据片作为数据片序列SDr，数据片数量为(k－1)×r/m，选取第一中间矩阵GA标记的行向量的行序号作为校验片序号，其所对应的各校验片作为校验片序列SCr，校验片数量为m×r/m；通过计算Mr和由数据片序列SDr与校验片序列SCr组成的矩阵的乘积重建数据块Di：Di=Mr×SDrSCr.]]>