Granted Patent B2

US 10,809,928 · App. 15/613,012 · Granted Oct 20, 2020

Abstract

Claims (101)

1. A non-volatile memory system, comprising:

a non-volatile cache memory device to store a set of chunk reference signatures; and

a storage controller coupled to the non-volatile cache memory device and including one or more processors that execute instructions in one or more programs, causing the storage controller to perform operations comprising:

receiving a first data chunk including a first set of data blocks;

determining a first data chunk signature for the first data chunk;

comparing the first data chunk signature and the set of chunk reference signatures to determine a first match between the first data chunk signature and a first chunk reference signature from the set of chunk reference signatures;

responsive to determining the first match, identifying a first reference data chunk associated with the first chunk reference signature, the first reference data chunk including a first set of comparison blocks, wherein a comparison block in the first set of comparison blocks is a representation of a stored data block and is used to determine a match;

performing a deduplication technique on a subset of data blocks in the first set of data blocks that match one or more comparison blocks in the first set of comparison blocks, wherein a match between a data block and a comparison block is determined if at least 30% and less than 100% of fingerprints corresponding to the data block match fingerprints corresponding to the comparison block; and

identifying a second reference data chunk based on identifying the first reference data chunk.

2. The non-volatile memory system of claim 1 , wherein:

the second reference data chunk is a next sequential reference data chunk with respect to the first reference data chunk; and

identifying the second reference data chunk is based on the second reference data chunk being the next sequential reference data chunk with respect to the first reference data chunk.

3. The non-volatile memory system of claim 1 , wherein:

the second reference data chunk includes a second set of comparison blocks; and

the operations further comprise:

receiving a second data chunk including a second set of data blocks;

performing the deduplication technique on the second set of data blocks based on the second set of comparison blocks;

determining a deduplication ratio for the second set of data blocks; and

identifying a third reference data chunk based on the deduplication ratio.

4. The non-volatile memory system of claim 3 , wherein:

the third reference data chunk is identified responsive to the deduplication ratio being greater than a predetermined ratio; and

identifying the third reference data chunk comprises identifying a next sequential reference data chunk with respect to the second reference data chunk as the third reference data chunk.

5. The non-volatile memory system of claim 3 , wherein the operations further comprise:

responsive to the deduplication ratio being less than a predetermined ratio:

receiving a third data chunk;

determining a second data chunk signature for the third data chunk; and

comparing the second data chunk signature and the set of chunk reference signatures to determine a second match; and

wherein identifying the third reference data chunk comprises associating a second data chunk reference signature that matches the second data chunk signature with the third reference data chunk.

6. The non-volatile memory system of claim 1 , further comprising:

a non-volatile storage device coupled to the non-volatile cache memory device and the storage controller, wherein:

the non-volatile storage device comprises a primary database storing an active set of comparison blocks; and

the operations further comprise:

loading the active set of comparison blocks to the cache memory device; and

performing the deduplication technique on the first set of data blocks utilizing the active set of comparison blocks.

7. The non-volatile memory system of claim 6 , wherein:

the non-volatile storage device further comprises a first auxiliary database; and

the operations further comprise creating first candidate comparison blocks in the first auxiliary database for non-matched data blocks in the first set of data blocks via the deduplication technique.

8. The non-volatile memory system of claim 7 , wherein:

the non-volatile storage device further comprises a first set of global counters associated with the first candidate comparison blocks; and

the operations further comprise:

responsive to determining first matched data blocks in the first set of data blocks via the deduplication technique, incrementing first global counters in the first set of global counters for corresponding first candidate comparison blocks; and

responsive to a first counter associated with a first particular candidate comparison block exceeding a first predetermined threshold count, promoting the first particular candidate comparison block in the first auxiliary database to a comparison block in a buffer memory.

9. The non-volatile memory system of claim 8 , wherein:

the first candidate comparison blocks comprise respective second data signatures; and

the second data signatures are based on first fingerprints of the first candidate comparison blocks.

10. The non-volatile memory system of claim 9 , wherein the second data signatures are further based on second fingerprints of the first fingerprints.

11. The non-volatile memory system of claim 8 , wherein:

the non-volatile storage device further comprises:

a second auxiliary database storing a set of second candidate comparison blocks; and

a second set of global counters associated with second candidate comparison block signatures; and

the operations further comprise:

responsive to determining second matched data blocks in the first set of data blocks via the deduplication technique, incrementing second global counters in the second set of global counters for corresponding second candidate comparison blocks; and

responsive to a second counter associated with a second particular candidate comparison block exceeding a second predetermined threshold count, promoting the second particular candidate comparison block in the second auxiliary database to a first candidate comparison block in the first auxiliary database.

12. The non-volatile memory system of claim 11 , wherein the operations further comprise:

performing a first garbage collection technique on the buffer memory to delete a first predetermined quantity of candidate comparison blocks from the buffer memory to create space for promoted first candidate comparison blocks; and

performing a second garbage collection technique on the first auxiliary database to delete a second predetermined quantity of first candidate comparison blocks to create space in the first auxiliary database for promoted second candidate comparison blocks; and

wherein the first garbage collection technique and the second garbage collection technique create a multi-layer mechanism that provides an exponential increase in matching opportunity for the deduplication technique.

13. The non-volatile memory system of claim 1 , wherein the determining a first data chunk signature for the first data chunk comprises:

decomposing a data block of the first set of data blocks into one or more shingles; and

determining a hash value for at least one of the shingles, wherein the hash value acts as a fingerprint for the first data chunk signature.

14. A method, comprising:

storing, in a non-volatile cache memory device, a set of chunk reference signatures;

receiving a first data chunk including a first set of data blocks;

determining a first data chunk signature for the first data chunk;

comparing the first data chunk signature and the set of chunk reference signatures to determine a first match between the first data chunk signature and a first chunk reference signature;

responsive to determining the first match, selecting a first reference data chunk associated with the first chunk reference signature, the first reference data chunk including one or more comparison blocks, wherein a comparison block in the one or more comparison blocks is a representation of a stored data block and is used to determine a match;

performing a first instance of a deduplication technique on a subset of data blocks in the first set of data blocks that match the one or more comparison blocks in the first reference data chunk, wherein a match between a data block and a comparison block is determined when at least 30% and less than 100% of fingerprints corresponding to the data block match fingerprints corresponding to the comparison block;

anticipating a receipt of a first anticipated next sequential data chunk with respect to the first data chunk; and

selecting a first anticipated reference data chunk that is associated with the first anticipated next sequential data chunk.

15. The method of claim 14 , further comprising:

receiving the first anticipated next sequential data chunk; and

performing a second instance of the deduplication technique on the first anticipated next sequential data chunk utilizing the first anticipated reference data chunk.

16. The method of claim 15 , further comprising:

determining a deduplication ratio for the second instance of the deduplication technique, the deduplication ratio being greater than a predetermined ratio;

selecting a second anticipated reference data chunk that is associated with a second anticipated next sequential data chunk; and

performing a third instance of the deduplication technique on the second anticipated next sequential data chunk utilizing the second estimated reference data chunk.

17. The method of claim 15 , further comprising:

determining a deduplication ratio for the second instance of the deduplication technique, the deduplication ratio being less than a predetermined ratio;

receiving a second data chunk;

determining a second data chunk signature for the second data chunk;

comparing the second data chunk signature and the set of chunk reference signatures to determine a second match; and

responsive to the second match, selecting a second reference data chunk for use in a third instance of the deduplication technique.

18. A method, comprising:

storing a plurality of comparison blocks in a memory of a non-volatile storage device in association with a first plurality of reference blocks;

storing a plurality of first candidate comparison blocks in a first auxiliary database of the non-volatile storage device in association with a second plurality of reference blocks;

storing a plurality of second candidate comparison blocks in a second auxiliary database of the non-volatile storage device in association with a third plurality of reference blocks;

ordering the memory, the first auxiliary database, and the second auxiliary database hierarchically;

receiving a set of data blocks; and

performing a deduplication technique on a subset of data blocks in the set of data blocks that match one or more comparison blocks in the plurality of comparison blocks wherein a match between a data block and a comparison block is determined when at least 30% and less than 100% of fingerprints corresponding to the data block match fingerprints corresponding to the comparison block.

19. The method of claim 18 , further comprising:

identifying an active set of comparison blocks in the plurality of comparison blocks;

comparing first data signatures of the data blocks and second data signatures of the comparison blocks to determine matched data signatures and unmatched data signatures;

creating first reference blocks for first data blocks pointing to first stored data blocks corresponding to the matched data signatures;

incrementing counters associated with comparison blocks in the active set of comparison blocks having the matched data signatures;

storing second data blocks corresponding to the unmatched data signatures; and

creating a set of second candidate comparison blocks in the second auxiliary database corresponding to the stored second data blocks.

20. The method of claim 19 , further comprising:

responsive to a counter associated with a second candidate comparison block in the set of second candidate comparison blocks exceeding a predetermined quantity, promoting the second candidate comparison block to a set of first candidate comparison blocks in the first auxiliary database.

21. The method of claim 20 , wherein creating the set of second candidate comparison blocks comprises:

generating first fingerprints for the second candidate comparison blocks of the set; and

generating second fingerprints for the first fingerprints as fingerprints of fingerprints (FOFs), the second data signatures including the FOFs, and the FOFs being utilized for comparing the second data signatures and the first data signatures to determine the matched data signatures and unmatched data signatures.

Assignments (10)