公开(公告)号：US20120221920A1

公开(公告)日：2012-08-30

申请号：US13036817

申请日：2011-02-28

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler ,  Daniel F. Smith

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler ,  Daniel F. Smith

IPC分类号： G11C29/00

CPC分类号： G06F11/108 ,  G11C2029/0411

摘要： Embodiments of the invention relate to erasure correcting codes for storage arrays. An aspect of the invention includes receiving a read stripe from a plurality of storage devices. The read stripe includes a block of pages arranged in rows and columns, with each column corresponding to one of the storage devices. The pages include data pages and parity pages, with the number of parity pages at least one more than the number of rows and not a multiple of the number of rows. The method further includes reconstructing at least one erased page in response to determining that the read stripe includes the at least one erased page and that the number of erased pages is less than or equal to the number of parity pages. The reconstructing is responsive to a multiple erasure correcting code and to the block of pages. The reconstructing results in a recovered read stripe.

摘要翻译： 本发明的实施例涉及存储阵列的擦除校正码。 本发明的一个方面包括从多个存储设备接收读取条带。 读取条带包括以行和列排列的页面块，每一列对应于其中一个存储设备。 这些页面包括数据页和奇偶校验页，奇偶校验页的数量至少比行数多一个，而不是行数的倍数。 所述方法还包括响应于确定所述读取条带包括所述至少一个已擦除页面并且所述擦除页面的数量小于或等于所述奇偶校验页数来重构至少一个已擦除页面。 重建响应于多个擦除校正码和页块。 重建导致恢复的读取条带。

公开(公告)号：US09058291B2

公开(公告)日：2015-06-16

申请号：US13036817

申请日：2011-02-28

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler ,  Daniel F. Smith

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler ,  Daniel F. Smith

IPC分类号： G11C29/00 ,  G06F11/10 ,  G11C29/04

CPC分类号： G06F11/108 ,  G11C2029/0411

摘要： Embodiments of the invention relate to erasure correcting codes for storage arrays. An aspect of the invention includes receiving a read stripe from a plurality of storage devices. The read stripe includes a block of pages arranged in rows and columns, with each column corresponding to one of the storage devices. The pages include data pages and parity pages, with the number of parity pages at least one more than the number of rows and not a multiple of the number of rows. The method further includes reconstructing at least one erased page in response to determining that the read stripe includes the at least one erased page and that the number of erased pages is less than or equal to the number of parity pages. The reconstructing is responsive to a multiple erasure correcting code and to the block of pages. The reconstructing results in a recovered read stripe.

摘要翻译： 本发明的实施例涉及存储阵列的擦除校正码。 本发明的一个方面包括从多个存储设备接收读取条带。 读取条带包括以行和列排列的页面块，每一列对应于其中一个存储设备。 这些页面包括数据页和奇偶校验页，奇偶校验页的数量至少比行数多一个，而不是行数的倍数。 所述方法还包括响应于确定所述读取条带包括所述至少一个已擦除页面并且所述擦除页面的数量小于或等于所述奇偶校验页数来重构至少一个已擦除页面。 重建响应于多个擦除校正码和页块。 重建导致恢复的读取条带。

公开(公告)号：US20120331367A1

公开(公告)日：2012-12-27

申请号：US13563123

申请日：2012-07-31

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： H03M13/29 ,  G06F11/10

CPC分类号： G06F11/108 ,  G06F2211/1045 ,  G06F2211/1057 ,  G06F2211/1059

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving write data. The write data is arranged into “r” rows and “n” columns of pages, with each page including a plurality of sectors. The write data is encoded using a plurality of horizontal and vertical erasure correcting codes on the pages. The encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r-1 rows, up to tr-2 erasures in any one of the remaining r-2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row. Encoded write data is output from the encoding. The encoded write data is written as a write stripe across n storage devices in a storage array.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收写入数据。 写入数据被排列成r行和n列的页面，每个页面包括多个扇区。 使用页面上的多个水平和垂直擦除校正码对写入数据进行编码。 该编码允许在r行中的任何一行中从最多到三次的恢复进行恢复，直到剩余的r-1行中的任何一行中的tr-1次擦除，直到剩下的r-2行中的任一个中的tr-2擦除 ，等等，使得编码允许在最后剩余的行中从高达t1个删除恢复。 从编码输出编码的写入数据。 编码的写入数据被写入存储阵列中的n个存储设备上的写入条带。

公开(公告)号：US20130205181A1

公开(公告)日：2013-08-08

申请号：US13364390

申请日：2012-02-02

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： H03M13/05 ,  G06F11/10

CPC分类号： G06F11/1076 ,  G06F11/108 ,  G06F11/1092 ,  G06F2211/1057 ,  G06F2211/1059 ,  H03M13/033

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving and arranging read data in array that includes m rows and n columns of entries, with each entry including at least one sector. In the array, mr+s locations are assigned to parity entries, such that each row has at least r parity entries. The parity entries correspond to a partial-maximum distance separable (PMDS) code that allows recovery from up to r erasures in each of the m rows as well as s additional erasures in any locations in the data array, where s is an integer greater than zero. The write data and the associated parity entries are written to the set of storage devices.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收和排列包括m行和n列条目的阵列中的读取数据，其中每个条目包括至少一个扇区。 在阵列中，mr + s位置被分配给奇偶校验项，使得每行至少具有r个奇偶校验项。 奇偶校验条目对应于部分最大距离可分离（PMDS）码，其允许从m行中的每个m行中恢复到最多的擦除以及在数据阵列中的任何位置的附加擦除，其中s是大于 零。 将写入数据和相关联的奇偶校验条目写入存储设备集合。

公开(公告)号：US08874995B2

公开(公告)日：2014-10-28

申请号：US13364390

申请日：2012-02-02

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： G11C29/00 ,  G06F11/10

CPC分类号： G06F11/1076 ,  G06F11/108 ,  G06F11/1092 ,  G06F2211/1057 ,  G06F2211/1059 ,  H03M13/033

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving and arranging read data in array that includes m rows and n columns of entries, with each entry including at least one sector. In the array, mr+s locations are assigned to parity entries, such that each row has at least r parity entries. The parity entries correspond to a partial-maximum distance separable (PMDS) code that allows recovery from up to r erasures in each of the m rows as well as s additional erasures in any locations in the data array, where s is an integer greater than zero. The write data and the associated parity entries are written to the set of storage devices.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收和排列包括m行和n列条目的阵列中的读取数据，其中每个条目包括至少一个扇区。 在阵列中，mr + s位置被分配给奇偶校验项，使得每行至少具有r个奇偶校验项。 奇偶校验条目对应于部分最大距离可分离（PMDS）码，其允许从m行中的每个m行中恢复到最多的擦除以及在数据阵列中的任何位置的附加擦除，其中s是大于 零。 将写入数据和相关联的奇偶校验条目写入存储设备集合。

公开(公告)号：US20130205168A1

公开(公告)日：2013-08-08

申请号：US13552271

申请日：2012-07-18

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： G06F11/16 ,  G06F12/00

CPC分类号： G06F11/1076 ,  G06F11/108 ,  G06F11/1092 ,  G06F2211/1057 ,  G06F2211/1059 ,  H03M13/033

摘要： Embodiments of the invention relate to correcting erasures in a storage array. A read stripe is received from a plurality of n storage devices. The read stripe includes an array of entries arranged in m rows and n columns with each column corresponding to one of the storage devices. The entries include data entries and mr+s parity entries. Each row contains at least r parity entries generated from the data entries according to a partial maximum distance separable (PMDS) code. It is determined that the read stripe includes at least one erased entry, at most mr+s erased entries and that no row has more than r+s erased entries. The erased entries are reconstructed from the non-erased entries, resulting in a recovered read stripe.

摘要翻译： 本发明的实施例涉及校正存储阵列中的擦除。 从多个n个存储设备接收读取条带。 读取的条带包括以m行和n列排列的条目数组，每列对应于一个存储设备。 条目包括数据条目和mr + s奇偶校验条目。 每行至少包含根据部分最大距离可分离（PMDS）代码从数据条目生成的r个奇偶校验项。 确定读取的条带包括至少一个被擦除的条目，至多mr + s个擦除条目，并且没有行具有多于r + s个擦除的条目。 从未擦除的条目重建已擦除的条目，导致恢复的读取条带。

公开(公告)号：US08433979B2

公开(公告)日：2013-04-30

申请号：US13036845

申请日：2011-02-28

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： G11C29/00

CPC分类号： G06F11/108 ,  G06F2211/1045 ,  G06F2211/1057 ,  G06F2211/1059

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving write data. The write data is arranged into “r” rows and “n” columns of pages, with each page including a plurality of sectors. The write data is encoded using a plurality of horizontal and vertical erasure correcting codes on the pages. The encoding allows recovery from up to tr erasures in any one of the r rows, up to tr−1 erasures in any one of the remaining r−1 rows, up to tr−2 erasures in any one of the remaining r−2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row. Encoded write data is output from the encoding. The encoded write data is written as a write stripe across n storage devices in a storage array.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收写入数据。 写入数据被布置成“r”行和“n”列的页面，每个页面包括多个扇区。 使用页面上的多个水平和垂直擦除校正码对写入数据进行编码。 该编码允许在r行中的任何一行中从最多到三次的恢复进行恢复，直到剩余的r-1行中的任何一行中的tr-1次擦除，直到剩下的r-2行中的任一个中的tr-2擦除 ，等等，使得编码允许在最后剩余的行中从高达t1个删除恢复。 从编码输出编码的写入数据。 编码的写入数据被写入存储阵列中的n个存储设备上的写入条带。

公开(公告)号：US08869006B2

公开(公告)日：2014-10-21

申请号：US13552271

申请日：2012-07-18

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： G11C29/00 ,  G06F11/10

CPC分类号： G06F11/1076 ,  G06F11/108 ,  G06F11/1092 ,  G06F2211/1057 ,  G06F2211/1059 ,  H03M13/033

摘要： Embodiments of the invention relate to correcting erasures in a storage array. A read stripe is received from a plurality of n storage devices. The read stripe includes an array of entries arranged in m rows and n columns with each column corresponding to one of the storage devices. The entries include data entries and mr+s parity entries. Each row contains at least r parity entries generated from the data entries according to a partial maximum distance separable (PMDS) code. It is determined that the read stripe includes at least one erased entry, at most mr+s erased entries and that no row has more than r+s erased entries. The erased entries are reconstructed from the non-erased entries, resulting in a recovered read stripe.

摘要翻译： 本发明的实施例涉及校正存储阵列中的擦除。 从多个n个存储设备接收读取条带。 读取的条带包括以m行和n列排列的条目数组，每列对应于一个存储设备。 条目包括数据条目和mr + s奇偶校验条目。 每行至少包含根据部分最大距离可分离（PMDS）代码从数据条目生成的r个奇偶校验项。 确定读取的条带包括至少一个被擦除的条目，至多mr + s个擦除条目，并且没有行具有多于r + s个擦除的条目。 从未擦除的条目重建已擦除的条目，导致恢复的读取条带。

公开(公告)号：US08918701B2

公开(公告)日：2014-12-23

申请号：US13563123

申请日：2012-07-31

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： G11C29/00 ,  G06F11/10

CPC分类号： G06F11/108 ,  G06F2211/1045 ,  G06F2211/1057 ,  G06F2211/1059

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving write data. The write data is arranged into “r” rows and “n” columns of pages, with each page including a plurality of sectors. The write data is encoded using a plurality of horizontal and vertical erasure correcting codes on the pages. The encoding allows recovery from up to tr erasures in any one of the r rows, up to tr−1 erasures in any one of the remaining r−1 rows, up to tr−2 erasures in any one of the remaining r−2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row. Encoded write data is output from the encoding. The encoded write data is written as a write stripe across n storage devices in a storage array.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收写入数据。 写入数据被布置成“r”行和“n”列的页面，每个页面包括多个扇区。 使用页面上的多个水平和垂直擦除校正码对写入数据进行编码。 该编码允许在r行中的任何一行中从最多到三次的恢复进行恢复，直到剩余的r-1行中的任何一行中的tr-1次擦除，直到剩下的r-2行中的任一个中的tr-2擦除 ，等等，使得编码允许在最后剩余的行中从高达t1个删除恢复。 从编码输出编码的写入数据。 编码的写入数据被写入存储阵列中的n个存储设备上的写入条带。

公开(公告)号：US20120221926A1

公开(公告)日：2012-08-30

申请号：US13036845

申请日：2011-02-28

申请人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

发明人： Mario Blaum ,  James L. Hafner ,  Steven R. Hetzler

IPC分类号： H03M13/05 ,  G06F11/10

CPC分类号： G06F11/108 ,  G06F2211/1045 ,  G06F2211/1057 ,  G06F2211/1059

摘要： Embodiments of the invention relate to storing data in a storage array. An aspect of the invention includes receiving write data. The write data is arranged into “r” rows and “n” columns of pages, with each page including a plurality of sectors. The write data is encoded using a plurality of horizontal and vertical erasure correcting codes on the pages. The encoding allows recovery from up to tr erasures in any one of the r rows, up to tr-1 erasures in any one of the remaining r−1 rows, up to tr-2 erasures in any one of the remaining r−2 rows, and so on, such that the encoding allows recovery from up to t1 erasures in the last remaining row. Encoded write data is output from the encoding. The encoded write data is written as a write stripe across n storage devices in a storage array.

摘要翻译： 本发明的实施例涉及将数据存储在存储阵列中。 本发明的一个方面包括接收写入数据。 写入数据被布置成“r”行和“n”列的页面，每个页面包括多个扇区。 使用页面上的多个水平和垂直擦除校正码对写入数据进行编码。 该编码允许在r行中的任何一行中从最多到三次的恢复进行恢复，直到剩余的r-1行中的任何一行中的tr-1次擦除，直到剩下的r-2行中的任一个中的tr-2擦除 ，等等，使得编码允许在最后剩余的行中从高达t1个删除恢复。 从编码输出编码的写入数据。 编码的写入数据被写入存储阵列中的n个存储设备上的写入条带。