Efficient management of reference blocks used in data deduplication

• US 10,503,608 B2
• Filed: 07/24/2017
• Issued: 12/10/2019
• Est. Priority Date: 07/24/2017
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Battaje, Ajith Kumar, Goel, Tanay, Manchanda, Saurabh, Sharma, Sandeep
• Primary Examiner(s): Matin, Tasnima
• Application Number:
  US15/657,224
• Publication Number:
  US 20190026191A1
• Time in Patent Office: 869 Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0671 In-line storage system
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Various aspects for managing data blocks in a storage system are provided. For instance, a method may include storing, in a buffer memory, a plurality of comparison blocks, initiating a data deduplication process utilizing the plurality of comparison blocks, and performing garbage collection in conjunction with the data deduplication process. Garbage collection may include maintaining a hit count for comparison blocks of a passive set of comparison blocks in the buffer memory and deleting the passive set from the buffer memory when the hit count is decremented to a predetermined value. The hit count may be incremented and decremented based on utilization of a comparison block in the data deduplication process.

Claims

1. A data storage system, comprising:

a non-volatile cache memory device including a buffer memory storing a plurality of comparison blocks; and

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

initialize a data deduplication process utilizing the plurality of comparison blocks stored in the non-volatile cache memory device, and

perform garbage collection in conjunction with the data deduplication process, wherein to perform the garbage collection, the processor is further configured to;

maintain a hit count for comparison blocks of a passive set of comparison blocks in the buffer memory by incrementing or decrementing the hit count based on utilization of a comparison block in the data deduplication process, wherein the hit count is indicative of whether data in the comparison block matches data in an incoming user data block, and

delete the passive set from the buffer memory responsive to the hit count satisfying a predetermined value.

2. The data storage system of claim 1, wherein to perform the garbage collection, the processor is further configured to:

delete a comparison block with a zero hit count from the passive set prior to deletion of the passive set.

3. The data storage system of claim 2, wherein to perform the garbage collection, the processor is further configured to:

delete a comparison block with a zero hit count from the passive set responsive to no user data blocks being represented by the comparison block.

4. The data storage system of claim 1, wherein:

the passive set is deleted from the buffer memory responsive to the hit count being decremented to the predetermined value;

the hit count is incremented responsive to data in the comparison block matching data in an incoming user data block; and

the hit count is decremented responsive to a user data block associated with the comparison block no longer having a reference block referring to the user data block.

5. The data storage system of claim 4, wherein the user data block no longer has the reference block referring to the user data block upon an occurrence of one of:

the user data block is overwritten with new data; and

the user data block is deleted from the data storage system.

6. The data storage system of claim 1, further comprising a non-volatile memory device storing a plurality of management units coupled to the storage controller, wherein:

a user data block and one or more reference blocks referring to the user data block are stored in a same management unit from the plurality of management units.

7. The data storage system of claim 6, wherein to perform the garbage collection, the processor is further configured to:

track a quantity of valid user data blocks in the management units;

select a management unit from the plurality of management units for release based on the tracked quantity of valid user data blocks;

relocate one or more valid user data blocks in the selected management unit to a different management unit in the plurality of management units; and

release the selected management unit in association with performing the garbage collection.

8. The data storage system of claim 7, wherein the processor is further configured to:

determine a management unit from the plurality of management units with a least quantity of valid user data blocks; and

select the management unit with the least quantity of valid user data blocks for release.

9. The data storage system of claim 7, wherein to relocate the one or more valid user data blocks, the processor is further configured to:

preserve a spatial proximity between two or more valid user data blocks including substantially similar data responsive to the two or more valid user data blocks being relocated to the different management unit.

10. The data storage system of claim 7, wherein to relocate the one or more valid user data blocks, the processor is further configured to relocate a valid user data block utilizing one or more of:

a moved-compressed relocation technique;

a compression-as-part-of-relocation technique; and

a re-encode relocation technique.

11. The data storage system of claim 10, wherein the valid user data block is relocated utilizing the re-encode relocation technique, and the re-encode relocation technique utilizes one or more of:

a data recompression technique utilizing a different algorithm; and

a data recompression technique utilizing one or more additional user data blocks.

12. The data storage system of claim 6, wherein to perform the garbage collection, the processor is further configured to:

throttle a forced garbage collection on the buffer memory responsive to a local garbage collection being performed on the non-volatile memory device.

13. The data storage system of claim 12, wherein to perform the garbage collection, the processor is further configured to:

un-throttle the forced garbage collection responsive to the local garbage collection not being performed on the non-volatile memory device.

14. The data storage system of claim 1, wherein each of the plurality of comparison blocks is a representation of a user data block stored in the data storage system and is utilized in the data deduplication process for comparison to incoming user data blocks for determining a match.

15. The data storage system of claim 14, wherein each of the plurality of comparison blocks is a hash value of a corresponding user data block stored in the data storage system.

16. The data storage system of claim 1, wherein to perform the garbage collection, the processor is further configured to:

throttle a forced garbage collection on the buffer memory responsive to a local garbage collection being performed on the non-volatile memory device.

17. A method of operation in a data storage system including a set of non-volatile memory devices, the method comprising:

storing, in a buffer memory, a plurality of comparison blocks;

initializing a data deduplication process utilizing the plurality of comparison blocks stored in the buffer memory; and

performing garbage collection in conjunction with the data deduplication process, the garbage collection comprising;

maintaining a hit count for comparison blocks of a passive set of comparison blocks in the buffer memory by incrementing or decrementing the hit count based on utilization of a comparison block in the data deduplication process, wherein the hit count is indicative of whether data in the comparison block matches data in an incoming user data block, and

deleting the passive set from the buffer memory responsive to the hit count satisfying a predetermined value.

18. The method of claim 17, further comprising:

storing, in a non-volatile memory device coupled to the buffer memory, a plurality of management units, wherein;

the data deduplication process comprises storing a user data block and one or more reference blocks referring to the user data block in a same management unit, and

the garbage collection further comprises;

tracking a quantity of valid user data blocks in one or more management units,

selecting one or more management units from the plurality of management units for release based on the quantity of valid user data blocks,

relocating one or more valid user data blocks in one or more of the selected management units to a different management unit in the plurality of management units, and

releasing one or more of the selected management units in association with performing the garbage collection.

19. The method of claim 18, further comprising:

throttling performance of a forced garbage collection on the buffer memory responsive to a local garbage collection being performed on the non-volatile memory device; and

un-throttling performance of the forced garbage collection responsive to the local garbage collection not being performed on the non-volatile memory device.

20. The method of claim 17, further comprising:

throttling performance of a forced garbage collection on the buffer memory responsive to a local garbage collection being performed on the non-volatile memory device.