[go: up one dir, main page]

CN119834814B - System MSR code generation and restoration method with minimum packet number - Google Patents

System MSR code generation and restoration method with minimum packet number

Info

Publication number
CN119834814B
CN119834814B CN202411904690.3A CN202411904690A CN119834814B CN 119834814 B CN119834814 B CN 119834814B CN 202411904690 A CN202411904690 A CN 202411904690A CN 119834814 B CN119834814 B CN 119834814B
Authority
CN
China
Prior art keywords
code
nodes
msr
node
repair
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202411904690.3A
Other languages
Chinese (zh)
Other versions
CN119834814A (en
Inventor
初婧雯
李国栋
胡思煌
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shandong University
Original Assignee
Shandong University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shandong University filed Critical Shandong University
Priority to CN202411904690.3A priority Critical patent/CN119834814B/en
Publication of CN119834814A publication Critical patent/CN119834814A/en
Application granted granted Critical
Publication of CN119834814B publication Critical patent/CN119834814B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention discloses a system MSR code generation and restoration method with minimum packet number, relating to the technical field of computer and distributed storage, comprising defining the structure of (n, k, d) system MSR codes for a distributed storage system formed by n nodes, wherein the system MSR codes share n code blocks, the former k code blocks are used as information nodes, the rest of the latter n-k code blocks are used as check nodes, storing all information in the information nodes, and grouping the k information nodes, wherein the packet number of the system MSR codes is the same as the packet number of the system MSR codesBased on the defined system MSR code structure, a (n, k, d) system MSR code is computationally generated in a finite field. The invention adopts a specific MSR construction mode to construct the system MSR code, so that the system MSR code has smaller sub-packet number, utilizes fixed parameters to combine code calculation, realizes the system MSR code with the minimum sub-packet number, and generates a corresponding check matrix.

Description

System MSR code generation and restoration method with minimum packet number
Technical Field
The invention relates to the technical field of computers and distributed storage, in particular to a system MSR code generation and restoration method with minimum packet number.
Background
The statements in this section merely provide background information related to the present disclosure and may not necessarily constitute prior art.
The distributed storage system is widely applied to scenes such as modern Cloud storage, internet service, big data analysis and the like, plays a great role in a global data center, and particularly depends on an efficient distributed storage system to meet the increasing data storage demands of large Cloud storage service providers such as Microsoft Azure, amazon S3, google Cloud and the like. In a distributed storage system, data is partitioned and stored on a plurality of storage nodes in order to improve the fault tolerance and reliability of the storage system. However, as the amount of data increases rapidly, how to efficiently handle node failures and maintain the availability of data without wasting storage resources becomes an important issue that needs to be addressed by distributed storage systems.
In the existing erasure codes, the extremely large distance separable (Maximum Distance Separable, MDS) codes, such as Reed-Solomon (RS) codes, are widely used in distributed storage systems because they can cope with the most node damage under the same storage efficiency, i.e. all data can be recovered under the condition of any k nodes. MSR codes are a special class of MDS codes that, when a single node fails, can repair the failed node with a minimum total amount of network data transmission. Various researches on MSR code construction have been proposed, such as product matrix construction of MSR code explicit construction, high-rate MSR code explicit construction is proposed in consideration of the fact that the MSR code is limited to low code rate, and MSR code construction with optimal access property is given in the prior art for the fact that the number of nodes to be repaired is d < n-1 (n is the number of nodes of the system) during repairS=d-k+1, d e { k+1, k+2, k+3}, and other structures.
The size of the MSR code packet number will affect the complexity of the codec and the I/O (input/output) overhead, and when the number of packets increases, the complexity of the codec will increase significantly, for example, when using a scalar code (scalar code), each node stores a scalar, the complexity of each layer in the encoding and recovery process is O (rk), the complexity of the l layer is O (rk), and when using an array code (array code) with a larger number of packets, the complexity of the l layer stores a vector, the complexity of the l layer is O (rkl 2), and in addition, when having a larger number of packets, the MSR code will generate additional I/O overhead when repairing a single node, the I/O overhead increases, which is not suitable for practical storage systems, for example, when using a scalar code, when one node is in error, all data needs to be transmitted through other nodes, each node needs to perform an I/O operation only once, when using an array code, and when using an array code, the recovery of the node needs more data transmission of the node is required for error, and the total data transmission of the node is reduced, and the total data transmission cost of each node is not increased, which is due to the continuous I/O.
Therefore, the MSR code is constructed such that the MSR code with the smallest possible packet number is constructed for all possible parameters (n, k, d) without requiring optimal access. The MSR code with the smallest number of packets, which is currently designed under the given parameters (n, k, d), has the number of packetsS=d-k+1, but the number of packets of the MSR code is still large, and there is still a certain optimization space.
Disclosure of Invention
To solve the above-mentioned shortcomings of the prior art, the present invention provides a method for generating and repairing MSR codes with minimum number of packets, which is designed under the current given parameters (n, k, d)Based on MSR code, adopting specific MSR construction mode to construct system MSR code, making it possess smaller sub-packet number, then utilizing fixed parameter to combine code calculation to implement system MSR code with minimum sub-packet number, and producing correspondent check matrix.
In a first aspect, the present invention provides a method for generating a systematic MSR code with a minimum fractional packet number.
A system MSR code generation method with minimum packet count, comprising:
For a distributed storage system formed by n nodes, defining the structure of (n, k, f) system MSR codes, wherein the system MSR codes have n code blocks C= (C 0,C1,…,Cn-1), the former k code blocks are used as information nodes, the rest n-k code blocks are used as check nodes, all information is stored in the information nodes, k information nodes are grouped, and the number of the packets of the system MSR codes is calculated according to the number of packets of the system MSR codes
Based on the structure of the defined system MSR code, the (n, k, d) system MSR code is calculated and generated in a finite field, wherein a primitive element is selected in the finite field F 2/(F (x)) by utilizing a primitive irreducible polynomial F (x) generated by default, a plurality of different elements are generated by utilizing the primitive element, mapping is carried out based on the generated elements, a kernel matrix of each code block is obtained, and a corresponding check matrix is determined according to the kernel matrix, so that the generation of the system MSR code is completed.
Further technical proposal, mapping an element vector x [s] into a matrix with the size of st multiplied by s on a finite field F q The mapping is expressed as:
Wherein b epsilon s+1, t is a positive integer, A matrix of blocks of sxs, each block being a column vector of length t, for b e s +1, i, j e s,The ith row and jth column of (a) are expressed as:
In the above-mentioned method, the step of, Element x e F q.
Further, the method generates (n=14, k=10, d=13) systematic MSR codes, and the generated systematic MSR codes have the minimum number of packetsS=d-k+1, d represents the number of nodes that help repair when repairing;
With the former k=10 code blocks as the information nodes and the remaining last 4 code blocks as check nodes, all information is stored in the information nodes, and 10 information nodes are grouped.
According to a further technical scheme, a primitive irreducible polynomial F (x) generated by default is utilized, one primitive element is selected in a finite field F 2/(F (x)), and a plurality of different elements are generated by utilizing the primitive element, wherein the method comprises the following steps:
Using the primitive irreducible polynomial F (x) =x 8+x4+x3+x2 +1, a finite field GF (256) is generated by F 2/(F (x)), expressed as:
GF(256)＝F2/(f(x))＝{a7x7+a6x6+...+a1x+a0|ai∈{0,1}};
selecting one primitive x in the finite field GF (256), generating a plurality of different elements by using the primitive x, and setting the elements Wherein each element lambda i is a polynomial of degree up to 7.
According to a further technical scheme, a corresponding check matrix is determined according to the kernel matrix, and the check matrix is defined as:
in the above formula, I is an identity matrix, Representing the kronecker product of the two,The matrix A and the matrix B are represented by Cronecker product of each element block, a represents the divided group number, and B represents the B-th information node in the group.
In a second aspect, the present invention provides a method for repairing a systematic MSR code with a minimum fractional packet number.
A systematic MSR code repair method with minimum packet count, comprising:
Repairing information nodes of the (n=14, k=10, d=13) system MSR codes generated by the method according to the first aspect, repairing the error nodes according to different nodes with errors, wherein the method comprises the following steps:
when any node in the first b-1 nodes in the a group generates an error, the set of the help nodes is I h=13, then the error node is repaired by { R a,bCj:j e H };
When any node in the last node in the a group generates an error, the set of the help nodes is that |H|=13, set:
H1=H∩(5a+[5]),a∈[2];
H2=H\(5a+[5],a∈[2]);
The last node C 5a+4 of group a is repaired by { R a,bC5a+z:5a+z∈H1, b e [4] } and { R a,bCi:i∈H2, b e [4] }.
According to a further technical scheme, when any node in the first group of the first 4 nodes C 0～C3 generates errors, each auxiliary node C j transmits discontinuous 4 symbols to the error node for repairing;
When an error occurs at any of the first 4 nodes C 5～C8 of the second set, each helping node C j passes the consecutive 4 symbols to the error node for repair.
In a third aspect, the present invention further provides an electronic device, including a memory, configured to store executable instructions, and a processor, configured to implement the above-mentioned method for generating a system MSR code with a minimum packet number when executing the executable instructions stored in the memory.
In a fourth aspect, the present invention further provides a computer readable storage medium storing executable instructions for causing a processor to execute the executable instructions, to implement a system MSR code generating method with a minimum packet number as described above.
In a fifth aspect, the present invention further provides a computer program product, where the computer program product includes executable instructions, where the executable instructions are stored in a computer readable storage medium, and where a processor of an electronic device reads the executable instructions from the computer readable storage medium and executes the executable instructions to implement a system MSR code generating method with a minimum packet number as described above.
The one or more of the above technical solutions have the following beneficial effects:
1. The invention provides a system MSR code generation and restoration method with minimum packet number, which is designed under the current given parameters (n, k, d) Based on MSR codes of the system, a specific MSR construction mode is adopted to construct the MSR codes of the system, so that the MSR codes have smaller sub-packet numbers, fixed parameters are combined with code calculation to obtain MSR codes with the number of storage nodes of 14, the number of information nodes of 10 and the number of sub-packets of 16 and check matrixes thereof, the MSR codes of the system with the minimum number of sub-packets are realized, corresponding check matrixes are generated, and further, the storage efficiency and the node fault recovery efficiency can be effectively improved.
2. The MSR code of the system provided by the invention optimizes storage and data repair, and by designing the MSR code of the system, the system can realize optimal repair under the condition that any given k nodes have faults, and other check nodes do not participate in the repair process any more. Because all the information is stored in the information node, a user only needs to acquire the information node when downloading the data, and the check node is not required to be involved, the data recovery process is greatly simplified, and particularly in a distributed storage system, the dependence of the user on the check node is reduced, so that the user only needs to pay attention to the quick repair of the information node, the complexity of the repair process can be effectively reduced, and the efficiency of the system is improved.
3. The MSR code of the system provided by the invention realizes smaller sub-packet number, reduces the coding complexity and reduces the I/O overhead. The invention can realize the system MSR code with smaller packet number under the same parameters, and the smaller packet number means that the data quantity to be processed in the coding process is smaller, thereby reducing the complexity of coding and recovering each layer, and further reducing the I/O expenditure by reducing the packet number.
4. The system MSR code generation strategy with smaller packet number adopted by the invention not only has obvious reduction in the aspects of coding complexity and I/O overhead, but also optimizes the performance of the whole distributed storage system, and in practical application, the optimization can obviously improve the repair speed of the system, reduce the consumption of resources and effectively improve the user experience.
5. The MSR code of the system provided by the invention has minimum repair bandwidth. When the MDS code restores data, the lost data needs to be read from a plurality of storage nodes, and although the MDS code ensures that the data can be restored from any k data blocks, the restoration bandwidth is very high because k equally large data blocks need to be downloaded when a single failure node is restored. The MSR code uses a regeneration code technology, only needs to download small data volume from other nodes, recovers the data of the failure node through linear combination, and has the minimum repair bandwidth particularly important in a large-scale distributed storage system, can remarkably reduce network load, namely, the repair efficiency is improved by reducing the volume of transmitted data, the requirement of the system on the network bandwidth is reduced, and the efficiency of repairing a single failure node is high. MDS codes, when repairing a single node failure, need to read complete data blocks from the other k nodes and recover the lost data through decoding operations. This approach results in the restoration process not only consuming more bandwidth, but also increasing node load. The MSR code is optimized for repairing the single failure node, and only the linearly combined data fragments are read from part of nodes, so that all data are not required to be downloaded. The repairing process is more efficient than MDS codes, so that the quantity of transmitted data is reduced, the recovery time is shortened, the load pressure of the system in data recovery is reduced, and the storage redundancy is optimized. The MDS code has higher storage efficiency and can achieve less redundancy (theoretically near optimal), i.e., the total number of stored data blocks is n, any k data blocks can recover all data, the storage overhead is fixed, and the redundancy is less. The MSR code can reach the minimum storage cost as the MDS code, and the storage efficiency is very high, but the MSR code simultaneously considers the optimization of the repair efficiency and the bandwidth, so that the repair process is more efficient under the same redundancy condition, and the multi-node repair is optimized. When an error occurs in a plurality of nodes, the MDS code needs to download a large amount of data to recover the nodes, and the demand for repairing bandwidth increases linearly with the increase of the number of failed nodes, so that the repairing cost increases exponentially. The MSR code can repair the error node by combining the rest nodes, thereby reducing the repair bandwidth. Thus, repair efficiency is higher than MDS codes when multiple nodes fail simultaneously.
6. The system MSR code provided by the invention is more suitable for network environment. The high bandwidth requirement of the MDS code limits the use of the MDS code in the environment with limited network bandwidth, the repair cost of the MDS code is great for the scene with poor network condition or higher bandwidth cost, the MSR code minimizes the data quantity transmitted in the repair process, reduces the bandwidth pressure in the repair process, and improves the overall operation efficiency of the system, so the MDS code is more excellent in the environment with limited bandwidth, and is suitable for bandwidth sensitive applications such as data transmission across data centers and edge computing scenes.
Additional aspects of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.
Drawings
The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the invention.
FIG. 1 is a flow chart of a method for generating a MSR code of a system with a minimum packet number according to an embodiment of the present invention;
FIG. 2 is a schematic diagram of a polynomial form, a 2-ary form, and a 16-ary form of a plurality of different elements generated in an embodiment of the present invention;
FIG. 3 is a diagram of the calculated H 4 matrix values in the embodiment of the present invention;
FIG. 4 is a schematic diagram of repairing when an error occurs in any node of the first 4 nodes C 0～C3 in the first group according to an embodiment of the present invention;
Fig. 5 is a schematic diagram of repairing when an error occurs in any node of the first 4 nodes C 5～C8 in the second group according to an embodiment of the present invention.
Detailed Description
It should be noted that the following detailed description is exemplary only for the purpose of describing particular embodiments and is intended to provide further explanation of the invention and is not intended to limit exemplary embodiments according to the invention. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Furthermore, it will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, steps, operations, devices, components, and/or groups thereof.
Example 1
The embodiment provides a method for generating a system MSR code with a minimum packet number, as shown in fig. 1, specifically including:
first, the minimum number of packets is designed under the current given parameters (n, k, d) Based on the MSR code, adopting a specific MSR construction mode to construct the system MSR code to enable the system MSR code to have smaller sub-packet number, specifically:
For a distributed storage system formed by n nodes, defining the structure of (n, k, d) system MSR codes, wherein the system MSR codes have n code blocks C= (C 0,C1,…,Cn-1), the former k code blocks are used as information nodes, the rest n-k code blocks are used as check nodes, all information is stored in the information nodes, k information nodes are grouped, and the number of the packets of the system MSR codes is calculated according to the number of packets of the system MSR codes
Secondly, based on the structure of the defined system MSR code, the (n, k, d) system MSR code is calculated and generated in a finite field by utilizing fixed parameter and code calculation, so that the system MSR code with the minimum packet number is realized, and a corresponding check matrix is generated, specifically:
and selecting one primitive element in a finite field F 2/(F (x)) by utilizing a primitive irreducible polynomial F (x) generated by default, generating a plurality of different elements by utilizing the primitive element, mapping based on the generated elements to obtain a kernel matrix of each code block, and determining a corresponding check matrix according to the kernel matrix to finish the generation of the MSR code of the system.
The system MSR code generating method with the minimum packet number proposed in this embodiment will be described in more detail by the following.
Before systematic MSR code generation, the following definitions are given:
(1) For element x ε F q and positive integer t, set:
(2) For either matrix a and a block matrix B of size mxn, wherein:
Then define:
wherein, the Is the product of kronecker and,It represents the kronecker product of each block of elements in matrix a and matrix B.
(3) For b ε [ s+1] and positive integer t, the following mapping is defined:
That is, a vector x [s] is mapped to a matrix of size st×s over finite field F q Can be used forConsider a matrix of s x s blocks, where each block is a column vector of length t. Then, for b e s+1, i, j e s,The ith row and jth column of (a) may be expressed as:
further, for ease of understanding, s=3 is taken as an example, and based on the above formula, when b e [4], i, j e [3], there are:
(4) For any non-negative integer a, b, R a,b is defined as:
In the above formula, e b represents a vector with a length s, a b-th bit of 1 and the rest of bits of 0, I m represents an identity matrix with a size of m×m, where m is l/s a+1、sa, l and s are non-negative integers, and l represents a packet number.
Based on the above definition, a systematic MSR code with minimum packet number is constructed. Specifically, a distributed storage system composed of n nodes is provided, and a structure is providedAnd the system MSR code is used for carrying out distributed storage on the data or files to be stored. Wherein the system MSR code has n code blocks C= (C 0,C1,…,Cn-1), the former k code blocks are used as information nodes, the remaining last n-k code blocks are used as check nodes, all information is stored in the information nodes, k information nodes are grouped, and the number of the packets of the system MSR code is the sameS=d-k+1, d represents the number of nodes that help repair during repair, and l is the number of packets.
In this embodiment, a (n=14, k=10, d=13) systematic MSR code is generated. For the MSR code of the system, the first 10 code blocks are information nodes, the first 10 code blocks are divided into 2 groups, 5 code blocks are arranged in each group, all data information is stored only through the 10 code blocks, the remaining last 4 code blocks are used as check nodes, the check nodes are not grouped, and at the moment, s=d-k+1=4, and the number of the packets is equal to the number of the packetsCompared with the prior (n=14, k=10) optimal MSR code, the number of the packets isUnder the same parameters, the MSR code of the system provided by the embodiment only considers the optimal repair of 10 information nodes, and the number of the packets is as followsThe packet number can be further reduced, so that the complexity of encoding and decoding and the effective reduction of I/O overhead are realized.
Further, for ease of representation, a ε [2], b ε [5] are used to represent the b-th node of group a, i.e., the first 10 nodes may be represented as (C 5a+b: a ε [2], b ε [5 ]). On this basis, the generation process of the (n=14, k=10, d=13) system MSR code is introduced.
First, a finite field GF (256) is generated by F 2/(F (x)) using a primitive irreducible polynomial F (x) generated by default by the system, one primitive x is arbitrarily selected in the finite field GF (256), and a plurality of different elements are generated using the primitive x, whereby the elements λ i＝xi, i=0, 1,..43 can be set. Specifically, the mathematical software system sagemath is adopted in this embodiment, and the primitive irreducible polynomial f (x) generated by default in the system is f (x) =x 8+x4+x3+x2 +1.
The finite field GF (256) is generated by F 2/(F (x)), which can be expressed as:
GF(256)＝F2/(f(x))＝{a7x7+a6x6+...+a1x+a0|ai∈{0,1}}.
A primitive x is optionally selected over the finite field GF (256) to generate a number of different elements, where each element λ i is a polynomial of degree up to 7, and the resulting polynomial form, 2-ary, 16-ary representation of λ 0,λ1,...,λ43 is shown in fig. 2.
Second, based on the generated elements, the above-defined mapping is combinedMapping is carried out, and a kernel matrix of each code block is obtained. Specifically, it is provided withMapping according to the definition aboveObtaining a kernel matrixA e [2], b e [5], t=r, i.e.:
And finally, determining a corresponding check matrix according to the kernel matrix, thereby completing the generation of the MSR code of the system. Specifically, a check matrix is defined according to the kernel matrix, and is:
Taking H 4 as an example, H 4 is obtained according to the definition above:
And calculating and obtaining a specific numerical value of each matrix according to the definition of the check matrix. Taking the H 4 matrix as an example, the numerical value of the H 4 matrix is calculated by using the mathematical software system sagemath, which is specifically shown in fig. 3.
Example two
Based on the above proposed method for generating the system MSR code, this embodiment also provides a method for repairing the system MSR code with the minimum packet number, including:
The (n=14, k=10, d=13) system MSR codes generated in the above embodiment are repaired by information nodes, and the error nodes are repaired according to the different nodes with errors.
First, the definition of node repair is clarified. Assuming that one of the nodes is in error, the error node is C i, i epsilon [10], the auxiliary node is C j, j epsilon [14] \ { i }, and since the node repair of the MSR code needs to be downloaded from each auxiliary nodeThe symbols D j→i is designed as a matrix of size 4×16, meaning that when an error occurs at the ith node, the jth node selects which part of the data to download to the error node C i, i.e. the data transmitted from the auxiliary node C j can be represented as D j→iCj, and the (n-1) β=52 symbols downloaded from all the auxiliary nodes can be represented as:
further, after obtaining the transmitted data, the error node C i repairs the error block according to the data by using the repair matrix R i to recover the original data, which can be expressed as:
By the method, the error block can be repaired.
Secondly, repairing the error node according to different nodes with errors.
(1) First case
When any node in the first b-1 nodes in the a group generates errors, namely the node generating the errors is C 5a+b, a epsilon [2], b epsilon [4], the set of the help nodes is that I h=13, the erroneous node can be repaired by { R a,bCj:j e H }.
Further, according to the formulaThe method can obtain:
where e i denotes a row vector of length 4, i-th bit of 1, and the rest of bits of 0, i=0, 1,2,3, and r a,b denotes data that the b-th node of the a-th group selects for transmission to the wrong node.
When C 0 makes an error, each helping node C j passes the 1 st, 5 th, 9 th, 13 th symbol, C j(0),Cj(4),Cj(8),Cj (12), to C 0 as known from R 0,0 above. As shown in FIG. 4, when any node in the first set of the first 4 nodes C 0～C3 experiences an error, each helping node C j transmits 4 discontinuous symbols to the error node for repairing, and the total I/O operation is 4 times, so that C 0,C1,C2,C3 stores important data.
As shown in fig. 5, when an error occurs at any node of the first 4 nodes C 5～C8 of the second group, each helping node C j passes the consecutive 4 symbols to the error node for repair, for a total of 1I/O operation, so C 5,C6,C7,C8 can hold the most important data.
(2) Second case
When any node in the last node in group a (i.e., C 4,C9) experiences an error, the set of helper nodes is|H|=13, set:
H1=H∩(5a+[5]),a∈[2];
H2=H\(5a+[5],a∈[2]);
The last node C 5a+4 of group a may be repaired by { R a,bC5a+z:5a+z∈H1, b e [4] } and { R a,bCi:i∈H2, b e [4] }, i.e., the helping nodes of the same group pass data { R a,bCi:i∈H2 } to the wrong node, b e [4], and the nodes of different groups pass data { R a,bC5a+Z:5a+z∈H1, b e [4] }.
Specifically, when an error occurs in C 4, the data transferred from each node to C 4 is:
when C 9 makes an error, the data that each node passes to C 9 is:
In this way, the present embodiment realizes the construction and generation of the system MSR Code (SYSTEMATIC MSR Code) with the smallest packet number, and compared with the existing general MSR Code (GENERAL MSR Code), the system MSR Code provided in the present embodiment further optimizes storage and data repair. Namely, the system MSR code provided by the embodiment, the storable data not only comprises a redundant coding part, but also comprises a directly stored original data part, the system MSR code can realize optimal repair under the condition of any k nodes, and other check nodes do not consider the optimal repair. Because all information is stored in the information nodes, a user only needs to acquire the information nodes when downloading data and is irrelevant to check nodes, the system only needs to pay attention to the quick repair of the information nodes in an actual distributed storage system, and is different from the conventional common MSR code which considers the optimal repair of all the nodes, the MSR code of the system provided by the embodiment only pays attention to the optimal repair of 10 information nodes and ignores the repair problem of 4 check nodes, so that the optimization of storage and data repair is realized.
More importantly, the number of packets is compared to the existing (n=14, k=10) MSR code structureThe MSR code of the system proposed in this embodiment can realize smaller number of packets under the same parameters, and the number of packets is as the embodiment only considers the optimal repair of 10 information nodesThe embodiment can reduce the coding complexity by reducing the number of the sub-packets, effectively reduce the I/O overhead and further optimize the overall performance. In addition, when the MSR code of the system provided by the embodiment is repaired, only a small data volume is needed to be downloaded from other nodes, the data of the failure node is recovered through linear combination, the MSR code has minimum repair bandwidth, the efficiency of repairing a single failure node is higher, the storage redundancy can be optimized, the multi-node repair is optimized, and the like.
In addition, the system MSR code can improve the expandability of the system, in a large-scale storage system, the MSR code can process the scene of failure of more nodes while guaranteeing the reliability of data, which is very important for the system with high expansibility requirements, and the energy efficiency is optimized, because the MSR code reduces the bandwidth required by data transmission and repair, the MSR code can reduce the energy consumption of the system in the process of data recovery, especially in a large-scale data center, and the MSR code is designed and realized more flexibly, wherein the MSR code can be designed through different parameters, and flexible trade-off is realized among the storage expense, the repair bandwidth and the repair complexity, so that the MSR code is suitable for the requirements of different application scenes.
Example III
The embodiment provides electronic equipment, which comprises a memory and a processor, wherein the memory is used for storing executable instructions, and the processor is used for realizing the method provided by the embodiment when executing the executable instructions stored in the memory.
Example IV
The present embodiment also provides a computer-readable storage medium storing executable instructions that, when executed by a processor, cause the processor to perform the above-described method provided by the present embodiment.
Example five
The present embodiment provides a computer program product comprising executable instructions that are a computer instruction, the executable instructions being stored in a computer readable storage medium. The executable instructions, when read from the computer readable storage medium by a processor of an electronic device, when executed by the processor, cause the electronic device to perform the method provided by the present embodiment.
The steps involved in the second to fifth embodiments correspond to the first embodiment of the method, and the detailed description of the second embodiment refers to the relevant description of the first embodiment. The term "computer-readable storage medium" shall be taken to include a single medium or multiple media that includes one or more sets of instructions, and shall also be taken to include any medium that is capable of storing, encoding or carrying a set of instructions for execution by the processor and that cause the processor to perform any one of the methodologies of the present invention.
It will be appreciated by those skilled in the art that the modules or steps of the invention described above may be implemented by general-purpose computer means, alternatively they may be implemented by program code executable by computing means, whereby they may be stored in storage means for execution by computing means, or they may be made into individual integrated circuit modules separately, or a plurality of modules or steps in them may be made into a single integrated circuit module. The present invention is not limited to any specific combination of hardware and software.
While the foregoing is illustrative of the preferred embodiments of the present invention, and while the present invention has been described in connection with the accompanying drawings, it is not intended to limit the scope of the invention, and it will be apparent to those skilled in the art, on the basis of the technical scheme of the invention, various modifications or variations which can be made by the person skilled in the art without the need of creative efforts are still within the protection scope of the invention.

Claims (7)

1.一种具有最小分包数的系统MSR码生成方法，其特征在于，包括：1. A method for generating MSR codes in a system with a minimum number of packets, characterized in that it includes: 对于由n个节点构成的分布式存储系统，定义系统MSR码的结构；其中，系统MSR码共有n个码块，以前k个码块作为信息节点，以剩余的后n-k个码块作为校验节点，将所有信息存储在信息节点中，并对k个信息节点分组，此时系统MSR码的分包数；For a distributed storage system consisting of n nodes, define The structure of the system MSR code; wherein the system MSR code has n code blocks. The first k code blocks are used as information nodes, and the remaining nk code blocks are used as check nodes. All information is stored in the information nodes, and the k information nodes are grouped. At this time, the number of packets of the system MSR code is... ; 基于定义的系统MSR码的结构，在有限域中计算生成系统MSR码，为：利用默认生成的本原不可约多项式，在有限域中任选一个本原元，利用该本原元生成若干不同的元素，基于所生成的元素进行映射，得到每一码块的kernel矩阵，并根据kernel矩阵确定相应校验矩阵，以此完成系统MSR码的生成；Based on the defined structure of the systematic MSR code, it is calculated and generated in a finite field. The system MSR code is: using the default generated primitive irreducible polynomial. In a finite field Choose one primitive element and use it to generate several different elements. Map the generated elements to obtain the kernel matrix of each code block. Determine the corresponding parity check matrix based on the kernel matrix to complete the generation of the system MSR code. 其中，将一个元素向量映射为有限域上大小为的矩阵，所述映射表示为：Among them, a vector of elements Mapping to a finite field The size of the top is matrix The mapping is represented as: ； ; 其中，，为正整数，为的块矩阵，其中每个块为长为的列向量；对于，的第行第列表示为：in, , It is a positive integer. for A block matrix, where each block is of length . Column vectors; for , The Line number The column is represented as: ； ; 上式中，，元素；In the above formula, ,element ; 利用默认生成的本原不可约多项式，在有限域中任选一个本原元，利用该本原元生成若干不同的元素，包括：Using the default generated primitive irreducible polynomial In a finite field Choose any one primitive element and use it to generate several different elements, including: 采用本原不可约多项式，通过生成有限域，表示为：Using primitive irreducible polynomials ,pass Generating finite fields , represented as: ； ; 在有限域中任选一个本原元，利用该本原元生成若干不同的元素，设定元素，其中每个元素为次数至多为7的多项式；In a finite field Choose one of the fundamental elements Using this primitive element, several different elements are generated, and the elements are set. Each element It is a polynomial with a maximum degree of 7; 根据kernel矩阵确定相应校验矩阵，定义校验矩阵为：The corresponding parity check matrix is determined based on the kernel matrix, and the parity check matrix is defined as follows: ； ; 上式中，为单位矩阵，表示克罗内克积，表示矩阵A与矩阵B中各元素块进行克罗内克积，a表示划分的组数，b表示组内第b个信息节点。In the above formula, It is the identity matrix. Indicates the Kronecker product. This represents the Kronecker product of the element blocks in matrix A and matrix B, where 'a' represents the number of groups and 'b' represents the b- th information node within a group. 2.如权利要求1所述的一种具有最小分包数的系统MSR码生成方法，其特征在于，生成系统MSR码，所生成的系统MSR码具备最小分包数，，表示修复时帮助修复的节点个数；2. The method for generating a system MSR code with the minimum number of packets as described in claim 1, characterized in that, the generation... The system MSR code, the generated system MSR code has a minimum number of packets. , , Indicates the number of nodes that helped with the repair process; 以前k=10个码块作为信息节点，以剩余的后4个码块作为校验节点，将所有信息存储在信息节点中，并对10个信息节点分组。Previously, k=10 code blocks were used as information nodes, and the remaining 4 code blocks were used as check nodes. All information was stored in the information nodes, and the 10 information nodes were grouped together. 3.一种具有最小分包数的系统MSR码修复方法，其特征在于，包括：3. A method for repairing MSR codes in a system with a minimum number of packets, characterized in that it includes: 对利用如权利要求1-2任一项所述方法生成的系统MSR码进行信息节点的修复，根据发生错误的节点的不同，分情况对错误节点进行修复，包括：For those generated using the method described in any one of claims 1-2 The system uses MSR codes to repair information nodes. Depending on the specific node that erroneous, the repair process is tailored to different scenarios, including: 当a组中的前b-1个节点中任一节点发生错误时，帮助节点的集合为，则错误节点被修复；When any of the first b -1 nodes in group a encounters an error, the set of helper nodes is: Then the faulty node is repair; 当a组中的最后一个节点中任一节点发生错误时，帮助节点的集合为，设：When any node in the last node of group a encounters an error, the set of helper nodes is: ,set up: ； ; ； ; 则第组的最后一个节点被和修复。Then the first The last node of the group quilt and repair. 4.如权利要求3所述的一种具有最小分包数的系统MSR码修复方法，其特征在于，包括：4. A system MSR code repair method with minimum packet count as described in claim 3, characterized in that it includes: 当第一组前4个节点中任一节点发生错误时，每个帮助节点向错误节点传递不连续的4个符号进行修复；When the first 4 nodes of the first group When any node in the process encounters an error, each helper node... To repair the erroneous node, pass four discontinuous symbols. 当第二组前4个节点中任一节点发生错误时，每个帮助节点向错误节点传递连续的4个符号进行修复。When the first 4 nodes of the second group When any node in the process encounters an error, each helper node... Send four consecutive symbols to the faulty node to repair it. 5.一种电子设备，其特征在于，包括：5. An electronic device, characterized in that it comprises: 存储器，用于存储可执行指令；处理器，用于执行所述存储器中存储的可执行指令时，实现权利要求1-2任一项所述的具有最小分包数的系统MSR码生成方法。A memory for storing executable instructions; a processor for executing the executable instructions stored in the memory to implement the system MSR code generation method with minimum number of packets as described in any one of claims 1-2. 6.一种计算机可读存储介质，其特征在于，存储有可执行指令，用于引起处理器执行所述可执行指令时，实现权利要求1-2任一项所述的具有最小分包数的系统MSR码生成方法。6. A computer-readable storage medium, characterized in that it stores executable instructions for causing a processor to execute the executable instructions to implement the system MSR code generation method with minimum number of packets as described in any one of claims 1-2. 7.一种计算机程序产品，其特征在于，所述计算机程序产品包括可执行指令，所述可执行指令存储在计算机可读存储介质中；7. A computer program product, characterized in that the computer program product includes executable instructions, the executable instructions being stored in a computer-readable storage medium; 当电子设备的处理器从所述计算机可读存储介质读取所述可执行指令，并执行所述可执行指令时，实现权利要求1-2任一项所述的具有最小分包数的系统MSR码生成方法。When the processor of the electronic device reads the executable instructions from the computer-readable storage medium and executes the executable instructions, it implements the system MSR code generation method with minimum number of packets as described in any one of claims 1-2.
CN202411904690.3A 2024-12-23 2024-12-23 System MSR code generation and restoration method with minimum packet number Active CN119834814B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202411904690.3A CN119834814B (en) 2024-12-23 2024-12-23 System MSR code generation and restoration method with minimum packet number

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202411904690.3A CN119834814B (en) 2024-12-23 2024-12-23 System MSR code generation and restoration method with minimum packet number

Publications (2)

Publication Number Publication Date
CN119834814A CN119834814A (en) 2025-04-15
CN119834814B true CN119834814B (en) 2025-10-31

Family

ID=95293410

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202411904690.3A Active CN119834814B (en) 2024-12-23 2024-12-23 System MSR code generation and restoration method with minimum packet number

Country Status (1)

Country Link
CN (1) CN119834814B (en)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN120215840B (en) * 2025-05-22 2025-08-15 浪潮电子信息产业股份有限公司 Data restoration method, distributed storage system, device, medium and product

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108512918A (en) * 2018-03-23 2018-09-07 山东大学 The data processing method of heterogeneous distributed storage system
CN109062724A (en) * 2018-07-21 2018-12-21 湖北大学 A kind of correcting and eleting codes conversion method and terminal

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017041231A1 (en) * 2015-09-08 2017-03-16 广东超算数据安全技术有限公司 Codec of binary exact-repair regenerating code
WO2020010505A1 (en) * 2018-07-10 2020-01-16 深圳花儿数据技术有限公司 Synchronization recovery method for data of distributed storage system, and storage medium
CN115237662A (en) * 2022-06-24 2022-10-25 北京航空航天大学 Distributed storage node error correction method and system
CN117785015A (en) * 2022-09-20 2024-03-29 华为技术有限公司 A data storage method and data storage system

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN108512918A (en) * 2018-03-23 2018-09-07 山东大学 The data processing method of heterogeneous distributed storage system
CN109062724A (en) * 2018-07-21 2018-12-21 湖北大学 A kind of correcting and eleting codes conversion method and terminal

Also Published As

Publication number Publication date
CN119834814A (en) 2025-04-15

Similar Documents

Publication Publication Date Title
CN103688514B (en) An Encoding and Storage Node Restoration Method of Minimal Storage Regeneration Code
CN103688515B (en) An Encoding and Storage Node Restoration Method of Minimal Bandwidth Regenerating Codes
KR101270815B1 (en) In-place transformations with applications to encoding and decoding various classes of codes
CN103336785B (en) A kind of distributed storage method based on network code and device thereof
CN111682874B (en) A data recovery method, system, device and readable storage medium
CN110168505B (en) Data repair method of distributed storage system and storage medium
CN103746774B (en) The fault-tolerant coding method that a kind of efficient data is read
EP2533450B1 (en) Method and device for data check processing
CN114153393B (en) Data coding method, system, equipment and medium
Hou et al. A new design of binary MDS array codes with asymptotically weak-optimal repair
CN119834814B (en) System MSR code generation and restoration method with minimum packet number
CN112799875A (en) Method, system, device and medium for verification recovery based on Gaussian elimination
CN111697976A (en) RS erasure correcting quick decoding method and system based on distributed storage
CN109347486A (en) Low-complexity high-throughput 5G LDPC encoder and encoding method
CN101192833A (en) A device and method for parallel encoding of low density check code LDPC
CN113360264A (en) Erasure processing system and method and distributed storage system
CN109257049B (en) A construction method and repair method for repairing binary array code parity check matrix
Hou et al. Triple-fault-tolerant binary MDS array codes with asymptotically optimal repair
CN115454712B (en) A check code recovery method, system, electronic equipment and storage medium
WO2017041232A1 (en) Encoding and decoding framework for binary cyclic code
WO2020029417A1 (en) Method for encoding and framing binary mds array code
Song et al. A Low complexity design of reed solomon code algorithm for advanced RAID system
CN115993941B (en) Distributed data storage error correction method and system
CN105955839B (en) A kind of regeneration code fault-tolerance approach based on the displacement of finite field binary addition
CN114546708A (en) Method and device suitable for uniform and distributed storage erasure correction

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant