Hybrid storage device with three-level memory mapping

Patent metadata

Field	Value
Publication number	US-11630779-B2
Application number	US-202117528977-A
Country	US
Kind code	B2
Filing date	Nov 17, 2021
Priority date	May 31, 2017
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

A hybrid storage device with three-level memory mapping is provided. An illustrative device comprises a primary storage device comprising a plurality of primary sub-blocks; a cache memory device comprising a plurality of cache sub-blocks implemented as a cache for the primary storage device; and a controller configured to map at least one portion of one or more primary sub-blocks of the primary storage device stored in the cache to a physical location in the cache memory device using at least one table identifying portions of the primary storage device that are cached in one or more of the cache sub-blocks of the cache memory device, wherein a size of the at least one table is independent of a capacity of the primary storage device.

First claim

What is claimed is:

1. A device, comprising:
a primary storage device comprising a plurality of primary sub-blocks;
a cache memory device comprising a plurality of cache sub-blocks implemented as a cache for the primary storage device; and
a controller configured to implement a three-level map comprising:
a zero-level map identifying primary sub-blocks of the primary storage device having at least a portion thereof cached in one of the plurality of cache sub-blocks of the cache memory device, wherein a size of the zero-level map is independent of a capacity of the primary storage device, and
a two-level map mapping host page addresses to physical locations in the cache sub-blocks where data associated with each cached host page address resides, the two-level map formed by a plurality of second-level map pages, each of the plurality of second-level pages being associated with a respective one of a plurality of first-level map entries.

2. The device of claim 1 , wherein the zero-level map is implemented as a content addressable memory where an address of an entry identifies one of the plurality of cache sub-blocks of the cache memory device and where a content of the entry identifies the one or more primary sub-blocks of the primary storage device having at least a portion thereof stored in the cache sub-block.

3. The device of claim 1 , wherein the cache memory device comprises a solid-state drive (SSD) and wherein the primary storage device comprises one or more of a hard disk drive (HDD) and another solid-state drive.

4. The device of claim 1 , the controller further implementing a primary storage device-to-cache memory device mapper identifying where a given portion of the primary storage device is stored within one or more cache sub-blocks of the cache memory device, and wherein the primary storage device-to-cache memory device mapper provides an index into the two-level map.

5. The device of claim 1 , wherein the two-level map is recovered using data in the cache memory device and wherein the zero-level map is regenerated to obtain the mapping of the at least one portion of the one or more primary sub-blocks of the primary storage device stored in the cache to the physical location in the cache memory device.

6. The device of claim 1 , wherein the zero-level map further comprises a timestamp indicating when each cache sub-block was last accessed, the controller configured to evict a least recently used cache sub-block when the cache memory device reaches a predefined capacity threshold.

7. The device of claim 1 , wherein data within the primary storage device is promoted to the cache in the cache memory device based on an access frequency of the data.

8. The device of claim 7 , wherein an amount of the data from the primary storage device that is promoted to the cache in the cache memory device is configurable.

9. The device of claim 7 , wherein the controller is further configured to promote a plurality of portions of a plurality of random primary sub-blocks from the primary storage device to one cache sub-block in the cache memory device.

10. The device of claim 1 , wherein each of the plurality of second-level map pages comprises a plurality of entries, each second-level map page entry mapping a host page address to a physical location in an associated cache sub-block of the cache memory where data associated with the host page address resides.

11. The device of claim 10 , wherein the controller is configured to divide an incoming host page address by a number of entries in each secondary-level map page resulting in a quotient and remainder, the resulting quotient used as an index into the first-level map to select an entry and its associated second-level map page, and the resulting remainder used as an index of into the selected second-level map page to select the physical location in the cache memory from the second-level map page entry.

12. A method of mapping a host page address associated with data stored in a primary storage device comprising a plurality of primary sub-blocks to a physical location of the data cached in a cache memory device comprising a plurality of cache sub-blocks utilizing a three-level map, the method comprising:
mapping at least one of the plurality of primary sub-blocks storing the data associated with the host page address to one of the plurality of cache sub-blocks caching at least a portion of the data using a zero-level map identifying primary sub-blocks of the primary storage device having at least a portion thereof cached in one of the plurality of cache sub-blocks of the cache memory device, wherein a size of the zero-level map is independent of a capacity of the primary storage device; and
mapping the host page address to a physical location in the cache sub-block caching the at least a portion of the data using a two-level map mapping host page addresses to physical locations in cache sub-blocks where data associated with each cached host page address resides, the two-level map formed by a plurality of second-level map pages, each of the plurality of second-level pages being associated with a respective one of a plurality of first-level map entries.

13. The method of claim 12 , wherein the zero-level map is implemented as a content addressable memory where an address of an entry identifies one of the plurality of cache sub-blocks of the cache memory device and where a content of the entry identifies primary sub-block of the primary storage device having at least a portion thereof stored in the cache sub-block.

14. The method of claim 12 , wherein the zero-level map further comprises a timestamp indicating when each cache sub-block was last accessed, and wherein a least recently used cache sub-block is evicted when the cache memory device reaches a predefined capacity threshold.

15. The method of claim 12 , wherein data within the primary storage device is promoted to the cache in the cache memory device based on an access frequency of the data.

16. A non-transitory processor-readable storage media storing executable program code that, when executed by a controller of a hybrid storage device, causes the controller to:
map a first primary sub-block of a plurality of primary sub-blocks of a primary storage device, the first primary sub-block storing data associated with a host page address, to a first cache sub-block of a plurality of cache sub-blocks of a cache memory device implemented as a cache for the primary storage device, the first cache sub-blocks caching at least a portion of the data, using a zero-level map identifying primary sub-blocks of the primary storage device having at least a portion thereof cached in one of the plurality of cache sub-blocks of the cache memory device, wherein a size of the zero-level map is independent of a capacity of the primary storage device; and
map the host page address to a physical location in the cache sub-block caching the at least a portion of the data using a two-level map mapping host page addresses to physical locations in cache sub-blocks where data associated with each cached host page address resides, the two-level map formed by a plurality of second-level map pages, each of the plurality of second-level pages being associated with a respective one of a plurality of first-level map entries.

17. The non-transitory processor-readable storage media of claim 16 , wherein the zero-level map is implemented as a content addressable memory where an address of an entry identifies one of the plurality of cache sub-blocks of the cache memory device and where a content of the entry identifies the prim

Assignees

• Seagate Technology Llc

Inventors

• Kabra Nitin Satishchandra
• Ellis Jackson
• Pol Niranjan Anant
• Ish Mark

Classifications

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F12/0292

  using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10) · CPC title

• G06F12/0873 Primary

  Mapping of cache memory to specific storage devices or parts thereof · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F2212/217

  Hybrid disk, e.g. using both magnetic and solid state storage devices · CPC title