Adaptive Erasure Codes

• US 20170033806A1
• Filed: 07/30/2015
• Published: 02/02/2017
• 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
• Granted Patent: US 10,044,374 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 storing data in a data storage system, the method comprising:

accessing a message, where the message has a message size;

selecting an encoding strategy that includes an erasure code approach, where the encoding strategy is selected as a function of the message size, of failure statistics associated with one or more data storage devices in the data storage system, of wear periods associated with one or more data storage devices in the data storage system, of space constraints associated with one or more data storage devices in the data storage system, or of overhead constraints associated with one or more data storage devices in the data storage system;

generating an encoded message from the message using the encoding strategy;

generating an encoded block that includes the encoded message and metadata associated with the message; and

storing the encoded block in the data storage system.

2. The non-transitory computer-readable storage medium of claim 1, where selecting the encoding strategy includes:

upon determining that the message size is less than a threshold size, selecting an algebraic erasure code approach; and

upon determining that the message size is equal to or greater than the threshold size, selecting a probabilistic erasure code approach.

3. The non-transitory computer-readable storage medium of claim 2, where the algebraic erasure code approach uses a Reed-Solomon (RS) code, and where the probabilistic erasure code approach uses a Fountain code.

4. The non-transitory computer-readable storage medium of claim 3, where the one or more data storage devices are susceptible to wear and have a life span.

5. The non-transitory computer-readable storage medium of claim 4, where the failure statistics associated with the one or more data storage devices include reliability indicators.

6. The non-transitory computer-readable storage medium of claim 5, the method comprising automatically adjusting the message size as a function of the reliability indicators.

7. The non-transitory computer-readable storage medium of claim 6, where the encoding strategy is selected as a function of the life span associated with members of the one or more data storage devices or the current age of members of the one or more data storage devices.

8. The non-transitory computer-readable storage medium of claim 7, where the one or more data storage devices include 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).

9. The non-transitory computer-readable storage medium of claim 8, the method comprising, updating the encoding strategy upon detecting that the reliability indicators are within a threshold value.

10. The non-transitory computer-readable storage medium of claim of 9, where updating the encoding strategy includes updating a file block size to be encoded, a number of coding segments generated from a message segment, a number of parity segments generated from the message segment, a storage strip size used by the data storage system, a packet size used by the data storage system, an internal buffer size of the one Of more data storage devices, or the erasure encoding approach.

11. The non-transitory computer-readable storage medium of claim 10, where the reliability indicators include self-monitoring, analysis, and reporting technology (SMART) indicators.

12. The non-transitory computer-readable storage medium of claim 11, the method comprising, upon detecting a change in available hardware capabilities within the data storage system, adapting the encoding strategy based, at least in part, on the change in available hardware capabilities, where adapting the encoding strategy includes employing single instruction multiple data (MID) processing, multi-threaded processing, or adapting the number of threads employed by the encoding strategy.

13. The non-transitory computer-readable storage medium of claim 12, where the metadata associated with the message includes a coding flag, a seed, a data identifier, processing information, or a cyclic redundancy check (CRC).

14. The non-transitory computer-readable storage medium of claim 13, the method comprising decoding the encoded block, where decoding the encoded block comprises controlling an RS code decoder, a Fountain code decoder, or a hybrid decoder, to decode the encoded block.

15. 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 message, where the message has a message size;

upon determining that the message size 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 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 zero;

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 zero;

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; and

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

16. The non-transitory computer-readable storage medium of claim 15, the method comprising decoding the message, where decoding the message includes controlling an RS code decoder, a Fountain code decoder, or a hybrid decoder to decode the encoded message.

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

18. The non-transitory computer-readable storage medium of claim 17, 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.

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

20. The non-transitory computer-readable storage medium of claim 19, 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.

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

22. The non-transitory computer-readable storage medium of claim 17, 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 precede rate r_p.

23. The non-transitory computer-readable storage medium of claim 21, the method comprising preceding the message.

24. The non-transitory computer-readable storage medium of claim 23, where preceding the message includes precoding the message with an RS precede, a multiple of RS precodes, or one RS precode and another code, in conjunction with an LT code stage.

25. The non-transitory computer-readable storage medium of claim 24, 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;

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

26. An apparatus for storing a message in a set of data storage devices, the apparatus comprising:

a processor;

a memory;

a set of logics; and

an interface that connects the processor, the memory, and the set of logics;

the set of logics comprising;

a monitoring logic that monitors a set of operating parameters associated with the set of data storage devices;

a strategy selection logic that selects an encoding strategy based on a property of the message or the set of operating parameters, where the encoding strategy includes an encoding technique;

an adaptation logic that adapts the encoding strategy as a function of the set of operating parameters;

an encoding logic that generates an encoded message by encoding the message using the encoding strategy; and

a storage logic that stores the encoded message in the distributed storage system.

27. The apparatus of claim 26, where the set of operating parameters includes data storage device failure statistics associated with members of the set of data storage devices, data storage device wear periods associated with members of the set of data storage devices, data storage space constraints associated with members of the set of data storage devices, hardware capabilities available for members of the set of data storage devices, overhead constraints associated with members of the set of data storage devices, data storage device life spans associated with members of the set of data storage devices, a data protection policy, or a property of the message.

28. The apparatus of claim 27, where the encoding technique includes a Reed-Solomon coding technique, a Fountain coding technique, a Raptor coding technique, or an XOR-block MDS coding technique.

29. The apparatus of claim 28, where the adaptation logic automatically dynamically adapts the encoding strategy by adjusting the encoding technique, a number of data units to be encoded, a number of coded units generated from the number of data units, a number of parity units generated from the number of data units, a word size associated with the encoding technique, a packet size associated with the encoding technique, a symbol size associated with the encoding technique, a buffer size of a member of the set of data storage devices, a decoder failure probability, a coding parameter for an online coding technique, a coding overhead for a Fountain coding technique, a degree of distribution for a Fountain coding technique, a precode rate for a Fountain coding technique, a level of hardware acceleration used by the encoding logic, or a level of hardware parallelism used by the encoding logic.

30. The apparatus of claim 29, the set of logics including a decoding logic that decodes the encoded message, where the decoding logic includes an RS code decoding logic, a Fountain code decoding logic, or a hybrid decoding logic.

31. The apparatus of claim 30, where the encoding logic generates an encoded message by encoding the message using the encoding strategy and by associating metadata with the encoded message, the metadata including a coding flag, a seed, a data ID, processing information, or a cyclic redundancy check (CRC).

32. The apparatus of claim 31, where the encoding logic, upon determining that the message is within a threshold size, precodes the message using an online code before generating the encoded message.