Aggressive data deduplication using lazy garbage collection

• US 9,940,234 B2
• Filed: 03/26/2015
• Issued: 04/10/2018
• Est. Priority Date: 03/26/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Davis, John D.
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/670,288
• Publication Number:
  US 20160283372A1
• Time in Patent Office: 1,111 Days
• Field of Search: 707692
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method for extending data lifetime for reference in deduplication is provided. The method includes determining that a quantity of user data has at least a threshold amount of data that is re-created in a storage system. The method includes protecting at least portions of the quantity of user data from erasure by garbage collection in the storage system during a predetermined time interval, wherein the protected at least portions are available for data deduplication of further user data in the storage system during the predetermined time interval.

Claims

1. A method for extending reference data lifetime in deduplication, comprising:

determining that a quantity of user data has at least a threshold amount of data that is re-created in a storage system;

protecting at least portions of the quantity of user data from erasure by garbage collection in the storage system during a predetermined time interval, wherein the protected at least portions are available for deduplication of further user data in the storage system during the predetermined time interval; and

performing garbage collection, which includes erasing portions of storage memory of the storage system, corresponding to files that the storage system considers no longer in existence, except where metadata prevents the erasure during the garbage collection.

2. The method of claim 1, wherein the determining comprises:

forming a data structure, over one or more sampling windows of time, of data of the storage system, the data structure indicating amounts of the data of files or blocks in the storage system having hash function results matching hash function results of at least one other file or block seen during the one or more sampling windows of time.

3. The method of claim 1, wherein the protecting is based on metadata that includes an aging parameter for each of the at least portions of the quantity of user data, and further comprising:

setting the aging parameter for one of the at least portions of the quantity of user data to a first value, responsive to determining the one of the at least portions matches a fingerprint result of a file or block seen during a sampling window of time, wherein the first value indicates to not erase during garbage collection; and

adjusting the aging parameter for a further one of the at least portions of the quantity of user data to a second value, responsive to determining the further one of the at least portions has a fingerprint result unmatched by files or blocks seen during the sampling window of time, wherein the second value indicates to erase during garbage collection.

4. The method of claim 1, further comprising:

performing garbage collection, which includes erasing a plurality of fingerprints not matched in at least one deduplication operation, except where a fingerprint, corresponding to one of the at least portions of the quantity of user data is protected from erasure.

5. The method of claim 1, wherein the determining is on a basis of a file, a file type, a block or a range of blocks, and wherein the threshold amount of data is one or more times as much as a data chunk corresponding to a fingerprint or a hash function result.

6. The method of claim 1, further comprising:

establishing in metadata that at least portions of the quantity of user data are to have erasure immunity in the storage system for the predetermined time interval; and

writing to a table in the storage system, regarding how often incoming data to the storage system re-creates a same data or includes greater than the threshold amount of data that is re-created.

7. A deduplication method comprising:

identifying user data having at least a threshold amount of data that is re-created, by one or more applications;

writing an indicator to metadata associated with the identified user data, wherein the indicator establishes a time interval of erasure immunity;

preventing at least portions of the user data from being erased during garbage collection, during the time interval in accordance with the indicator, wherein the at least portions of the identified user data are kept available during the time interval of erasure immunity as reference data for deduplication of further data;

generating a histogram tracking re-creation of files or blocks over one or more sampling windows of time; and

adjusting a value of the threshold amount based on the histogram.

8. The method of claim 7, further comprising:

setting an aging parameter of the indicator in metadata at a start of the time interval; and

adjusting the aging parameter towards allowance of erasure, responsive to one of completing a cycle of garbage collection or a passage of time.

9. The method of claim 7, further comprising:

tracking one of file creation, file deletion, block creation, block deletion, object creation, object deletion or frequency of re-creation of data, in a metadata table; and

adjusting the time interval based on the tracking.

10. The method of claim 7, further comprising:

adjusting a value of the threshold amount, based on utilization of storage capacity of the storage system.

11. The method of claim 7, further comprising:

performing garbage collection, to erase portions of storage memory of the storage system except where the indicator establishes the time interval of erasure immunity for the at least portions of the identified user data.

12. A storage system, comprising:

storage memory;

at least one processor of the storage system, configured to write an indicator to metadata of the storage system, the indicator protecting at least portions of user data from erasure during garbage collection, for a time interval, responsive to the at least one processor identifying the user data as having at least a threshold amount of data that is re-created on a periodic basis, wherein the at least portions of the user data associated with the indicator are available during the time interval as a reference for deduplication, and wherein the at least one processor is configured to execute a garbage collection process, which includes erasing portions of storage memory of the storage system, corresponding to files that the storage system considers no longer in existence, except where metadata prevents the erasure during the garbage collection.

13. The storage system of claim 12, further comprising:

the at least one processor configured to generate a data structure of user data over time, the data structure indicating at least one of;

frequency of re-creation of data or amount of re-created data, wherein the identifying is based on the data structure.

14. The storage system of claim 12, further comprising:

the at least one processor configured to monitor amount of storage capacity of the storage memory utilized and to adjust the time interval or a value of the threshold amount based on the amount of storage capacity utilized.

15. The storage system of claim 12, further comprising:

the indicator including an aging parameter;

the at least one processor configured to adjust the aging parameter towards a first value, responsive to the identifying, wherein the first value prevents the erasure during garbage collection; and

the at least one processor configured to adjust the aging parameter towards a second value, responsive to one of passage of time or completion of a garbage collection cycle, wherein the second value allows the erasure during garbage collection.

16. The storage system of claim 12, further comprising:

the at least one processor configured to perform in-line deduplication on data arriving for storage in the storage memory, with reference to the at least portions of the user data associated with the indicator.

17. The storage system of claim 12, further comprising:

the at least one processor configured to perform post-process deduplication on data stored in the storage memory, with reference to the at least portions of the user data associated with the indicator.

18. The storage system of claim 12, further comprising:

the at least one processor configured to perform a hash function on data arriving for storage in the storage memory or data stored in the storage memory, wherein the identifying is based on results of the hash function.