Background deduplication of data sets in a memory

• US 8,930,612 B2
• Filed: 05/31/2012
• Issued: 01/06/2015
• Est. Priority Date: 05/31/2012
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Goss, Ryan James, Gaertner, Mark Allen, Seekins, David Scott
• Primary Examiner(s): Blair, April Y
• Assistant Examiner(s): KWONG, EDMUND H
• Application Number:
  US13/485,455
• Publication Number:
  US 20130326115A1
• Time in Patent Office: 950 Days
• Field of Search: 711/163, 711/103, 711/154, 707/747, 707/161, 707/162
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• 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/0688 Non-volatile semiconductor memory arrays

Abstract

Apparatus and method for data management in a memory, such as but not limited to a flash memory array. In accordance with some embodiments, a plurality of data sets in a memory are identified as having a common data content and different physical addresses in the memory. A selected one of the data sets is marked as valid data and the remaining data sets are marked as stale data responsive to evaluation of at least one variable parameter associated with the physical addresses at which the data sets are respectively stored.

Claims

1. A method comprising:

storing a plurality of data sets in a memory at different physical locations, each physical location having an associated physical address;

determining that a first data set and a second data set from the plurality of data sets share a common data content using respective first and second hash values;

comparing a first total number of write/erase cycles that have been applied to the first physical address to a second total number of write/erase cycles that have been applied to the second physical address;

and

marking a selected one of the first or second data sets as valid data and the remaining one of the first or second data sets as stale data responsive to the comparison of the respective first and second total numbers of write/erase cycles.

2. The method of claim 1, further comprising retaining the selected one of the first or second data sets marked as valid data in the memory at the associated physical location and jettisoning the remaining one of the first or second data sets from the memory.

3. The method of claim 1, in which the memory is characterized as a flash memory array comprising a plurality of garbage collection units (GCUs) each erased and reallocated as a unit, the first data set stored in a first GCU and the second data set stored in a different, second GCU.

4. The method of claim 1, in which each of the first and second data sets has a different logical address.

5. The method of claim 1, in which the first and second data sets are identified as respective first and second cold data sets.

6. The method of claim 1, wherein the first and second cold data sets are selected from a predetermined percentage of the plurality of data sets that have received a fewest number of access operations during the elapsed time interval.

7. The method of claim 1, further comprising scheduling a garbage collection operation to jettison the stale data from the array.

8. An apparatus comprising a memory in which a plurality of data blocks are stored at different physical locations therein, and a deduplication processor configured to identify first and second data blocks in the memory having a common data content, to compare a first variable parameter associated with the physical location of the first data block to a second variable parameter associated with the physical location of the second data block, and to select one of the first or second data blocks for retention in the memory and to select the remaining one of the first or second data blocks for jettisoning from the memory responsive to the comparison of the at least one variable parameter for each physical location, the first variable parameter comprising a total number of erasure cycles applied to the first physical location, the second variable parameter comprising a total number of erasure cycles applied to the second physical location.

9. The apparatus of claim 8, in which the deduplication processor comprises a hash generator which generates respective first and second hash values responsive to the data content of the first and second data blocks, and a comparison circuit which compares the first and second hash values to identify the first and second data blocks as duplicate blocks.

10. The apparatus of claim 8, in which the deduplication processor further comprises a parametric evaluation module which generates each of the first and second variable parameters as a composite state value derived in relation to the total number of erasure cycles for the associated physical location and in relation to a measured temperature at the time of writing of the respective first and second data blocks to the respective first and second physical locations.

11. The apparatus of claim 8, in which the deduplication processor comprises a selection module which selects a population of data blocks for evaluation responsive to access rates associated with the data blocks, the selected population characterized as a predetermined percentage of the data blocks having the fewest number of accesses over the selected time period.

12. The apparatus of claim 8, in which the memory is characterized as a flash memory array comprising a plurality of erasure blocks, the first data block stored in a first erasure block of the flash memory array and the second data block stored in a different, second erasure block of the flash memory array.

13. The apparatus of claim 8, in which the at least one variable parameter further comprises a measured error rate associated with the retrieval of data from the respective physical locations, and the one of the first or second data blocks selected for retention in the memory has an associated physical location with a lower measured error rate.

14. A data storage device comprising a main memory and a control circuit adapted to direct data transfer operations between the main memory and a host device, the control circuit further adapted to remove duplicate data sets from the main memory by identifying first and second data sets sharing a common data content and stored at different physical locations within the main memory each having an associated physical address, marking a selected one of the first or second data sets as valid data and the remaining one of the first or second data sets as stale data responsive to a variable parameter associated with each of the respective physical locations, and jettisoning the stale data from the main memory, the variable parameter comprising measured temperatures at the time of writing of the first and second data sets to the different physical locations.

15. The data storage device of claim 14, in which the control circuit is further adapted to generate a first hash value from the data content of the first data set and a second hash value from the data content of the second data set, and to compare the first and second hash values.

16. The data storage device of claim 14, in which the main memory is characterized as a flash memory array.

17. The data storage device of claim 16, in which the variable parameter further comprises a total accumulated count of erasure operations upon the respective physical locations of the first and second data sets.

18. The data storage device of claim 14, in which the first and second data sets are selected from a population of cold data sets in the memory as a subset of a total number of data sets in the memory, each cold data set having been accessed a total number of times less than a selected threshold over an elapsed time interval.

19. The data storage device of claim 14, in which the control circuit uses a bloom filter to combine a plurality of variable parameters associated with each of the different physical locations of the first and second data sets.