Joint de-duplication-erasure coded distributed storage

• US 10,318,389 B2
• Filed: 07/15/2016
• Issued: 06/11/2019
• 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:
  US15/211,208
• Publication Number:
  US 20180018235A1
• Time in Patent Office: 1,061 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, 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, where the chunk ID table is stored in a data storage device with a faster access time than the data storage system;

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 using an unequal error protection (UEP) rateless Luby transform (LT) code based, at least in part, on the chunk ID table; 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 unique chunk ID is generated using a weak hash function.

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

4. 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.

5. The non-transitory computer-readable storage device of claim 1, 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.

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 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.

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

8. The non-transitory computer-readable storage device of claim 1, 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 outer precode comprises a cyclic redundancy check (CRC) code.

13. 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.

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

15. 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.