Systems and methods for a multi-level cache

• US 8,996,807 B2
• Filed: 11/02/2011
• Issued: 03/31/2015
• Est. Priority Date: 02/15/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Joshi, Vikram, Luan, Yang, Brown, Michael F., Vidwans, Hrishikesh A.
• Primary Examiner(s): THAI, TUAN V
• Application Number:
  US13/288,005
• Publication Number:
  US 20120210068A1
• Time in Patent Office: 1,245 Days
• Field of Search: 711/100, 711/103, 711/117, 711/118, 711/154
• US Class Current: 711/117
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects

Abstract

A multi-level cache comprises a plurality of cache levels, each configured to cache I/O request data pertaining to I/O requests of a different respective type and/or granularity. A cache device manager may allocate cache storage space to each of the cache levels. Each cache level maintains respective cache metadata that associates I/O request data with respective cache address. The cache levels monitor I/O requests within a storage stack, apply selection criteria to identify cacheable I/O requests, and service cacheable I/O requests using the cache storage device.

Claims

1. A method for caching input/output (I/O) request data using a non-volatile cache, the method comprising:

monitoring I/O requests at each of a plurality of layers of a storage stack, each cache level of a plurality of cache levels configured to cache I/O request data of a different respective layer of the storage stack; and

in each of the plurality of cache levels;

maintaining cache metadata associating I/O request data cached within the respective cache level with cache addresses of the non-volatile cache device,

applying respective selection criteria to the monitored I/O requests to identify I/O requests that are cacheable within the respective cache level, and

servicing cacheable I/O requests that satisfy the selection criteria within the respective cache level using the non-volatile cache device.

2. The method of claim 1, wherein each of the cache levels maintains cache metadata within a virtual machine, and wherein the non-volatile cache device operates in a host for the virtual machine.

3. The method of claim 1, further comprising configuring each of the cache levels to prevent more than one of the cache levels from caching the same I/O request data.

4. The method of claim 1, wherein a first one of the cache levels and a second one of the cache levels are configured to service the same I/O request data, the method further comprising applying a run-time exclusion rule to service the I/O request data exclusively in one of the first cache level and the second cache level.

5. The method of claim 1, wherein servicing a cacheable I/O request in a cache level comprises bypassing one or more layers of the storage stack.

6. The method of claim 1, wherein one of the plurality of cache levels comprises a file level cache, and wherein servicing a cacheable I/O request in the file-level cache level comprises accessing data of the I/O request on the non-volatile cache device to bypass a volume layer of the storage stack.

7. The method of claim 1, further comprising:

determining an allocation ratio of cache storage space between two or more of the cache levels; and

allocating cache storage space of the non-volatile cache device to the two or more cache levels in accordance with the allocation ratio, wherein each of the two or more cache levels service cacheable I/O requests from cache storage space allocated to the respective cache level.

8. The method of claim 7, further comprising allocating cache storage space to the two or more cache levels in accordance with an interleaved allocation pattern that is configured to preserve the allocation ratio between the two or more cache levels despite deallocation of contiguous ranges of the cache storage space.

9. The method of claim 1, further comprising:

determining a virtual machine allocation ratio between two or more virtual machines, each virtual machine comprising two or more cache levels;

allocating cache storage of the non-volatile cache to the two or more virtual machines according to the virtual machine allocation ratio; and

within each of the two or more virtual machines;

determining a cache level allocation ratio between two or more of the cache levels of the virtual machine, and

allocating cache storage space to the two or more cache levels of the virtual machine in accordance with the cache level allocation ratio of the virtual machine and within the cache space allocated to the virtual machine.

10. The method of claim 1, further comprising:

receiving a notification at a first one of the cache levels from another one of the cache levels regarding I/O request data cached by the first one of the cache levels; and

invalidating the I/O request data cached by the first cache level in response to the notification, the I/O request data identified by the notification.

11. The method of claim 1, further comprising:

receiving a notification at a file-level cache that one of a volume and a disk has been unmounted;

determining that the file-level cache is configured to cache file data stored on one of the volume and the disk; and

invalidating I/O request data on the non-volatile cache device pertaining to the files stored on one of the storage volume and the storage media device in response to the determination.

12. The method of claim 1, further comprising monitoring I/O requests in each of a plurality of I/O monitors, each I/O request monitor configured to monitor I/O requests of a respective granularity within the storage stack and corresponding to a respective one of the cache levels.

13. The method of claim 1, wherein the cache levels comprise one of a file-level cache, an object-level cache, application-level cache, a volume-level cache, a disk-level cache, and a Small Computer System Interface (SCSI)-level cache.

14. The method of claim 1, further comprising:

each of the cache levels;

applying application criteria to monitored I/O requests, and

servicing the monitored I/O requests within the respective cache level using the non-volatile cache device when the monitored I/O requests satisfy the application criteria.

15. A system for caching data on a non-volatile cache storage device, comprising:

a non-volatile cache storage device;

a multi-level cache comprising an I/O request monitor configured to monitor I/O requests at each of a plurality of layers of a storage stack; and

a plurality of cache levels, each cache level configured to cache I/O request data of a respective granularity of the storage stack,

wherein each cache level is configured to maintain cache metadata associating I/O request data with respective cache addresses of the non-volatile cache storage device, to apply respective selection criteria to monitored I/O requests to identify I/O requests that are cacheable within the respective cache level, and to service cacheable I/O requests within the respective cache level using the non-volatile cache storage device.

16. The system of claim 15, wherein the cache levels operate within a virtual machine, and wherein the non-volatile cache storage device operates in a host for the virtual machine.

17. The system of claim 15, wherein the multi-level cache comprises exclusion rules configured to prevent I/O request data from being cached within more than one of the cache levels.

18. The system of claim 15, wherein one of the cache levels is a file-level cache, and wherein the file-level cache is configured to bypass one or more layers of the storage stack when servicing an I/O storage request using the cache device.

19. A non-transitory computer-readable storage medium comprising instructions to cause a computing device to perform a method for caching I/O request data on a cache device, the method comprising:

monitoring I/O requests at each of a plurality of layers of a storage stack, each cache level configured to cache I/O request data of a different respective layer of the storage stack; and

in each of a plurality of cache levels,

maintaining respective cache metadata associating I/O request data with cache addresses of the cache device,

applying respective selection criteria to the monitored I/O requests to identify I/O requests that are cacheable within the respective cache level, and

servicing I/O requests that satisfy the selection criteria within the respective cache level using the cache device;

wherein the selection criteria of a cache level comprises one of file selection criteria, volume selection criteria, and disk selection criteria.

20. The non-transitory computer-readable storage medium of claim 19, wherein servicing a cacheable I/O request comprises bypassing one or more layers of the storage stack.

21. The non-transitory computer-readable storage medium of claim 19, wherein the cache levels maintain cache metadata within a virtual machine, and wherein the cache device operates in a host for virtual machine.