Multi-leveled cache management in a hybrid storage system

• US 9,430,386 B2
• Filed: 03/17/2014
• Issued: 08/30/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: BiTMICRO, LLC (BiTMICRO Networks, Inc.)
• Original Assignee: BiTMICRO Networks, Inc.
• Inventors: DELA CRUZ, ELMER PAULE, Bruce, Rolando H., ARCEDERA, MARK IAN ALCID
• Primary Examiner(s): OBERLY, ERIC T
• Application Number:
  US14/217,436
• Publication Number:
  US 20150012690A1
• Time in Patent Office: 897 Days
• US Class Current: 1/1
• 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. An apparatus for storing data comprising:

a first cache for storing data;

wherein the first cache comprises a volatile memory;

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

wherein the second cache comprises a non-volatile memory;

a first group of IO interface DMA controllers for communicating between the first cache and a plurality of external host systems;

a second group of IO interface DMA controllers for communicating between the first cache and a plurality of external mechanical 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 copies data from the first cache to the second cache if a pre-defined threshold of unused cache lines is reached in the first cache;

wherein the apparatus is configured for flushing of data to the external mechanical disk drives;

wherein said flushing of data to the external mechanical disk drives is reduced by moving data from the first cache to the second cache until contents of the second cache reaches an allowed percentage usage threshold; and

wherein if there are no IO requests coming from the external host systems, wherein a storage device comprising the first cache and the second cache is idle, data is flushed to the external mechanical disk drives from the storage device from the first cache.

2. An apparatus as in claim 1, further comprising a volatile memory buffer for supporting the first group of IO interface DMA controllers in communicating with the first flash interface DMA controller, said volatile memory buffer configured for transferring of data directly between the second cache and the external host systems without going through the first cache.

3. An apparatus as in claim 1,

wherein one of the first group of IO interface DMA controllers or one of the second group of IO interface DMA controllers, and the first flash interface DMA controller concurrently execute separate data transfer tasks using separate DMA paths.

4. An apparatus as in claim 1,

wherein the external host systems access data comprising one or more LBUs (logical block units), each LBU comprising one or more stripes, said one or more stripes being distributed among the one or more external mechanical disk drives;

and

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

5. An apparatus as in claim 1, wherein an external host system included among the external host systems comprises a host and a hybrid storage device, said hybrid storage device comprising:

a third cache for storing data;

wherein the third cache comprises another volatile memory;

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

wherein the fourth cache comprises another non-volatile memory;

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

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

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

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

6. An apparatus as in claim 1,

wherein the external host system comprises a host and a network;

and

wherein one of the first group of IO interface DMA controllers communicates between the first cache and the host via the network.

7. An apparatus as in claim 1, wherein the first cache and the second cache are both residing in a storage device.

8. An apparatus as in claim 1, wherein the first cache and the second cache are both residing in one of the external host systems.

9. An apparatus for storing data comprising:

a 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 a volatile memory;

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

wherein the second cache comprises a non-volatile memory;

a first group of IO interface DMA controllers for communicating between the first cache and a plurality of external mechanical 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 copies data from the first cache to the second cache if a pre-defined threshold of unused cache lines is reached in the first cache;

wherein the apparatus is configured for flushing of data to the external mechanical disk drives;

wherein said flushing of data to the external mechanical disk drives is reduced by moving data from the first cache to the second cache until contents of the second cache reaches an allowed percentage usage threshold; and

wherein if there are no IO requests coming from an external host, wherein a storage device comprising the first cache and the second cache is idle, data is flushed to the external mechanical disk drives from the first cache.

10. An apparatus as in claim 9, wherein one of the external mechanical disk drives comprises:

a third cache for storing data;

wherein the third cache comprises another volatile memory;

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

wherein the fourth cache comprises another non-volatile memory;

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

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

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

11. An apparatus as in claim 9 further comprising a computer readable medium, said computer readable medium comprises computer instructions for supporting RAID functionalities, device level virtualization, or pre-fetching.

12. A method for storing data comprising,

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

storing data in a second cache, wherein the second cache comprises a non-volatile memory;

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

wherein the first flash interface DMA controller copies data from the first cache to the second cache if a pre-defined threshold of unused cache lines is reached in the first cache;

transferring data between the first cache and a plurality of external hosts using a first group of IO interface DMA controllers;

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

flushing of data to the external mechanical disk drives;

wherein said flushing of data to the external mechanical disk drives is reduced by moving data from the first cache to the second cache until contents of the second cache reaches an allowed percentage usage threshold; and

wherein if there are no IO requests coming from the external hosts, wherein a storage device comprising the first cache and the second cache is idle, data is flushed to the external mechanical disk drives from the first cache.

13. A method as in claim 12 further comprising,

finding a location of any data using a cache information table that keeps track of a state of the first cache and a state of the second cache, and a physical address of the data in the first cache and a physical address of the data in the second cache;

wherein a valid LBA (Logical Block Address), dirty LBA, clean LBA, and invalid LBA within each cache line are tracked using LBA status bits;

wherein if the data is currently being transferred between the first cache and one of the external hosts, or between the first cache and the second cache, or between the first cache and the external mechanical disk drives, a direction of data is tracked using a cache sub-status, comprising of a source and a destination of the data transfer;

wherein an LBA already in transit, or being transferred between the first cache and the second cache or between one of the external hosts and the first cache or between the external mechanical 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 a location of the data within one of the external mechanical disk drives.

14. A method as in claim 12 further comprising,

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 and a previous state of the second cache, a relative position within a cache line of the data being transferred, a size of the data being transferred, and a source and a destination of the data being transferred.

15. A method as in claim 12 further comprising,

copying of data from the first cache to the second cache;

wherein when used cache lines in the first cache has reached a pre-defined percentage of the total cache lines available, copying of data to the second cache is initiated;

wherein if there are no IO requests coming from the external hosts, wherein a storage device comprising the first cache and second is idle, an actual transfer of data from the first cache to the second cache is executed; and

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

16. A method as in claim 12 further comprising,

performing a selection of cache lines for copying from the first cache to the second cache;

wherein cache lines containing a less recently used data are selected over cache lines containing more recently used data; and

wherein cache lines that can be transferred concurrently across multiple DMA paths between the first flash interface DMA controller and the second cache, using multiple DMA engines within the first flash interface DMA controller, are selected over among least recently used candidates.

17. A method as in claim 12 further comprising,

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

wherein the candidate cache lines containing less recently used data are selected over candidate cache lines containing more recently used data;

wherein candidate cache lines that form consecutive locations in the mechanical disk drives are selected among least recently used candidates so that a resulting access is a sequential type; and

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

18. A method as in claim 12 further comprising,

preventing data loss due to an external power source interruption by flushing dirty data in the first cache to the second cache comprising the non-volatile memory with a support of a backup power source;

and

keeping an updated copy of the cache information table in the non-volatile memory for retrieval of the information for the second cache upon a next boot-up of a storage device comprising the first cache and the second cache.

19. An article of manufacture, comprising:

a non-transient computer-readable medium having stored thereon instructions that are configured to;

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

store data in a second cache, wherein the second cache comprises a non-volatile memory;

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

wherein the first flash interface DMA controller copies data from the first cache to the second cache if a pre-defined threshold of unused cache lines is reached in the first cache;

transfer data between the first cache and a plurality of external hosts using a first group of IO interface DMA controllers;

transfer data between the first cache and a plurality of external mechanical disk drives using a second group IO interface DMA controllers; and

flush of data to the external mechanical disk drives;

wherein said flush of data to the external mechanical disk drives is reduced by moving data from the first cache to the second cache until contents of the second cache reaches an allowed percentage usage threshold; and

wherein if there are no IO requests coming from the external hosts, wherein a storage device comprising the first cache and second cache is idle, then data is flushed to the external mechanical disk drives from the first cache.