Adaptive erasure codes

• US 10,044,374 B2
• Filed: 07/30/2015
• Issued: 08/07/2018
• Est. Priority Date: 07/30/2015
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Arslan, Suayb, Goker, Turguy
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US14/813,442
• Publication Number:
  US 20170033806A1
• Time in Patent Office: 1,104 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• 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

Methods, apparatus, and other embodiments associated with adaptive use of erasure codes for distributed data storage systems are described. One example method includes accessing a message, where the message has a message size, selecting an encoding strategy as a function of the message size, data storage device failure statistics, data storage device wear periods, data storage space constraints, or overhead constraints, and where the encoding strategy includes an erasure code approach, generating an encoded message using the encoding strategy, generating an encoded block, where the encoded block includes the encoded message and metadata associated with the message, and storing the encoded block in the data storage system. Example methods and apparatus may employ Reed Solomon erasure codes or Fountain erasure codes. Example methods and apparatus may display to a user the storage capacity and durability of the data storage system.

Claims

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.