Granted Patent B2

US 10,044,374 · App. 14/813,442 · Granted Aug 7, 2018

Abstract

Claims (106)

1. A non-transitory computer-readable storage medium storing computer executable instructions that when executed by a computer control the computer to perform a method for encoding a message to be stored in a distributed data storage system, the method comprising:

accessing a plurality of messages, where a member of the plurality of messages has a message size;

upon determining that the message size of the member of the plurality of messages is greater than or equal to a threshold size:

selecting a Fountain coding approach as a selected coding approach;

upon determining that the message size of the member of the plurality of messages is less than the threshold size:

computing an interleaving overhead;

computing a coding overhead;

upon determining that the interleaving overhead is greater than one and the coding overhead is less than a threshold coding overhead amount:

selecting a Fountain coding approach as the selected coding approach;

upon detecting that the interleaving overhead is not greater than one and the coding overhead is not less than the threshold coding overhead amount:

selecting a Reed Solomon coding approach as the selected coding approach;

upon detecting that a number of parities is less than a threshold number of parities, where the threshold number of parities is four when a STAR coding approach is employed, and where the threshold number of parities is three when a non-STAR coding approach is employed:

using an exclusive or (XOR) based block-maximum distance separable (MDS) coding approach as the selected coding approach;

upon detecting that the number of parities is greater than or equal to the threshold number of parities:

using a classical construction coding approach as the selected coding approach;

upon determining that the data storage system is within a threshold reliability level:

automatically and dynamically generating an adapted coding approach by adjusting a set of coding parameters, where the set of coding parameters is based, at least in part, on the selected coding approach;

upon determining that the data storage system is not within the threshold reliability level, encoding the message using the adapted coding approach, and

storing the encoded message in the distributed data storage system.

2. The non-transitory computer-readable storage medium of claim 1 , the method comprising decoding the message, where decoding the message includes controlling a Reed Solomon (RS) code decoder, a Fountain code decoder, or a hybrid decoder to decode the encoded message.

3. The non-transitory computer-readable storage medium of claim 2 , where the threshold size is 10 KB.

4. The non-transitory computer-readable storage medium of claim 3 , where the set of coding parameters includes:

a number of data units k;

a number of coded units n;

a number of parity units p;

a word size;

a packet size;

a symbol size;

a buffer size;

a decoder failure probability γ;

a coding parameter q;

a coding overhead ε;

a degree distribution Δ(γ,ε); or

a precode rate r p .

5. The non-transitory computer-readable storage medium of claim 4 , where the classical construction coding approach is a Cauchy-RS coding approach or a Vandermonde-RS coding approach.

6. The non-transitory computer-readable storage medium of claim 5 , where the XOR-block MDS coding approach is a Blaum-Roth coding approach, an even-odd coding approach, a row-diagonal parity (RDP) coding approach, a STAR coding approach, or an X-coding approach.

7. The non-transitory computer-readable storage medium of claim 6 where the Fountain coding approach is an online coding approach, a Raptor coding approach, or a Rapar coding approach.

8. The non-transitory computer-readable storage medium of claim 3 , where the set of coding parameters includes:

a number of data units k;

a number of coded units n;

a number of parity units p;

a word size;

a packet size;

a symbol size;

a buffer size;

a decoder failure probability γ;

a coding parameter q;

a coding overhead ε;

a degree distribution Δ(γ,ε); and

a precode rate r p .

9. The non-transitory computer-readable storage medium of claim 7 , the method comprising precoding the message.

10. The non-transitory computer-readable storage medium of claim 9 , where precoding the message includes precoding the message with an RS precode, a multiple of RS precodes, or one RS precode and another code, in conjunction with a Luby Transform (LT) code stage.

11. The non-transitory computer-readable storage medium of claim 10 , the method comprising:

upon detecting that the message is below a threshold length:

adjusting the rate of the RS code; and

bypassing the LT code stage;

upon detecting that the message is equal to or larger than the threshold length:

precoding the message with a different precode and a different LT code stage.

12. A non-transitory computer-readable storage device storing computer executable instructions that when executed by a computer control the computer to perform a method for encoding a message to be stored in a data storage system, the method comprising:

accessing a plurality of messages, where a member of the plurality of messages has a message size;

upon determining that the message size of the member of the plurality of messages is greater than or equal to a threshold size:

selecting a first coding approach as a selected coding approach;

upon determining that the message size of the member of the plurality of messages is less than the threshold size:

computing an interleaving overhead;

computing a coding overhead; and

selecting the first coding approach or a second, different coding approach as the selected coding approach based, at least in part, on the interleaving overhead or the coding overhead;

upon determining that the data storage system is within a threshold reliability level:

automatically and dynamically generating an adapted coding approach by adjusting a set of coding parameters, where the set of coding parameters is based, at least in part, on the selected coding approach;

upon determining that the data storage system is not within the threshold reliability level:

generating an encoded message by encoding the message using the adapted coding approach, and storing the encoded message in the data storage system.

13. The non-transitory computer-readable storage device of claim 12 , where the first coding approach is a Fountain coding approach, where the second coding approach is a Reed Solomon coding approach, and where the Fountain coding approach is an online coding approach, a Raptor coding approach, or a Rapar coding approach.

14. The non-transitory computer-readable storage device of claim 13 , where selecting a first coding approach or a second, different coding approach as the selected coding approach based, at least in part, on the interleaving overhead or the coding overhead includes:

upon determining that the interleaving overhead is greater than one and the coding overhead is less than a threshold coding overhead level:

selecting a Fountain coding approach as the selected coding approach;

upon detecting that the interleaving overhead is not greater than one and the coding overhead is not less than the threshold coding overhead level:

selecting a Reed Solomon coding approach as the selected coding approach;

upon detecting that a number of parities is less than a threshold number of parities, where the threshold number of parities is four when a STAR coding approach is employed, and where the threshold number of parities is three when a non-STAR coding approach is employed:

using an exclusive or (XOR) based block-maximum distance separable (MDS) coding approach as the selected coding approach;

upon detecting that the number of parities is greater than or equal to the threshold number of parities:

using a classical construction coding approach as the selected coding approach.

15. The non-transitory computer-readable storage device of claim 14 , the method further comprising:

decoding the message, where decoding the message includes controlling a Reed Solomon (RS) code decoder, a Fountain code decoder, or a hybrid decoder to decode the encoded message.

16. The non-transitory computer-readable storage device of claim 15 , where the set of coding parameters includes:

a number of data units k;

a number of coded units n;

a number of parity units p;

a word size;

a packet size;

a symbol size;

a buffer size;

a decoder failure probability γ;

a coding parameter q;

a coding overhead ε;

a degree distribution Δ(γ,ε); and

a precode rate r p .

17. The non-transitory computer-readable storage device of claim 16 , where the classical construction coding approach is a Cauchy-RS coding approach or a Vandermonde-RS coding approach, or where the XOR-block MDS coding approach is a Blaum-Roth coding approach, an even-odd coding approach, a row-diagonal parity (RDP) coding approach, a STAR coding approach, or an X-coding approach.

18. The non-transitory computer-readable storage device of claim 17 , the method comprising precoding the message with an RS precode, a multiple of RS precodes, or one RS precode and another code, in conjunction with a Luby Transform (LT) code stage.

19. The non-transitory computer-readable storage device of claim 18 , the method further comprising:

upon detecting that the message is below a threshold length:

adjusting the rate of the RS code; and

bypassing the LT code stage;

upon detecting that the message is equal to or larger than the threshold length:

precoding the message with a different precode and a different LT code stage.

20. The non-transitory computer-readable storage device of claim 12 , the method further comprising:

generating an encoded block that includes the encoded message and metadata associated with the message, where the metadata associated with the message includes a coding flag, a seed, a data identifier, processing information, or a cyclic redundancy check (CRC); and

storing the encoded block in the data storage system, where the data storage system includes one or more data storage devices, where the one or more data storage devices includes a tape drive, a hard disk drive (HDD), a solid state device, (SSD), a hybrid solid state device (HSSD), or a shingled magnetic recording device (SMR), and where the threshold reliability level is based, at least in part, on failure statistics associated with the one or more data storage devices, on wear periods associated with the one or more data storage devices, or on space constraints associated with the one or more data storage devices.

Assignments (12)