Managing data in a storage system

• US 10,282,127 B2
• Filed: 04/20/2017
• Issued: 05/07/2019
• Est. Priority Date: 04/20/2017
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Battaje, Ajith Kumar, Goel, Tanay, Manchanda, Saurabh, Sharma, Sandeep
• Primary Examiner(s): Bataille, Pierre Miche
• Application Number:
  US15/492,221
• Publication Number:
  US 20180307432A1
• Time in Patent Office: 747 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Various aspects for managing data blocks in a storage system are provided. For instance, a method may include storing, in a buffer memory device, a comparison block library, selecting a first set of comparison blocks in the comparison block library to create an active set of comparison blocks, and utilizing the active set in conjunction with a data deduplication technique. A method may further include determining an occurrence of a predetermined event in the data deduplication technique, selecting a second set of comparison blocks in the comparison block library to create a new active set of comparison blocks in response to the predetermined event, replacing the active set with the new active set, and utilizing the new active set in conjunction with the data deduplication technique.

Claims

1. A method of operation for managing data blocks, comprising:

storing, in a non-volatile cache memory device, a comparison block library;

selecting a first set of comparison blocks in the comparison block library to create an active set of comparison blocks;

utilizing the active set in conjunction with a data deduplication technique;

determining an occurrence of a predetermined event in the data deduplication technique;

selecting a second set of comparison blocks in the comparison block library to create a new active set of comparison blocks in response to the predetermined event;

replacing the active set with the new active set;

storing a passive set of comparison blocks based on the active set that is replaced with the new active set; and

utilizing the new active set in conjunction with the data deduplication technique.

2. The method of claim 1, further comprising one of:

selecting at least one comparison block in the active set for inclusion in the new active set;

selecting at least one comparison block in the comparison block library not in the active set for inclusion in the new active set; and

selecting at least one comparison block in the active set for inclusion in the new active set and at least one comparison block in the comparison block library not in the active set for inclusion in the new active set.

3. The method of claim 1, further comprising:

storing, in an auxiliary database, candidate comparison blocks;

receiving a data block for storage;

comparing the data block and comparison blocks in the non-volatile cache memory device for a match;

comparing the data block and the candidate comparison blocks in the auxiliary database for a match; and

responsive to the data block not matching any of the comparison blocks in the non-volatile cache memory device and not matching any of the candidate comparison blocks in the auxiliary database, adding the data block to the candidate comparison blocks in the auxiliary database.

4. The method of claim 3, further comprising:

responsive to the data block not matching any of the comparison blocks in the non-volatile cache memory device and matching a candidate comparison block in the auxiliary database, incrementing a counter associated with the candidate comparison block; and

responsive to the counter reaching a predetermined threshold count, promoting the candidate comparison block to a reference block in the non-volatile cache memory device.

5. The method of claim 4, wherein:

a match is determined responsive to data in the data block matching at least a relative percentage of data in a comparison block or a candidate comparison block; and

a non-match is determined responsive to data in the data block matching less than the relative percentage of data in a comparison block or a candidate comparison block.

6. The method of claim 1, further comprising:

removing one or more comparison blocks from the comparison block library responsive to the one or more comparison blocks being no longer representative of a data block in the non-volatile memory system.

7. A system, comprising:

a non-volatile cache memory device to store a comparison block library;

means for calculating scores for comparison blocks in the comparison block library;

means for selecting a first set of comparison blocks in the comparison block library to create an active set of comparison blocks;

means for utilizing the active set in conjunction with a data deduplication technique;

means for determining an occurrence of a predetermined event in the data deduplication technique;

means for selecting a second set of comparison blocks in the comparison block library to create a new active set of comparison blocks in response the predetermined event;

means for replacing the active set with the new active set; and

means for utilizing the new active set in conjunction with the data deduplication technique.

8. The system of claim 7, further comprising one of:

means for selecting at least one comparison block in the active set for inclusion in the new active set;

means for selecting at least one comparison block in the comparison block library not in the active set for inclusion in the new active set; and

means for selecting at least one comparison block in the active set for inclusion in the new active set and at least one comparison block in the comparison block library not in the active set for inclusion in the new active set.

9. A non-volatile memory system, comprising:

a non-volatile cache memory device including a buffer memory to store a comparison block library; and

a storage controller coupled to the non-volatile cache memory device, the storage controller configured to;

calculate scores for comparison blocks in the comparison block library;

select a first set of comparison blocks in the comparison block library to create an active set of comparison blocks, wherein the first set of comparison blocks is selected based on the scores of the comparison blocks;

utilize the active set in conjunction with a data deduplication technique;

determine an occurrence of a predetermined event in the data deduplication technique;

select a second set of comparison blocks in the comparison block library to create a new active set of comparison blocks in response to the predetermined event, wherein the second set of comparison blocks is selected based on the scores of the comparison blocks;

replace the active set with the new active set; and

utilize the new active set in conjunction with the data deduplication technique.

10. The non-volatile memory system of claim 9, wherein the storage controller is further configured to store a passive set of comparison blocks based on the active set that is replaced with the new active set.

11. The non-volatile memory system of claim 9, wherein selecting the second set further comprises carrying over at least one comparison block in the first set for inclusion in the second set.

12. The non-volatile memory system of claim 11, wherein selecting the second set further comprises selecting at least one comparison block not included in the first set for inclusion in the second set.

13. The non-volatile memory system of claim 9, wherein selecting the second set further comprises dropping at least one comparison block in the first set from inclusion in the second set.

14. The non-volatile memory system of claim 9, wherein calculating the scores for the comparison blocks further comprises calculating each of the scores based on at least one of a logical block count (LBN) factor, a recent-lookup factor, and a deduplication ratio factor.

15. The non-volatile memory system of claim 14, wherein calculating the scores for the comparison blocks further comprises providing a weighting factor to at least one of the LBN factor, the recent look-up factor, and the deduplication ratio factor.

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

the non-volatile cache memory device further includes an auxiliary memory to store candidate comparison blocks; and

the storage controller is further configured to;

receive a data block for storage;

compare the data block to comparison blocks in the buffer memory for a match;

compare the data block to the candidate comparison blocks in the auxiliary memory for a match; and

responsive to the data block not matching any of the comparison blocks in the buffer memory and not matching any of the candidate comparison blocks in the auxiliary memory, add the data block to the candidate comparison blocks in the auxiliary memory.

17. The non-volatile memory system of claim 16, wherein the storage controller is further configured to determine a match responsive to data in the data block matching at least a predetermined percentage of data in any comparison block or any candidate comparison block.

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

the non-volatile cache memory device further includes an auxiliary memory to store candidate comparison blocks; and

the storage controller is further configured to;

receive a data block for storage;

compare the data block and the candidate comparison blocks in the auxiliary memory for a match; and

responsive to the data block not matching any of the comparison blocks in the buffer memory but matching a candidate comparison block in the auxiliary memory, increment a counter associated with the candidate comparison block.

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

the non-volatile cache memory device further includes an auxiliary memory to store candidate comparison blocks; and

the storage controller is further configured to, responsive to a counter associated with a candidate comparison block exceeding a predetermined threshold count, promote the candidate comparison block in the auxiliary memory to a comparison block in the buffer memory.

20. The non-volatile memory system of claim 9, wherein the storage controller is further configured to, responsive to a comparison block being no longer representative of a data block in the non-volatile memory system, remove the comparison block from the comparison block library.