Cache oblivious algorithm for butterfly code

Patent metadata

Field	Value
Publication number	US-10164655-B2
Application number	US-201514865411-A
Country	US
Kind code	B2
Filing date	Sep 25, 2015
Priority date	Sep 25, 2015
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

Techniques for generating parities and repairing data erasures using a cache oblivious encoding algorithm are disclosed. The system includes an encoding module which receives a request to recreate data for a subset of a plurality of content stores from a storage manager. The encoding module generates a new first parity and a new second parity using the remaining content in the plurality of content stores. The encoding module generates a first portion of the requested data using the new first parity and a first parity for the plurality of content stores and a second portion of the requested data using the new second parity and a second parity for the plurality of content stores. The encoding module may recreate the data for the plurality of content stores using the first portion of the requested data and the second portion of the requested data.

First claim

What is claimed is:

1. A computer-implemented method comprising:
retrieving a first subset of content from memory;
generating a first combination of data elements from the first subset of content using a combinatorial circuit coupled with a cache memory;
updating a first parity for the content with the first combination of data elements from the first subset of content;
storing the first combination of data elements in the cache memory;
generating an orthogonal permutation based on the first subset of content by:
retrieving the first combination of data elements from the cache memory; and
processing the first combination of data elements with a first correcting factor using the combinatorial circuit;

updating a second parity for the content using the orthogonal permutation;
retrieving a second subset of content from memory;
generating a second combination of data elements from the second subset of content using the combinatorial circuit;
updating the first parity for the content with the second combination of data elements from the second subset of content;
storing the second combination of data elements in the cache memory;
generating an inverse orthogonal permutation based on the second subset of content by:
retrieving the second combination of data elements from the cache memory; and
processing the second combination of data elements with a second correcting factor using the combinatorial circuit; and

updating the second parity for the content using the inverse orthogonal permutation.

2. The computer-implemented method of claim 1 , wherein the first correcting factor and the second correcting factor are based on the first parity.

3. 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.

4. 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.

5. The computer-implemented method of claim 4 further comprising:
in response to receiving the request to recreate data for the content store, 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.

6. The computer-implemented method of claim 5 , wherein the comparison is an “exclusive or” (XOR) operation on the new first parity and the first parity and an XOR operation on the new second parity and the second parity.

7. The computer-implemented method of claim 1 further comprising generating the inverse orthogonal permutation in a recursive pattern, wherein the recursive pattern is based on a size of the content.

8. A system comprising:
one or more processors; and
a memory storing instructions that, when executed, cause the one or more processors to:
retrieve a first subset of content;
generate a first combination of data elements from the first subset of content using a combinatorial circuit coupled with a cache memory;
update a first parity for the content with the first combination of data elements from the first subset of content;
store the first combination of data elements in the cache memory;
generate an orthogonal permutation based on the first subset of content by:
retrieving the first combination of data elements from the cache memory; and
processing the first combination of data elements with a first correcting factor using the combinatorial circuit

update a second parity for the content using the orthogonal permutation;
retrieve a second subset of content;
generate a second combination of data elements from the second subset of content using the combinatorial circuit;
update the first parity for the content with the second combination of data elements from the second subset of content;
store the second combination of data elements in the cache memory;
generate an inverse orthogonal permutation based on the second subset of content by:
retrieving the second combination of data elements from the cache memory; and
processing the second combination of data elements with a second correcting factor using the combinatorial circuit; and

update the second parity for the content using the inverse orthogonal permutation.

9. A computer program product comprising a non-transitory computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:
retrieve a first subset of content from memory;
generate a first combination of data elements from the first subset of content using a combinatorial circuit coupled with a cache memory;
update a first parity for the content with the first combination of data elements from the first subset of content;
store the first combination of data elements in the cache memory;
generate an orthogonal permutation based on the first subset of content by:
retrieving the first combination of data elements from the cache memory; and
processing the first combination of data elements with a first correcting factor using the combinatorial circuit;

update a second parity for the content using the orthogonal permutation;
retrieve a second subset of content from memory;
generate a second combination of data elements from the second subset of content using the combinatorial circuit;
update the first parity for the content with the second combination of data elements from the second subset of content;
store the second combination of data elements in the cache memory;
generate an inverse orthogonal permutation based on the second subset of content by:
retrieving the second combination of data elements from the cache memory; and
processing the second combination of data elements with a second correcting factor using the combinatorial circuit; and

update the second parity for the content using the inverse orthogonal permutation.

Assignees

• HGST Netherlands BV
• Western Digital Tech Inc

Inventors

• Guyot Cyril
• Mateescu Robert
• Pamies-Juarez Lluis
• Blagojevic Filip

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/13

  Linear codes · CPC title

• H03M13/033

  Theoretical methods to calculate these checking codes · CPC title

• G06F11/1012

  using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence) · CPC title