Hybrid storage device with three-level memory mapping

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.

SUMMARY

In some embodiments, a 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.

DETAILED DESCRIPTION

Illustrative embodiments will be described herein with reference to exemplary storage devices, such as hard disk drives (HDD) and/or solid state drives (SSD) and associated storage media, controllers, and other processing devices. It is to be appreciated, however, that these and other embodiments are not restricted to the particular illustrative system and device configurations shown. Accordingly, the term “hybrid storage device” as used herein is intended to be broadly construed, so as to encompass, for example, any storage device employing the hybrid storage, SSD caching and/or three-level mapping techniques described herein. Numerous other types of storage systems are also encompassed by the term “hybrid storage device” as that term is broadly used herein.

In one or more embodiments, improved hybrid storage techniques are provided that employ a cache memory device, such as an SSD memory, as a cache for a primary storage device, such as an HDD or another SSD. A hybrid controller in at least one embodiment maps sub-blocks of the primary storage device (e.g., an HDD or another SSD) that are stored in the cache to corresponding physical locations in the cache memory device using a three-level map identifying portions of the primary storage device that are cached in sub-blocks of the cache memory device. In some embodiments, a size of the three-level map is independent of a capacity of the primary storage device.

For example, in one or more embodiments, the disclosed hybrid storage system can be implemented as a solid state hybrid drive (SSHD) where the cache memory device is implemented as an SSD memory and the primary storage device is implemented as an HDD. In other exemplary embodiments of the disclosed hybrid storage system, the cache memory device can be implemented as an SSD memory, such as a multi-level cell (MLC) flash memory device or a triple-level cell (TLC) flash memory device, and the primary storage device can be implemented as another SSD memory, such as a quad-level cell (QLC) flash memory device or a TLC flash memory device, or any suitable combination of primary SSD memory and SSD cache.

In at least one embodiment, the three-level map comprises a zero-level map implemented as a content addressable memory (CAM), where an address of each entry identifies one sub-block of the cache memory device and where a content of each entry identifies at least portions of the sub-blocks of the primary storage device that are stored in corresponding sub-blocks of the cache memory device. In addition, a primary storage device-to-cache memory device mapper identifies where a given portion of the primary storage device is stored within one or more sub-blocks of the cache memory device. The primary storage device-to-cache memory device mapper provides an index into a two-level map.

In addition, in some embodiments, improved techniques are provided for recovery and coherence, as well as promotion and demotion of data into, and out of, the SSD cache, respectively.

FIG. 1is a block diagram of a hybrid storage system100, in an illustrative embodiment of the present disclosure. The exemplary hybrid storage system100comprises a hybrid drive controller200, discussed further below in conjunction withFIG. 2, and a number of storage components. In the exemplary embodiment described in the figures, the cache memory device is implemented as a solid state disk/drive130and the primary storage device is implemented as a hard disk drive140. As noted above, in other exemplary embodiments, the cache memory device can be implemented, for example, as a first SSD memory, such as an MLC or TLC flash memory device, and the primary storage device can be implemented as another SSD memory, such as a QLC or TLC flash memory device, or any suitable combination of primary SSD memory and SSD cache. The hybrid drive controller200is coupled to a host processor110. As discussed hereinafter, in one or more embodiments, the exemplary SSD130serves as a cache for the HDD140. In the exemplary embodiment ofFIG. 1, the SSD130and the HDD140are comprised of a plurality of sub-blocks of substantially equal size. For example, the SSD130and the HDD140are comprised of a plurality of 128 MB (megabyte) sub-blocks. A three-level map300, discussed further below in conjunction withFIG. 3, maps portions of the sub-blocks of the HDD140that are stored in the SSD cache130to a physical location in the SSD cache130.

As discussed hereinafter, the SSD cache130can be configured to temporarily store data of the HDD140. The HDD140includes a memory space that corresponds to a number of memory sectors, each sector addressable using a substantially unique host page address (HPA). The sectors of the HDD140are directly accessible by the host110using the HPAs, and thus the corresponding HPAs of the HDD140are referred to herein as host HPAs.

The host110sends memory access requests to the hybrid drive controller200to read or write data. The memory access requests may specify a host HPA range used for the operation of the memory access request. For example, a memory access request from the host110may request that a host HPA range be written to the hybrid storage system100and/or a memory access request may request that a host HPA range be read from the hybrid storage system100. The memory access requests received from the host110are managed by the hybrid drive controller200to cause data to be written to and/or read from the hybrid storage system100.

FIG. 2illustrates the hybrid storage system100ofFIG. 1in further detail, in an illustrative embodiment of the present disclosure. As shown inFIG. 2, the hybrid drive controller200may be coupled via one or more host interfaces210to the host110. According to various embodiments, the host interfaces210may be implemented as one or more of: a serial advanced technology attachment (SATA) interface; a serial attached small computer system interface (serial SCSI or SAS interface); a (peripheral component interconnect express (PCIe) interface; a Fibre Channel interface; an Ethernet Interface (such as 10 Gigabit Ethernet); a non-standard version of any of the preceding interfaces; a custom interface; or any other type of interface used to interconnect storage and/or communications and/or computing devices. For example, in some embodiments, the hybrid drive controller200includes a SATA interface and a PCIe interface.

The hybrid drive controller200is further coupled via one or more device interfaces250to one or more storage devices, such as SSD130and HDD140. According to various embodiments, device interfaces250are one or more of: an asynchronous interface; a synchronous interface; a double data rate (DDR) synchronous interface; an ONFI (Open NAND Flash Interface) compatible interface, such as an ONFI 2.2 compatible interface; a Toggle-mode compatible non-volatile memory interface; a non-standard version of any of the preceding interfaces; a custom interface; or any other type of interface used to connect to storage devices.

The200may have one or more processing modules230, such as data processing modules and device management modules, as would be apparent to a person of ordinary skill in the art.

As noted above, in one or more embodiments, the three-level map300, discussed further below in conjunction withFIG. 3, maps portions of the sub-blocks of the HDD140stored in the SSD cache130to a physical location in the SSD cache130.

For additional details regarding suitable implementations of the hybrid drive controller200, see, for example, U.S. Pat. No. 9,216,633, entitled “Flash Translation Layer With Lower Write Amplification,” and/or United States Published Patent Application No. 2015/0058527, filed Aug. 20, 2013, entitled “Hybrid Memory With Associative Cache,” each assigned to the assignee of the present application and incorporated by reference herein.

FIG. 3illustrates the three-level map300ofFIGS. 1 and 2in further detail, according to some embodiments of the disclosure. In one or more embodiments, the three-level map300may be implemented as a hardware translation layer or firmware, for mapping HDD addresses to SSD addresses.

As shown inFIG. 3, the exemplary three-level map300comprises a zero-level map (ZLM)325, a first-level map (FLM)335and a second-level map (SLM)340. The example ofFIG. 3assumes that 128 MB sub-blocks of the HDD140are mapped to 128 MB sub-blocks of the SSD130. In further implementations, however, any block size can be selected, for example, to optimize workloads. In addition, in the example ofFIG. 3, the exemplary SSD cache130has a capacity of 128 GB and the HDD140has a capacity of 16 TB.

In some embodiments, a given application will determine the granularity of the SSD/HDD sub-blocks, for example, depending upon Promotion and Demotion time targets without affecting host bandwidth. Based on the granularity, the number of sub-blocks for a SSD cache capacity and HDD capacity will be calculated.

Typically, the various tables (or portions thereof) of the three-level map300are stored in on-chip SRAM (Static Random Access Memory) or in a DRAM (Dynamic Random Access Memory) for best performance and lower latency to access the data by the host110. Since the capacity of the SSD130is very small compared with the expected capacity of the HDD140, the metadata associated with the three-level map300can be stored in on-chip SRAM (without a need for external DRAM memory for normal operations).

It is estimated that 2 GB of map metadata is needed for each 1 TB (terabyte) of storage capacity, adding significant cost and power considerations. Among other benefits, the three-level map300grows in proportion to the size of the cache (capacity of SSD130) and is independent of the capacity of the HDD140. In this manner, the same hybrid drive controller200can serve future (expanded) generations of hybrid storage systems.

In one or more embodiments, the exemplary zero-level map325is implemented as a content addressable memory (CAM) and comprises an entry for each sub-block of the SSD130, where each ZLM entry identifies the sub-block (if any) of the HDD140that is stored in the corresponding sub-block of the SSD130. For example, each entry address within the zero-level map325will reflect the SSD sub-block number. Thus, the zero-level map325address will point to the corresponding sub-block of the SSD130and the content of an entry in the zero-level map325will specify the corresponding HDD sub-block stored in the entry. The exemplary zero-level map325isolates the HPA addressing of the SSD130from the HPA of the HDD140.

Generally, when the host110writes to (or reads from) the HDD140using a host page address (HPA) identifying a portion of the HDD140, the identifier of the sub-block that includes the specified HPA is searched in the zero-level map325to determine if the HDD sub-block is already cached in the SSD130(or stored in the HDD140). For example, for a 1 TB/1024 GB HDD, and a block size (in zero-level map325) of 128 MB (0.128 GB), each sub-block in the HDD is equal to HDD Capacity (1 TB)/Blk Size (128 MB).

If the HDD sub-block is not found within the zero-level map325(shown inFIG. 3as HDD_Hit_ZLM355) then the entire content of the indicated HDD sub-block is either empty or inside the HDD140and all such I/O requests are directed directly to HDD for further handling (and outside the scope of the present disclosure). If, however, the HDD sub-block is found within the zero-level map325(shown inFIG. 3as ZLM_SSD_Hit) (e.g., when access to the zero-level map325returns a valid SSD sub-block number) then either the sub-block (or a portion thereof) is in the SSD Cache130, resulting in an identifier of the SSD_SubBlk_# storing the target HDD sub-block. As shown inFIG. 3, an HDD-SSD HPA Mapper345translates the SSD_SubBlk_# storing the target HDD sub-block to an HPA within the SSD sub-block where the desired data is stored. The search is then forwarded to the FLM table335to determine if the data is within the HDD140or the SSD130.

As shown inFIG. 3, the HPA of the SSD130(provided by the zero-level map325when the HDD sub-block is in the SSD cache130) is mapped to a physical location in the SSD130using an SSD two-level map330. The SSD two-level map330comprises the first-level map (FLM)335and the second-level map (SLM)340. In one or more embodiments, the first-level map335and second-level map340may be implemented using the techniques described in U.S. Pat. No. 9,216,633, entitled “Flash Translation Layer With Lower Write Amplification,” assigned to the assignee of the present application and incorporated by reference herein.

Generally, the FLM335and SLM340are indexed using a quotient and a remainder, respectively, (not shown inFIG. 3) generated by an integer divider based on a number of SLM entries per SLM page, as described in U.S. Pat. No. 9,216,633. In the SSD two-level map330ofFIG. 3, “CS” indicates the Cache State and “EPA” indicates an E-Page Address. In one or more embodiments, an E-page corresponds to a physical location within the NAND media where the HPA resides. The EPA represents the particular NAND page address within a specific NAND die, among multiple NAND dies, and in a NAND block containing multiple pages spread across substantially all NAND dies.

In some embodiments, a 128 GB capacity SSD cache130will need 0.256 GB of total map memory (FLM335and SLM340) plus the zero-level map325, as described above (for an exemplary rule of thumb of 2 GB of MAP (two-level) for 1 TB of main memory, where FLM can be on chip memory). Storing the tables of the three-level map300on silicon is thus feasible and saves the cost of having an external non-volatile memory as well.

The hybrid drive controller200optionally operates with multiple modes, where in an “SSD only” storage system100, the HDD HPA-to-SSD HPA mapping is simply bypassed; and where the hybrid functionality is enabled for a hybrid storage system100comprising both SSD and HDD.

For a read operation from the host110, the three-level map300is evaluated to determine where the target data is located (HDD or SSD). Likewise, for a write operation, the three-level map300is evaluated to determine where to write the data (e.g., by identifying available sub-blocks).

Since the number of sub-blocks within the HDD140is typically significantly more than the number of sub-blocks in the SSD Cache130, in one or more embodiments, the zero-level map325will only have entries equal to the number of sub-blocks in the SSD cache130. As the SSD cache130begins to fill, more HDD sub-blocks are allocated inside the SSD cache130. Beyond a threshold (shown as Demote Threshold365inFIG. 3), some sub-blocks must be evicted that are least used by the Host110from the SSD cache130to the HDD140, in order to allocate sub-blocks of the SSD cache130for new “hot” data that is coming from the Host110. Thus, the zero-level map325also implements a side timestamp table350, for example, in shared/dedicated RAM memory, with an entry for each sub-block in the SSD130. The content of each entry in the table350is the latest timestamp (shown as real time clock (RTC)_Time_Stamp375inFIG. 3) when the Host110last accessed the corresponding sub-block. The timestamp table350is optionally stored separately from the zero-level map325to keep the content addressable memory design manageable and the Si are cost reasonable.

As the zero-level map325is allocated to sub-blocks of the SSD130, beyond the system-defined Demote Threshold365, detected at step370, the zero-level map325, implemented either in firmware or hardware, will issue an SSDSubBlockFill_Threshold_Hit to the firmware along with the sub-block number of the oldest SSD sub-block from the timestamp table350. The firmware will use this information to start a demote operation for each identified demoted sub-block to the HDD140and thereby free additional sub-blocks in the SSD130, thereby making the freed sub-block available for new “hot” data coming from the Host110.

Promotions

As the Host110begins to frequently access data that resides within the HDD140, such data will then need to be promoted to the SSD cache130. When the entire sub-block is within the HDD140, the exemplary firmware promotion engine will quickly allocate the SSD sub-block to such data in the zero-level map325and then begins the promotion of that data with a granularity offered by one FLM entry (number of entries within SLM). The promotion can begin anywhere in the sub-block, as per host access of the data.

The Data Range within the sub-block can be immediately promoted to the SSD cache130without having to completely transfer the sub-block worth of data (128 MB in the present example ofFIG. 3) thereby making quick data promotions and avoiding long access latencies associated with moving the entire sub-block to the SSD cache130before marking that the data is in the SSD cache130.

As shown inFIG. 3and as discussed further below in conjunction withFIG. 4, a portion (e.g., 25%) of the exemplary zero-level map325is employed as a promotion table328where the sub-block entries are used during promotions from the HDD140to the SSD cache130. In one or more embodiments, the sub-block entries used for promotion may be some dedicated sub-blocks around the bottom of the ZLM table325or they could be spread randomly across the ZLM table325, as needed, as would be apparent to a person of ordinary skill in the art. However, the percentage of the ZLM promote table can be a fraction of the full ZLM table in order to keep the data structures small which can reasonabily fit on an on-chip SRAM and do not need an external storage solution to maintain this information. The table325in the example ofFIG. 3assumes that some bottom entries of the ZLM CAM325are dedicated for promotion purposes, for simplicity and clarity of illustration.

One or more embodiments of the disclosure recognize that an entire sub-block of data may not be “hot” within a given sub-block, and promoting the entire sub-block may affect the media endurance of the non-volatile memory because of increased write amplification due to promotions of the entire sub-blocks. In addition, in some applications, the data within a given sub-block may be sparse (e.g., with some logical block address (LBA) ranges written by the Host110and some LBA ranges that are not written by the Host110).

To avoid such drawbacks, the exemplary three-level map300ofFIG. 3incorporates an optional extension of the zero-level map325so that promotion granularity can be as small as a HPA, while still allowing the benefits of dynamic sub-block allocation optimization.

FIG. 4illustrates a variation400of the zero-level map325ofFIG. 3, according to one or more embodiments of the disclosure. Among other benefits, the exemplary optional zero-level map variation400demonstrates promotion granularity as small as a single host page address (4 KB (kilobytes) in the above example). For example, if a number of 4 KB host pages are accessed in a number of random HDD sub-blocks, the multiple 4 KB host pages can be mapped to a single SDD sub-block, as discussed further below.

The exemplary zero-level map variation400optionally employs a portion (e.g., 25%) of the zero-level map420as a Promote_CAM425. The entries in the Promote_CAM425are used during promotions from the HDD140to the SSD cache130. The Promote_CAM425portion of the zero-level map420will also have a secondary variable length table450with an entry for each sub-block. The secondary table450records a starting HPA address and length of the data promoted from the HDD140to an SSD sub-block. The table450also records the SSD_SubBlk identifier where this data is actually written to the SSD sub-block. In this manner, a sub-block can slowly fill up to its full capacity within the SSD sub cache130and once that is done, then the sub-block is freed from the Promote ZLM CAM425and moved to primary zero-level map420, for example, by the firmware.

It may happen that only a few HPAs within a given sub-block ever becomes “hot,” whereas the remaining portions of the given sub-blocks within that space remains cold. In such situations, the same promote CAM sub-block can be used to collect “hot” data from multiple HDD sub-blocks and aggregated into a single SSD sub-block as long as the HPA promoted to one SSD sub-block from different HDD/SSD sub-blocks are non-overlapping, thereby greatly improving the efficiency of the granularity of the zero-level map420. In addition, related promotion/demotions tradeoffs are improved, while significantly reducing the non-volatile memory (NVM) SSD write amplification. Most of these features can be implemented either in hardware or firmware (FW) and, in one or more embodiments, have full FW overide control when implemented in hardware, full hardware acceleration capability can be available at the same time firmware can come back for any stage to override the hardware behavior.

For additional details regarding suitable implementations of the promotion and/or demotion aspects of hybrid drive controller200, see, for example, United States Published Patent Application No. 2015/0058527, filed Aug. 20, 2013, entitled “Hybrid Memory With Associative Cache,” assigned to the assignee of the present application and incorporated by reference herein.

Recovery and Coherence

Generally, the three-level map300ofFIG. 3can be recovered on power-up by reading the pages in the SSD130to obtain the HPAs of the cached HDD sub-blocks to rebuild the tables of the three-level map300. In event of a power failure, the contents of the three-level map300will be lost and the mapping between sub-blocks of the HDD140and sub-blocks of the SSD130is also lost. In one or more embodiments, the exemplary three-level map300is fully coherent and allows rebuilding the maps of the three-level map300from the user data itself in the SSD130, after a power failure event occurs. Since the Host HPA information is stored along with the data in the SSD130, the FLM335and SLM340can be built after a power failure. Once the FLM335and SLM340are regenerated, along with the Host LBA number information from the SSD cache130, the zero-level map325can then be reprogrammed back to the desired HDD to SSD HPA Mapping, even if this mapping is not the same as the block mapping that was present before the power failure event. In this manner, the zero-level map325is immune to power failure events and truly self-healing. Furthermore, complex firmware coherency and recovery overheads to rebuild the zero-level map325after a power failure event are avoided.

For additional details regarding recovery and coherence of the three-level map300, see, for example, U.S. Pat. No. 9,216,633, entitled “Flash Translation Layer With Lower Write Amplification,” assigned to the assignee of the present application and incorporated by reference herein.

Caching Data Structures for Tracking Data Hotness and/or Coldness

FIG. 5illustrates a sample promotion table500, according to one or more embodiments of the disclosure. The illustrative promotion table500serves as a hotness tracker to monitor when data should be promoted from the HDD140to the SSD cache130. As shown inFIG. 5, the promotion table500records a timestamp of a most recent access of a given sub-block, as well as a write count and read count for the respective sub-block. The promotion table500can be stored, for example, in local CPU DRAM. The data that is already in the SSD cache130is already “hot” until it become cold via the demotion timestamp table350in the three-level map300. Data that is getting “hot” from the HDD140is instantaneous and hence, in one or more embodiments, the table500only needs to cover the instantaneous data temperature changes within the HDD and not record information about the entire cold data within the HDD140. With the approach shown inFIG. 5, the caching structure can be implemented within CPU DRAM, thereby saving on Si cost and power, and access latencies seen by the host110. In one or more embodiments, oldest entries (e.g., Least Recently used) in the promotion table500are overwritten.

A coldness tracker can be implemented within the condensed zero-level map325on a sub-block basis.

CONCLUSION

It should be understood that the particular hybrid storage arrangements illustrated inFIGS. 1 through 5are presented by way of illustrative example only, and should not be construed as limiting in any way. Numerous alternative configurations of system and device elements and associated processing operations can be used in other embodiments.

Illustrative embodiments disclosed herein can provide a number of significant advantages relative to conventional arrangements.

For example, one or more embodiments provide significantly reduced write amplification. The disclosed three-level maps300provide a translation from, for example, logical block addresses (LBAs) in a logical block address space (such as used by a host) to physical addresses in a non-volatile memory (NVM), such as a solid state disk/drive (SSD) or a hard disk drive (HDD). SSDs using some NVM types such as NAND flash use garbage collection (or recycling) to reclaim free space created when an logical block address (LBA) is over-written with new data (rendering a previous physical location associated with that LBA unused). Garbage collection causes write amplification—a multiplicative factor on the amount of host data written versus the amount of data written to NVM. There are multiple components of write amplification, including a map component of write amplification (termed map write amplification). The map write amplification arises from a need to save the three-level maps300in a non-volatile memory and any necessary recycling of the three-level maps300. In storage devices that reduce the user data, the map write amplification is a larger fraction of the total write amplification, since the data write amplification is decreased.

In some embodiments, improved hybrid storage techniques are provided that employ a cache memory device, such as an SSD, as a cache for another storage device, such as a HDD or another SSD. A hybrid controller in at least one embodiment maps sub-blocks of the HDD storage device that are stored in the SSD cache to corresponding physical locations in the SSD memory device using a three-level map identifying portions of the HDD storage device that are cached in sub-blocks of the SSD memory device. In some embodiments, a size of the three-level map is independent of a capacity of the first storage device. In addition, in some embodiments, improved techniques are provided for recovery and coherence, as well as promotion and demotion of data into, and out of, the SSD cache, respectively.

Some illustrative embodiments of a processing platform that may be used to implement at least a portion of an information processing system comprises cloud infrastructure including virtual machines. The cloud infrastructure further comprises sets of applications running on respective ones of the virtual machines. These and other types of cloud infrastructure can be used to provide what is also referred to herein as a multi-tenant environment. One or more system components such as hybrid drive controller200, or portions thereof, are illustratively implemented for use by tenants of such a multi-tenant environment.

The disclosed hybrid storage arrangements may be implemented using one or more processing platforms. One or more of the processing modules or other components may therefore each run on a computer, storage device or other processing platform element. A given such element may be viewed as an example of what is more generally referred to herein as a “processing device.” An exemplary processing platform comprises at least a portion of the given system and includes at least one processing device comprising a processor coupled to a memory. The processor may comprise a microprocessor, a microcontroller, an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other type of processing circuitry, as well as portions or combinations of such circuitry elements. The memory may comprise random access memory (RAM), read only memory (ROM) or other types of memory, in any combination. The memory and other memories disclosed herein should be viewed as illustrative examples of what are more generally referred to as “processor-readable storage media” storing executable program code of one or more software programs. The exemplary processing device may also comprise network interface circuitry, which is used to interface the processing device with a network and other system components, and may comprise conventional transceivers.

Also, numerous other arrangements of computers, servers, storage devices or other components are possible in the hybrid storage system. Such components can communicate with other elements of the hybrid storage system over any type of network or other communication media.

As indicated previously, components of an information processing system as disclosed herein can be implemented at least in part in the form of one or more software programs stored in memory and executed by a processor of a processing device. For example, at least portions of the functionality of the three-level mapping process ofFIG. 3are illustratively implemented in the form of software running on one or more processing devices.