公开(公告)号：US10901844B2

公开(公告)日：2021-01-26

申请号：US16599298

申请日：2019-10-11

Applicant: NetApp, Inc.

Inventor： Syed Abid Hussain ,  Srinivasan Narayanamurthy

IPC: G06F11/10 ,  H03M13/03 ,  H03M13/37 ,  H03M13/13 ,  G06F3/06 ,  H03M13/15

Abstract: A distributed storage system can use a high rate MSR erasure code to repair multiple nodes when multiple node failures occur. An encoder constructs m r-ary trees to determine the symbol arrays for the parity nodes. These symbol arrays are used to generate the parity data according to parity definitions or parity equations. The m r-ary trees are also used to identify a set of recovery rows across helper nodes for repairing a systematic node. When failed systematic nodes correspond to different ones of the m r-ary trees, a decoder may select additional recovery rows. The decoder selects additional recovery rows when the parity definitions do not provide a sufficient number of independent linear equations to solve the unknown symbols of the failed nodes. The decoder can select recovery rows contiguous to the already identified recovery rows for access efficiency.

公开(公告)号：US20180060169A1

公开(公告)日：2018-03-01

申请号：US15248047

申请日：2016-08-26

Applicant: NetApp, Inc.

Inventor： Syed Abid Hussain ,  Srinivasan Narayanamurthy

IPC: G06F11/10 ,  H03M13/15 ,  G06F3/06

CPC classification number: G06F11/1076 ,  G06F3/0619 ,  G06F3/064 ,  G06F3/067 ,  H03M13/03 ,  H03M13/134 ,  H03M13/154 ,  H03M13/373

Abstract: A distributed storage system can use a high rate MSR erasure code to repair multiple nodes when multiple node failures occur. An encoder constructs m r-ary trees to determine the symbol arrays for the parity nodes. These symbol arrays are used to generate the parity data according to parity definitions or parity equations. The m r-ary trees are also used to identify a set of recovery rows across helper nodes for repairing a systematic node. When failed systematic nodes correspond to different ones of the m r-ary trees, a decoder may select additional recovery rows. The decoder selects additional recovery rows when the parity definitions do not provide a sufficient number of independent linear equations to solve the unknown symbols of the failed nodes. The decoder can select recovery rows contiguous to the already identified recovery rows for access efficiency.

公开(公告)号：US10452477B2

公开(公告)日：2019-10-22

申请号：US15248047

申请日：2016-08-26

Applicant: NetApp, Inc.

Inventor： Syed Abid Hussain ,  Srinivasan Narayanamurthy

IPC: G06F11/10 ,  H03M13/15 ,  G06F3/06 ,  H03M13/03 ,  H03M13/13 ,  H03M13/37

Abstract: A distributed storage system can use a high rate MSR erasure code to repair multiple nodes when multiple node failures occur. An encoder constructs m r-ary trees to determine the symbol arrays for the parity nodes. These symbol arrays are used to generate the parity data according to parity definitions or parity equations. The m r-ary trees are also used to identify a set of recovery rows across helper nodes for repairing a systematic node. When failed systematic nodes correspond to different ones of the m r-ary trees, a decoder may select additional recovery rows. The decoder selects additional recovery rows when the parity definitions do not provide a sufficient number of independent linear equations to solve the unknown symbols of the failed nodes. The decoder can select recovery rows contiguous to the already identified recovery rows for access efficiency.

公开(公告)号：US20170179979A1

公开(公告)日：2017-06-22

申请号：US14974799

申请日：2015-12-18

Applicant: NetApp, Inc.

Inventor： Syed Abid Hussain

IPC: H03M13/15 ,  H03M13/00 ,  G06F11/10

CPC classification number: H03M13/154 ,  G06F11/1076 ,  H03M13/03 ,  H03M13/13 ,  H03M13/3761 ,  H03M13/615

Abstract: m r-Ary trees for generating High-Rate MSR (HMSR) erasure codes for application in data storage systems. Nodes in the tree structures represent systematic and parity storage nodes. Each parity symbol for the HMSR erasure codes will be a linear combination of maximum k+k/r systematic symbols. The tree structures show that when a systematic node fails, its original systematic symbols can be recovered by accessing β symbols for each of its leaf nodes from each of the remaining nodes. Traversing the m r-Ary trees to design a codeword array will provide the linear equations needed to solve for and recover the lost systematic symbols. When forming the linear equations, random number or other coefficients can be added to the systematic symbols to construct the parity symbols. The parities of the HMSR erasure code will ensure recovery of any systematic node failure using significantly reduced IO and network bandwidth.