Enhancing data processing performance by cache management of fingerprint index

• US 9,110,815 B2
• Filed: 05/07/2012
• Issued: 08/18/2015
• Est. Priority Date: 05/07/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hyde, Joseph Smith II, Roy, Subhojit
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US13/465,456
• Publication Number:
  US 20130297569A1
• Time in Patent Office: 1,198 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0833 in combination with broadcast means (e.g. for invalidation or updating)
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements

Abstract

Various embodiments for improving hash index key lookup caching performance in a computing environment are provided. In one embodiment, for a cached fingerprint map having a plurality of entries corresponding to a plurality of data fingerprints, reference count information is used to determine a length of time to retain the plurality of entries in cache. Those of the plurality of entries having a higher reference counts are retained longer than those having lower reference counts.

Claims

1. A system for improving fingerprint storage mapping caching performance in a computing environment, comprising:

a deduplication engine;

a fingerprint map having a plurality of entries corresponding to a plurality of data fingerprints, the fingerprint map populated by the deduplication engine;

a memory including a cache configured for at least temporarily storing the fingerprint map; and

a processing device coupled to the memory;

a cache management module in operable communication with the cache;

wherein the cache management module is configured for;

using reference count information to determine a length of time to retain the plurality of entries of the fingerprint map in the cache, by;

examining the reference count information of the plurality of entries of the fingerprint map in the cache and a storage policy related to the plurality of entries to establish a retention duration for the plurality of entries, and

querying whether the reference count information for a data segment has been incremented or whether a predetermined time interval has expired,

if the reference count information for a data segment has not been incremented or if the predetermined time interval has not expired, reiterating the step of querying,

if the reference count information for a data segment has been incremented or if the predetermined time interval has expired in which no physical activity has been observed on a physical block, re-determining a new appropriate duration of retention in the cache, and

when the cache is full, retaining in the cache the plurality of entries of the fingerprint map having higher reference counts and removing from the cache the plurality of entries of the fingerprint map having lower reference counts.

2. The system of claim 1, wherein the reference count information is obtained from the deduplication engine.

3. The system of claim 1, wherein the cache management module is further configured for one of performing the re-determining for every reference count increment.

4. The system of claim 1, further including a policy module in operable communication with the cache management module, wherein the policy module is configured for, pursuant to determining the length of time to retain the plurality of entries in cache, implementing at least one policy corresponding to one of the length of time or at least one of the plurality of entries.

5. The system of claim 4, wherein the policy module is further configured for selecting one of an available plurality of policies for implementing.

6. The system of claim 5, wherein each of the available plurality of policies corresponds to one of a predetermined number of the plurality of entries and a predetermined time to retain some of the plurality of entries.

7. The system of claim 1, wherein the determining the length of time to retain the plurality of entries in cache performed in approximate synchronization with a deduplication operation for those of the plurality of entries retained in the cache.

8. A computer program product for improving hash index key lookup caching performance in a computing environment by a processor, the computer program product comprising a non-transitory physical computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

a first executable portion for, for a cached fingerprint map having a plurality of entries corresponding to a plurality of data fingerprints used by a data deduplication system, using reference count information to determine a length of time to retain the plurality of entries of the fingerprint map in cache, by;

examining the reference count information of the plurality of entries of the fingerprint map in the cache and a storage policy related to the plurality of entries to establish a retention duration for the plurality of entries,

querying whether the reference count information for a data segment has been incremented or whether a predetermined time interval has expired,

if the reference count information for a data segment has not been incremented or if the predetermined time interval has not expired, reiterating the step of querying,

if the reference count information for a data segment has been incremented or if the predetermined time interval has expired in which no physical activity has been observed on a physical block, re-determining a new appropriate duration of retention in the cache, and

when the cache is full, retaining in the cache the plurality of entries of the fingerprint map having higher reference counts in the cache and removing from the cache the plurality of entries of the fingerprint map having lower reference counts.

9. The computer program product of claim 8, further including a second executable portion for obtaining the reference count information from a data deduplication engine.

10. The computer program product of claim 8, further including a third executable portion for performing the re-determining for every reference count increment.

11. The computer program product of claim 8, further including a second executable portion for, pursuant to determining the length of time to retain the plurality of entries in cache, implementing at least one policy corresponding to one of the length of time or at least one of the plurality of entries.

12. The computer program product of claim 8, further including a second executable portion for, performing the determining the length of time to retain the plurality of entries in cache in approximate synchronization with a deduplication operation for those of the plurality of entries retained in the cache.