Patent Publication Number: US-9898406-B2

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

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a divisional of U.S. patent application Ser. No. 13/301,594, filed Nov. 21, 2011, entitled “IMPROVED CACHING OF DATA IN DATA STORAGE SYSTEMS BY MANAGING THE SIZE OF READ AND WRITE CACHE BASED ON A MEASUREMENT OF CACHE RELIABILITY”, assigned to the assignee of the present application, and incorporated herein by reference. 
    
    
     BACKGROUND 
     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. 
     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&#39;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&#39;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&#39;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.