Multi-leveled cache management in a hybrid storage system

• US 10,210,084 B1
• Filed: 08/29/2016
• Issued: 02/19/2019
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: BiTMICRO, LLC (BiTMICRO Networks, Inc.)
• Original Assignee: BiTMICRO, LLC (BiTMICRO Networks, Inc.)
• Inventors: Bruce, Rolando H., Dela Cruz, Elmer Paule, Arcedera, Mark Ian Alcid
• Primary Examiner(s): Oberly, Eric T
• Application Number:
  US15/249,475
• Time in Patent Office: 904 Days
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/217 Hybrid disk, e.g. using both magnetic and solid state storage devices
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/225 Hybrid cache memory, e.g. having both volatile and non-volatile portions
• CPC Class Codes: G06F 2212/305 being part of a memory device, e.g. cache DRAM
• CPC Class Codes: G06F 2212/313 In storage device

Abstract

A hybrid storage system is described having a mixture of different types of storage devices comprising rotational drives, flash devices, SDRAM, and SRAM. The rotational drives are used as the main storage, providing lowest cost per unit of storage memory. Flash memory is used as a higher-level cache for rotational drives. Methods for managing multiple levels of cache for this storage system is provided having a very fast Level 1 cache which consists of volatile memory (SRAM or SDRAM), and a non-volatile Level 2 cache using an array of flash devices. It describes a method of distributing the data across the rotational drives to make caching more efficient. It also describes efficient techniques for flushing data from L1 cache and L2 cache to the rotational drives, taking advantage of concurrent flash devices operations, concurrent rotational drive operations, and maximizing sequential access types in the rotational drives rather than random accesses which are relatively slower. Methods provided here may be extended for systems that have more than two cache levels.

Claims

1. A data storage apparatus, comprising:

a first cache for storing data, wherein the first cache comprises volatile memory;

a second cache for storing data, the second cache being in communication with the first cache, wherein the second cache comprises non-volatile memory including a plurality of flash memory devices;

one or more host interface controllers for communicating between the first cache and one or more external host systems;

a first group of IO interface DMA controllers for communicating between the first cache and a plurality of external rotational disk drives; and

a first flash interface DMA controller for communicating between the second cache and the first cache;

wherein the data storage apparatus is configured to perform operations comprising;

storing data in the first cache;

storing data in the second cache; and

performing data transfers, wherein the data transfers include;

transferring data between the first cache and the second cache using the first flash interface DMA controller;

transferring data between the first cache and the one or more external host systems using the one or more host interface controllers; and

transferring data between the first cache and the plurality of external rotational disk drives using the first group of IO interface DMA controllers; and

wherein the first flash interface DMA controller includes including a plurality of flash interface engines and a plurality of flash buses, wherein each flash interface engine is coupled to the flash memory devices in the second cache via a corresponding flash bus, wherein the first flash interface DMA controller is configured to perform concurrent flash operations selected from a group comprising;

a first concurrent flash operation comprising a first flash operation associated with a first flash memory device performed concurrently with a second flash operation associated with a second flash memory device, different from the first flash memory device; and

a second concurrent flash operation comprising a first flash operation associated with a first flash memory device performed concurrently with a second flash operation also associated with the first flash memory device.

2. The data storage apparatus of claim 1, further comprising:

a volatile memory buffer configured to;

receive and store data fetched from the second cache; and

forward data stored in the volatile memory buffer to a first external host system of the one or more external host systems, wherein data residing in the second cache, when requested by the first external host system, is transferred from the second cache to the first external host system without being stored in the first cache.

3. The data storage apparatus of claim 1, wherein one of the one or more host interface controllers or one of the first group of IO interface DMA controllers, and the first flash interface DMA controller concurrently execute separate data transfer tasks using separate DMA paths.

4. The data storage apparatus of claim 1,

wherein at least one of the one or more external host systems accesses data comprising one or more logical block units (LBUs), each LBU comprising one or more stripes, said one or more stripes being distributed among one or more rotational disk drives;

and

wherein a size of each stripe equals a cache line size, said cache line size being equal to a native flash section size.

5. The data storage apparatus of claim 1, wherein at least one of the one or more external host systems comprises an external host and an external hybrid storage device, said external hybrid storage device comprising:

a third cache for storing data;

wherein the third cache comprises volatile memory;

a fourth cache for storing data, the fourth cache being in communication with the third cache;

wherein the fourth cache comprises non-volatile memory;

a one or more host interface controllers for communicating between the third cache and the external host; and

a fourth group of IO interface DMA controllers for communicating between the third cache and the one or more host interface controllers; and

a second flash interface DMA controller for communicating between the third cache and the fourth cache;

wherein the third cache and the fourth cache are managed independent of the first and second cache.

6. The data storage apparatus of claim 1,

wherein at least one of the one or more external host systems comprises an external host and a network;

and

wherein at least one of the one or more host interface controllers communicates between the first cache and the external host via the network.

7. The data storage apparatus of claim 1, wherein at least one of the first cache the second cache reside in the one or more external host systems.

8. The data storage apparatus of claim 1, wherein the first cache and the second cache both reside in the one or more external host systems.

9. An apparatus for storing data, wherein the apparatus comprises:

A central processing unit (CPU) for executing software application;

a first cache for storing data, the first cache being in communication with the CPU;

wherein the first cache comprises volatile memory;

a second cache for storing data, the second cache being in communication with the first cache;

wherein the second cache comprises non-volatile memory;

a first group of IO interface DMA controllers for communicating between the first cache and a plurality of external rotational disk drives; and

a first flash interface DMA controller for communicating between the second cache and the first cache

wherein the first flash interface DMA controller includes including a plurality of flash interface engines and a plurality of flash buses, wherein each flash interface engine is coupled to the flash memory devices in the second cache via a corresponding flash bus, wherein the first flash interface DMA controller is configured to perform concurrent flash operations selected from a group comprising;

a first concurrent flash operation, comprising a first flash operation associated with a first flash memory device, performed concurrently with a second flash operation associated with a second flash memory device, different from the first flash memory device; and

a second concurrent flash operation comprising a first flash operation associated with a first flash memory device performed concurrently with a second flash operation also associated with the first flash memory device.

10. The apparatus of claim 9, wherein at least one of the plurality of external rotational disk drives comprises:

a third cache for storing data, wherein the third cache comprises volatile memory;

a fourth cache for storing data, the fourth cache being in communication with the third cache, wherein the fourth cache comprises non-volatile memory;

a second group of IO interface DMA controllers for communicating between the third cache and the first group of IO interface controllers;

a third group of IO interface DMA controllers for communicating between the third cache and a plurality of external rotational disk drives; and

a second flash interface DMA controller for communicating between the fourth cache and the third cache.

11. The apparatus of claim 9, further comprising:

a computer readable medium including computer-executable instructions for supporting RAID functionality, device level virtualization, and pre-fetching.

12. A method for storing data, the method comprising:

storing data in a first cache, wherein the first cache comprises volatile memory;

storing data in a second cache, wherein the second cache comprises non-volatile memory including a plurality of flash memory devices;

transferring data between the first cache and the second cache using a first flash interface DMA controller;

transferring data between the first cache and one or more external hosts using one or more host interface controllers; and

transferring data between the first cache and any of a plurality of external rotational disk drives using a first group of IO interface DMA controllers;

wherein the first flash interface DMA controller includes including a plurality of flash interface engines and a plurality of flash buses, wherein each flash interface engine is coupled to the flash memory devices in the second cache via a corresponding flash bus, wherein the first flash interface DMA controller is configured to perform concurrent flash operations selected from a group comprising;

a first concurrent flash operation comprising a first flash operation associated with a first flash memory device performed concurrently with a second flash operation associated with a second flash memory device, different from the first flash memory device; and

a second concurrent flash operation comprising a first flash operation associated with a first flash memory device performed concurrently with a second flash operation also associated with the first flash memory device.

13. The method of claim 12, further comprising:

maintaining a cache information table state indicative of a state of the cache line in the first cache, and a second state indicative a state of the cache line in the second cache;

wherein the cache information table includes LBA status bits including a valid/invalid bit and a clean/dirty bit, for each of the plurality of LBAs included in the cache line;

wherein if the data is currently being transferred between the first cache and the host, or between the first cache and the second cache, or between the first cache and the external rotational disk drives, the direction of data is tracked using the cache sub-status, wherein the cache sub-status is determined, at least in part, by the source and destination of the data transfer;

wherein the LBA already in transit, or being transferred between the first cache and the second cache or between the external host and the first cache or between the external rotational disk drives and the first cache, are tracked using in-transit LBA status bits; and

wherein if the data is not in the first cache and not in the second cache and not in-transit, a translation formula is used to determine the location of the data within one of the external rotational disk drives.

14. The method of claim 12 further comprising:

for each transfer of data, determining a next state of the first cache and a next state of the second cache based on a previous state of the first cache, a previous state of the second cache, a source and destination of the data being transferred, and whether any portions of a destination cache line that were invalid before said transfer remain invalid after said transfer.

15. The method of claim 12, further comprising;

responsive to detecting particular conditions, copying data from the first cache to the second cache, wherein the particular conditions include;

a percentage of used cache lines in the first cache greater than or equal to a particular percentage of total cache lines in the first cache; and

the storage device being in an idle state, wherein the idle state is indicated by an absence of IO requests from the one or more external host systems; and

wherein if a loss of external power supply is detected, the copying of data from the first cache to the second cache is executed with the aid of an internal back-up power source.

16. The method of claim 12, further comprising:

selecting a cache line for copying from the first cache to the second cache;

wherein said selecting includes identifying a first cache line, wherein the first cache line comprises a cache line with a valid full clean state in the first cache and an invalid state in the second cache.

17. The method of claim 12 further comprising;

transferring data from the first cache to the second cache until a usage of the second cache equals or exceeds a particular usage threshold; and

responsive to the usage of the second cache reaching or exceeding the particular usage threshold and further responsive to detecting an idle storage device, wherein the idle storage device is indicated by an interval during which no IO requests are received from the external hosts wherein a length of the interval exceeds a particular length, flushing data to the external rotational disk drives.

18. The method of claim 12, further comprising:

selecting among the candidate cache lines for flushing to the external rotational disk drives;

wherein said candidate cache lines include a cache line containing less recently used data and a cache line containing more recently used data and wherein selecting among the candidate includes selecting the cache line containing less recently used data before selecting the cache line containing more recently used data;

wherein cache lines that form consecutive locations in the rotational disk drive are preferred among the least recently used candidates so that the resulting access is a sequential type; and

wherein cache lines that belong to different rotational disk drives and can be transferred concurrently using different IO interface DMA controllers are transferred simultaneously.

19. The method of claim 12, further comprising;

preventing data loss due to external power source interruption by flushing dirty data in the first cache to the second cache using power provided a backup power source; and

maintaining a copy of the cache information table in non-volatile memory for retrieval of the information for the second cache upon next boot-up of the storage device.