Caching of data in data storage systems by managing the size of read and write cache based on a measurement of cache reliability

Description

BACKGROUND

1. Technical Field

This disclosure relates to disk drives, including but not limited to hybrid hard drives. More particularly, the disclosure relates to systems and methods for caching data in solid-state memory of a disk drive.

2. Description of the Related Art

Non-volatile memory devices typically provide better performance for reading and writing data than magnetic media. Accordingly, in storage devices it is advantageous to utilize non-volatile memory for storing data. However, a problem with using non-volatile memory for storing data is that reliability of non-volatile memory degrades over time.

Non-volatile memory devices can typically endure a limited number of write cycles over their useful life. Various factors can contribute to data errors in non-volatile memory devices, which include charge loss or leakage over time, read disturb, and device wear caused by program-erase cycles. Non-volatile memory degradation can cause stored data to be corrupted. For example, when the number of bit errors on a read operation exceeds the ECC (error correction code) correction's capability of the non-volatile memory device, a read operation fails.

BRIEF DESCRIPTION OF THE DRAWINGS

Systems and methods that embody the various features of the invention will now be described with reference to the following drawings, in which:

FIG. 1 is a block diagram illustrating a storage device that implements improved caching mechanisms in accordance with one embodiment of the invention.

FIG. 2 is a flow diagram illustrating improved caching mechanisms in accordance with one embodiment of the invention.

FIG. 3 is a flow diagram illustrating improved caching mechanisms in accordance with another embodiment of the invention.

FIGS. 4-6 illustrate several caching policy adjustments in accordance with some embodiments of the invention.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

While certain embodiments are described, these embodiments are presented by way of example only, and are not intended to limit the scope of protection. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the scope of protection.

Overview

Non-volatile memory devices (NVM) (e.g., flash memory and other types of solid-state memory devices) store information in an array of memory cells. In single-level cell (SLC) non-volatile memory, each cell stores a single bit of information. In multi-level cell (MLC) non-volatile memory, each cell stores two or more bits of information. Non-volatile memory has a limited usable life that is measured by the number of times data can be written to a specific NVM location. As NVM wear increases (e.g., number of program-erase cycles increases), the reliability and data retention of the NVM decreases. MLC non-volatile memory (e.g., MLC NAND) is cheaper than SLC non-volatile memory, but tends to have slower access time, lower endurance, and lower data retention.

To improve performance, some disk drives take advantage of the speed of non-volatile memory to store certain data in non-volatile memory. This data can include frequently accessed data and data accessed at start-up. Disk drives that comprise non-volatile memory cache in addition to magnetic storage are referred to as “hybrid hard disk drives” or “hybrid hard drives” throughout this disclosure. In some hybrid hard drives, MLC NVM can be a good choice for cache storage due to its low cost and high storage density. Non-volatile memory is typically used both as read cache (e.g., a copy of data exists in magnetic storage) and write cache (e.g., data stored in NVM cache is the most recent version than data stored in magnetic storage).

In some embodiments of the present invention, a caching policy of a hybrid hard drive is varied as the NVM wears out such that a larger portion of the NVM is used as read cache and a smaller portion of the NVM is used as write cache. In some embodiments, when the reliability (e.g., retention) of the NVM device falls below a minimum threshold, the non-volatile memory is used exclusively as a read cache. In this mode, hybrid hard drives continue to derive a performance advantage from the NVM, but if a NVM read operation fails, no user data is lost since an identical copy can be read from the magnetic storage. In some embodiments, varying the caching policy allows the hybrid hard drive to continue providing improved performance as the NVM nears the end of its usable life because the NVM can still be used for storing frequently read data. In addition, storing data in the non-volatile memory can result in improved power consumption.

System Overview

FIG. 1 illustrates a storage system 100 that implements improved caching mechanisms in accordance with one embodiment of the invention. As shown, a storage system 120 (e.g., a hybrid hard drive) includes a controller 130, non-volatile storage memory module 150, which comprises cache 152, and magnetic storage module 160, which comprises magnetic media 164 (e.g., a magnetic disk). The non-volatile memory module 150 can comprise one or more non-volatile solid-state memory arrays. The controller 130 can be configured to receive data and/or storage access commands from a storage interface module 112 (e.g., a device driver) in a host system 110. Storage access commands communicated by the storage interface 112 can include write and read commands issued by the host system 110. Read and write commands can specify a logical block address in the storage system. The controller 130 can execute the received commands in the non-volatile memory module 150 or in the magnetic storage module 160. In one embodiment, the controller can include memory (e.g., DRAM) for storing data, such as system tables.

The non-volatile memory module 150 is preferably implemented using NAND flash memory devices. Other types of solid-state memory devices can alternatively be used, including flash integrated circuits, Chalcogenide RAM (C-RAM), Phase Change Memory (PC-RAM or PRAM), Programmable Metallization Cell RAM (PMC-RAM or PMCm), Ovonic Unified Memory (OUM), Resistance RAM (RRAM), NAND memory, NOR memory, EEPROM, Ferroelectric Memory (FeRAM), or other discrete NVM (non-volatile memory) chips. In one embodiment, the memory devices are preferably MLC devices, although SLC memory devices, or a combination of SLC and MLC devices may be used in some embodiments.

Storage system 120 can store data communicated by the host system 110. That is, the storage system 120 can act as memory storage for the host system 110. To facilitate this function, the controller 130 can implement a logical interface. Logical interface can present to the host system 110 storage system's memory as a set of logical addresses (e.g., contiguous address) where data can be stored. Internally, the controller 130 can map logical addresses to various physical memory addresses in the magnetic media 164 and/or the non-volatile memory module 150.

In one embodiment, at least a portion of the non-volatile memory module 150 can be used as cache 152. In another embodiment, entire non-volatile memory module 150 can be used as cache. The controller 130 can store data communicated by the host system 110 in the non-volatile memory. In one embodiment, non-volatile memory cache 152 can be used as a read cache and/or a write cache. When the non-volatile memory is used as a read cache, a copy of data also exists in the magnetic storage 160. When non-volatile memory is used as a write cache, data stored in non-volatile memory is a more recent version than data stored in the magnetic storage 160. To improve performance of the storage system 120 and/or host system 110, in some embodiments, various types of data can be stored in non-volatile memory cache, including frequently accessed data, data accessed at start-up (e.g., following a reset or power down), system data, sequentially accessed data, etc.

Variable Caching Policy

FIG. 2 illustrates improved caching mechanisms in accordance with one embodiment of the invention. The process 200 can be implemented by the controller 130 of a storage system 120, such as a hybrid disk drive. The process 200 starts in block 202, where a set of address ranges (e.g., logical address ranges of the storage system) frequently accessed by the host system are identified. In one embodiment, frequency of access can be determined by maintaining a list of access frequencies and sorting the list to determine address ranges having the highest access frequencies. For example, the list of access frequencies can comprise access counts, which are incremented upon receiving a read and write commands communicated by the host system 110. The list of access frequencies can be sorted and frequently accessed address ranges can be determined by comparing access counts to an access frequency threshold. Frequently accessed address ranges can be identified as those address ranges that are accessed in excess of the access frequency threshold. As another example, the list of access frequencies can be sorted and a portion of highest frequently accessed ranges (e.g., top 5%, 10%, 15%, etc.) can be identified as frequently accessed ranges. In one embodiment, the list of access frequencies is maintained in a sorted order.

In block 204, the process determines which of the address ranges from the set identified in block 202 are frequently written by the host system. In one embodiment, frequency of writing can be determined by maintaining a list of write access frequencies. For example, the list of write access frequencies can comprise write access counts, which are incremented upon receiving write commands communicated by the host system 110. The list of write access frequencies can be sorted and frequently written address ranges can be determined by comparing write access counts to a write access frequency threshold, which can be the same or different value than the access frequency threshold. Frequently written address ranges can be identified as those address ranges that are written in excess of the write access frequency threshold. As another example, the list of write access frequencies can be sorted and a portion of highest frequently accessed ranges (e.g., top 5%, 10%, 15%, etc.) can be identified as frequently written ranges. In one embodiment, the list of write access frequencies is maintained in a sorted order.

In block 206, the process determines the relative caching priority of each address range identified in block 202. In one embodiment, the process determines a metric (score) corresponding to the frequency of access identified in block 202. This is described in co-pending patent application Ser. No. 13/301,543y, entitled “DISK DRIVE DATA CACHING USING A MULTI-TIERED MEMORY,” the disclosure of which is hereby incorporated by reference in its entirety. In one embodiment, the metric (score) can correspond to the number of access commands (e.g., read and write commands) issued by the host system to the address range.

In block 208, based on the write frequency identified in block 204 and on the remaining usable life of the non-volatile memory, the process adjusts the relative caching priority determined in block 206. In one embodiment, the write frequency is compared to a threshold and the relative caching priority is decreased if the threshold is exceeded. The threshold can correspond to the remaining usable life of the non-volatile memory.

In one embodiment, the remaining usable life can correspond to the number of remaining program-erase cycles that the NVM can endure. For example, certain types of NAND NVM can endure between 3,000 and 100,000 program-erase cycles. In another embodiment, the remaining usable life (or reliability measure) can be determined based partly or wholly on the total number of bytes that have been written to non-volatile memory.

In one embodiment, the remaining usable life (or reliability measure) can be determined based partly or wholly on a number of errors encountered when reading data stored in non-volatile memory. Non-volatile memory can degrade and wear out, which can cause corruption of stored data. With NAND flash memory, for example, data corruption can be caused by a program disturb (e.g., data not intended to be programmed is nonetheless changed by a program operation directed to adjacent NVM blocks), read disturb (e.g., data not intended to be read is changed by a read operation directed to adjacent NVM pages), data loss (e.g., charge loss over an extended storage period), etc. Various error correction code (ECC) mechanisms can be used for detecting and correcting data corruption. In one embodiment, the number of bit corruptions detected and/or fixed by the ECC mechanism can be monitored during the execution of read operations. The number of bit corruptions can provide a measure of remaining usable life of non-volatile memory. This measure can be determined, for example, by comparing the average number of bits corruptions to a set of tiered thresholds.

The remaining usable life (or reliability measure) can also be determined based partially or wholly on voltage threshold levels or voltage reference values selected or determined when reading data from MLC flash memory. The remaining usable life can correspond to a voltage threshold level selected from a range of possible threshold levels during reading data so that data errors are reduced or minimized. In another embodiment, the remaining usable life can correspond to the adjustment of programming algorithm parameters (e.g., programming time, erase time, etc.) when storing data in non-volatile memory.

In one embodiment, the remaining usable life can be determined by a signal processing subsystem. The non-volatile memory module 150 can include a bridge device coupled with non-volatile memory module via an interface such as ONFI. The bridge device can be further configured to communicate with the controller 130 over a high speed interface such as PCIe and to provide to the controller physical, page-level access/control to non-volatile memory. The bridge device can perform basic signal processing and channel management of non-volatile memory. This architecture is described in a co-pending patent application Ser. No. 13/226,393, entitled “SYSTEMS AND METHODS FOR AN ENHANCED CONTROLLER ARCHITECTURE IN DATA STORAGE SYSTEMS,” filed Sep. 6, 2011, the disclosure of which is hereby incorporated by reference in its entirety. In other embodiments, a bridge device may not be used and the non-volatile memory module 150 may be managed directly by the controller 130.

In block 210, the process determines whether the adjusted relative caching priority determined in block 208 exceeds a threshold. In one embodiment, the threshold can correspond to the lowest relative caching priority of an entry that is already stored in the NVM. In another embodiment, a predetermined threshold can be used. In another embodiment, the threshold can be adjusted (e.g., decreased or increased) based on the remaining usable life of the non-volatile memory. If the threshold is exceeded, the process transitions to block 212 where it writes data to the non-volatile memory. Data can correspond to data stored in the address range identified in block 204. If the threshold is not exceeded, the process 200 returns to block 204, where the next address range from the set is processed. Similarly, the process 200 returns to block 204 after storing data in 212. In one embodiment, the process terminates when there are no more remaining address ranges in the set identified in block 202.

Candidate Lists

In some embodiments, data corresponding to address ranges that are frequently accessed can be placed in one or more candidate lists. FIG. 3 illustrates a flow diagram 300 of improved caching mechanisms in accordance with another embodiment of the invention. As is illustrated, two candidate lists 310 and 320 are maintained. List 310 stores data that is frequently read by the host system and list 320 stores data that is frequently written by the host system. Entries 312, 314, 316, and 318 of the list 310 stores frequently read data that corresponds to various address ranges. For example, entry 312 stores data that corresponds to frequently read address range X, entry 314 stores data that corresponds to frequently read address range Y, etc. Entries 312, 314, 316, and 318 stores data along with information identifying each corresponding address range. In one embodiment, the lists 310 and 320 are mutually exclusive, that is, they have no common entries. In other words, an entry can be either in list 310 or 320, but not in both lists.

Similarly, entries 322, 324, 326, and 328 of the list 320 stores frequently written data corresponding to various address ranges. For example, entry 322 stores data that corresponds to frequently read address range A, entry 324 stores data that corresponds to frequently read address range B, etc. Entries 322, 324, 326, and 328 stores data along with information identifying each corresponding address range.

In block 330, the process 300 selects a ratio of entries from candidate lists 310 and 320 that are written to non-volatile memory. For example, the ratio can be selected such that 40% of frequently written data is stored in the non-volatile memory. Accordingly, and the process 300 selects two entries from the candidate list 320 for every five entries selected from the candidate list 310. The ratio of block 330 is adjusted based on the remaining usable life of non-volatile memory. Thus, the portion of non-volatile memory used for storing frequently read data is increased in relation to the portion used for storing frequently written data.

In one embodiment, entries in the candidate lists can be ordered according to their relative caching priorities determined in block 206 of FIG. 2. Entries are selected according to the relative caching priority. For example, entries with higher relative caching priorities are selected and written to non-volatile memory before entries with lower relative caching priorities are selected and written.

Caching Policy Adjustment

In some embodiments, selecting the ratio in block 330 of FIG. 3 or adjusting the relative threshold in block 208 of FIG. 2 can be performed according to the following policies.

FIG. 4 illustrates linear caching policy adjustment 400 in accordance with one embodiment of the invention. X-axis indicates the usable remaining life of non-volatile memory and y-axis indicates the ratio of non-volatile memory cache used for frequently written data. As is illustrated by line 402, the ratio starts at 60% when substantially full life of non-volatile memory remains and is decreased linearly as the usable remaining life of non-volatile memory decreases.

FIG. 5 illustrates piecewise linear caching policy adjustment 500 in accordance with another embodiment of the invention. X-axis indicates the usable remaining life of non-volatile memory and y-axis indicates the ratio of non-volatile memory cache used for frequently written data. As is illustrated by line 502, the ratio starts at 60% when substantially full life of non-volatile memory remains and continues to stay at 60% until a retention threshold is reached at 504. At this point, as is illustrated by line 506, the ratio is decreased linearly as the usable remaining life of non-volatile memory decreases.

FIG. 6 illustrates non-linear caching policy adjustment 600 in accordance with another embodiment of the invention. X-axis indicates the usable remaining life of non-volatile memory and y-axis indicates the ratio of non-volatile memory cache used for frequently written data. As is illustrated by line 602, the ratio starts at 60% when substantially full life of non-volatile memory remains and is decreased linearly as the usable remaining life of non-volatile memory decreases. When a first retention threshold 604 is reached, the ratio is being decreased according to a non-linear curve 606. When a second retention threshold 608 is reached, the ratio is set to zero. That is, no frequently written data is stored in non-volatile memory, and the entire non-volatile memory cache is used to store frequently read data. The ratio stays at zero until the end of non-volatile memory's usable life is reached in 610.

In another embodiment, caching policy can be adjusted according to a characterization of data stored in non-volatile memory. For example, at least some frequently written data stored in the non-volatile memory cache can be determined to be important to the overall performance of the storage and/or host systems. In such case, the policy may be adjusted in accordance with the goal of retaining this type of frequently written data in non-volatile memory. As another example, a portion of non-volatile memory cache can be reserved for certain data, such as data accessed at system start-up.

CONCLUSION

In some embodiments, varying a caching policy allows hybrid hard drives to improve performance by utilizing non-volatile memory throughout its entire usable life. As the non-volatile memory degrades (e.g., looses data retention), caching policy can be varied to store less frequently written data and more frequently read data. Accordingly, hybrid hard drives can continue to utilize non-volatile memory for caching even as retention of non-volatile memory degrades. The ratio of frequently written and frequently read data stored in non-volatile memory can be adjusted as non-volatile memory degrades. Toward the end of usable life of non-volatile memory, the caching policy can be adjusted to store frequently read data in non-volatile memory. Accordingly, performance improvements and slower degradation of non-volatile memory can be attained.

Other Variations

As used in this application, “non-volatile memory” typically refers to solid-state memory such as, but not limited to, NAND flash. However, the systems and methods of this disclosure may also be useful in more conventional hard drives and hybrid hard drives including both solid-state and hard drive components. The solid-state storage devices (e.g., dies) may be physically divided into planes, blocks, pages, and sectors, as is known in the art. Other forms of storage (e.g., battery backed-up volatile DRAM or SRAM devices, magnetic disk drives, etc.) may additionally or alternatively be used.

Those skilled in the art will appreciate that in some embodiments, other types of caching policies can be implemented. In addition, the actual steps taken in the processes shown in FIGS. 2-3 may differ from those shown in the figures. Depending on the embodiment, certain of the steps described above may be removed, others may be added. Accordingly, the scope of the present disclosure is intended to be defined only by reference to the appended claims.

While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of protection. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the protection. For example, the various components illustrated in the figures may be implemented as software and/or firmware on a processor, ASIC/FPGA, or dedicated hardware. Also, the features and attributes of the specific embodiments disclosed above may be combined in different ways to form additional embodiments, all of which fall within the scope of the present disclosure. Although the present disclosure provides certain preferred embodiments and applications, other embodiments that are apparent to those of ordinary skill in the art, including embodiments which do not provide all of the features and advantages set forth herein, are also within the scope of this disclosure. Accordingly, the scope of the present disclosure is intended to be defined only by reference to the appended claims.