Multi-site data redundancy

• US 8,510,625 B1
• Filed: 03/31/2010
• Issued: 08/13/2013
• Est. Priority Date: 03/31/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: DECHO Corporation (Open Text Corporation)
• Inventors: Bozeman, Patrick E., Back, Adam, Wily, Zachary
• Primary Examiner(s): BRITT, CYNTHIA H
• Application Number:
  US12/798,233
• Time in Patent Office: 1,231 Days
• Field of Search: 714/784, 714/20, 714/758, 714/766
• US Class Current: 714/758
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: H03M 13/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 error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/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

Abstract

Storing data includes encoding the data using an erasure encoding to provide encoded data, separating the encoded data into a number of components, and providing each of the components to separate data sites. The data may be encoded using a Reed/Solomon encoding. The data may be encoded using a 3-1 Reed/Solomon encoding and the encoded data may be separated into four components that are provided to four separate sites. The data may be encoded by a site that receives the data prior to encoding. The data may be encoded by a client that provides the data to a plurality of sites coupled thereto. Storing data may also include each of the separate data sites providing an additional encoding for the components. The data and the components may be encoded using a Reed/Solomon encoding.

Claims

1. A method of storing data, comprising:

receiving or generating first data at a first site of a plurality of data sites, wherein the first site includes a plurality of storage devices;

encoding, at the first site, in a first encoding process, the first data using erasure encoding to provide first encoded data;

separating the first encoded data into a plurality of first components;

distributing, from the first site, the first components among at least two separate data sites of the plurality of data sites, the at least two separate data sites being different from the first site;

encoding, at the first site, in a second encoding process, the first data using erasure encoding to provide second encoded data;

separating the second encoded data into a plurality of second components; and

storing, locally at the first site, the second components of the second encoded data among the plurality of storage devices of the first site, wherein the first encoding process and the plurality of first components depend on a number of available data sites of the plurality of data sites that are available to receive first component transmissions from the first site, and wherein the second encoding process and the plurality of second components depend on a number of available storage devices of the first site that are available to store second components.

2. The method, according to claim 1, wherein the first data is encoded using a Reed/Solomon encoding.

3. The method, according to claim 1, wherein the first data is encoded using a 3-1 Reed/Solomon encoding and wherein the first encoded data is separated into four components that are provided to four separate sites.

4. The method, according to claim 1, wherein the first data is generated at the first site before the first data is encoded by the first site.

5. The method, according to claim 1, wherein the first data is generated by a client site that provides the first data to the first site coupled thereto.

6. The method, according to claim 1, further comprising:

after receiving the distributed first components, each of the separate data sites providing an additional encoding for the first components.

7. The method, according to claim 6, wherein the first components are additionally encoded at the separate data sites using a Reed/Solomon encoding.

8. The method according to claim 1, further comprising:

after distributing the first components of the first encoded data, obtaining, at the first site, at least one of the first components from at least one of the separate data sites; and

performing recovery of the first data using the at least one of the first components obtained from the at least one of the separate data sites.

9. The method according to claim 1, wherein the first encoding process is independent of the second encoding process.

10. The method according to claim 1, further comprising:

receiving, at the first site, at least one other component of encoded data distributed by at least one other site of the plurality of data sites to the first site, the first site thereby acting as a separate data site to receive encoded data component transmissions from the at least one other data site.

11. The method according to claim 1, further comprising:

performing recovery of the first data using at least one of the second components locally stored among the plurality of storage devices at the first site.

12. A non-transitory computer-readable medium having software, the software comprising:

executable code that receives or generates first data at a first site of a plurality of data sites, wherein the first site includes a plurality of storage devices;

executable code that encodes, at the first site, in a first encoding process, the first data using erasure encoding to provide first encoded data;

executable code that separates the first encoded data into a plurality of first components;

executable code that distributes, from the first site, the first components among at least two separate data sites of the plurality of data sites, the at least two separate data sites including a second site and a third site, the second site and the third site being different from the first site;

executable code that encodes, at the first site, in a second encoding process, the first data using erasure encoding to provide second encoded data;

executable code that separates the second encoded data into a plurality of second components; and

executable code that stores, locally at the first site, the second components of the second encoded data among the plurality of storage devices of the first site, wherein the first encoding process and the plurality of first components depend on a number of available data sites of the plurality of data sites that are available to receive first component transmissions from the first site, and wherein the second encoding process and the plurality of second components depend on a number of available storage devices of the first site that are available to store second components.

13. The non-transitory computer readable medium according to claim 12, wherein the first data is encoded using a Reed/Solomon encoding.

14. The non-transitory computer readable medium according to claim 12, wherein the first data is encoded using a 3-1 Reed/Solomon encoding and wherein the first encoded data is separated into four components that are provided to four separate sites.

15. The non-transitory computer readable medium according to claim 12, wherein the data is generated at the first site before the first data is encoded by the first site.

16. The non-transitory computer readable medium according to claim 12, wherein the first data is generated by a client site that provides the first data to the first site coupled thereto.

17. The non-transitory computer readable medium according to claim 12, wherein, after receiving the distributed first components, each of the separate data sites provides an additional encoding for the first components.

18. The non-transitory computer readable medium according to claim 12, wherein the software further comprises:

executable code that, after distributing the first components of the first encoded data, obtains, at the first site, at least one of the first components from at least one of the separate data sites; and

executable code that performs recovery of the first data using the at least one of the first components obtained from the at least one of the separate data sites.

19. The non-transitory computer readable medium according to claim 12, wherein the first encoding process is independent of the second encoding process.

20. The non-transitory computer readable medium according to claim 12, further comprising:

executable code that receives, at the first site, at least one other component of encoded data distributed by at least one other site of the plurality of data sites to the first site, the first site thereby acting as a separate data site to receive encoded data component transmissions from the at least one other data site.

21. The non-transitory computer readable medium according to claim 12, further comprising:

executable code that performs recovery of the first data using at least one of the second components locally stored among the plurality of storage devices at the first site.