Indexing a deduplicated cache system by integrating fingerprints of underlying deduplicated storage system

• US 9,336,143 B1
• Filed: 09/26/2013
• Issued: 05/10/2016
• Est. Priority Date: 09/26/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Wallace, Grant R., Douglis, Frederick, Shilane, Philip N., Shim, Hyong, Smaldone, Stephen
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US14/038,694
• Time in Patent Office: 957 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0649 Lifecycle management
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/068 Hybrid storage device

Abstract

A computer-implemented method for indexing content stored in a cache memory device is disclosed. The method starts with maintaining a file index having a plurality of extent entries, each extent entry corresponding to one of a plurality of file extents stored in a cache memory device that caches data stored in a persistent storage device of a storage system. The method continues with maintaining a fingerprint index having a plurality of fingerprint entries, each mapping a fingerprint to a data region of a file indexed in the file index, wherein each fingerprint indexed in the fingerprint index is retrieved from metadata stored in the persistent storage device of the storage system when one or more corresponding data chunks were accessed, and deduplicating and accessing the file extents stored in the cache memory device using the file index and the fingerprint index.

Claims

1. A computer-implemented method for indexing content stored in a cache memory device, the method comprising:

maintaining a file index having a plurality of extent entries, each extent entry corresponding to one of a plurality of file extents stored in a cache memory device that caches data stored in a persistent storage device of a deduplicated storage system, wherein each extent entry maps a particular data region of a particular file to a storage location of the cache memory device storing a corresponding file extent;

maintaining a fingerprint index having a plurality of fingerprint entries, each mapping a fingerprint to a data region of a file indexed in the file index, wherein each fingerprint indexed in the fingerprint index is retrieved from metadata stored in the persistent storage device of the storage system when one or more corresponding data chunks were accessed; and

deduplicating and accessing the file extents stored in the cache memory device using the file index and the fingerprint index, wherein the file index is used to determine whether the particular data region of the particular file has been previously stored in the cache memory device, and wherein the fingerprint index is used to determine whether the particular data region is shared by another data region of the particular file or shared by another file and the particular data region has been stored in the cache memory device during access of another data region of the particular file or another file.

2. The method of claim 1, further comprising:

receiving a first request to read a first region of a first file, the first request including a first file handle representing the first file and a first offset;

looking up in the file index based on the first file handle and the first offset;

if an extent entry is found that matches the first file handle and the first offset, retrieving and returning a first extent from a corresponding storage location of the first extent entry.

3. The method of claim 2, further comprising:

if no extent entry matching the first file handle and the first offset is found in the file index, reading one or more data chunks from the deduplicated storage system to serve the first request;

caching in the cache memory device at least some of the data chunks representing the first region of the first file;

creating a new extent entry in the file index, the new extent entry including the first file handle, the first offset, and a storage location of the cache memory device that caches the first region of the first file.

4. The method of claim 3, further comprising:

prior to reading one or more data chunks from the deduplicated storage system, retrieving fingerprints associated with a file region corresponding to the first file handle and the first offset; and

looking up in the fingerprint index based on the retrieved fingerprints to determine whether the data chunks have been cached in the cache memory device.

5. The method of claim 3, further comprising creating a new fingerprint entry in the fingerprint index, the new fingerprint entry including a fingerprint of the one or more data chunks retrieved from the metadata of the deduplicated storage system.

6. The method of claim 1, further comprising:

receiving a second request to read a second region of a second file, the second request including a fingerprint that is extracted from some levels of a tree of fingerprints representing the second region of the second file stored in the deduplicated storage system;

looking up in the fingerprint index based on the fingerprint in the second request;

if a fingerprint entry matching the fingerprint is found, retrieving a second file handle and a second offset from the matching fingerprint entry;

looking up in the file index based on the second file handle and the second offset to determine a second storage location of the cache memory device; and

retrieving and returning at least one extent from the cache memory device from the second storage location.

7. The method of claim 6, wherein a new entry is added in the file index which maps the requested region to the second file and offset determined in the fingerprint index.

8. The method of claim 1, wherein each extent entry of the file index further includes a portion of a fingerprint to reference to a related fingerprint entry of the fingerprint index.

9. The method of claim 1, wherein each of the file extents stored in the cache memory device includes a file handle and an offset representing a file region of a file associated with the file extent.

10. The method of claim 8, further comprising:

receiving a request to evict a third file extent stored in the cache memory device;

extract a third file handle and a third offset from the third file extent;

looking up and removing an extent entry in the file index that matches the third file handle and the third offset; and

looking up and removing a fingerprint entry in the fingerprint index that matches the third file handle and the third offset.

11. A storage system, comprising:

one or more storage units to store a plurality of files;

a cache memory device to cache at least some data blocks of at least some of the files; and

a cache manager executed by the processor configured to

maintain a file index having a plurality of extent entries, each extent entry corresponding to one of a plurality of file extents stored in the cache memory device that caches data stored in the storage units, wherein each extent entry maps a particular data region of a particular data object to a storage location of the cache memory device storing a corresponding file extent,

maintain a fingerprint index having a plurality of fingerprint entries, each mapping a fingerprint to a data region of a file indexed in the file index, wherein each fingerprint indexed in the fingerprint index is retrieved from metadata stored in the storage units when one or more corresponding data chunks were accessed, and

deduplicate and access the file extents stored in the cache memory device using the file index and the fingerprint index, wherein the file index is used to determine whether the particular data region of the particular file has been previously stored in the cache memory device, and wherein the fingerprint index is used to determine whether the particular data region is shared by another data region of the particular file or shared by another file and the particular data region has been stored in the cache memory device during access of another data region of the particular file or another file.

12. The storage system of claim 11, wherein the cache manager is further configured to:

receive a first request to read a first region of a first file, the first request including a first file handle representing the first file and a first offset;

look up in the file index based on the first file handle and the first offset; and

if an extent entry is found that matches the first file handle and the first offset, retrieve and return a first extent from a corresponding storage location of the first extent entry.

13. The storage system of claim 12, wherein the cache manager is further configured to:

if no extent entry matching the first file handle and the first offset is found in the file index, read one or more data chunks from the deduplicated storage system to serve the first request;

cache in the cache memory device at least some of the data chunks representing the first region of the first file; and

create a new extent entry in the file index, the new extent entry including the first file handle, the first offset, and a storage location of the cache memory device that caches the first region of the first file.

14. The storage system of claim 13, wherein the cache manager is further configured to:

prior to reading one or more data chunks from the deduplicated storage system, retrieve fingerprints associated with a file region corresponding to the first file handle and the first offset; and

look up in the fingerprint index based on the retrieved fingerprints to determine whether the data chunks have been cached in the cache memory device.

15. The storage system of claim 13, wherein the cache manager is further configured to create a new fingerprint entry in the fingerprint index, the new fingerprint entry including a fingerprint of the one or more data chunks retrieved from the metadata of the deduplicated storage system.

16. The storage system of claim 11, wherein the cache manager is further configured to:

receive a second request to read a second region of a second file, the second request including a fingerprint that is extracted from some levels of a tree of fingerprints representing the second region of the second file stored in the deduplicated storage system;

look up in the fingerprint index based on the fingerprint in the second request;

if a fingerprint entry matching the fingerprint is found, retrieve a second file handle and a second offset from the matching fingerprint entry;

look up in the file index based on the second file handle and the second offset to determine a second storage location of the cache memory device; and

retrieve and returning at least one extent from the cache memory device from the second storage location.

17. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for indexing content stored in a cache memory device, the operations comprising:

maintaining a file index having a plurality of extent entries, each extent entry corresponding to one of a plurality of file extents stored in a cache memory device that caches data stored in a persistent storage device of a deduplicated storage system, wherein each extent entry maps a particular data region of a particular data object to a storage location of the cache memory device storing a corresponding file extent;

maintaining a fingerprint index having a plurality of fingerprint entries, each mapping a fingerprint to a data region of a file indexed in the file index, wherein each fingerprint indexed in the fingerprint index is retrieved from metadata stored in the persistent storage device of the storage system when one or more corresponding data chunks were accessed; and

deduplicating and accessing the file extents stored in the cache memory device using the file index and the fingerprint index, wherein the file index is used to determine whether the particular data region of the particular file has been previously stored in the cache memory device, and wherein the fingerprint index is used to determine whether the particular data region is shared by another data region of the particular file or shared by another file and the particular data region has been stored in the cache memory device during access of another data region of the particular file or another file.

18. The non-transitory computer-readable storage medium of claim 17, wherein the operations further comprise:

receiving a first request to read a first region of a first file, the first request including a first file handle representing the first file and a first offset;

looking up in the file index based on the first file handle and the first offset;

if an extent entry is found that matches the first file handle and the first offset, retrieving and returning a first extent from a corresponding storage location of the first extent entry.

19. The non-transitory computer-readable storage medium of claim 18, wherein the operations further comprise:

if no extent entry matching the first file handle and the first offset is found in the file index, reading one or more data chunks from the deduplicated storage system to serve the first request;

caching in the cache memory device at least some of the data chunks representing the first region of the first file; and

creating a new extent entry in the file index, the new extent entry including the first file handle, the first offset, and a storage location of the cache memory device that caches the first region of the first file.

20. The non-transitory computer-readable storage medium of claim 19, wherein the operations comprise:

prior to reading one or more data chunks from the deduplicated storage system, retrieving fingerprints associated with a file region corresponding to the first file handle and the first offset; and

looking up in the fingerprint index based on the retrieved fingerprints to determine whether the data chunks have been cached in the cache memory device.

21. The non-transitory computer-readable storage medium of claim 19, wherein the operations further comprise creating a new fingerprint entry in the fingerprint index, the new fingerprint entry including a fingerprint of the one or more data chunks retrieved from the metadata of the deduplicated storage system.

22. The non-transitory computer-readable storage medium of claim 17, wherein the operations further comprise:

receiving a second request to read a second region of a second file, the second request including a fingerprint that is extracted from some levels of a tree of fingerprints representing the second region of the second file stored in the deduplicated storage system;

looking up in the fingerprint index based on the fingerprint in the second request;

if a fingerprint entry matching the fingerprint is found, retrieving a second file handle and a second offset from the matching fingerprint entry;

looking up in the file index based on the second file handle and the second offset to determine a second storage location of the cache memory device; and

retrieving and returning at least one extent from the cache memory device from the second storage location.