Joint de-duplication-erasure coded distributed storage

• US 10,853,187 B2
• Filed: 02/26/2019
• Issued: 12/01/2020
• Est. Priority Date: 07/15/2016
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Arslan, Suayb S., Goker, Turguy, Wideman, Roderick B.
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): Gandhi, Dipakkumar B
• Application Number:
  US16/285,320
• Publication Number:
  US 20190188087A1
• Time in Patent Office: 644 Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1177 Regular LDPC codes with parity-check matrices wherein all rows and columns have the same row weight and column weight, respectively
• 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 and apparatus deduplicate and erasure code a message in a data storage system. One example apparatus includes a first chunking circuit that generates a set of data chunks from a message, an outer precoding circuit that generates a set of precoded data chunks and a set of parity symbols from the set of data chunks, a second chunking circuit that generates a set of chunked parity symbols from the set of parity symbols, a deduplication circuit that generates a set of deduplicated data chunks by deduplicating the set of precoded chunks or the set of chunked parity symbols, an unequal error protection (UEP) circuit that generates an encoded message from the set of deduplicated data chunks, and a storage circuit that controls the data storage system to store the set of deduplicated data chunks, the set of parity symbols, or the encoded message.

Claims

1. 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 deduplicating and erasure coding a message, the method comprising:

accessing the message,

generating a set of message chunks by chunking the message using a first chunking approach;

generating a set of outer-precoded parity symbols and a set of outer-precoded data symbols from the set of message chunks using an outer precode, where the outer precode is a low density parity check (LDPC) precode that uses an LDPC parity check matrix, where the LDPC parity check matrix has a column weight and a row weight;

selectively adapting the LDPC parity check matrix by;

computing a set of chunk statistics associated with a first set of erasure codes;

generating a worst-case (WC) symbol characterization for a member of the first set of erasure codes based, at least in part, on a WC average number of symbol erasures or a WC average number of symbol errors;

computing an average number of symbol errors for the first set of erasure codes based, at least in part, on a set of deduplication parameters, the set of chunk statistics, and the worst-case symbol characterization;

choosing a column weight or a row weight such that a failure probability Pf is less than a decoding threshold;

upon determining that there has been a change in a chunk pool;

generating a new LDPC parity check matrix based, at least in part, on the column weight and the row weight; and

replacing the LDPC parity check matrix with the new LDPC parity check matrix;

storing the set of outer-precoded parity symbols in a data storage system;

generating a set of unique data symbols by deduplicating the set of outer-precoded data symbols based, at least in part, on a chunk identification (ID) table;

storing a copy of the set of unique data symbols in the data storage system;

generating a set of inner-precoded data symbols from the set of unique data symbols using an inner-precode;

generating the first set of erasure codes from the set of inner-precoded data symbols; and

storing the first set of erasure codes in the data storage system.

2. The non-transitory computer-readable storage device of claim 1, where the chunk ID table stores a unique chunk ID associated with a unique data symbol stored in the data storage system, a chunk size associated with the unique data symbol, or a chunk reference count associated with the unique chunk ID, and where the chunk ID table is stored in a data storage device with a faster access time than the data storage system.

3. The non-transitory computer-readable storage device of claim 2, where the unique chunk ID is generated using a weak hash function.

4. The non-transitory computer-readable storage device of claim 2, where the unique chunk ID is a 16 bit cyclic redundancy check (CRC).

5. The non-transitory computer-readable storage device of claim 1, where the generating the first set of erasure codes comprises generating the first set of erasure codes using an unequal error protection (UEP) rateless Luby transform (LT) code based, at least in part, on the chunk ID table.

6. The non-transitory computer-readable storage device of claim 5, where generating the first set of erasure codes from the set of inner-precoded data symbols using the UEP LT code comprises generating a concatenated subset of inner-precoded data symbols by concatenating a subset of the set of inner-precoded data symbols, where a size of the subset of the set of inner-precoded data symbols is based, at least in part, on a data protection policy.

7. The non-transitory computer-readable storage device of claim 6, where generating the first set of erasure codes from the set of inner-precoded data symbols using the UEP LT code includes assigning a protection level to a member of the first set of erasure codes, where the protection level is based on a chunk size or a chunk reference count stored in the chunk ID table.

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

generating a set of chunked outer-precoded parity symbols by chunking the set of outer-precoded parity symbols using a second chunking approach;

generating a set of unique parity symbols by deduplicating the set of chunked outer-precoded parity symbols based, at least in part, on the chunk ID table; and

storing the set of unique parity symbols in the data storage system.

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

generating a second set of erasure codes from the set of unique parity symbols using the UEP LT code based, at least in part, on the chunk ID table; and

storing the second set of erasure codes in the data storage system.

10. The non-transitory computer-readable storage device of claim 9, the method further comprising storing the copy of the set of unique data symbols, the first set of erasure codes, the set of unique parity symbols, or the second set of erasure codes, in a buffer.

11. The non-transitory computer-readable storage device of claim 8, where the second chunking approach is different than the first chunking approach.

12. The non-transitory computer-readable storage device of claim 1, where the set of outer-precoded parity symbols comprises a subset of outer-precoded parity symbols that is distinct from the set of outer-precoded data symbols.

13. The non-transitory computer-readable storage device of claim 1, where the column weight is three and the row weight is 47.

14. The non-transitory computer-readable storage device of claim 1, where the outer precode comprises a cyclic redundancy check (CRC) code.

15. The non-transitory computer-readable storage device of claim 1, the method further comprising generating a reconstructed message by decoding the first set of erasure codes.

16. The non-transitory computer-readable storage device of claim 15, where generating the reconstructed message includes performing a CRC on a decoded member of the first set of erasure codes.

17. The non-transitory computer-readable storage device of claim 1, where the first chunking approach is a variable length chunking approach, or a two-thresholds two divisors chunking approach.

18. An apparatus for deduplicating and erasure coding a message, the apparatus comprising:

a processor;

a data storage system;

a memory that stores a chunk index (ID) table;

a set of circuits; and

an interface that connects the processor, the memory, the data storage system, and the set of circuits, the set of circuits comprising;

a first chunking circuit that generates a set of data chunks from the message using a variable length chunking approach;

an outer precoding circuit that generates a set of precoded data chunks and a set of parity symbols from the set of data chunks using a low density parity check (LDPC) code that uses an LDPC parity check matrix, where the LDPC parity check matrix has a column weight and a row weight, where the outer precoding circuit selectively adapts the LDPC parity check matrix by;

computing a set of chunk statistics associated with a first set of erasure codes;

generating a worst-case (WC) symbol characterization for a member of the first set of erasure codes based, at least in part, on a WC average number of symbol erasures or a WC average number of symbol errors;

computing an average number of symbol errors for the first set of erasure codes based, at least in part, on a set of deduplication parameters, the set of chunk statistics, and the worst-case symbol characterization;

choosing a column weight or a row weight such that a failure probability Pf is less than a decoding threshold;

upon determining that there has been a change in a chunk pool, the outer precoding circuit is further configured to;

generate a new LDPC parity check matrix based, at least in part, on the column weight and the row weight; and

replace the LDPC parity check matrix with the new LDPC parity check matrix;

a second chunking circuit that generates a set of chunked parity symbols from the set of parity symbols using the variable length chunking approach;

a deduplication circuit that generates a set of unique deduplicated data chunks by deduplicating the set of precoded chunks or the set of chunked parity symbols based, at least in part, on the chunk ID table;

an unequal erasure protection (UEP) circuit that generates an encoded message from the set of deduplicated data chunks; and

a storage circuit that controls the data storage system to store the set of deduplicated data chunks, the set of parity symbols, or the encoded message in the data storage system.

19. The apparatus of claim 18, where the first chunking circuit and the second chunking circuit use a weak hash based variable length chunking approach or a two-thresholds, two-divisors chunking approach.

20. The apparatus of claim 18, where the first chunking circuit uses a first chunking approach, and the second chunking circuit uses a second, different chunking approach.

21. The apparatus of claim 18, where the chunk ID table stores a chunk ID associated with a unique data chunk stored in the data storage system, a reference count associated with the chunk ID associated with the unique data chunk, or a chunk size associated with the chunk associated with the chunk ID.

22. The apparatus of claim 21, where the LDPC code uses an LDPC parity check matrix, where the outer precoding circuit selectively adapts the LDPC parity check matrix as a function of a worst case average number of symbol erasures, a worst case average number of symbol errors, a length of a chunk ID, a change in the set of deduplicated data chunks, a change in the set of parity symbols, or a change in the set of erasure codes stored in the data storage system.

23. The apparatus of claim 18, where the UEP circuit generates the encoded message using an inner precode and a Luby transform (LT) base code, where a level of erasure protection provided by the UEP circuit is based on a chunk size or a chunk reference count stored in the chunk ID table.

24. The apparatus of claim 23, where the UEP circuit selectively dynamically adapts the level of erasure protection provided by the UEP circuit by adjusting the LT base code, a number of deduplicated data chunks to be encoded, a number of coded units generated from the number of deduplicated data chunks, a number of parity units generated from the number of deduplicated data chunks, a word size associated with the LT base code, a packet size associated with the LT base code, a symbol size associated with the LT base code, a buffer size of a member of the data storage system, a decoder failure probability, a coding parameter for an online coding technique, a coding overhead for a Fountain coding technique, a degree distribution for a Fountain coding technique, a precode rate for a Fountain coding technique, a level of hardware acceleration used by the UEP circuit, or a level of hardware parallelism used by the UEP circuit.

25. The apparatus of claim 18, where the storage circuit controls the data storage system to store the set of deduplicated data chunks in a first buffer, and the set of parity symbols or the encoded message in a second, different buffer.

26. The apparatus of claim 18, where the set of circuits further comprises a decoding circuit that reconstructs the message based on the set of deduplicated data chunks, the set of parity symbols, or the encoded message.

27. A method comprising:

accessing a data set;

generating a chunked data set by chunking the data set;

generating an outer precoded chunked data set and a set of parity symbols by precoding the chunked data set using an outer precode, where the outer precode is a low density parity check (LDPC) precode that uses an LDPC parity check matrix, where the LDPC parity check matrix has a column weight and a row weight;

selectively adapting the LDPC parity check matrix by;

computing a set of chunk statistics associated with an erasure coded unique data set;

generating a worst-case (WC) symbol characterization for a member of the erasure coded unique data set, at least in part, on a WC average number of symbol erasures or a WC average number of symbol errors;

computing an average number of symbol errors for the erasure coded unique data set based, at least in part, on a set of deduplication parameters, the set of chunk statistics, and the worst-case symbol characterization;

choosing a column weight or a row weight such that a failure probability Pf is less than a decoding threshold;

upon determining that there has been a change in a chunk pool;

generating a new LDPC parity check matrix based, at least in part, on the column weight and the row weight; and

replacing the LDPC parity check matrix with the new LDPC parity check matrix;

storing the set of parity symbols in a cloud-based data storage system;

generating a set of unique data chunks by deduplicating the outer precoded chunked data set;

storing the set of unique data chunks in the cloud-based data storage system;

generating an inner precoded unique data set by precoding the set of unique data chunks with an inner precode;

generating the erasure coded unique data set by erasure coding the inner precoded unique data set; and

distributing the erasure coded unique data set across the cloud-based data storage system.