一种基于纠删码的失效数据线形修复方法

摘要

本发明公开了一种基于纠删码的失效数据线形修复方法，目的是设计针对纠删码特点的失效数据修复方法。方案是构建由一个控制节点和N个存储节点构成的分布存储系统，控制节点装有任务管理程序和结果回收程序，存储节点装有修复程序；任务管理程序为失效数据块选择新存储节点LN；从数据对象的可用数据块中选择可用数据块，构建线形修复路径；修复程序进行解码计算，将解码计算结果沿线形修复路径传送和合并；LN的修复程序接收来自线形修复路径最后一个存储节点的解码计算结果，结果回收程序接收LN的修复成功信息。采用本发明能有效避免网络中的瓶颈带宽，缩短修复数据的传输距离，降低失效数据修复的带宽成本，提高失效数据的修复效率。

主权项

一种基于纠删码的失效数据线形修复方法，其特征在于包括以下步骤：第一步，构建一个由多个节点构成分布存储系统，每个节点都是一台可独立运行的计算机，各节点通过网络设备互连；分布存储系统中的节点分为两类：控制节点和存储节点，控制节点和存储节点上均安装有操作系统、TCP/IP协议软件，配置了网络环境；分布存储系统包括一个控制节点，负责与用户交互，接收用户提交的失效数据块修复请求；负责存储解码系数，构建线形修复路径，向各存储节点分发失效数据块修复任务和接收修复成功信息，向用户返回修复成功信息；分布存储系统包括N个存储节点，N为正整数，它们负责存储数据对象的原始数据块和冗余数据块，执行失效数据块修复任务，并向控制节点返回修复成功信息；设数据对象DO分割为k个原始数据块，对其进行编码计算得到m个冗余数据块，这k+m个数据块分别存储在不同的存储节点上，k+m<N；在分布存储系统中，每个数据块拥有唯一的数据块编号；控制节点上安装有任务管理程序和结果回收程序，任务管理程序接收用户提交的失效数据块修复请求，为失效数据块选择新存储节点；从数据对象DO的k+m‑1个可用数据块中选择k个可用数据块；根据存储节点之间的网络距离构建线形修复路径，向k个可用数据块所在的存储节点发送失效数据块修复请求及修复所需的相关信息；结果回收程序负责接收存储节点的修复成功信息并返回给用户；存储节点上安装有修复程序，修复程序负责接收来自控制节点的失效数据块修复请求，并对存储节点上存储的可用数据块进行解码计算，完成修复后向控制节点发送修复成功信息；第二步，控制节点执行任务管理程序，为待修复的失效数据块D_i选择新存储节点LN；从数据对象DO的k+m‑1个可用数据块中选择k个可用数据块；根据存储节点之间的网络距离构建线形修复路径，向k个可用数据块所在的存储节点发送失效数据块D_i修复请求、可用数据块编号及其解码系数H_ij、线形修复路径数组Path、失效数据块D_i的新存储节点LN的编号，1≤i≤k，j＝1,2,…,k，具体方法是：2.1控制节点的任务管理程序接收用户提交的失效数据块D_i修复请求；2.2控制节点的任务管理程序从可用存储节点中选择一个存储节点作为失效数据块D_i的新存储节点LN，选择原则是新存储节点LN未存储数据对象DO的任何数据块；2.3控制节点的任务管理程序从数据对象DO的k+m‑1个可用数据块中选择k个可用数据块，k个可用数据块所在的存储节点构成集合NSet；2.4控制节点的任务管理程序根据存储节点之间的网络距离构建线形修复路径，采用线形修复路径数组Path存储线形修复路径中的存储节点，Path[j]表示线形修复路径的第j个存储节点，1≤j≤k，线形修复路径长度也为k，具体步骤如下：2.4.1初始化信息，具体包括：2.4.1.1目标存储节点TN＝LN；2.4.1.2线形修复路径节点序号j＝k；2.4.2根据集合NSet中的所有存储节点与目标存储节点TN之间的网络距离，确定与目标存储节点TN距离最近的存储节点NN，Path[j]＝NN；2.4.3将存储节点NN从NSet中删除，即，NSet＝NSet‐{NN}；2.4.4更新目标存储节点，TN＝NN；2.4.5更新线形修复路径节点序号，j＝j‑1；2.4.6如果j＝0，转第2.5步；否则，转到第2.4.2步；2.5控制节点的任务管理程序向k个可用数据块所在的存储节点发送失效数据块D_i修复请求、可用数据块编号及其解码系数H_ij、线形修复路径数组Path、失效数据块D_i的新存储节点LN的编号；解码系数H_ij是指纠删码解码计算H_i1×E₁+…+H_ij×E_j+…+H_ik×E_k＝D_i中的解码系数，E_j是可用数据块，“×”表示H_ij与可用数据块E_j进行逐位相乘；第三步，线形修复路径中的各存储节点执行修复程序，接收来自控制节点的失效数据块D_i修复请求、可用数据块编号及其解码系数H_ij、线形修复路径数组Path、失效数据块D_i的新存储节点LN的编号；基于可用数据块及其解码系数H_ij进行解码计算，并将解码计算结果沿着线形修复路径进行传送和合并，并将合并后的最终解码结果发送给失效数据块D_i的新存储节点LN：3.1初始化信息，线形修复路径节点序号j＝1；3.2存储节点Path[j]的修复程序接收来自控制节点的失效数据块D_i修复请求、可用数据块编号及其解码系数H_ij、线形修复路径数组Path、失效数据块D_i的新存储节点LN的编号；3.3存储节点Path[j]的修复程序根据可用数据块编号获取本地存储的可用数据块E_j，进行本地解码计算，将解码系数H_ij与可用数据块E_j进行逐位相乘，即，S_ij＝H_ij×E_j，解码计算结果得到新数据块S_ij；3.4如果j>1，存储节点Path[j]的修复程序接收存储节点Path[j]在线形修复路径中的前继存储节点Path[j‑1]发送来的解码计算结果数据块S_i(j‑1)，并将S_i(j‑1)与本地解码计算结果数据块S_ij进行合并，即，S_ij＝S_ij+S_i(j‑1)，将数据块S_ij和S_i(j‑1)进行逐位相加，转第3.5步；否则，转第3.5步；3.5如果j<k，存储节点Path[j]的修复程序将解码计算结果数据块S_ij发送给存储节点Path[j]在线形修复路径中的后继存储节点Path[j+1]，转第3.6步；否则，存储节点Path[j]的修复程序将解码计算结果数据块S_ij发送给失效数据块D_i的新存储节点LN，转第四步；3.6更新线形修复路径节点序号，j＝j+1，转第3.2步；第四步，失效数据块D_i的新存储节点LN的修复程序接收来自线形修复路径的最后一个存储节点的最终解码计算结果，向控制节点发送修复成功信息；第五步，控制节点的结果回收程序接收来自新存储节点LN的修复成功信息，并向用户返回修复成功信息。