CN106100801A

CN106100801A - A kind of non-homogeneous erasure code method of cloud storage system

Info

Publication number: CN106100801A
Application number: CN201610743775.7A
Authority: CN
Inventors: 胡玉鹏; 邓俊杰; 伍麟珺; 温冠超; 皮玲
Original assignee: Hunan University
Current assignee: Hunan University
Priority date: 2016-08-29
Filing date: 2016-08-29
Publication date: 2016-11-09
Anticipated expiration: 2036-08-29
Also published as: CN106100801B

Abstract

The invention discloses a non-uniform erasure correction coding method for a cloud storage system. According to the failure rate of physical storage nodes, data blocks stored on them are divided into logical groups of different sizes, and different levels of data are provided for different groups. Erasure protection, thus giving more protection to data on storage nodes with high failure rates, while making their repair costs lower. In this way, the present invention can improve the overall reliability of the system by strengthening the protection of data on storage nodes with high failure rates, and can further reduce the overall system repair costs by reducing the data recovery costs on storage nodes with high failure rates.

Description

A non-uniform erasure coding method for cloud storage system

技术领域technical field

本发明涉及一种云存储系统的非均匀纠删编码方法。The invention relates to a non-uniform erasure correction coding method for a cloud storage system.

背景技术Background technique

近年来，以大型数据中心为代表的云存储系统发展迅猛(如Windows AzureStorage、Amazon S3、Google GFS^]、EMC ATMOS等)，累积的数据量从PB到EB甚至到ZB，使得云存储网络规模和节点数量呈爆炸式增长，但是数据的失效率也随之越来越高(例如，Google云存储中心的每执行一个MapReduce作业平均有5个左右节点失效，大约4000个节点的Hadoop系统平均6个小时就有一个磁盘失效，且其失效率随系统规模增长而迅速增长)。存储节点(指存储服务器或磁盘)在失效后，导致所存储数据不可访问，尤其是关键数据的丢失，将给用户带来巨大损失。所以，需要采用数据纠删或灾备技术来保证数据的可靠性，在一部分数据删除(即丢失)后，能够进行纠删操作，仍然能保证存储系统正常工作。多副本技术(通常是3副本)是众多云存储系统的默认存储标准，是常用的数据灾备技术，在原始数据丢失后，用剩余副本进行替换。Google GFS、Hadoop HDFS和CFS等云存储系统中均采用多副本技术，其基本策略是：在文件对象写入时，将其拆分为固定大小的数据块(如64M)进行分布式存储，且每个数据块在写入时复制为多个副本，采用链式方式依次推送到云存储网络中的不同存储节点，当某些存储节点失效时，可对冗余副本进行复制操作，恢复出数据块。总的来看，n副本技术的主要优点体现在：一是能很好地支持并发读操作，在数据读取率高时具有性能优势；二是数据重构/恢复开销不大，丢失一个数据块，只要复制一个数据块即可。但是，其缺点也较明显：数据副本的存储开销极其巨大，其存储开销是正常情况的n倍，尤其是当对系统容删除能力要求高时，该问题尤为突出。基于有限域运算的(n,k)纠删码(Erasure Codes)能将n个数据块编码为(n+k)个纠删码分块(多出k个冗余校验数据块)，只要获取其中任意n个纠删码分块就能恢复所有n个原始数据块，能最多容删除k个数据块。代表性的Reed-Solomon编码，即RS(n,k)纠删码是一种系统性编码，即编码后原n个数据块保持不变，剩余k个冗余校验数据块为原始数据块计算得来。与多副本技术相比，容错能力相同条件下纠删码技术的存储效率更高、成本更低；例如，若按照100PB数据(WindowsAzure Storage 2012年左右规模)，$1/GB/年，按容错能力1来计算(若副本技术和纠删码各需要2倍和1.5倍存储空间)，则仅存储开销纠删码每年便可节省$52,428,800。In recent years, cloud storage systems represented by large-scale data centers have developed rapidly (such as Windows AzureStorage, Amazon S3, Google GFS ^] , EMC ATMOS, etc.), and the accumulated data volume has ranged from PB to EB or even to ZB, making cloud storage network scale and The number of nodes is growing explosively, but the data failure rate is also getting higher and higher (for example, every time a MapReduce job is executed in the Google cloud storage center, there are about 5 node failures on average, and the Hadoop system with about 4000 nodes has an average of 6 failures. One disk fails every hour, and the failure rate increases rapidly with the size of the system). When a storage node (referring to a storage server or a disk) fails, the stored data becomes inaccessible, especially the loss of key data, which will bring huge losses to users. Therefore, it is necessary to use data correction or disaster recovery technology to ensure the reliability of data. After some data is deleted (that is, lost), the correction operation can be performed, and the normal operation of the storage system can still be guaranteed. Multi-copy technology (usually 3 copies) is the default storage standard of many cloud storage systems, and it is a commonly used data disaster recovery technology. After the original data is lost, the remaining copies are used to replace it. Cloud storage systems such as Google GFS, Hadoop HDFS, and CFS all use multi-copy technology. The basic strategy is: when a file object is written, it is split into fixed-size data blocks (such as 64M) for distributed storage, and Each data block is copied into multiple copies when written, and pushed to different storage nodes in the cloud storage network in a chained manner. When some storage nodes fail, the redundant copies can be copied to restore the data piece. In general, the main advantages of n-copy technology are as follows: first, it can well support concurrent read operations, and has performance advantages when the data reading rate is high; second, the data reconstruction/recovery overhead is not large, and one data loss block, just copy a block of data. However, its disadvantages are also obvious: the storage overhead of the data copy is extremely huge, and its storage overhead is n times that of the normal situation, especially when the system has high requirements for the capacity to delete. (n,k) erasure codes (Erasure Codes) based on finite field operations can encode n data blocks into (n+k) erasure code blocks (more than k redundant check data blocks), as long as Obtaining any n erasure code blocks among them can restore all n original data blocks, and can delete up to k data blocks. The representative Reed-Solomon code, that is, the RS(n,k) erasure code is a systematic code, that is, the original n data blocks remain unchanged after coding, and the remaining k redundant check data blocks are the original data blocks Calculated. Compared with multi-copy technology, erasure coding technology has higher storage efficiency and lower cost under the same fault tolerance; 1 (if the copy technology and the erasure code require 2 times and 1.5 times the storage space respectively), then only the storage overhead erasure code can save $52,428,800 per year.

因此，为了在保障数据高可靠性的同时尽可能地降低系统的存储开销和运营成本，各主流云存储服务供应商采用的典型技术是将逐渐冷却后的数据块编码为纠删码并删除多余副本，即在热数据块存储早期采用多副本冗余(如标准的3副本机制)以保证并发读操作性能，而当数据块逐渐冷却后(用户访问率低时)则采用纠删码技术将其转换为纠删码分块存储。例如，微软的Windows Azure Storage采用LRC纠删码处理冷数据块、Google的GFS II(colossus)系统采用RS(6,3)纠删码处理冷数据块，Facebook的f4云存储系统则采用Xorbas和Hitchhiker纠删码、DiskReduce系统和EMC的ATMOS系统则采用RS(10,6)或RS(9,3)等纠删码。然而，纠删码技术的缺点也很明显：(n,k)纠删码最大的缺陷是需要获取至少n个数据块才能恢复原始数据；当只需要恢复一个数据块时，仍然需要获取n个数据块，其数据恢复时的系统I/O和网络带宽成本太高，远高于多副本技术中只要一个数据块的开销。显然，在大规模云存储环境下将导致其数据恢复/重构效率低，网络开销大，往往难以适应云存储环境下的数据密集型处理需求。目前纠删码技术主要是研究如何在存储空间开销和数据修复流量开销之间进行权衡处理，以解决纠删码技术数据修复流量开销大的问题，近年来产生了多种新技术，如再生码、本地重构码LRC(Local Reconstruction Codes)。Therefore, in order to reduce system storage overhead and operating costs as much as possible while ensuring high data reliability, the typical technology adopted by mainstream cloud storage service providers is to encode gradually cooled data blocks into erasure codes and delete redundant data blocks. Copy, that is, in the early stage of hot data block storage, multi-copy redundancy (such as the standard 3-copy mechanism) is used to ensure the performance of concurrent read operations, and when the data block gradually cools down (when the user access rate is low), erasure coding technology is used to It translates to erasure coded block storage. For example, Microsoft's Windows Azure Storage uses LRC erasure codes to process cold data blocks, Google's GFS II (colossus) system uses RS (6,3) erasure codes to process cold data blocks, and Facebook's f4 cloud storage system uses Xorbas and Hitchhiker erasure codes, DiskReduce systems, and EMC's ATMOS systems use erasure codes such as RS(10,6) or RS(9,3). However, the disadvantages of erasure code technology are also obvious: (n,k) The biggest defect of erasure code is that at least n data blocks need to be obtained to restore the original data; when only one data block needs to be restored, n data blocks still need to be obtained For data blocks, the cost of system I/O and network bandwidth during data recovery is too high, much higher than the overhead of only one data block in multi-copy technology. Obviously, in a large-scale cloud storage environment, the data recovery/reconstruction efficiency will be low, and the network overhead will be large, which is often difficult to adapt to the data-intensive processing requirements in the cloud storage environment. At present, the erasure code technology is mainly to study how to balance the storage space overhead and the data repair traffic overhead, so as to solve the problem of large data repair traffic overhead of the erasure code technology. In recent years, a variety of new technologies have been produced, such as regenerative code , Local Reconstruction Codes LRC (Local Reconstruction Codes).

然而，目前云存储中心的纠删码技术均沿袭传统的通信领域的编码方法，没有针对数据失效模式的特点进行设计。近年来，已经有不少研究表明，各个存储节点的失效率是不一致的，受到多种物理参数的影响(如，存储节点所在机柜的水槽温度、磁盘工作温度、磁盘工作年龄等)，呈现出一种非均匀分布的特点。例如，微软公司通过大量的实验统计，得出的研究结果表明，不同磁盘的年平均失效率随平均工作温度变化而有较大的波动，年平均失效率最高可达12％，最低时则为3％左右；而存储服务器的年平均失效率与所在机柜的水槽温度有较大关联，在2％～14％之间波动，可见通常最大失效率是最小失效率的6-7倍。由于各个存储设备的失效率不同，将导致其存储的数据的失效率不同，呈现出一种非均匀分布。However, the current erasure coding technology in the cloud storage center follows the traditional coding method in the communication field, and has not been designed for the characteristics of data failure modes. In recent years, many studies have shown that the failure rate of each storage node is inconsistent and is affected by various physical parameters (such as the temperature of the water tank in the cabinet where the storage node is located, the operating temperature of the disk, the age of the disk, etc.), showing a A characteristic of a non-uniform distribution. For example, Microsoft Corporation, through a large number of experimental statistics, has obtained research results that show that the annual average failure rate of different disks fluctuates greatly with the average operating temperature. The average annual failure rate of the storage server is closely related to the water tank temperature of the cabinet where it is located, fluctuating between 2% and 14%. It can be seen that the maximum failure rate is usually 6-7 times the minimum failure rate. Since the failure rate of each storage device is different, the failure rate of the data stored therein will be different, presenting a non-uniform distribution.

发明内容Contents of the invention

本发明所要解决的技术问题是，针对现有技术不足，提供一种云存储系统的非均匀纠删编码方法。The technical problem to be solved by the present invention is to provide a non-uniform erasure correction coding method for a cloud storage system in view of the deficiencies in the prior art.

为解决上述技术问题，本发明所采用的技术方案是：一种云存储系统的非均匀纠删编码方法，包括以下步骤：In order to solve the above-mentioned technical problems, the technical solution adopted in the present invention is: a method for non-uniform erasure correction coding of a cloud storage system, comprising the following steps:

1)找出要编码的冷数据块，并对所述冷数据块进行分组，将易失数据块放入小分组，不易失效的数据块放入大分组；1) Find out the cold data blocks to be encoded, and group the cold data blocks, put the volatile data blocks into small groups, and put the data blocks that are not easy to fail into large groups;

2)构造非均匀编码生成矩阵，并利用编码生成矩阵对冷数据块进行编码；2) Construct a non-uniform encoding generation matrix, and use the encoding generation matrix to encode the cold data block;

3)对编码后的数据块和冗余校验块进行部署。3) Deploy the encoded data blocks and redundancy check blocks.

步骤1)的具体实现过程包括：The specific implementation process of step 1) includes:

1)采用冷数据判断方法找出需要处理的冷数据块集合C，分批对冷数据块进行处理，每次处理一个子集SC＝{D₀,D₁,...,D_z},D_z表示冷数据块；z表述冷数据块的个数；1) Use the cold data judgment method to find out the cold data block set C that needs to be processed, and process the cold data blocks in batches, one subset at a time SC={D ₀ , D ₁ ,...,D _z }, D _z represents the cold data block; z represents the number of cold data blocks;

2)对子集SC包含的数据块分别进行随机映射，即采用随机哈希函数，将某个冷数据映射到某个存储节点上，表示该冷数据块在编码处理后要迁移到该存储节点，记录存储节点的ID值；2) Randomly map the data blocks contained in the subset SC, that is, use a random hash function to map a certain cold data to a certain storage node, indicating that the cold data block will be migrated to the storage node after encoding processing , record the ID value of the storage node;

3)利用目前已获得的存储节点的失效率对冷数据进行排序，将要存储在高失效率节点上(如年平均失效率高于10％)的易失效数据块排在最前面，存储在较低失效率(如年平均失效率低于10％)节点上的不易失效数据块排后面；3) Sort the cold data by using the failure rate of the storage nodes that have been obtained so far, and arrange the vulnerable data blocks that will be stored on the nodes with high failure rate (such as the annual average failure rate is higher than 10%) at the top, and store them in the lower Low failure rate (such as the annual average failure rate is less than 10%) nodes that are not prone to failure data blocks are ranked behind;

4)将最前面k₀个数据块，即放入第一组，在将随后的(k₀+1)个数据块放入第二组，再将随后的(k₀+2)个数据块放入第三组，以此类推，直到把最后的(k₀+l-1)个数据块放入第l个分组，且 4) Put the first k ₀ data blocks, namely Put into the first group, put the subsequent (k ₀ +1) data blocks into the second group, then put the subsequent (k ₀ +2) data blocks into the third group, and so on, until the The last (k ₀ +l-1) data blocks are put into the lth packet, and

构造非均匀编码生成矩阵，并利用编码生成矩阵对冷数据块进行编码的具体实现过程包括：构建编码生成矩阵G，通过G编码后让第(i+1)个分组有一个本地校验数据块p_i，i＝0,1,...,l-1，此外，所有分组还共享r个全局校验数据块P_j，j＝0,1,...,r-1，p_i由各个组内的冷数据块异或生成，P_j由所有的冷数据块乘以编码系数后再异或生成，G满足下式：The specific implementation process of constructing a non-uniform coding generation matrix and using the coding generation matrix to encode cold data blocks includes: constructing a coding generation matrix G, and allowing the (i+1)th group to have a local check data block after G coding p _i , i=0,1,...,l-1, in addition, all groups also share r global parity data blocks P _j , j=0,1,...,r-1, p _i is determined by The cold data blocks in each group are XOR generated, and P _j is generated by multiplying all the cold data blocks by the coding coefficient and then XOR is generated. G satisfies the following formula:

$G G \cdot \cdot (\begin{matrix} {D D.}_{00} \\ {D D.}_{11} \\ ... ... \\ {D D.}_{| | S S C C | | - - 11} \end{matrix}) = = (\begin{matrix} {p p}_{00} \\ {p p}_{11} \\ ... ... \\ {p p}_{l l - - 11} \\ {P P}_{00} \\ {P P}_{11} \\ ... ... \\ {P P}_{r r - - 11} \end{matrix});;$

用线性方程组表示为：Expressed as a system of linear equations:

$\{\begin{matrix} {D D.}_{00} + + {D D.}_{11} + + ... ... + + {D D.}_{{k k}_{00} - - 11} = = {p p}_{00} \\ {D D.}_{{k k}_{00}} + + {D D.}_{{k k}_{00} + + 11} + + ... ... + + {D D.}_{22 {k k}_{00}} = = {p p}_{11} \\ ...... … \\ {D D.}_{| | S S C C | | - - {k k}_{00} - - l l + + 11} + + ... ... + + {D D.}_{| | S S C C | | - - 11} = = {p p}_{l l - - 11} \\ {a a}_{00} {D D.}_{00} + + {a a}_{11} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}} {D D.}_{22 {k k}_{00}} + + {c c}_{00} ... ... = = {P P}_{00} \\ {a a}_{00}^{22} {D D.}_{00} + + {a a}_{11}^{22} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11}^{22} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00}^{22} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}}^{22} {D D.}_{22 {k k}_{00}} + + {c c}_{00}^{22} ... ... = = {P P}_{11} \\ ...... … \\ {a a}_{00}^{r r - - 22} {D D.}_{00} + + {a a}_{11}^{r r - - 22} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11}^{r r - - 22} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00}^{r r - - 22} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}}^{r r - - 22} {D D.}_{22 {k k}_{00}} + + {c c}_{00}^{r r - - 22} ... ... {P P}_{r r - - 11} \end{matrix} . .$

对编码后的数据块和冗余校验块进行部署的具体实现过程包括：利用G生成冗余的校验数据块，得到编码后的冷数据块集合将它们部署到相应的存储节点，所有冷数据块根据已记录的存储节点ID值进行部署，校验数据块按随机映射方法进行部署。The specific implementation process of deploying the encoded data blocks and redundant check blocks includes: using G to generate redundant check data blocks, and obtain the encoded cold data block set Deploy them to the corresponding storage nodes, all cold data blocks are deployed according to the recorded storage node ID value, and the verification data blocks are deployed according to the random mapping method.

与现有技术相比，本发明所具有的有益效果为：本发明通过加强高失效率存储节点上数据的保护能提高系统的总体可靠性，通过降低高失效率存储节点上数据的修复开销能进一步降低系统总体修复开销，可以在保持相同容删除能力的前提下，有效地降低数据重构开销，包括磁盘I/O开销和网络流量开销，从而有效提升存储系统的性能。Compared with the prior art, the present invention has the beneficial effects that: the present invention can improve the overall reliability of the system by strengthening the protection of data on storage nodes with high failure rates, and can reduce the data repair overhead on storage nodes with high failure rates. Further reducing the overall system repair overhead can effectively reduce data reconstruction overhead, including disk I/O overhead and network traffic overhead, while maintaining the same capacity for deletion, thereby effectively improving the performance of the storage system.

附图说明Description of drawings

图1显示了UFP-LRC(2,2,2)编码方案的示意图。Figure 1 shows a schematic diagram of the UFP-LRC(2,2,2) encoding scheme.

图2显示了理论数值分析下的平均恢复开销对比。Figure 2 shows the comparison of average recovery overhead under theoretical numerical analysis.

图3显示了不同存储开销下的平均恢复开销对比。Figure 3 shows the comparison of average recovery overhead under different storage overheads.

图4显示了可用性对比。Figure 4 shows the usability comparison.

图5显示了实际系统实验中的平均恢复开销对比。Figure 5 shows the comparison of the average recovery overhead in the actual system experiment.

图6显示了数据恢复失败率对比。Figure 6 shows the comparison of data recovery failure rates.

具体实施方式detailed description

本发明设计的编码方法UFP-LRC(Unequal Failure Protection based LocalReconstruction Codes)分为以下几个步骤：第一步是找出对要编码的冷数据块，并对它们进行分组，将易失数据块放入较小分组，不易失效的数据块放入较大分组；第二步是构造非均匀编码生成矩阵，并利用编码生成矩阵对冷数据块进行编码；第三步是对编码后的数据块和冗余校验块进行部署。The encoding method UFP-LRC (Unequal Failure Protection based Local Reconstruction Codes) designed by the present invention is divided into the following steps: the first step is to find out the cold data blocks to be encoded, and group them, and put the volatile data blocks into into smaller groups, and data blocks that are not easy to fail are put into larger groups; the second step is to construct a non-uniform encoding generation matrix, and use the encoding generation matrix to encode cold data blocks; the third step is to encode the encoded data blocks and Redundancy check blocks are deployed.

对于编码方案UFP-LRC(k₀,l,r)而言，具体编码实施过程如下：For the coding scheme UFP-LRC(k ₀ ,l,r), the specific coding implementation process is as follows:

第一步：采用通用的冷数据判断方法找出需要处理的冷数据块集合C，分批对冷数据块进行处理，每次处理一个子集SC＝{D₀,D₁,...,D_z},D_z表示冷数据块。Step 1: Use the common cold data judgment method to find out the cold data block set C that needs to be processed, and process the cold data blocks in batches, one subset at a time SC={D ₀ , D ₁ ,...,D _z }, where D _z represents a cold data block.

第二步：对子集SC包含的数据块分别进行随机映射，即采用通用的随机哈希函数，将某个冷数据映射到某个存储节点上(通常可以保证不同的数据块映射到不同的存储节点，避免关联失效)，表示该冷数据块在编码处理后要迁移到该存储节点，记录存储节点的ID值。Step 2: Randomly map the data blocks contained in the subset SC, that is, use a general random hash function to map a certain cold data to a certain storage node (usually it can be guaranteed that different data blocks are mapped to different storage node, to avoid association failure), indicating that the cold data block will be migrated to the storage node after encoding processing, and record the ID value of the storage node.

第三步：利用目前已获得的存储节点的失效率对冷数据进行排序，那些将要存储在高失效率节点上的易失效数据块排在最前面，存储在较低失效率节点上的不易失效数据块排后面。Step 3: Sort the cold data by using the failure rate of the storage nodes that have been obtained so far. Those data blocks that are prone to failure to be stored on nodes with a high failure rate are ranked at the top, and those stored on nodes with a lower failure rate are not easy to fail. The data blocks are in the back.

第四步：把数据块分为l个分组。即将最前面k₀个数据块(即)放入第一组，在将随后的(k₀+1)个数据块(即)放入第二组，再将随后的(k₀+2)个数据块放入第三组，以此类推，直到把最后的(k₀+l-1)个数据块放入第l个分组。且 Step 4: Divide the data block into l groups. That is, the first k ₀ data blocks (ie ) into the first group, and the subsequent (k ₀ +1) data blocks (ie ) into the second group, and then put the subsequent (k ₀ +2) data blocks into the third group, and so on, until the last (k ₀ +l-1) data blocks are put into the lth grouping. and

第五步：构建校验码生成矩阵G，即系数矩阵。通过G编码后可以让第(i+1)个分组有一个本地校验数据块p_i(i＝0,1,...,l-1)，此外，所有分组还共享r个全局校验数据块P_j(j＝0,1,...,r-1)。p_i由各个组内的数据块异或生成，P_j而由所有的数据块乘以编码系数后再异或生成。G满足下面式(1)，运算都在有限域上进行。Step 5: Construct the check code generation matrix G, that is, the coefficient matrix . After G encoding, the (i+1)th group can have a local check data block p _i (i=0,1,...,l-1), in addition, all groups also share r global checks Data block P _j (j=0,1,...,r-1). p _i is generated by XOR of the data blocks in each group, and P _j is generated by XOR of all data blocks multiplied by coding coefficients. G satisfies the following formula (1), and the operations are performed on finite fields.

$G G \cdot &Center Dot; (\begin{matrix} {D D.}_{00} \\ {D D.}_{11} \\ ... ... \\ {D D.}_{| | S S C C | | - - 11} \end{matrix}) = = (\begin{matrix} {p p}_{00} \\ {p p}_{11} \\ ... ... \\ {p p}_{l l - - 11} \\ {P P}_{00} \\ {P P}_{11} \\ ... ... \\ {P P}_{r r - - 11} \end{matrix}) - - - - - - ((11))$

用线性方程组表示为：Expressed as a system of linear equations:

$\{\begin{matrix} {D D.}_{00} + + {D D.}_{11} + + ... ... + + {D D.}_{{k k}_{00} - - 11} = = {p p}_{00} \\ {D D.}_{{k k}_{00}} + + {D D.}_{{k k}_{00} + + 11} + + ... ... + + {D D.}_{22 {k k}_{00}} = = {p p}_{11} \\ ...... … \\ {D D.}_{| | S S C C | | - - {k k}_{00} - - l l + + 11} + + ... ... + + {D D.}_{| | S S C C | | - - 11} = = {p p}_{l l - - 11} \\ {a a}_{00} {D D.}_{00} + + {a a}_{11} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}} {D D.}_{22 {k k}_{00}} + + {c c}_{00} ... ... = = {P P}_{00} \\ {a a}_{00}^{22} {D D.}_{00} + + {a a}_{11}^{22} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11}^{22} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00}^{22} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}}^{22} {D D.}_{22 {k k}_{00}} + + {c c}_{00}^{22} ... ... = = {P P}_{11} \\ ...... … \\ {a a}_{00}^{r r - - 22} {D D.}_{00} + + {a a}_{11}^{r r - - 22} {D D.}_{11} + + ... ... {a a}_{{k k}_{00} - - 11}^{r r - - 22} {D D.}_{{k k}_{00} - - 11} + + {b b}_{00}^{r r - - 22} {D D.}_{{k k}_{00}} + + ... ... + + {b b}_{{k k}_{00}}^{r r - - 22} {D D.}_{22 {k k}_{00}} + + {c c}_{00}^{r r - - 22} ... ... {P P}_{r r - - 11} \end{matrix} - - - - - - ((22))$

其中，a,b,c,...,都为需要构造的有限域上的编码系数，所有的参数a对应的是第一组数据的编码系数，b对应的是第二组数据的编码系数，c为第三组的编码系数,以此类推。这些编码系数都是一旦设定好，下一轮数据块子集处理时，即可重复使用。Among them, a, b, c,..., are the coding coefficients on the finite field that need to be constructed, and all parameters a correspond to the coding coefficients of the first group of data, and b correspond to the coding coefficients of the second group of data , c is the coding coefficient of the third group, and so on. Once these coding coefficients are set, they can be reused in the next round of data block subset processing.

这些编码系数需要满足下面的式(3)：These coding coefficients need to satisfy the following formula (3):

a_x,a_y,b_s,b_t,c_v,c_w...≠0a _x ,a _y ,b _s ,b _t ,c _v ,c _w ...≠0

a_x≠a_y,b_s≠b_t,c_v≠c_w,...a _x ≠a _y ,b _s ≠b _t ,c _v ≠c _w ,...

a_x,a_y≠b_s,b_t≠c_v,c_w≠...a _x ,a _y ≠b _s ,b _t ≠c _v ,c _w ≠...

a_x+a_y≠b_s+b_t≠c_v+c_w≠...a _x +a _y ≠b _s +b _t ≠c _v +c _w ≠...

a_x≠b_s+b_t,b_s≠a_x+a_y,c_v≠a_x+a_y,... (3)a _x ≠b _s +b _t ,b _s ≠a _x +a _y ,c _v ≠a _x +a _y ,... (3)

式(3)表示：所有编码系数a,b,c,...,都不为0；任意组内和组之间的两个编码系数都不相等；任意组内的两个系数之和都不等于另外一个组内的两个系数之和；任意一个系数都不等于其它组内的任意两个系数之和(注意：这里的和运算表示有限域上的异或运算)。Equation (3) expresses: all coding coefficients a, b, c, ... are not 0; the two coding coefficients in any group and between groups are not equal; the sum of the two coefficients in any group is equal to It is not equal to the sum of two coefficients in another group; any coefficient is not equal to the sum of any two coefficients in other groups (note: the sum operation here represents the XOR operation on the finite field).

通过选择满足式(3)的编码系数，UFP-LRC(k₀,l,r)将具有良好的容删除能力：By selecting the coding coefficients satisfying formula (3), UFP-LRC(k ₀ ,l,r) will have a good ability to tolerate erasure:

(1)所构造的UFP-LRC编码具有最大可恢复性。即只要线性方程组理论上能解码，即可进行数据恢复。(1) The constructed UFP-LRC code has maximum recoverability. That is, as long as the linear equations can be decoded theoretically, data recovery can be performed.

(2)具有非均匀纠删编码保护，即前(r-k₀+1)个分组能容忍删除任意(r+2)个原始数据块；而后面的分组没有此特性。(2) It has non-uniform erasure coding protection, that is, the first (rk ₀ +1) group can tolerate the deletion of any (r+2) original data blocks; but the latter group does not have this feature.

(3)能够容忍删除任意(r+1)个删除的块(包括原始数据块和校验数据块)。、(3) It can tolerate deletion of any (r+1) deleted blocks (including original data blocks and check data blocks). ,

(4)最多容忍删除(l+r)个块(包括原始数据块和校验数据块)。(4) Tolerate deletion of (l+r) blocks (including original data blocks and check data blocks) at most.

第六步：按照式(1)，利用G生成冗余的校验数据块。最后得到编码后的数据块集合将它们部署到相应的存储节点，所有数据块D根据已记录的存储节点ID值进行部署，校验数据块按随机映射方法或其它常用映射方法进行部署。Step 6: According to formula (1), use G to generate redundant check data blocks. Finally, the encoded data block collection is obtained Deploy them to corresponding storage nodes, all data blocks D are deployed according to the recorded storage node ID values, and check data blocks are deployed according to random mapping method or other commonly used mapping methods.

第七步：最后，当某些存储节点失效时，设当有m个数据块，n个校验数据块丢失时，将失效的校验数据块p_i或P_j对应的方程从式(2)中删除，删除对应的n个方程后，再从剩余的线性方程中找出任意m个方程构建一个新的方程组(只要该方程组理论上有确定唯一解，即对应的线性矩阵可逆)，求解该方程组即可得出所有|SC|个原始数据块D₀,D₁,...,D^|SC|-1，完成数据修复。Step 7: Finally, when some storage nodes fail, it is assumed that when there are m data blocks and n verification data blocks are lost, the equation corresponding to the failed verification data block p _i or P _j is calculated from the formula (2 ), delete the corresponding n equations, and then find any m equations from the remaining linear equations to construct a new equation system (as long as the equation system has a unique solution in theory, that is, the corresponding linear matrix is invertible) , solving this equation system can obtain all |SC| original data blocks D ₀ , D ₁ ,...,D ^|SC|-1 , and complete the data restoration.

下面以UFP-LRC(2,2,2)为例进行详细说明具体的编码和修复过程。The following takes UFP-LRC(2,2,2) as an example to describe the specific encoding and restoration process in detail.

第一步：设采用通用的冷数据块判断方法(如，根据最近访问时间，长时间没有访问的数据标记为冷数据)，找出目前需要编码的5个冷数据块子集SC＝{D₀,D₁,...,D₄}。Step 1: Assume that a common cold data block judgment method is adopted (for example, according to the latest access time, data that has not been accessed for a long time is marked as cold data), and find out the 5 cold data block subsets that need to be coded at present SC={D ₀ ,D ₁ ,...,D ₄ }.

第二步：对子集SC包含的数据块分别进行随机映射，让不同的数据块映射到不同的存储节点或机柜，记录目标存储节点的ID值。Step 2: Randomly map the data blocks included in the subset SC, so that different data blocks are mapped to different storage nodes or cabinets, and record the ID value of the target storage node.

第三步：利用目标存储节点的失效率(失效率可由相关物理参数估计出)对冷数据块进行排序，设排序后为{D₀,D₁,...,D₄}；D₀为最易失效数据块，D₄为最不易失效数据块。Step 3: Use the failure rate of the target storage node (the failure rate can be estimated by the relevant physical parameters) to sort the cold data blocks, and set it to be {D ₀ ,D ₁ ,...,D ₄ } after sorting; D ₀ is The data block most prone to failure, D ₄ is the data block least likely to fail.

第四步：把数据块分为2个分组。即将最前面2个数据块(即D₀～D₁)放入第一组，在将随后的3个数据块(即D₂～D₄)放入第二组。Step 4: Divide the data block into 2 groups. That is, put the first two data blocks (ie, D ₀ to D ₁ ) into the first group, and put the next three data blocks (ie, D ₂ to D ₄ ) into the second group.

第五步：构建校验码生成矩阵G。构建G关键是在有限域空间选择有效的满足式(3)的编码系数a,b。具体的选择方法是采用一种交错的方式：让第一组的编码系数的高位为0，低位为1，而第二组编码系数的高位为1，低位为0。因此，在有限域GF(2⁵)空间中选择系数：a₀＝00011,a₁＝00010,b₀＝11000,b₁＝10000,b₂＝01000。以后每轮数据块编码都用这些系数。Step 5: Construct the check code generation matrix G. The key to constructing G is to select effective coding coefficients a and b satisfying formula (3) in the finite field space. The specific selection method is to use an interleaving method: let the high bit of the first group of coding coefficients be 0 and the low bit be 1, while the high bit of the second group of coding coefficients is 1 and the low bit is 0. Therefore, the coefficients are selected in the finite field GF(2 ⁵ ) space: a ₀ =00011, a ₁ =00010, b ₀ =11000, b ₁ =10000, b ₂ =01000. These coefficients are used in each subsequent round of data block encoding.

则校验数据块生成矩阵为：Then the check data block generation matrix is:

$G G = = (\begin{matrix} 11 & 11 & 00 & 00 & 00 \\ 00 & 00 & 11 & 11 & 11 \\ {a a}_{00} & {a a}_{11} & {b b}_{00} & {b b}_{11} & {b b}_{22} \\ {a a}_{00}^{22} & {a a}_{11}^{22} & {b b}_{00}^{22} & {b b}_{11}^{22} & {b b}_{22}^{22} \end{matrix}) - - - - - - ((44))$

则生成校验数据块的方程组为：Then the equations for generating the check data block are:

$\{\begin{matrix} {D D.}_{00} + + {D D.}_{11} = = {p p}_{00} \\ {D D.}_{22} + + {D D.}_{33} + + {D D.}_{44} = = {p p}_{11} \\ {a a}_{00} {D D.}_{00} + + {a a}_{11} {D D.}_{11} + + {b b}_{00} {D D.}_{22} + + {b b}_{11} {D D.}_{33} + + {b b}_{22} {D D.}_{44} = = {P P}_{00} \\ {a a}_{00}^{22} {D D.}_{00} + + {a a}_{11}^{22} {D D.}_{11} + + {b b}_{00}^{22} {D D.}_{22} + + {b b}_{11}^{22} {D D.}_{33} + + {b b}_{22}^{22} {D D.}_{44} = = {P P}_{11} \end{matrix} - - - - - - ((55))$

图1显示了UFP-LRC(2,2,2)的编码后的分组示意图。Figure 1 shows a schematic diagram of the encoded grouping of UFP-LRC(2,2,2).

第六步：按照式(1)，利用G生成冗余的校验数据块。具体编码时，是采用循环方式每次选取对每个数据块的一小块字节进行编码处理(如从每个数据块D中取16个bits)，以保证编码速度,则编码运算在GF(2¹⁶)上进行；最后得到编码后的数据块集合将它们部署到相应的存储节点，所有数据块D根据已记录的存储节点ID值进行部署，校验数据块按随机映射方法或其它常用映射方法进行部署。Step 6: According to formula (1), use G to generate redundant check data blocks. When encoding specifically, a small block of bytes of each data block is selected each time in a cyclic manner (for example, 16 bits are taken from each data block D) to ensure the encoding speed, and the encoding operation is performed in GF (2 ¹⁶ ); finally get the encoded data block set Deploy them to corresponding storage nodes, all data blocks D are deployed according to the recorded storage node ID values, and check data blocks are deployed according to random mapping method or other commonly used mapping methods.

第七步：当某些存储节点失效时，设数据块D₀,D₁,D₂都丢失，校验数据块p₀丢失时，将失效的校验数据块p₀对应的方程删除，再从剩余的线性方程中仍然可以找出3个方程构建一个新的方程组，D₃,D₄作为常数，解出下面式(6)的方程组即可恢复出D₀,D₁,D₂。Step 7: When some storage nodes fail, assume that the data blocks D ₀ , D ₁ , and D ₂ are all lost, and when the verification data block p ₀ is lost, delete the equation corresponding to the failed verification data block p ₀ , and then From the remaining linear equations, 3 equations can still be found to construct a new equation system, D ₃ , D ₄ are used as constants, and D ₀ , D ₁ , D ₂ can be recovered by solving the equation system of the following formula (6) .

$\{\begin{matrix} {D D.}_{22} = = {p p}_{11} - - {D D.}_{33} - - {D D.}_{44} \\ {a a}_{00} {D D.}_{00} + + {a a}_{11} {D D.}_{11} + + {b b}_{00} {D D.}_{22} = = {P P}_{00} - - {b b}_{11} {D D.}_{33} - - {b b}_{22} {D D.}_{44} \\ {a a}_{00}^{22} {D D.}_{00} + + {a a}_{11}^{22} {D D.}_{11} + + {b b}_{00}^{22} {D D.}_{22} = = {P P}_{11} - - {b b}_{11}^{22} {D D.}_{33} - - {b b}_{22}^{22} {D D.}_{44} \end{matrix} - - - - - - ((66))$

即 which is

其对应的系数矩阵G'如式(7)所示。由于有效地选择了编码系数，可以保证系数矩阵的向量是线性无关的，即|G'|＝a₀a₁(a₁-a₀)≠0，故式(7)具有逆矩阵，式(6)有唯一确定解。Its corresponding coefficient matrix G' is shown in formula (7). Since the coding coefficients are effectively selected, the vector of the coefficient matrix can be guaranteed to be linearly independent, that is, |G'|=a ₀ a ₁ (a ₁ -a ₀ )≠0, so formula (7) has an inverse matrix, and formula ( 6) There is a unique definite solution.

${G G}^{' '} = = (\begin{matrix} 00 & 00 & 11 \\ {a a}_{00} & {a a}_{11} & {b b}_{00} \\ {a a}_{00}^{22} & {a a}_{11}^{22} & {b b}_{00}^{22} \end{matrix}) - - - - - - ((77))$

即如式(8)所示，通过求逆矩阵可以恢复原数据D₀,D₁,D₂。其它情况下的数据丢失采用类似的方法进行恢复。That is, as shown in formula (8), the original data D ₀ , D ₁ , and D ₂ can be recovered by calculating the inverse matrix. Data loss in other situations can be recovered in a similar way.

$(\begin{matrix} {D D.}_{00} \\ {D D.}_{11} \\ {D D.}_{22} \end{matrix}) = = {(\begin{matrix} 00 & 00 & 11 \\ {a a}_{00} & {a a}_{11} & {b b}_{00} \\ {a a}_{00}^{22} & {a a}_{11}^{22} & {b b}_{00}^{22} \end{matrix})}^{- - 11} . . (\begin{matrix} {p p}_{11} - - {D D.}_{33} - - {D D.}_{44} \\ {P P}_{00} - - {b b}_{11} {D D.}_{33} - - {b b}_{22} {D D.}_{44} \\ {P P}_{11} - - {b b}_{11}^{22} {D D.}_{33} - - {b b}_{22}^{22} {D D.}_{44} \end{matrix}) - - - - - - ((88))$

相对于现有的RS(Reed-Solomon)、LRC编码技术，本发明改进了数据的分组方案，实现分组大小不均匀，并把易失效的数据块放在较小的组，由于同时采用本地校验数据块和全局校验数据块对数据进行保护，将带来两方面的优势：Compared with the existing RS (Reed-Solomon) and LRC coding techniques, the present invention improves the data grouping scheme, realizes that the grouping size is uneven, and puts data blocks that are prone to failure into smaller groups. The verification data block and the global verification data block are used to protect the data, which will bring two advantages:

(1)可以使得易失效的数据块在丢失时，消耗少量恢复开销即可恢复数据，从而总体上降低恢复失效数据的恢复开销。(1) When a data block that is prone to failure is lost, the data can be recovered with a small amount of recovery cost, thereby reducing the recovery cost of recovering invalid data as a whole.

(2)可以使得易失效数据的容删除能力更好，能抵抗更多的数据失效模式，从而总体上提高数据恢复成功率和存储系统的可靠性。(2) It can make the deletion capacity of vulnerable data better, and can resist more data failure modes, thereby improving the success rate of data recovery and the reliability of the storage system as a whole.

UFP-LRC比经典的RS编码，以及在顶级会议2012 USENIX ATC(现产品化在windowsserver中)上面发表的LRC方法，都要具有更好的恢复性能和可用性。以下用理论数值分析和实验数据来证明本发明的优点。UFP-LRC has better recovery performance and availability than the classic RS code, as well as the LRC method published at the top conference 2012 USENIX ATC (now productized in windows server). The advantages of the present invention are demonstrated below with theoretical numerical analysis and experimental data.

首先，在理论数值分析方面，主要是两个性能指标：(1)平均恢复开销：指恢复一个丢失的数据块的所需要下载/获取数据块的平均数量(指网络流量开销，计算延时相对网络延时几乎可以忽略)；(2)可用性：当有一些存储节点失效时，单个数据块能成功恢复/获取的概率。First of all, in terms of theoretical numerical analysis, there are mainly two performance indicators: (1) Average recovery overhead: refers to the average number of data blocks that need to be downloaded/obtained to recover a lost data block (referring to network traffic overhead, and the calculation delay is relatively Network delay is almost negligible); (2) Availability: When some storage nodes fail, the probability that a single data block can be successfully recovered/acquired.

图2首先对相同存储开销下的UFP-LRC和LRC编码方法进行对比。X轴的失效率比值表示高失效率存储节点与低失效率存储节点的平均失效率之比。UFP-LRC(2,3,2)与LRC(9,3,2)具有相同的数据块、校验数据块和存储开销。UFP-LRC(1,3,2)与LRC(6,3,2)具有相同的数据块、校验数据块和存储开销。但是随着失效率比值的逐渐增大(如超过2时，微软的研究显示通常存储节点最大失效率是最小失效率的6-7倍)，即各个存储节点之间的失效率差别越大时，UFP-LRC明显比LRC具有更小的恢复开销。Figure 2 first compares UFP-LRC and LRC encoding methods under the same storage overhead. The failure rate ratio on the X-axis represents the ratio of the average failure rate of storage nodes with a high failure rate to storage nodes with a low failure rate. UFP-LRC(2,3,2) and LRC(9,3,2) have the same data block, parity data block and storage overhead. UFP-LRC(1,3,2) and LRC(6,3,2) have the same data block, parity data block and storage overhead. However, as the failure rate ratio gradually increases (for example, when it exceeds 2, Microsoft's research shows that the maximum failure rate of a storage node is usually 6-7 times the minimum failure rate), that is, when the failure rate difference between each storage node is greater , UFP-LRC has significantly smaller recovery overhead than LRC.

图3显示了多种参数组合情况下的对比。在失效率比值ρ变大时，UFP-LRC在各种参数情况下的恢复开销都比LRC要低(即相同存储开销时，会有更低的恢复开销)。Figure 3 shows the comparison of various parameter combinations. When the failure rate ratio ρ becomes larger, the recovery cost of UFP-LRC is lower than that of LRC under various parameters (that is, the recovery cost is lower when the storage cost is the same).

图4显示了可用性对比情况。X轴表示目前失效的存储节点比例。UFP-LRC比RS的可用性要高得多，而且相同条件下和LRC的可用性基本一样，差距只有4.00E-08，基本可以忽略不计。Figure 4 shows the usability comparison. The X-axis represents the proportion of storage nodes that are currently failed. The availability of UFP-LRC is much higher than that of RS, and the availability of LRC is basically the same under the same conditions. The gap is only 4.00E-08, which is basically negligible.

然后，在实验方面，通过搭建30个存储节点组成的真实分布式存储系统，对相同存储开销情况下的UFP-LRC(2,3,2)、LRC(9,3,2)和RS(6,3)的性能进行了分析对比。主要关注两个性能参数：(1)平均恢复开销。(2)恢复失败率：即数据恢复/解码失败次数除以总的修复次数。Then, in terms of experiments, by building a real distributed storage system composed of 30 storage nodes, UFP-LRC(2,3,2), LRC(9,3,2) and RS(6 , 3) performance analysis and comparison. We mainly focus on two performance parameters: (1) Average recovery overhead. (2) Recovery failure rate: the number of data recovery/decoding failures divided by the total number of repairs.

图5显示了平均恢复开销，X轴表示失效的存储节点中属于高失效率的节点比例(即失效率高于0.2)，明显UFP-LRC和LRC比经典的RS编码的恢复性能要好，RS的恢复开销基本固定。而UFP-LRC总体上比LRC的恢复开销低10-12％。因为更多的失效情况发生在易失效分组内，这些分组的数据的恢复开销更少，所以总体上恢复开销更少。Figure 5 shows the average recovery cost, and the X-axis indicates the proportion of nodes with high failure rate among the failed storage nodes (that is, the failure rate is higher than 0.2). It is obvious that UFP-LRC and LRC have better recovery performance than the classic RS code, and RS Restoration overhead is basically fixed. While UFP-LRC has an overall 10-12% lower recovery overhead than LRC. Since more failure cases occur in failure-prone packets, the recovery overhead for data in these packets is less, and therefore overall less recovery overhead.

图6显示了恢复失败率。由于RS(6,3)只能容忍3个数据块失效，它的失败率高于其它两个编码方法。UFP-LRC和LRC都能容忍3-5个数据块失效。随着系统中失效的存储节点数不断增加，UFP-LRC(2,3,2)的失败率逐渐要低于LRC(9,3,2)，这是因为更多的失效会发生在易失效数据所在分组内，但是这些分组内的数据获得的保护更好，容删除能力更强，所以总体上可靠性更好。Figure 6 shows the recovery failure rate. Since RS(6,3) can only tolerate 3 data block failures, its failure rate is higher than that of the other two encoding methods. Both UFP-LRC and LRC can tolerate 3-5 data block failures. As the number of failed storage nodes in the system continues to increase, the failure rate of UFP-LRC (2,3,2) is gradually lower than that of LRC (9,3,2), because more failures will occur in the failure-prone The data is in the group, but the data in these groups is better protected, and the ability to delete is stronger, so the overall reliability is better.

Claims

1. the non-homogeneous erasure code method of a cloud storage system, it is characterised in that comprise the following steps:

1) find out cold data block to be encoded, and described cold data block is grouped, volatile data block is put into little packet, no The data block easily lost efficacy puts into big packet；

2) structure non-uniform encoding generator matrix, and utilize code generator matrix that cold data block is encoded；

3) data block after coding and redundancy check block are disposed.

The non-homogeneous erasure code method of cloud storage system the most according to claim 1, it is characterised in that step 1) tool Body realizes process and includes:

1) use cold data judgment method to find out and need cold data block set C to be processed, cold data block is processed, often in batches One subset of secondary processSC={D₀,D₁,...,D_z},D_zRepresent cold data block；Z states the number of cold data block；

2) data block comprising subset SC carries out Random Maps respectively, i.e. uses random Harsh function, certain cold data is reflected It is mapped on certain memory node, represents that this cold data block to move to this memory node after coded treatment, record memory node ID value；

3) utilize the crash rate of current acquired memory node that cold data are ranked up, high failure rate node will be stored in On easy inefficacy data block come foremost, be stored on relatively low crash rate node be difficult to fail data block row after；

4) by foremost k₀Individual data block, i.e.Put into first group, by (k subsequently₀+ 1) individual data block puts into second Group, then by (k subsequently₀+ 2) individual data block puts into the 3rd group, by that analogy, until last (k₀+ l-1) individual data block puts Enter the l packet, and

The non-homogeneous erasure code method of cloud storage system the most according to claim 2, it is characterised in that construct non-homogeneous Code generator matrix, and the process that implements utilizing code generator matrix to encode cold data block includes: build coding Generator matrix G, has local verification data block p by G coding relief (i+1) individual packet_i, i=0,1 ..., l-1, this Outward, r overall situation verification data block P is also shared in all packets_j, j=0,1 ..., r-1, p_iBy the cold data block XOR in each group Generate, P_jBeing multiplied by after code coefficient XOR again by all of cold data block to generate, G meets following formula:

G \cdot (\begin{matrix} D_{0} \\ D_{1} \\ ... \\ D_{| S C | - 1} \end{matrix}) = (\begin{matrix} p_{0} \\ p_{1} \\ ... \\ p_{l - 1} \\ P_{0} \\ P_{1} \\ ... \\ P_{r - 1} \end{matrix});

It is expressed as with system of linear equations:

\{\begin{matrix} D_{0} + D_{1} + ... + D_{k_{0} - 1} = p_{0} \\ D_{k_{0}} + D_{k_{0} + 1} + ... + D_{2 k_{0}} = p_{1} \\ ...... \\ D_{| S C | - k_{0} - l + 1} + ... + D_{| S C | - 1} = p_{l - 1} \\ a_{0} D_{0} + a_{1} D_{1} + ... a_{k_{0} - 1} D_{k_{0} - 1} + b_{0} D_{k_{0}} + ... + b_{k_{0}} D_{2 k_{0}} + c_{0} ... = P_{0} \\ a_{0}^{2} D_{0} + a_{1}^{2} D_{1} + ... a_{k_{0} - 1}^{2} D_{k_{0} - 1} + b_{0}^{2} D_{k_{0}} + ... + b_{k_{0}}^{2} D_{2 k_{0}} + c_{0}^{2} ... = P_{1} \\ ...... \\ a_{0}^{r - 2} D_{0} + a_{1}^{r - 2} D_{1} + ... a_{k_{0} - 1}^{r - 2} D_{k_{0} - 1} + b_{0}^{r - 2} D_{k_{0}} + ... + b_{k_{0}}^{r - 2} D_{2 k_{0}} + c_{0}^{r - 2} ... = P_{r - 1} \end{matrix} .

The non-homogeneous erasure code method of cloud storage system the most according to claim 3, it is characterised in that after coding The process that implements that data block and redundancy check block carry out disposing includes: utilizes G to generate the verification data block of redundancy, is compiled Cold data block set after Ma They are deployed to phase The memory node answered, all cold data blocks are disposed according to the memory node ID value recorded, and verify data block by reflecting at random Shooting method is disposed.