[go: up one dir, main page]

WO2018171111A1 - Procédé de codage et de réparation de code de réseau mds à tolérance aux défaillances multiples - Google Patents

Procédé de codage et de réparation de code de réseau mds à tolérance aux défaillances multiples Download PDF

Info

Publication number
WO2018171111A1
WO2018171111A1 PCT/CN2017/097669 CN2017097669W WO2018171111A1 WO 2018171111 A1 WO2018171111 A1 WO 2018171111A1 CN 2017097669 W CN2017097669 W CN 2017097669W WO 2018171111 A1 WO2018171111 A1 WO 2018171111A1
Authority
WO
WIPO (PCT)
Prior art keywords
information
column
bits
parity
code
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.)
Ceased
Application number
PCT/CN2017/097669
Other languages
English (en)
Chinese (zh)
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.)
Dongguan University of Technology
Original Assignee
Dongguan University of Technology
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 Dongguan University of Technology filed Critical Dongguan University of Technology
Publication of WO2018171111A1 publication Critical patent/WO2018171111A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/10—Protocols in which an application is distributed across nodes in the network
    • H04L67/1097—Protocols in which an application is distributed across nodes in the network for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0614—Improving the reliability of storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/067—Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/02—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word
    • H03M7/04—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word the radix thereof being two

Definitions

  • the present invention relates to the field of data processing, and in particular, to a multi-fault-tolerant MDS array code encoding and repair method.
  • the binary maximum distance separable (MDS) array code is a special erasure code that achieves fault tolerance with minimal storage redundancy and low computational complexity.
  • the binary array code is composed of an array of k+r columns, each column having L bits, wherein for the k+r columns, the k column information column stores information bits, and the r column parity column stores redundancy The remaining position.
  • the L bits in each column are stored in the same storage node. If any k in the k+r column is sufficient to reconstruct all of the k-column information columns, then such a code can be referred to as an MDS (ie, it can tolerate any r-column failure).
  • the repair bandwidth is defined as the number of download bits in the repair operation. Minimizing repair bandwidth is critical to speeding up repair operations and minimizing fragile windows, especially in distributed storage systems where network transport often becomes a bottleneck.
  • the repair problem was first elaborated and studied by Dimakis et al. [5] based on the information flow diagram. As stated in [5], the minimum repair bandwidth is subject to minimum storage redundancy, also known as the Minimum Memory Regeneration (MSR) point, which is calculated as follows:
  • the present invention provides a multi-fault-tolerant MDS array code encoding and repairing method, which solves the problem that the prior art cannot combine optimal repair and higher fault tolerance.
  • a multi-fault-tolerant MDS array code coding is designed and manufactured, and the component thereof is a C(k, 3, p) code, and the data block is divided into k(p-1) ⁇ .
  • the information column is represented by a polynomial, and each corresponding information column is a data polynomial, and the corresponding three parity columns form an encoded polynomial, and the data polynomial and the encoded polynomial form a column vector [s 1 (x), s 2 (x), ..., s k+3 (x)].
  • the product of G is calculated, where G is the matrix of the kxk unit matrix I and a kx3 matrix
  • the kx(k+3) composed of P generates a matrix.
  • the C(k,3,p) code is such that a systematic linear code is penetrated within R p ⁇ .
  • the invention also provides a method for repairing a multi-fault-tolerant MDS array code, comprising the steps of: obtaining an information column that has failed; if the information column has failed Then fix the information bits s l,f by the first parity, where l mod 2 f ⁇ 0,1,2,...2 f-1 -1 ⁇ , otherwise repaired by the second parity Information bits s l,f , where l mod 2 f ⁇ 2 f-1 , 2 f-1 +1,2 f-1 +2,...,2 f -1 ⁇ ; if the information column has failed
  • the information bits s l,f are fixed by the first parity, where l mod 2 f ⁇ 0,1,2,...,2 f-1 -1 ⁇ , otherwise, pass the third parity To fix the information bits s l,f , where l mod 2 f ⁇ 2 f-1 , 2 f-1 +1,2 f-1 +2,...,2 f -1 ⁇ .
  • the information column that has failed The repaired broadband is (p-1)((k+2)2 k-3 -2 kf-2 ).
  • the parity sets of the second parity column and the third parity column are not corresponding to those columns of information in a straight line in the array, but correspond to those columns of information in a broken line;
  • the number of lines is divisible by 2 k-2 .
  • the invention has the beneficial effects that the fault tolerance of the system is improved; the computational complexity of the codec process is lower, and the repair of the broadband is greatly reduced.
  • FIG. 1 is a schematic diagram of an embodiment of a memory code used in a three parity check column of the present invention.
  • a multi-fault-tolerant MDS array code coding the component of which is a C(k,3,p) code, which divides the data block into k(p-1) ⁇ information bits and encodes to generate 3(p-1) ⁇ redundancy.
  • the information column is represented by a polynomial, and each corresponding information column is a data polynomial, and the corresponding three parity columns form a coded polynomial, and the data polynomial and the coded polynomial form a column vector [s 1 (x), s 2 (x),...,s k+3 (x)].
  • the product of G is calculated, where G is kx (k) consisting of a kxk unit matrix I and a kx3 coding matrix P +3) Generate a matrix.
  • the C(k,3,p) code is a systematic linear code penetrating into R p ⁇ .
  • the invention also provides a method for repairing a multi-fault-tolerant MDS array code, comprising the steps of: obtaining an information column that has failed; if the information column has failed Then fix the information bits s l,f by the first parity, where l mod 2 f ⁇ 0,1,2,...2 f-1 -1 ⁇ , otherwise repaired by the second parity Information bits s l,f , where l mod 2 f ⁇ 2 f-1 , 2 f-1 +1,2 f-1 +2,...,2 f -1 ⁇ ; if the information column has failed
  • the information bits s l,f are fixed by the first parity, where l mod 2 f ⁇ 0,1,2,...,2 f-1 -1 ⁇ , otherwise, pass the third parity To fix the information bits s l,f , where l mod 2 f ⁇ 2 f-1 , 2 f-1 +1,2 f-1 +2,...,2 f -1 ⁇ .
  • the repaired broadband is (p-1) ((k+2) 2 k-3 -2 kf-2 ).
  • the parity sets of the second parity column and the third parity column do not correspond to those columns of information in a line in the array, but correspond to those columns of information in a line; the number of rows of the array is 2 k-2 Divisible.
  • the multi-fault-tolerant MDS array code is constructed as follows:
  • the polynomial of k + 3) is called a coding polynomial.
  • the algorithm embodied in [S 1 (x), s 2 (x),..., s k+3 (x)] [s 1 (x), s 2 (x),...,s
  • the product of k (x)] ⁇ G is calculated.
  • the kx(k+3) generation matrix G is composed of a kxk unit matrix I and a kx3 coding matrix P,
  • the variable x represents the cyclic right shift operator on the polynomial. This is critical to reducing the repair bandwidth for a column failure.
  • the proposed code is represented as C(k,3,p). Please note that extra bits are not stored on disk; they are for convenience only.
  • the encoding matrix for this example is
  • the encoding process can be described in the form of a polynomial as follows. Given k(p-1) ⁇ information bits, ⁇ extra bits are appended for each (p-1) ⁇ information bit and form a message vector [s 1 (x), s 2 (x),...,s k (x)].
  • the number of times of storage is 0 to the term coefficient in the (p-1) ⁇ -1 polynomial.
  • the proposed array code can be viewed as a systematic linear code that operates within Rp ⁇ .
  • a progressive optimal repair of information failure in one embodiment, will show how to repair the bits stored in information column f by accessing bits from k-1 other columns of information and 2 parity columns.
  • extra bits can be calculated by (2).
  • the bit elements of column i are represented as p ⁇ bits s 0,i , s 1,i ,...,s p ⁇ -1,i .
  • the parity set is formally defined as follows.
  • Definition 1 For 0 ⁇ l ⁇ p ⁇ -1, define the first parity set of the first column, the second column, and the third column as
  • parity set Includes multiple information bits that can be used to generate redundant bits When it is said that one information bit is repaired by a parity column, this means that in addition to the erased bits, the redundant bits of the parity column and all the information bits in the parity column are accessed.
  • the first column is erased.
  • the eight bits stored in the second information column can be downloaded by downloading six bits from the first information column and from the third information column, the fourth information column, the first parity column, and the second parity column.
  • the four bits in each column are restored.
  • a total of 22 bits were downloaded during the repair process.
  • the third column of information and the last column of information can be reconstructed by accessing 22 bits and 20 bits from 5 columns, respectively.
  • Theorem 3 When At the time, the information column f obtained by Algorithm 1 repairs the bandwidth as
  • the parity set of the first parity column in the proposed code is the same as the parity set of the first parity column in RDP and EVENODD.
  • the key difference between the proposed code and the existing binary MDS array code is the construction of the second and third parity columns.
  • the parity sets of the second and third parity columns in the proposed code do not correspond to those bits that are straight in the array, but rather to those bits that are in a broken line.
  • the number of rows in the array in the proposed code can be divisible by 2 k-2 . These two properties are critical to reducing the repair bandwidth.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Probability & Statistics with Applications (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

La présente invention concerne le domaine du traitement de données, et concerne notamment un codage de code de réseau MDS à tolérance aux défaillances multiples, un composant de celui-ci étant un code (k,3,p), l'expression de blocs de données sous la forme de bits d'information k(p-1)τ, et le codage pour générer 3(p-1)τ bits redondants, (p-1)τ étant un nombre entier, τ=2k-2, p étant un nombre premier, k≥3, et τ bits supplémentaires étant ajoutés à chaque (p-1)τ bit d'information pour former un vecteur de message. Les effets avantageux de la présente invention sont : la tolérance aux défaillances d'un système est améliorée; la complexité de calcul du codage et du décodage est relativement faible, et une bande passante de réparation est ainsi significativement réduite.
PCT/CN2017/097669 2017-07-12 2017-08-16 Procédé de codage et de réparation de code de réseau mds à tolérance aux défaillances multiples Ceased WO2018171111A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN201710566011.XA CN107395207B (zh) 2017-07-12 2017-07-12 多容错性的mds阵列码编码以及修复方法
CN201710566011.X 2017-07-12

Publications (1)

Publication Number Publication Date
WO2018171111A1 true WO2018171111A1 (fr) 2018-09-27

Family

ID=60339499

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2017/097669 Ceased WO2018171111A1 (fr) 2017-07-12 2017-08-16 Procédé de codage et de réparation de code de réseau mds à tolérance aux défaillances multiples

Country Status (2)

Country Link
CN (1) CN107395207B (fr)
WO (1) WO2018171111A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11038533B2 (en) 2019-04-25 2021-06-15 International Business Machines Corporation Expansion for generalized EVENODD codes

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109257050A (zh) * 2018-08-09 2019-01-22 东莞理工学院 一种修复二进制码生成矩阵构造方法及修复方法
CN109062725A (zh) * 2018-08-09 2018-12-21 东莞理工学院 一种二进制mds阵列编码的编码框架方法
CN109257049B (zh) * 2018-08-09 2020-11-06 东莞理工学院 一种修复二进制阵列码校验矩阵的构造方法及修复方法
CN110289864A (zh) * 2019-08-01 2019-09-27 东莞理工学院 二进制mds阵列码的最优修复访问变换方法及装置
CN110532128B (zh) * 2019-08-16 2021-04-20 西安交通大学 一种降低数据更新代价的纠删码编码及数据重构方法
CN110750382B (zh) * 2019-09-18 2020-10-30 华中科技大学 用于提高数据修复性能的最小存储再生码编码方法及系统
CN110704232B (zh) * 2019-10-10 2023-03-14 广东工业大学 一种分布式系统中失效节点的修复方法、装置和设备
CN111143108B (zh) * 2019-12-09 2023-05-02 成都信息工程大学 一种降低阵列码Xcode修复的编译码方法及装置
CN111988437B (zh) * 2020-09-15 2023-03-24 东莞理工学院 一种通用的Expanded-Blaum-Roth码的编码方法及其解码方法
CN113641531B (zh) * 2021-07-27 2025-01-10 山西品尚网络科技有限责任公司 Star码的编码方法及其解码方法

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100153822A1 (en) * 2008-12-15 2010-06-17 Microsoft Corporation Constructing Forward Error Correction Codes
CN102624866A (zh) * 2012-01-13 2012-08-01 北京大学深圳研究生院 一种存储数据的方法、装置及分布式网络存储系统
WO2016058289A1 (fr) * 2015-01-20 2016-04-21 北京大学深圳研究生院 Code d'effacement mds permettant de réparer plusieurs nœud en panne

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100153822A1 (en) * 2008-12-15 2010-06-17 Microsoft Corporation Constructing Forward Error Correction Codes
CN102624866A (zh) * 2012-01-13 2012-08-01 北京大学深圳研究生院 一种存储数据的方法、装置及分布式网络存储系统
WO2016058289A1 (fr) * 2015-01-20 2016-04-21 北京大学深圳研究生院 Code d'effacement mds permettant de réparer plusieurs nœud en panne

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
YONGJUN: "the research about the encoding and repair mechanism based on erasure code in the distributed storage system", 15 May 2017 (2017-05-15) *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11038533B2 (en) 2019-04-25 2021-06-15 International Business Machines Corporation Expansion for generalized EVENODD codes

Also Published As

Publication number Publication date
CN107395207B (zh) 2019-11-22
CN107395207A (zh) 2017-11-24

Similar Documents

Publication Publication Date Title
WO2018171111A1 (fr) Procédé de codage et de réparation de code de réseau mds à tolérance aux défaillances multiples
US11233643B1 (en) Distributed data storage system data decoding and decryption
US10740183B1 (en) Recovering failed devices in distributed data centers
US9432341B2 (en) Securing data in a dispersed storage network
US9110819B2 (en) Adjusting data dispersal in a dispersed storage network
US9208331B2 (en) Efficient storage of encrypted data in a dispersed storage network
CN109643258B (zh) 使用高速率最小存储再生擦除代码的多节点修复
US9154298B2 (en) Securely storing data in a dispersed storage network
US8744071B2 (en) Dispersed data storage system data encryption and encoding
CN102624866B (zh) 一种存储数据的方法、装置及分布式网络存储系统
US9170884B2 (en) Utilizing cached encoded data slices in a dispersed storage network
US7386757B2 (en) Method and apparatus for enabling high-reliability storage of distributed data on a plurality of independent storage devices
US20150356305A1 (en) Secure data access in a dispersed storage network
Hou et al. Binary MDS array codes with optimal repair
US20140195875A1 (en) Achieving storage compliance in a dispersed storage network
WO2020047707A1 (fr) Procédé de codage, de décodage et de réparation de données pour système de stockage distribué
Hou et al. Triple-fault-tolerant binary MDS array codes with asymptotically optimal repair
US11991280B2 (en) Randomized transforms in a dispersed data storage system
Hou et al. A new construction of EVENODD codes with lower computational complexity
US12298854B2 (en) Storing data objects in a storage network with multiple memory types
CN109257049B (zh) 一种修复二进制阵列码校验矩阵的构造方法及修复方法
Malluhi et al. Coding for high availability of a distributed-parallel storage system
Yang et al. Hierarchical coding to enable scalability and flexibility in heterogeneous cloud storage
WO2020029418A1 (fr) Procédé de construction d'une matrice génératrice de code binaire de réparation et procédé de réparation
Chen et al. A new Zigzag MDS code with optimal encoding and efficient decoding

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 17902421

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 17902421

Country of ref document: EP

Kind code of ref document: A1