Granted Patent B1

US 9,852,076 · App. 14/971,285 · Granted Dec 26, 2017

Abstract

Claims (37)

1. A method of managing metadata for deduplicated data in a computer system, the method comprising:

using a processor configured to be operable to perform the steps of:

maintaining metadata for deduplicated data in a storage memory;

maintaining a deduplicated metadata cache, wherein the deduplicated metadata cache comprises a subset of the metadata for deduplicated data;

maintaining a history record of user read requests;

searching the deduplicated metadata cache in response to a user read request; and one of:

if the metadata for the deduplicated data is found in the deduplicated metadata cache, reading the deduplicated data from the storage memory using the metadata in the deduplicated metadata cache; or,

if the metadata for the deduplicated data is not found in the deduplicated metadata cache, reading the metadata for user read request from the storage memory:

reading the data from the storage memory using the metadata and responding to the user read request; and,

adding the metadata for the deduplicated data to the deduplicated metadata cache, based on a threshold value of an access counter in the history record.

2. The method of claim 1 , wherein the step of maintaining the history record comprises:

searching the history record in response to a user read request; and

if the metadata for the user read request is in the history record, incrementing the access counter;

purging each address of the history record after a predetermined period of time.

3. The method of claim 2 , wherein, if the user read request is not in the history record:

retrieving the metadata associated with the user read request and associating the metadata with the user read request in the history record and initializing the access counter.

4. The method of claim 3 , wherein, at a time prior to purging metadata from the history record, determining if the access counter associated with the metadata exceeds the threshold and:

if the access counter exceeds the threshold, maintaining the metadata in the deduplicated data cache; or,

purging the metadata from the history record after the predetermined period of time.

5. The method of claim 2 , wherein a Bloom filter is used to determine if the metadata is not in the history record prior to searching the history record.

6. The method of claim 5 , wherein cold data is evicted from the deduplicated metadata cache based on at least one of a relative hot or cold status of an access counter with respect to other metadata in the deduplicated metadata cache or a time of residence of the metadata in the deduplicated metadata cache, wherein the metadata has the hot status when the number of accesses exceeds a predetermined number of accesses to the metadata in the deduplicated data cache during a predetermined time interval and the metadata has the cold status when the number of accesses to the metadata is less than a predetermined number of accesses to the metadata in during a predetermined time interval.

7. The method of claim 1 , wherein the step of maintaining the deduplicated metadata cache comprises:

determining if the metadata associated with a user read request in the history record is hot based on the access counter; and

determining whether space is available in the deduplicated metadata cache for adding the metadata; and

if space is available, adding the metadata for hot metadata to the deduplicated metadata cache; or,

if no space is available, determining if metadata can be evicted from the deduplicated metadata cache; and

if metadata can be evicted, evict the metadata and add hot metadata to the deduplicated metadata cache,

wherein the metadata is hot when the access counter exceeds the threshold value during a predetermined time interval.

8. The method of claim 1 , wherein the step of determining whether metadata can be evicted from the deduplicated metadata cache comprises at least one of:

determining a current hot or cold data status of the metadata in the deduplicated data cache and selecting the coldest data for eviction; or,

determining an age status of the metadata and evicting the oldest metadata; or

determining the age status of the metadata as a combination of a number of accesses to the metadata stored in the deduplicated metadata cache divided by a time that the metadata has been in the deduplicated metadata cache and evicting the metadata having the least quotient; and,

wherein the metadata has the current hot status when the number of accesses exceeds a predetermined number of accesses to the metadata in the deduplicated data cache during a predetermined time interval and the metadata has the current cold status when the number of accesses to the metadata is less than a predetermined number of accesses to the metadata in during a predetermined time interval.

9. The method of claim 1 , wherein the history record is searched for metadata in response to the user read request prior to searching the deduplicated metadata cache.

10. The method of claim 1 , wherein an auxiliary history record is maintained where a density of read requests for a plurality of extents of a logical address space is maintained for a specified time interval and a hot or cold status of the extents are categorized as a number of read requests in the extent during the specified time interval, and at least one of the extents is selected as a filter such that the read requests are initially directed to the history record to search for metadata.

11. The method of claim 1 , wherein a Bloom filter is used to determine if the metadata is not in the deduplicated metadata cache prior to searching the deduplicated metadata cache.

12. The method of claim 11 , further comprising configuring the processor to maintain the deduplicated metadata cache by moving the metadata for hot data from the history record to the deduplicated metadata cache.

Assignments (8)