Distributed storage of data

Patent metadata

Field	Value
Publication number	US-9575846-B2
Application number	US-201414339757-A
Country	US
Kind code	B2
Filing date	Jul 24, 2014
Priority date	Jul 24, 2014
Publication date	Feb 21, 2017
Grant date	Feb 21, 2017

Abstract

Multi-reliability regenerating (MRR) erasure codes are disclosed. The erasure codes can be used to encode and regenerate data. In particular, the regenerating erasure codes can be used to encode data included in at least one of two or more data messages to satisfy respective reliability requirements for the data. Encoded portions of data from one data message can be mixed with encoded or unencoded portions of data from a second data message and stored at a distributed storage system. This approach can be used to improve efficiency and performance of data storage and recovery in the event of failures of one or more nodes of a distributed storage system.

First claim

The invention claimed is:

1. A system, comprising:
a processor; and
a memory that stores instructions that, when executed by the processor, cause the processor to perform operations comprising
obtaining a first set of data and a second set of data,
encoding the first set of data using an erasure code to generate a first set of coded symbols that represent the first set of data,
mixing the first set of coded symbols with the second set of data to generate a plurality of combined data values, wherein the second set of data is unencoded, and
transmitting the plurality of combined data values, the transmitting directed to a plurality of nodes of a distributed storage system.

2. The system of claim 1 , wherein the instructions, when executed by the processor, cause the processor to perform operations further comprising:
detecting a failure of one of the plurality of nodes;
retrieving two of the plurality of combined data values from two of the plurality of nodes;
determining, based on the two of the plurality of combined data values, two of the first set of coded symbols, and
recovering the first set of data by decoding the two of the first set of coded symbols using the erasure code.

3. The system of claim 1 , wherein the instructions, when executed by the processor, cause the processor to perform operations further comprising storing, in a database, a mapping of the plurality of combined data values to a plurality of node addresses that correspond to the plurality of nodes.

4. The system of claim 1 , wherein the plurality of nodes comprises four nodes, and wherein the first set of data is recovered using three of the plurality of combined data values obtained from three of the four nodes.

5. The system of claim 1 , wherein transmitting the plurality of combined data values comprises sending, to the plurality of nodes, a plurality of data messages that includes the plurality of combined data values.

6. The system of claim 1 , wherein one of the plurality of combined data values comprises a sum of one of the first set of coded symbols and one of the second set of data, and wherein another of the plurality of combined data values comprises the one of the second set of data.

7. The system of claim 6 , wherein the instructions, when executed by the processor, cause the processor to perform operations further comprising:
determining the one of the first set of coded symbols based upon the one of the plurality of combined data values and the other of the plurality of combined data values; and
decoding the one of the first set of coded symbols using the erasure code.

8. A method, comprising:
obtaining, at a storage server comprising a processor and a memory, a first set of data and a second set of data;
encoding, by the storage server and using an erasure code, the first set of data to generate a first set of coded symbols that represent the first set of data;
mixing, by the storage server, the first set of coded symbols with the second set of data to generate a plurality of combined data values, wherein the second set of data is unencoded; and
transmitting, by the storage server, the plurality of combined data values to a plurality of nodes of a distributed storage system.

9. The method of claim 8 , further comprising:
detecting a failure of one of the plurality of nodes;
retrieving two of the plurality of combined data values from two of the plurality of nodes;
determining, based on the two of the plurality of combined data values, two of the first set of coded symbols, and
recovering the first set of data by decoding the two of the first set of coded symbols using the erasure code.

10. The method of claim 8 , wherein the plurality of nodes comprises four nodes, and wherein the first set of data is recovered using any three of the plurality of combined data values obtained from three of the four nodes.

11. The method of claim 8 , further comprising:
storing, in a database, a mapping of the plurality of combined data values to a plurality of node addresses that correspond to the plurality of nodes.

12. The method of claim 8 , wherein transmitting the plurality of combined data values comprises transmitting, to the plurality of nodes, a plurality of data messages that includes the plurality of combined data values.

13. The method of claim 8 , wherein one of the plurality of combined data values comprises a sum of one of the first set of coded symbols and one of the second set of data, and wherein another of the plurality of combined data values comprises the one of the second set of data.

14. The method of claim 8 , further comprising:
determining the one of the first set of coded symbols based upon the one of the plurality of combined data values and the other of the plurality of combined data values; and
decoding the one of the first set of coded symbols using the erasure code.

15. A memory that stores instructions that, when executed by a processor, cause the processor to perform operations comprising:
obtaining a first set of data and a second set of data;
encoding the first set of data using an erasure code to generate a first set of coded symbols that represent the first set of data;
mixing the first set of coded symbols with the second set of data to generate a plurality of combined data values, wherein the second set of data is unencoded; and
transmitting the plurality of combined data values at a plurality of nodes of a distributed storage system.

16. The memory of claim 15 , wherein the instructions, when executed by the processor, cause the processor to perform operations further comprising:
detecting a failure of one of the plurality of nodes;
retrieving two of the plurality of combined data values from two of the plurality of nodes;
determining, based on the two of the plurality of combined data values, two of the first set of coded symbols, and
recovering the first set of data by decoding the two of the first set of coded symbols using the erasure code.

17. The memory of claim 15 , wherein one of the plurality of combined data values comprises a sum of one of the first set of coded symbols and one of the second set of data, and wherein another of the plurality of combined data values comprises the one of the second set of data.

18. The memory of claim 15 , wherein transmitting the plurality of combined data values comprises sending, to the plurality of nodes, a plurality of data messages that includes the plurality of combined data values.

19. The method of claim 8 , wherein each of the combined data values comprises a coded symbol and an unencoded data value included in the second set of data.

20. The memory of claim 15 , wherein the instructions, when executed by the processor, cause the processor to perform operations further comprising storing, in a database, a mapping of the plurality of combined data values to a plurality of node addresses that correspond to the plurality of nodes.

Assignees

• At & T Ip I Lp

Inventors

• Tian Chao

Classifications

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F2201/805

  Real-time · CPC title

• H03M13/154

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title

• G06F11/1076 Primary

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

• H03M13/1515

  Reed-Solomon codes · CPC title