专利交易市场

本发明公开了一种基于哈夫曼树的异构部分重复(Huffman Variable Fractional Repetition,HVFR)码的构造方法，包括以下步骤：将一定时间内的分布式系统的轨迹数据进行统计分析，分为不同访问频率的数据块；将这些不同访问频率的数据块当作哈夫曼树带有确定权值的叶子结点，根据哈夫曼算法构造哈夫曼树；再根据构造的哈夫曼树来确定不同访问频率数据块的重复度；对不同访问频率的数据块进行MDS编码，最后，利用成对平衡设计构造异构FR码。本发明的方法避免了热数据并行访问的瓶颈，达到负载均衡，同时提高系统存储效率，降低故障节点的修复局部性与修复带宽，且计算复杂度低，构造更加简单直观。

本发明公开了一种可同时恢复数据元素及冗余元素的纠删码解码方法，用以解决现有纠删码算法不能同时恢复数据元素与冗余元素的技术问题。该解码方法步骤包括：①构造一个方阵空间所述方阵空间由矩阵O及校验矩阵H上下拼接构成，其中，所述矩阵O由一个单位阵和一个全0矩阵左右拼接而成，矩阵O＝(I|0)；②构建丢失元素列表L；③对方阵空间A进行变换，得到新方阵空间A'由数据矩阵R和冗余矩阵U上下拼接构成；④A'中的非零行向量即为对应的丢失数据元素，非单位行向量即为对应的丢失冗余元素，建立方程组求解。本发明利用校验矩阵来恢复丢失元素，可以在恢复数据元素的同时将冗余元素也恢复出来，在一定程度上降低了计算量，提高了解码效率。

本发明公开了一种单节点故障快速修复纠删码的构造方法，包括：分别在横向方向和垂直(纵向)方向进行编码，首先进行横向方向上进行编码，生成横向局部校验和全局校验，保证编码的容错能力；在垂直方向上进行异或编码得到校验，使编码具有单节点快速修复能力。当分组内出现单个失效块时，通过垂直方向的异或校验进行修复，可减少修复带宽；当分组内出现多个块失效时，通过横向校验恢复，保持较高的容错能力。

本发明实施例公开了一种纠删译码方法及装置，方法包括：接收待译码数据，其中包含n个码元，n个码元包括：k个原始码元及r个校验码元；对n个码元进行递归运算，得到r个无偏伴随式；对r个无偏伴随式进行偏置，得到r个偏置伴随式；利用纠删求解关键方程及r个偏置伴随式，迭代计算删除位置多项式及删除值多项式；利用删除位置多项式及删除值多项式，计算得到每个删除位置对应的删除幅值，并利用删除幅值进行译码。一方面，先串行迭代计算每个无偏伴随式对应的偏置量，再根据偏置量对r个无偏伴随式进行偏置，得到r个偏置伴随式；这样，便可以处理码长不同的码元；另一方面，上述过程可以在n个周期内完成，提高了总线译码利用率。

本发明属于计算机领域，具体涉及非均匀故障保护的分组修复码构造方法及故障修复方法。分组修复码构造方法考虑到实际分布式存储系统中存在不同热度的文件，利用分组思想将整个条带分成长度依次递增的多个数据分组并在组内生成多个组编码块，并通过分组规模的选取为不同热度文件提供不同等级保护，进一步降低多故障节点的磁盘读取开销。该方法所存目标节点故障概率表征数据块故障概率并排序，为高故障概率数据节点提供更高等级保护。多节点故障修复方法在多节点故障修复时，选择先数据分组内修复后全局修复的整体修复原则，尽可能地降低了多节点修复时的磁盘读取开销。

本发明公开了一种基于部分重复码的局部性修复编码及节点故障修复方法，采用基于部分重复(Fractional Repetition,FR)码的局部性修复编码方法实现对数据的存储，可以控制局部修复组内的节点数目和局部修复组内的存储数据量，从而保证了节点的存储开销；当局部修复组中存在单节点和两节点故障时，都只需要通过局部修复组内有限的存活节点快速实现局部修复组内故障节点的数据重构，即可快速恢复出故障节点数据。