一种基于网络编码的分布式存储方法及其装置

摘要

一种基于网络编码的分布式存储方法及其装置，属于计算机存储技术领域，解决现有基于网络编码的分布式存储方法所存在的存储节点的磁盘IO过大的问题。本发明的分布式存储方法，适用于分布式存储系统，包括数据编码步骤、数据解码步骤和数据修复步骤；本发明的分布式存储装置，包括数据编码模块、数据解码模块和数据修复模块。本发明在数据节点损坏时，从d个数据节点下载不多于原始文件D大小的数据，修复损坏的数据，有效地减小修复带宽；直接从d个数据节点中下载随机选择的γ个编码数据块，数据块在数据节点内没有进行线性运算，在保证数据高可用性的前提下能够减小存储节点的磁盘IO，有效地提高数据节点的磁盘IO效率。

主权项

一种基于网络编码的分布式存储方法，适用于分布式存储系统，包括数据编码步骤、数据解码步骤和数据修复步骤，分布式存储系统由一个名字节点NS和P个存储节点{DS₁，DS₂，DS₃...DS_P}构成，P≥3，其中用于存储文件分块的存储节点称为数据节点，为n个，3≤n≤P；其特征在于：(1)数据编码步骤，包括下述子步骤：(1.1)数据分块：将原始文件D分割为c块等大小的原始数据块D_g，g＝0,1...c‑1，对于不足一块原始数据块大小的剩余原始数据D_B，先记下D_B的大小L_B，再将其使用零填充补足为原始数据块大小，作为原始数据块D_c‑1；c＝k×(d+1+i‑k)‑(i+1)×i/2，其中，k为恢复出原文件所需最少数据节点数目，2≤k<n；d为修复一个损坏节点时可用数据节点的数目，k≤d<n；i为编码冗余参数，0≤i≤k‑1；(1.2)冗余编码：将c个原始数据块D_g与编码矩阵M_e进行有限域2^q内的运算，编码为r个编码数据块C_b，q＝4、8、16、32或64；b＝0,1,...r‑1；r＝(d+1+i‑k)×n；$C_b={\Sigma }_{g=0}^{c-1}{a}_{b,g}{D}_g;$其中，编码矩阵M_e中的矩阵元素a_b,g为属于有限域2^q的整数，0≤a_b,g≤2^q－1,编码矩阵M_e为一个r行c列的范德蒙矩阵；每个C_b都是c个原始数据块D_g的线性组合，其中g＝0,1...c‑1，线性组合系数对应为编码矩阵M_e第b行的行向量V_b，即每个C_b对应编码矩阵M_e第b行的行向量V_b；(1.3)生成元数据文件D_meta：将编码矩阵M_e以及参数n、k、d、i、q和L_B保存在元数据文件D_meta中；(1.4)数据存储：将r个编码数据块C_b存放在n个数据节点d_f上,f＝0，1,...n‑1，每个数据节点存储α＝d+1+i‑k个编码数据块，并存储一份D_meta的副本；数据节点d_f存储的数据块为C_t，t＝f×α,f×α+1,...(f+1)α‑1；(2)数据解码步骤，包括下述子步骤：(2.1)获取文件元数据信息：下载原始文件D的元数据文件D_meta，得到编码矩阵M_e以及参数n、k、d、i、q和L_B；(2.2)下载可用数据块：判断n个数据节点中可用数据节点数是否小于k个，是则数据读取失败，退出；否则任意选择k个可用数据节点，k个可用数据节点中包含r_k＝k×α＝k×(d+1+i‑k)个编码数据块，共对应编码矩阵M_e中r_k个行向量：V_b1,V_b2...V_brk；从编码矩阵M_e这r_k个行向量中选择c个行向量，要求这c个行向量组成的方阵M_e1可逆，然后下载这c个行向量所对应的c个编码数据块：C_b0,C_b1...C_b(c‑1)；(2.3)冗余解码：对所述方阵M_e1矩阵求逆，得到其逆矩阵M_e1^‑1，逆矩阵M_e1^‑1中元素记为b_gj，其中行数g＝0,1,...c‑1，列数j＝0,1,...c‑1；将逆矩阵M_e1^‑1与下载的c个编码数据块做有限域2^q内的运算，得到c个原始数据块D_g，其中g＝0,1...c‑1；D_g为c个编码数据块C_b0,C_b1...C_b(c‑1)的线性组合，线性组合的系数为逆矩阵M_e1^‑1对应的行向量V_dg；(2.4)恢复数据：将冗余解码后得到的c个原始数据块D_g按其下标的顺序D₀,D₁...D_c‑1依次写入到恢复文件DO中，最后一块原始数据块D_c‑1只写其前L_B个字节到恢复文件DO中,形成恢复文件DO；(3)数据修复步骤，当一个数据节点d_v损坏时，v为0、1、...或n‑1，其存储的编码数据块的修复包括下述子步骤：(3.1)获取文件元数据信息：下载原始文件D的元数据文件D_meta，得到编码矩阵M_e以及参数n、k、d、i、q和L_B；设置下载数据块数目变量γ的初值：γ＝(2×c×d)/((2×k‑i‑1)×i+2×k×(d‑k+1))；(3.2)计算数据块修复信息，包括下述过程：(3.2.1)置循环次数变量N1＝0，判断n个数据节点中可用数据节点数是否小于d个，是则数据修复失败，退出；否则进行过程(3.2.2)；(3.2.2)从d个可用数据节点中随机选择γ个编码数据块，将它们对应的编码矩阵M_e的γ个行向量V_h组合为γ行c列矩阵Vs，h＝1,2...γ；置N1＝N1+1；(3.2.3)生成一个(d+1+i‑k)行γ列的修复矩阵M_r＝[m_p,h]，其中每个元素m_p,h从有限域2^q内随机取值，p＝1,2,...(d+1+i‑k)，h＝1,2,...γ；(3.2.4)建立r行c列的新编码矩阵M_e’，M_e’由原有行向量和新行向量V′_p构成，原有行向量为可用数据节点所包括的编码数据块对应的编码矩阵Me中的行向量，按其在M_e中原有位置存在于M_e’中，做有限域2^q内的矩阵M_r与矩阵Vs乘法运算，得到新行向量V′_p：$V_p^{\prime }={\Sigma }_{h=1}^{\gamma }{m}_{p,h}{V}_h,$用新行向量V′_p代替编码矩阵M_e中损坏的数据节点d_v所存储的α个编码数据块对应的行向量V_z,其中z＝v×α,v×α+1,...(v+1)×α‑1；(3.2.5)检查所述新编码矩阵M_e’是否满足MDS性质，是则进行子步骤(3.3)，否则进行过程(3.2.6)；所述MDS性质中文为最大距离可分性质，即n个节点中任意k个节点的数据可以恢复出原文件的数据；(3.2.6)判断是否N1≤L，是则转过程(3.2.2)；否则置N1＝0，置γ＝γ+1，然后转过程(3.2.2)，最大循环次数L＝1000～3000；(3.3)更新元数据文件：将元数据文件D_meta中的编码矩阵M_e替换为新编码矩阵M_e’,形成更新后的元数据文件D_meta’，将其拷贝到各个数据节点；(3.4)修复数据块：下载过程(3.2.2)中所随机选择的γ个编码数据块C_e1,C_e2,...C_eγ,做有限域2^q内矩阵M_r与γ个编码数据块C_e1,C_e2,...C_eγ的运算，得到修复的数据块C_p’：${C_p}^{\prime }={\Sigma }_{h=1}^{\gamma }{m}_{p,h}{C}_{eh};$C_p’为γ个编码数据块C_e1,C_e2,...C_eγ的线性组合，线性组合的系数为修复矩阵M_r对应的行向量V_rp；(3.5)存储数据块：将修复的数据块C_p’存储到一个新的可用数据节点上。