SYSTEMS AND METHODS FOR A DE-DUPLICATION CACHE

• US 20130198459A1
• Filed: 01/25/2013
• Published: 08/01/2013
• Est. Priority Date: 01/27/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Joshi, Vikram, Luan, Yang, Brown, Michael F., Radhakrishnan, Prashanth, Mehta, Bhavesh
• Granted Patent: US 9,116,812 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/151 Emulated environment, e.g. virtual machine
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 9/4406 Loading of operating system

Abstract

A de-duplication is configured to cache data for access by a plurality of different storage clients, such as virtual machines. A virtual machine may comprise a virtual machine de-duplication module configured to identify data for admission into the de-duplication cache. Data admitted into the de-duplication cache may be accessible by two or more storage clients. Metadata pertaining to the contents of the de-duplication cache may be persisted and/or transferred with respective storage clients such that the storage clients may access the contents of the de-duplication cache after rebooting, being power cycled, and/or being transferred between hosts.

Claims

1. An apparatus, comprising:

a de-duplication cache manager configured for operation on a host computing device comprising a plurality of virtual machines, the de-duplication cache manager configured to admit data into a de-duplication cache in response to admission requests from one or more of the plurality of virtual machines; and

a cache interface module configured to provide access to a single copy of data admitted into the de-duplication cache to two or more of the virtual machines.

2. The apparatus of claim 1, further comprising a virtual machine de-duplication module configured to identify files that are infrequently modified for admission into the de-duplication cache.

3. The apparatus of claim 1, wherein the de-duplication cache manager is configured to index data admitted into the de-duplication cache using context-independent data identifiers.

4. The apparatus of claim 3, wherein the de-duplication cache manager is configured to determine whether data has already been admitted into the de-duplication cache by use of the context-independent identifiers.

5. The apparatus of claim 4, wherein the de-duplication cache manager is configured to verify a match between context-independent identifiers by a byte-by-byte comparison of data corresponding to the context-independent identifiers.

6. The apparatus of claim 1, wherein the de-duplication cache manager is configured to restrict access to data admitted into the de-duplication cache to virtual machines that have previously requested admission of the data.

7. The apparatus of claim 1, further comprising a cache retention module configured to retain data admitted into the de-duplication cache by one of the virtual machines in response to determining that the one virtual machine is being transferred to a different host.

8. The apparatus of claim 1, further comprising a cache transfer module configured to transfer context-independent identifiers of files admitted into the de-duplication cache by a virtual machine to another host.

9. An apparatus, comprising:

a de-duplication cache policy module configured to identify I/O requests within a virtual machine pertaining to data that satisfy a de-duplication admission policy for admission into a de-duplication cache shared by a plurality of virtual machines; and

a virtual machine de-duplication module configured to service the identified I/O requests using the de-duplication cache.

10. The apparatus of claim 9, wherein the virtual machine de-duplication module is configured to admit a file into the de-duplication cache by deriving a data identifier of the file from data of the file, and providing the data of the file and the data identifier to the de-duplication cache.

11. The apparatus of claim 10, wherein the virtual machine de-duplication module is configured to admit the file into the de-duplication cache in response to an I/O request pertaining to the file, and wherein the operations to admit the file into the de-duplication cache are performed on a separate thread from a thread performing operations to satisfy the I/O request pertaining to the file.

12. The apparatus of claim 9, wherein the de-duplication cache manager is configured to associate names of files admitted into the de-duplication cache with respective data identifiers of the files to indicate that the files have been admitted into the de-duplication cache, wherein the de-duplication cache manager is further configured to request data of a file from the de-duplication cache by use of the data identifier associated with the file.

13. The apparatus of claim 9, wherein the virtual machine de-duplication module is configured to indicate that a file admitted into the de-duplication cache is no longer admitted in response to detecting an I/O request to modify the file.

14. The apparatus of claim 9, wherein the virtual machine de-duplication module is configured to store associations between file names of files admitted into the de-duplication cache and data identifiers of the files on a persistent storage medium and to load the associations in response to one or more of restarting the virtual machine, rebooting the virtual machine, power cycling the virtual machine, and migrating the virtual machine to a different host.

15. The apparatus of claim 9, further comprising file selection criteria configured to identify files for admission into the de-duplication cache based on one or more of file name, file extension, file path, file volume, file attribute, and a hint.

16. A method, comprising:

caching a file in a de-duplication cache shared by multiple virtual machines in response to a request to admit the file into the de-duplication cache from a first one of the virtual machines;

associating the cached file with a context-free identifier; and

providing data of the cached file from the de-duplication cache to a second one of the virtual machines in response to a request from the second virtual machine, wherein the request from the second virtual machine comprises the context-free identifier of the cached file.

17. The method of claim 16, further comprising determining whether a file has already been admitted into the de-duplication cache by comparing a context-free identifier derived from data of the file with context-free identifiers of files that have been admitted into the de-duplication cache.

18. The method of claim 16, further comprising:

comparing data of the file to existing cached file data in the de-duplication cache in response to the context-free identifier of the file matching a context-free identifier of a cached file that is already admitted into the de-duplication cache; and

providing a modified context-free identifier for the file data to the first one of the virtual machines in response to the file data differing from file data of the cached file already admitted into the de-duplication cache.

19. The method of claim 16, further comprising verifying that the second virtual machine is authorized to access the cached file.

20. The method of claim 19, wherein verifying that the second virtual machine is authorized to access the cached file comprises determining that the second virtual machine has access to the file on a primary storage.

21. A machine-readable storage medium comprising instructions configured to cause a computing device to perform a method, comprising:

identifying a file for admission into a de-duplication cache in response to monitoring file I/O requests within a storage stack of a virtual machine;

determining whether the file has been admitted into a de-duplication cache; and

servicing the I/O request by retrieving data from the de-duplication cache in response to determining that the file has been admitted, wherein servicing the I/O request comprises requesting data of the file from the de-duplication cache using a universal identifier of the file.

22. The machine-readable storage medium of claim 21, the method further comprising, in response to determining that the file has not been admitted into the de-duplication cache:

calculating the universal identifier of the file based on data of the file; and

generating a request to admit the file into the de-duplication cache, the request comprising the data of the file and the universal identifier.

23. The machine-readable storage medium of claim 21, the method further comprising associating a name of the file with the universal identifier in a de-duplication index of the virtual machine in response to receiving an indication that the file has been admitted into the de-duplication cache.

24. The machine-readable storage medium of claim 23, the method further comprising requesting data of the file from the de-duplication cache by use of the universal identifier associated with the name of the file in the de-duplication index.

25. The machine-readable storage medium of claim 23, the method further comprising:

persisting a snapshot of the de-duplication index; and

populating the de-duplication index using the snapshot subsequent to one or more of rebooting the virtual machine, power cycling the virtual machine, and transferring the virtual machine to a different host.

26. The machine-readable storage medium of claim 23, the method further comprising invalidating an entry in the de-duplication index in response to detecting an I/O request to modify a file referenced in the entry.