Repair-optimal parity code

Patent metadata

Field	Value
Publication number	US-9793922-B2
Application number	US-201514865388-A
Country	US
Kind code	B2
Filing date	Sep 25, 2015
Priority date	Sep 25, 2015
Publication date	Oct 17, 2017
Grant date	Oct 17, 2017

Abstract

Techniques for generating parities and repairing data erasures using repair-optimal parities are disclosed. The system includes an encoding module, which receives a request to recreate data for a subset of a plurality of content stores. The encoding module generates a new first parity and a new second parity using a subset of remaining content from the plurality of content stores. The encoding module generates a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores and a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores. The encoding module may recreate the data for the content store using the first portion of the requested data and the second portion of requested data.

First claim

What is claimed is:

1. A computer-implemented method comprising:
retrieving content from memory;
generating a first part of a first parity of the content from memory, the first part including a horizontal parity of the content from memory;
updating the first parity of the content from memory with a second part, the second part including an even row contribution of a first orthogonal permutation of the content from memory;
updating the first parity of the content from memory with a third part, the third part including a second orthogonal permutation based on a first subset of the content from memory;
generating a first part of a second parity of the content from memory, the first part including a third orthogonal permutation based on the content from memory; and
updating the second parity of the content from memory with a second subset of content from the second part of the first parity and the third part of the first parity, the second subset of the content selected from even rows of the first parity.

2. The computer-implemented method of claim 1 , further comprising:
determining that a code word is complete, wherein the content from memory includes the code word;
writing the first parity to a first content store; and
writing the second parity to a second content store.

3. The computer-implemented method of claim 1 , further comprising receiving a request to recreate data for a content store of a plurality of content stores, wherein the plurality of content stores include the content from memory that is represented in the first parity and the second parity.

4. The computer-implemented method of claim 3 , further comprising:
in response to receiving the request to recreate data for the content store of the plurality of content stores, comparing a new first parity for a subset of remaining content in the plurality of content stores and a new second parity for the subset of remaining content in the plurality of content stores with the first parity and the second parity, respectively; and
recreating the data for the content store based on the comparison.

5. The computer-implemented method of claim 4 , wherein the comparison is:
an exclusive-or (XOR) operation on the new first parity and the first parity for the content; and
an XOR operation on the new second parity and the second parity for the content.

6. The computer-implemented method of claim 1 , further comprising generating the first parity and the second parity in a recursive pattern, wherein the recursive pattern is based on the size of the content.

7. A system comprising:
a plurality of content stores; and
a storage controller including an encoding module configured to:
retrieve content from memory;
generate a first part of a first parity of the content from memory, the first part including a horizontal parity of the content from memory;
update the first parity of the content from memory with a second part, the second part including an even row contribution of a first orthogonal permutation of the content from memory;
update the first parity of the content from memory with a third part, the third part including a second orthogonal permutation based on a first subset of the content from memory;
generate a first part of a second parity of the content from memory, the first part including a third orthogonal permutation based on the content from memory; and
update the second parity of the content from memory with a second subset of content from the second part of the first parity and the third part of the first parity, the second subset of the content selected from even rows of the first parity.

8. The system of claim 7 , wherein the encoding module is further configured to:
determine that a code word is complete, wherein the content from memory includes the code word;
write the first parity to a first content store; and
write the second parity to a second content store.

9. The system of claim 7 , wherein the encoding module is further configured to receive a request to recreate data for a content store of the plurality of content stores, wherein the plurality of content stores include the content from memory that is represented in the first parity and the second parity.

10. The system of claim 9 , wherein the encoding module is further configured to:
in response to receiving the request to recreate data for the content store of the plurality of content stores, compare a new first parity for a subset of remaining content in the plurality of content stores and a new second parity for the subset of remaining content in the plurality of content stores with the first parity and the second parity, respectively; and
recreate the data for the content store based on the comparison.

11. The system of claim 10 , wherein the comparison is:
an exclusive-or (XOR) operation on the new first parity and the first parity for the content; and
an XOR operation on the new second parity and the second parity for the content.

12. The system of claim 7 , wherein the encoding module is further configured to generate the first parity and the second parity in a recursive pattern, wherein the recursive pattern is based on the size of the content.

13. A system comprising:
means for retrieving content from memory;
means for generating a first part of a first parity of the content from memory, the first part including a horizontal parity of the content from memory;
means for updating the first parity of the content from memory with a second part, the second part including an even row contribution of a first orthogonal permutation of the content from memory;
means for updating the first parity of the content from memory with a third part, the third part including a second orthogonal permutation based on a first subset of the content from memory;
means for generating a first part of a second parity of the content from memory, the first part including a third orthogonal permutation based on the content from memory; and
means for updating the second parity of the content from memory with a second subset of content from the second part of the first parity and the third part of the first parity, the second subset of the content selected from even rows of the first parity.

14. The system of claim 13 , further comprising:
means for determining that a code word is complete, wherein the content from memory includes the code word;
means for writing the first parity to a first content store; and
means for writing the second parity to a second content store.

15. The system of claim 13 , further comprising means for receiving a request to recreate data for a content store of a plurality of content stores, wherein the plurality of content stores include the content from memory that is represented in the first parity and the second parity.

16. The system of claim 15 , further comprising:
means for comparing, in response to receiving the request to recreate data for the content store of the plurality of content stores, a new first parity for a subset of remaining content in the plurality of content stores and a new second parity for the subset of remaining content in the plurality of content stores with the first parity and the second parity, respectively; and
means for recreating the data for the content store based on the comparison.

17. The system of claim 16 , wherein the comparison is:
an exclusive-or (XOR) operation on the new first parity and the first parity for the content; and
an XOR operation on the new second parity and the second parity for the content.

18. The system of clai

Assignees

• HGST Netherlands BV

Inventors

• Mateescu Robert
• Pamies-Juarez Lluis
• Guyot Cyril

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/11 Primary

  using multiple parity bits · CPC title

• H03M13/3761

  using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes · CPC title

• H03M13/13

  Linear codes · CPC title

• H03M13/033

  Theoretical methods to calculate these checking codes · CPC title