US20130242425A1 - Write reordering in a hybrid disk drive - Google Patents

Abstract

A hybrid drive and associated methods increase the rate at which data are transferred to a nonvolatile storage medium in the hybrid drive. By using a large nonvolatile solid state memory device as cache memory for a magnetic disk drive, a very large number of write commands can be cached and subsequently reordered and executed in an efficient manner. In addition, strategic selection and reordering of only a portion of the write commands stored in the nonvolatile solid state memory device increases efficiency of the reordering process.

Description

BACKGROUND
• 1. Field of the Invention
• Embodiments of the present invention relate generally to disk drives and, more particularly, to systems and methods of write reordering in a hybrid disk drive.
• 2. Description of the Related Art
• A hard disk drive (HDD) is a commonly used data storage device for the computer and primarily stores digital data in concentric tracks on the surface of a data storage disk. The data storage disk is a rotatable hard disk with a layer of magnetic material thereon, and data are read from or written to a desired track on the data storage disk using a read/write head that is held proximate to the track while the disk spins about its center at a constant angular velocity. Data are written to the data storage disk in accordance with a write command transferred to the HDD from a host computer.
• Generally, write commands can be received by an HDD much more quickly than the data associated with each command can be written to the data storage disk. Consequently, an HDD typically stores data received from the host computer temporarily in a volatile buffer, such as a DRAM chip, prior to actually executing the write command, and uses a command queue to track each write command received from the host computer. To maximize the speed at which data residing in the volatile buffer are safely written to the data storage disk, the command queue is typically reordered, so that write commands transferred from the host system are not executed in the order received. Instead, write commands are selected as a function of how quickly they can be executed by the HDD based on the current position of the read/write head, the write location specified by each write command, the rotational speed of the data storage disk, the maximum seek acceleration of the HDD, the servo-settle time of the HDD, etc.
• Various approaches for re-ordering the command queue in a hard disk drive are known, and in general the efficiency of such reordering schemes is enhanced by reordering larger numbers of writes. For example, when writing 4 kilobyte (kB) random writes, an HDD having a random-write performance of 70 input/output operations per second (IOPS) with no reordering of write commands, and approximately 200 IOPS when reordering 64 write commands, can potentially execute as many as 400 IOPS when using a reordering algorithm that reorders 1500 write commands. However, the time available for an HDD to select the next write command to be executed in the command queue is limited; during the time that the current write command is being executed, the queue of remaining commands must be reordered and the write command having the shortest access time determined. Because the time to reorder long command queues is generally longer than the time required to execute a typical write command, the use of such long command queues, e.g., command queues having 200 or more write commands, is generally impracticable. Consequently, improvements in random write performance of HDDs are generally limited to incremental enhancements in the mechanical performance of HDD servo systems and storage disk rotation speed. In light of the above, systems and methods that improve write reordering and/or increase the rate at which data are transferred to a non-volatile medium in an HDD are generally desirable.
SUMMARY
• One or more embodiments of the present invention provide systems and methods for increasing the rate at which data are transferred to a non-volatile medium in an HDD.
• According to one embodiment of the present invention, a method of storing data in a hybrid drive having a control unit programmed to control storing of data into a nonvolatile solid state memory device and a magnetic storage disk, includes the control unit performing the steps of receiving data to be stored, and writing the received data directly in the nonvolatile solid state memory device without storing the received data in a DRAM buffer associated with the magnetic storage disk.
• In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, according to another embodiment of the present invention, includes the steps of writing the data blocks to the nonvolatile solid state memory device, selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device, where N is less than M, ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk, and writing the first of the ordered data blocks to the magnetic storage disk, wherein selecting N data blocks comprises selecting the N oldest data blocks from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk.
• In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, according to another embodiment of the present invention, includes the steps of writing the data blocks to the nonvolatile solid state memory device, selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device, where N is less than M, ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk, writing the first of the ordered data blocks to the magnetic storage disk, and periodically writing the oldest data block stored in the nonvolatile solid state memory device from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk, wherein selecting N data blocks comprises selecting N data blocks whose logical block addresses correspond to the N closest locations on the magnetic storage disk to the current location of an active read-write head of the magnetic storage disk.
• In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, according to another embodiment of the present invention, includes the steps of writing the data blocks to the nonvolatile solid state memory device, selecting data blocks stored in the nonvolatile solid state memory device whose logical block addresses correspond to locations disposed in a subzone region of the magnetic storage disk in which an active read-write head of the magnetic storage disk is located, ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk, and writing the first of the ordered data blocks to the magnetic storage disk.
BRIEF DESCRIPTION OF THE DRAWINGS
• So that the manner in which the above recited features of embodiments of the invention can be understood in detail, a more particular description of embodiments of the invention, briefly summarized above, may be had by reference to the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.
• FIG. 1 is a schematic view of an exemplary disk drive, according to an embodiment of the invention.
• FIG. 2 illustrates a storage disk with data organized after servo wedges have been written on the storage disk.
• FIG. 3A illustrates an operational diagram of a disk drive with a flash memory device configured as a cache memory for the disk drive, according to an embodiment of the invention.
• FIG. 3B illustrates an operational diagram of a disk drive with a flash memory device configured as a cache memory for the disk drive, according to another embodiment of the invention.
• FIG. 3C sets forth a flowchart of method steps for storing data in a hybrid drive, according to embodiments of the invention.
• FIG. 4 illustrates a diagram of a cache directory used in embodiments of the invention.
• FIG. 5 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to one embodiment of the present invention.
• FIG. 6 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention.
• FIG. 7 sets forth a flowchart of method steps for an eviction algorithm for a disk drive, according to another embodiment of the present invention.
• FIG. 8 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention.
• FIG. 9 schematically illustrates a partial side-view of a disk drive configured with multiple storage disks, and multiple read/write heads.
• FIG. 10 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention.
• For clarity, identical reference numbers have been used, where applicable, to designate identical elements that are common between figures. It is contemplated that features of one embodiment may be incorporated in other embodiments without further recitation.
DETAILED DESCRIPTION
• FIG. 1 is a schematic view of an exemplary disk drive, according to an embodiment of the invention. For clarity,disk drive100 is illustrated without a top cover.Disk drive100 includes at least onestorage disk110 that is rotated by aspindle motor114.Spindle motor114 is mounted on abase plate116. Anactuator arm assembly120 is also mounted onbase plate116, and has aslider121 mounted on aflexure arm122 with a read/writehead127.Flexure arm122 is attached to anactuator arm124 that rotates about abearing assembly126.Voice coil motor128 movesslider121 relative tostorage disk110, thereby positioning read/writehead127 over the desired concentric data storage track disposed on thesurface112 ofstorage disk110.Spindle motor114, read/writehead127, andvoice coil motor128 are coupled toelectronic circuits130, which are mounted on a printedcircuit board132. Theelectronic circuits130 include a read channel, a microprocessor-basedcontroller133, random-access memory (RAM)134 (which may be a dynamic RAM), and/or aflash memory device135 andflash manager device136. For clarity,disk drive100 is illustrated with asingle storage disk110 and a singleactuator arm assembly120.Disk drive100 may also include multiple storage disks and multiple actuator arm assemblies. In addition, each side ofstorage disk110 may have an associated read/write head coupled to a flexure arm.
• In some embodiments,disk drive100 is configured as a hybrid drive, and in normal operation data can be stored to and retrieved fromstorage disk110 and/orflash memory device135. In a hybrid drive, non-volatile memory, such asflash memory device135, supplements the spinning HDD to provide faster boot, hibernate, resume and other data read-write operations, as well as lower power consumption. Such a hybrid drive configuration is particularly advantageous for battery operated computer systems, such as mobile computers or other mobile computing devices. In a preferred embodiment, flash memory device is a non-volatile solid state storage medium, such as a NAND flash chip that can be electrically erased and reprogrammed, and is sized to supplementstorage disk110 indisk drive100 as a non-volatile storage medium. For example, in some embodiments,flash memory device135 has data storage capacity that is orders of magnitude larger thanRAM134, e.g., gigabytes (GB) vs. megabytes (MB).
• FIG. 2 illustratesstorage disk110 with data organized afterservo wedges200 have been written onstorage disk110. Servowedges200 may be written onstorage disk110 by either a media writer or bydisk drive100 itself via a self servo-write (SSW) process.Servo wedges200 are substantially radially aligned and are shown crossing data storage tracks220.Servo wedges200 contain servo information that defines the radial position and track pitch, i.e., spacing, of data storage tracks220. In practice,servo wedges200 may be somewhat curved, for example,servo wedges200 may be configured in a spiral pattern that mirrors the path that would be followed by read/write head127 if it were to move across the stroke whilestorage disk110 is not spinning. Such a spiral pattern advantageously results in the wedge-to-wedge timing being independent of the radial position of read/write head127. For simplicity,servo wedges200 are depicted as substantially straight lines inFIG. 2.
• Storage disk110 also includes concentric data storage tracks220 located indata regions225 for storing data. Data storage tracks220 are positionally defined by the servo information written inservo wedges200. Typically, the actual number of data storage tracks220 andservo wedges200 included onstorage disk110 is considerably larger than illustrated inFIG. 1. For example,storage disk110 may include hundreds of thousands of concentric data storage tracks220 and hundreds ofservo wedges200. Data stored on data storage tracks220 are referenced by a host computer in terms of logical block addresses (LBAs) that are mapped bydisk drive100 to a specific physical location, so that each LBA ofdisk drive100 corresponds to a specific cylinder-head-sector location. In embodiments in whichdisk drive100 includesflash memory device135, LBAs of data sent todisk drive100 are also associated with a flash logical block address (FLB) when temporarily written toflash memory device135.
• When data are transferred to or fromstorage disk110,actuator arm assembly120 sweeps an arc between an inner diameter (ID) and an outer diameter (OD) ofstorage disk110.Actuator arm assembly120 accelerates in one angular direction when current is passed through the voice coil ofvoice coil motor128 and accelerates in an opposite direction when the current is reversed, thereby allowing control of the position ofactuator arm assembly120 and attached read/write head127 with respect tostorage disk110.Voice coil motor128 is coupled with a servo system known in the art that uses the positioning data read fromservo wedges200 by read/write head127 to determine the position of read/write head127 over a specificdata storage track220. The servo system determines an appropriate current to drive through the voice coil ofvoice coil motor128, and drives said current using a current driver and associated circuitry.
• After executing a write command having an LBA corresponding to afirst position251 onstorage disk110, an access time occurs beforedisk drive100 can execute a second write command having an LBA corresponding to asecond position252 onstorage disk110. Specifically, during the access time, read/write head127 is moved to the target data track and the servo system stabilizes the position of read/write head127 prior to passing over the target sector, i.e.,second position252. Thus, the total access time includes the seek time for radially positioning read/write head127 to the target data track and the rotational latency for circumferentially positioning read/write head127 over the target sector. Reordering of write commands in a command queue is based on the calculated access time for each write command in the command queue.
• According to some embodiments of the invention,disk drive100 is configured as a hybrid drive in which data received from a host computer are written directly toflash memory device135 for subsequent writing tostorage disk110. Essentially,flash memory device135 can be used as a very large, non-volatile buffer forstorage disk110. In such embodiments, the rate at which data are transferred from the host computer to a non-volatile medium indisk drive100 is substantially increased, since as soon as data are received bydisk drive100, the data can be considered “safe,” i.e., retrievable even after a power loss event.
• FIG. 3A illustrates an operational diagram ofdisk drive100 withflash memory device135 configured as a cache memory fordisk drive100, according to an embodiment of the invention. As shown,disk drive100 includesRAM134,flash memory device135, aflash manager device136, a system-on-chip137, and a high-speed data path138.Disk drive100 is connected to ahost10, such as a host computer, via ahost interface20, such as a serial advanced technology attachment (SATA) bus.
• Flash manager device136 controls interfacing offlash memory device135 with high-speed data path138 and is connected toflash memory device135 via aNAND interface bus139. System-on-chip137 includes microprocessor-basedcontroller133 and other hardware for controlling operation ofdisk drive100, and is connected to RAM134 andflash manager device136 via high-speed data path138. Microprocessor-basedcontroller133 is a control unit that may be a microcontroller such as an ARM microprocessor, a hybrid drive controller, or any control circuitry withindisk drive100. High-speed data path138 is a high-speed bus known in the art, such as a double data rate (DDR) bus, a DDR2 bus, a DDR3 bus, and the like.
• FIG. 3B illustrates an operational diagram ofdisk drive100 withflash memory device135 configured as a write-back cache fordisk drive100, according to another embodiment of the invention. As shown,flash manager device136 is incorporated into system-on-chip137, and is connected toflash memory device135 viaNAND interface bus139.
• In operation, microprocessor-basedcontroller133 ofdisk drive100 receives write commands fromhost10 viahost interface20. Each write command received by microprocessor-basedcontroller133 includes one or more data blocks and LBAs associated with each data block. The term “write command,” as used herein, generally includes a data block and associated metadata, such as LBA, etc. Microprocessor-basedcontroller133 then stores the received write commands directly inflash memory device135 without storing the received data inRAM134. In the embodiment illustrated inFIG. 3A, the received write commands and associated metadata are directed toflash manager device136 via high-speed data path138, andflash manager device136 passes the received write commands and associated metadata toflash memory device135. In the embodiment illustrated inFIG. 3B, the write commands and associated metadata received fromhost10 are directed toflash manager device136 in system-on-chip137, andflash manager device136 passes the received write commands and associated metadata toflash memory device135 viaNAND interface bus139.
• FIG. 3C sets forth a flowchart of method steps for storing data in a hybrid drive, according to embodiments of the invention. Although the method steps are described in conjunction withdisk drive100 inFIGS. 1,2,3A and3B, persons skilled in the art will understand thatmethod300 may be performed with other types of systems. For example, embodiments may ofmethod300 may be applied to a solid-state storage drive with a relatively large non-volatile storage element, such as an FeRAM, that is used as a non-volatile cache for the solid-state storage drive.
• As shown,method300 begins atstep301, when microprocessor-basedcontroller133 receives data to be stored fromhost10, e.g., write commands for data to be stored onstorage disk110.
• Instep302, microprocessor-basedcontroller133 stores the write commands directly inflash memory device135 without storing the write commands inRAM134. In some embodiments, both the data and metadata associated with the write commands received instep301 are written directly toflash memory device135. In other embodiments, the data associated with said write commands is written directly toflash memory device135 and the corresponding metadata may be temporarily stored inRAM134 and periodically written toflash memory device135 when convenient.
• Instep303, microprocessor-basedcontroller133 determines whether or not data stored inflash memory device135 should be written tostorage disk110. When the determination is made that data stored inflash memory device135 should be written tostorage disk110,method300 proceeds to step304. In some embodiments, data stored inflash memory device135 should be written tostorage disk110 when read/write head127 is determined to be idle and not reading data from or writing data tostorage disk110. In other embodiments, data stored inflash memory device135 should be written tostorage disk110 whenever the storage capacity offlash memory device135 is determined to be depleted. In some embodiments, the storage capacity offlash memory device135 is determined to be depleted when substantially no storage capacity is available for storing additional data received fromhost10. In other embodiments, the storage capacity offlash memory device135 is determined to be depleted whenflash memory device135 has less than a predetermined quantity of storage capacity available for storing additional data.
• Instep304, microprocessor-basedcontroller133 reads the write commands stored inflash memory device135 and executes said write commands tostorage disk110. Different methods of selecting which write commands are executed and in what order are described below in conjunction withFIGS. 5-10.
• Thus,method300 maximizes the data transfer rate fromhost10 todisk drive100 since write commands are stored directly toflash memory device135 and are only executed tostorage disk110 when read/write head127 would otherwise be idle. In addition, becauseflash memory device135 is a nonvolatile memory storage device, write commands received bydisk drive100 fromhost10 can be considered safe from loss due to power loss almost immediately; it is not necessary to wait until the received write commands have been executed tostorage disk110.
• While the disk drive architecture illustrated inFIGS. 3A,3B enables the use offlash memory device135 as a cache memory, reordering the very large number of write commands that can be stored inflash memory device135 using reordering schemes known in the art is not practical. For example, whenflash memory device135 has a storage capacity of 16 GB, the number of 4 kB random writesflash memory device135 can cache is on the order of 4 million. The time required to reorder just a few hundred write commands using simple reordering algorithms generally exceeds the time available to complete such a calculation, i.e., such a reordering calculation requires longer than the typical access time for a write command. Thus, using reordering schemes known in the art on the large number of write commands that can be stored inflash memory device135 likely will not result in an increase in the data transfer rate fromflash memory device135 tostorage disk110.
• In addition, onceflash memory device135 is filled with data from a host computer, data transfer from the host computer todisk drive100 is restricted to the rate at which data can be written tostorage disk110 fromflash memory device135. This is because data cannot be transferred from the host to computer toflash memory device135 until storage space has been made available inflash memory device135 by flushing data tostorage disk110 and “evicting” data fromflash memory device135. Consequently, the more efficiently data are transferred fromflash memory device135 tostorage disk110, the more quickly additional data can be received bydisk drive100 from the host computer and the less total power is consumed bydrive100. Furthermore, whenflash memory device135 is used as cache memory forstorage disk110, the large number of write commands received from the host computer and stored inflash memory device135 can lead to some write commands remaining for undesirably long periods inflash memory device135 without being written tostorage disk110. Although data received from the host computer and stored inflash memory device135 are considered safe, failure to write such data tostorage disk110 for extended periods of time is generally undesirable.
• In some embodiments, an eviction scheme is used in conjunction with a write-reordering algorithm to improve the performance ofdisk drive100. Such embodiments minimize how long data remains inflash memory device135 without being written tostorage disk110 by ensuring that the least-recently-used data stored inflash memory device135 are periodically evicted. In addition, such embodiments provide a computationally efficient method for selecting write commands to be executed tostorage disk110; specifically, a manageable number of write commands stored inflash memory device135 are selected for reordering based on criteria disclosed herein.
• FIG. 4 illustrates a diagram of acache directory400 used in embodiments of the invention.Cache directory400 represent a page replacement algorithm known in the art as an adaptive replacement cache (ARC) scheme, which tracks both recency and frequency of cache entries D1-D10 inflash memory device135. To that end,cache directory400 splits a standard cache directory of all cache entries inflash memory device135 into a recency list T1 and a frequency list T2 as shown.Cache directory400 further includes a ghost recency list B1 and a ghost frequency list B2 that are ghost entry lists linked to recency list T1 and frequency list T2, respectively.
• Together, recency list T1 and frequency list T2 include all cache entries currently held incache directory400, as indicated by fixedcache size410. Thus, the data corresponding to cache entries D1-D5 of recency list T1 and the cache entries D6-D10 of frequency list T2 include all data currently being stored inflash memory device135. For clarity, only five cache entries are illustrated in recency list T1 and five in frequency list T2, but in practice the total number of cache entries can be very large, e.g. on the order of thousands or millions. Furthermore, recency list T1 and frequency list T2 are depicted as having equal size inFIG. 4. In practice, recency list T1 and frequency list T2 can each include a different-sized portion of the total cache entries D1-D10 incache directory400. In some embodiments, the relative sizes of recency list T1 and frequency list T2 can vary during normal operation ofdisk drive100 based on cache hits associated with ghost recency list B1 and a ghost frequency list B2.
• Recency list T1, frequency list T2, ghost recency list B1, and ghost frequency list B2 are all least-recently used (LRU), linked lists configured to track properties of each block of data stored inflash memory device135. As such, entries are placed at the top of each list, and existing entries in each list are moved down the list when such an entry is made, eventually reaching the bottom of the list after a large number of cache entries have been made tocache directory400. Thus, when fully populated, any entry to one of these lists results in the eviction of whatever cache entry is located at the bottom of that list. The top of recency list T1 is located at anentry position451, which is adjacent to adivider450, and the bottom of recency list T1 is located at anentry position452, which is adjacent to ghost recency list B1. Similarly, the top of frequency list T2 is located at anentry position453, which is adjacent to divider450, and the bottom of frequency list T2 is located at anentry position454, which is adjacent to ghost frequency list B2. As indicated byarrows460, new cache entries to recency list T1, which occur atentry position451, push existing cache entries toward ghost recency list B1, and new cache entries to frequency list T2, which occur atentry position453, push existing cache entries toward ghost frequency list B2.
• Each of cache entries D1-D10 is a data structure associated with a specific block of data, e.g., 4 kB, 32 kB, etc., that has been received from a host computer bydisk drive100 and is stored inflash memory device135. In embodiments of the invention, said data structures may correspond to the data block associated with a specific write command received by microprocessor-basedcontroller133 fromhost10. Cache entries D1-D10 each include an LBA associated with a specific data block, a flash logical block address associated with the data bock, and a “dirty” flag for the data block that indicates if that block of data has already been written tostorage disk100. “Dirty” blocks are data blocks that have not yet been written tostorage disk110 and therefore only reside inflash memory device135. “Non-Dirty” blocks are data blocks that either were written to the flash memory device and then subsequently written to the disk, or data blocks that were read from the disk (in response to a host request for data that was not already in the flash memory device), and then subsequently copied to the flash memory device. Ghost entries G1-G5 in ghost recency list B1 are metadata entries representing cache entries recently evicted from recency list T1, and ghost entries G6-G10 in ghost frequency list B2 are metadata entries representing cache entries recently evicted from frequency list T2. It is noted that a cache entry from recency list T1 or frequency list T2 is generally only converted to a ghost entry, i.e., evicted fromflash memory device135, if an identical copy of the data associated with the cache entry already exists on thestorage disk110. In some embodiments, a cache entry may be converted to a ghost entry without being written to disk if the data associated with said cache entry corresponds to data designated byhost10 as no longer needed via a TRIM command.
• In operation, a cache entry is made to recency list T1 atentry position451 whenever a block of data is received bydisk drive100 from the host computer and is stored inflash memory device135. Any existing cache entries in recency list T1 are pushed toward ghost recency list B1, and the cache entry currently inentry position452 is flushed, i.e., written tostorage disk110, and then evicted, i.e., the metadata for the flushed cache entry is made as an entry to ghost recency list B1 atentry position456. Whenever the host computer asks to write a data block corresponding to any cache entry from any of the LRU lists making upcache directory400, i.e., any of cache entries D1-D10 or ghost entries G1-G10, the cache entry of interest is moved to the top of frequency list T2 atentry position453. Accordingly, all other entries in frequency list T2 are pushed toward ghost frequency list B2.
• In some embodiments, the page replacement algorithm illustrated inFIG. 4 is modified to reduce the total “book-keeping” operations associated with the use of double-linked LRU lists T1, T2, B1, and B2. Specifically, each of LRU lists T1, T2, B1, and B2 are linked lists that include a data structure for each data block, i.e., data associated with each write command received fromhost10, included in the linked list. Such data structures carry a significant record-keeping and memory allocation burden when the size of such LRU lists has hundreds of thousands of entries. For example, because each data structure includes a pointer referencing the next less-recently-used data block in the linked list and a pointer referencing the next more-recently-used data block in the linked list, whenever a write command is evicted from the linked list, several operations take place updating the pointers in adjacent entries in order to maintain the integrity of the linked list.
• In some embodiments of the invention, LRU lists T1, T2, B1, and B2 are lists of write command groups, rather than lists of individual write commands. In such an embodiment, write commands stored inflash memory device135 are collected in such write command groups, where write commands of a similar recency are included in the same write command group. Each write command group includes a pointer referencing the next less-recently-used data block group in the linked list and a pointer referencing the next more-recently-used data block group in the linked list, but each write command in a write command group does not require pointers to (temporally) adjacent write commands. Thus, when a write command is removed from an LRU list and/or moved to another LRU list, pointers of adjacent write commands are not updated. In such embodiments, the cache entries D1-D10 and ghost entries G1-G10 represent write command groups, rather than individual write commands. Once a write command group has less than a minimum predetermined number of write commands, the write command group can be merged with an adjacent write command group, and pointers referencing the next less-recently-used data block group in the linked list and a pointer referencing a next more-recently-used data block group in the linked list are updated accordingly.
• It is noted that in situations in which a write command with the same associated data is repeatedly received fromhost10, said write command can remain relatively high on list T1 and/or T2, and consequently remain in a “dirty” state for an arbitrarily long time. Thus, in some embodiments, the above-described eviction scheme may be modified by periodically flushing each and every “dirty” write command currently present in list T1 and/or T2 todisk drive110. In other embodiments, each cache entry in recency list T1 and/or each cache entry in frequency list T2 includes a time record of when that particular write command and associated data was first received fromhost10. In such embodiments, a predetermined number of the oldest dirty cache entries may be periodically written tostorage disk110 before any other data are written tostorage disk110. Alternatively, whenever a cache entry has remained in the dirty state for more than a predetermined time period, said cache entry can be immediately written tostorage disk100. In such embodiments, the length of time that cache entries remain in the dirty state can be directly controlled.
• Because it is impractical to fully consider every one of thousands of possible write commands inflash memory device135 that can be executed, in one embodiment of the invention, a predetermined number N of the oldest “dirty” write commands inflash memory device135 are reordered and then executed tostorage disk110. In such an embodiment, predetermined number N is selected to be a number of write commands that can be reordered in less time than the typical access time fordisk drive100, where N is generally a small fraction of the total number of dirty write commands presently stored inflash memory device135. In some embodiments, N is one or more orders of magnitude smaller than the total number of dirty write commands stored inflash memory device135, e.g., one tenth, one hundredth, one thousandth, etc. Because a manageable number of write commands stored inflash memory device135 are reordered, the transfer rate of data tostorage disk110 is maximized fordisk drive100. In addition, because the commands being reordered and executed are the oldest dirty write commands inflash memory135, the residence time of dirty write commands inflash memory device135 is minimized. One such embodiment is described below in conjunction withFIG. 5.
• FIG. 5 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to one embodiment of the present invention. Although the method steps are described in conjunction withdisk drive100 inFIG. 1, persons skilled in the art will understand that other disk drive systems configured to perform the method steps fall within the scope of the invention. Prior tomethod500, predetermined number N is selected based on the processing speed of microprocessor-basedcontroller133 and the typical access time of a write command when executed bydisk drive100. For example, in some embodiments, N is on the order of 100 to 200. As micro-processor speeds increase with respect to access times, the value of N can also increase.
• As shown,method500 begins atstep501, when N dirty write commands stored inflash memory device135 are selected for reordering. In some embodiments, the N write commands are selected entirely from the bottom of recency list T1, i.e., the oldest N dirty write commands are selected. In other embodiments, the N write commands selected are a combination of the oldest dirty write commands from recency list T1 and frequency list T2. In other embodiments, all N write commands are selected from either recency list T1 or from frequency list T2 in an alternating fashion. In such embodiments,method500 is performed on write commands selected from only one of these lists, e.g., recency list T1, then thenext time method500 is performed, write commands are only selected from the other list, e.g. frequency list T2.
• Instep501, selection of other combinations of write commands from recency list T1 and frequency list T2 instep501 also falls within the scope of the invention. For example, in embodiments in which LRU lists T1, T2, B1, and B2 are lists of write command groups, rather than lists of individual write commands, all dirty write commands in the oldest write command group associated with LRU list T1 or T2 may be selected. In some embodiments, when the number of dirty write commands in the oldest write command group is substantially less than N, some or all of the dirty write commands associated with the next oldest write command group associated with LRU list T1 or T2 are selected so that the number of write commands selected is closer to or exactly equal to N. Because in such an embodiment write commands stored inflash memory device135 are organized by write command group, such a selection process is computationally very economical and does not require randomly searching through the thousands of cache entries stored inflash memory device135.
• Instep502, a write command sequence using the N write commands selected instep501 is determined that optimizes how quickly the N write commands can be executed tostorage disk110. The reordering is based on the access time of each of the N write commands selected instep501. The access time for each write command is calculated based on a number of factors, including a starting location of read/write head127, the write location specified by the write command, the rotational speed ofstorage disk110, and the predicted seek time between the starting location and the write location.
• In some embodiments, all N! combinations of write command order are calculated instep502 to determine the best possible write command sequence for the N write commands selected instep501. In such embodiments, the value of N is necessarily a relatively small number to enable all calculations to be performed in a timely fashion. In other embodiments, an optimal write sequence is determined using a less calculation-intensive scheme, in which the most quickly accessed write command of the N write commands selected instep501 is chosen as the first in the write command sequence, the most quickly accessed write command of the remaining N−1 write commands is chosen as the second in the write command sequence, and so on. Such a scheme for determining a write command sequence instep502 is significantly less computationally demanding than determining all N! possible sequences, thereby allowing N to be a significantly larger number. Any other write command reordering schemes may also be applied to the N write commands selected instep502 and fall within the scope of the invention.
• Instep503, the first write command of the write command sequence determined instep502 is written tostorage disk110. It is noted that in some configurations ofdisk drive100, some buffering of data to RAM134 may be required when writing tostorage disk110 fromflash memory device135.
• Instep504, one or more write commands are evicted fromflash memory device135. Specifically, the evicted write command is removed fromcache directory400, i.e., either recency list T1 or frequency list T2, which produces an open entry position. Newer entries on the list containing the evicted write command are all pushed toward the associated ghost list. For example, referring tocache directory400 inFIG. 4, when cache entry D2 is evicted instep504, cache entries D3, D4, and D5 are pushed toward cache entry D1, leavingentry position451 open for more data to be received from the host computer.
• In some embodiments, the write command evicted fromflash memory device135 instep503 is the write command executed tostorage disk110 instep503. Alternatively, instep504 the oldest write command incache directory400 that has already been executed tostorage disk110 is evicted fromflash memory device135, rather than the write command executed tostorage disk110 instep503. Other eviction schemes can also be used to make space available inflash memory device135 without exceeding the scope of the invention.
• Instep504, the determination is made whether or not any further data stored inflash memory device135 should be written tostorage disk110. When the determination is made that data stored inflash memory device135 should be written tostorage disk110,method500 proceeds back tostep501. The determination made instep504 may be based on the factors described above instep303 ofmethod300, such as read/write head127 being idle or storage capacity depletion offlash memory device135.
• It is noted thatsteps501 and502 are performed to determine a current write command while a previously selected write command stored inflash memory device135 is being executed bydisk drive100 and then evicted, i.e., whilesteps503 and504 are being performed for the previously selected write command. Similarly, whilesteps503 and504 are being performed for the current write command, steps501 and502 are being performed to determine yet another write command to be executed tostorage disk110. In this way, dirty write commands in cache memory that are selected from the oldest data onflash memory device135 are continuously executed. Because data from among the oldest data present inflash memory device135 are continually selected to be written tostorage disk110 and then evicted, the average residence time of data onflash memory device135 is minimized.
• In some embodiments, a reordering algorithm and an eviction algorithm are performed independently indisk drive100 to achieve the dual goals of improving the efficiency of writing data fromflash memory device135 tostorage disk110 and maximizing the eviction of the least-used data stored inflash memory device135. Unlikemethod500, a reordering algorithm is used to select write commands stored inflash memory device135 that is not limited to reordering the N oldest dirty write commands inflash memory device135. In addition, the selection process for evicting data fromflash memory device135 is not determined by the write command sequence. One such embodiment is described below in conjunction withFIG. 6.
• FIG. 6 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention. Although the method steps are described in conjunction withdisk drive100 inFIG. 1, persons skilled in the art will understand that other disk drive systems configured to perform the method steps fall within the scope of the invention. Prior tomethod600, predetermined number N may be selected in the same fashion described above in conjunction withmethod500.
• As shown,method600 begins atstep601, when N dirty write commands stored inflash memory device135 are selected for reordering. The N write commands are selected based on proximity of the target location of each write commands to the current location of read/write head127. The proximity of dirty write commands to the current location of read/write head127 can be readily determined by comparing the LBA of the write command currently being executed to the LBA of dirty write commands stored inflash memory device135. Because the many write commands stored inflash memory device135 can be organized by LBA in a tabular fashion, such a proximity determination can be performed very quickly and with little computational overhead; the thousands or hundreds of thousands of cache entries inflash memory device135 are not randomly searched. In other embodiments, the proximity of dirty write commands to the current location of read/write head127 can be determined by using cylinder-head-sector location information for dirty write commands stored inflash memory device135. Cylinder-head-sector location information provides a more detailed physical location onstorage disk110 where data from each write command inflash memory device135 will be written to, but accessing such information may require more computation time than an LBA-based approach.
• Instep602, a write command sequence using the N write commands selected instep501 is determined that optimizes how quickly the N write commands can be executed tostorage disk110. Any of the reordering schemes described above instep502 ofmethod500 may be used to determine the write command sequence. Alternatively, any other technically feasible reordering scheme known in the art may be used to determine the write command sequence instep602.
• Instep603, the first write command of the write command sequence determined instep602 is written tostorage disk110. As noted above instep503 ofmethod500, some buffering of data to RAM134 may take place when writing data tostorage disk110 fromflash memory device135.
• Instep604, the determination is made whether or not any further data stored inflash memory device135 should be written tostorage disk110. When the determination is made that data stored inflash memory device135 should be written tostorage disk110,method600 proceeds back tostep601. The determination made instep604 may be based on the factors described above instep303 ofmethod300, such as read/write head127 being idle or storage capacity depletion offlash memory device135.
• Concurrently with steps601-604, in which data are written tostorage disk110 fromflash memory device135, data are also evicted as required fromflash memory device135. The process by which write commands are selected for eviction fromflash memory drive135 is described below in steps710-720.
• FIG. 7 sets forth a flowchart of method steps for an eviction algorithm for a disk drive, according to another embodiment of the present invention. As shown, theeviction algorithm700 for evicting write commands fromflash memory drive135 begins instep710, wheremethod700 is initialized to consider the eviction of the least-recently used (LRU) data inflash memory device135. The LRU data inflash memory device135 correspond to the cache entry at the bottom of either recency list T1 (cache entry D1), or frequency list T2 (cache entry D6) inFIG. 4. In some embodiments, the eviction algorithm inmethod700 may alternate between beginning at the bottom of recency list T1 and at the bottom of frequency list T2.
• Instep712, the determination is made whether or not data should be evicted fromflash memory device135. In some embodiments, data and associated cache entries incache directory400 are evicted whenflash memory device135 is substantially full of stored data and has little or no remaining storage capacity. In other embodiments, cache entries and associated data are required to be evicted only until a desired fraction offlash memory drive135 is available for receiving additional data from the host computer. In yet other embodiments, data are required to be evicted until all data less than a desired age remains inflash memory drive135. Other criteria may also be used to determine instep712 if data are to be evicted fromflash memory device135 without exceeding the scope of the invention. If it is determined that data should be evicted fromflash memory device135, the eviction algorithm proceeds to step714. If not, the eviction algorithm proceeds to step710.
• Instep714, the validity of data associated with the cache entry currently under consideration is checked. Data are considered “not dirty” when the data have been written tostorage disk110. If the data are not dirty, the eviction algorithm proceeds to step716 as shown inFIG. 7. If the data are dirty, the eviction algorithm proceeds to step718. It is noted that initially the cache entry under consideration instep714 is the least-recently used (LRU) data selected instep710. In later iterations, the cache entry under consideration by the eviction algorithm is generally a cache entry located higher up recency list T1 or frequency list T2, as described below instep720.
• Instep716, data determined to be not dirty instep714 are evicted fromflash memory device135, and the available storage capacity offlash memory device135 is increased.
• Instep718, the eviction algorithm checks if the cache entry currently under consideration is at the top of the LRU list. If yes, the eviction algorithm proceeds to step710. If the cache entry currently under consideration is not at the top of the LRU list, the eviction algorithm proceeds to step720.
• Instep720, the eviction algorithm considers the next cache entry on recency list T1 or frequency list T2. In some embodiments, only cache entries in recency list T1 are eligible for consideration, and the eviction algorithm advances one cache entry upward, i.e., to the next youngest cache entry, on recency list T1. In other embodiments, the eviction algorithm considers a combination of the cache entries in recency list T1 and frequency list T2, and increments up one cache entry on such a combined list instep720. As shown inFIG. 7,method700 proceeds to step712 after incrementing to the next cache entry on the list of eligible cache entries used instep720. Thus, over time, the eviction algorithm proceeds stepwise from the bottom to the top of the desired LRU list, evicting not dirty cache entries along the way. The eviction algorithm then returns to the bottom of the desired LRU list after reaching the top (i.e., newest) entry on said list.
• Due to the very large number of write commands that can be stored inflash memory device135, the time required for the eviction algorithm ofmethod700 to evict all eligible write commands fromflash memory device135 can be substantial. This is particularly true when a large number of additional write commands are being continuously stored inflash memory device135. In such situations, the eviction algorithm ofmethod700 cannot consider the validity of and subsequently evict cache entries located at the bottom of recency list T1 and/or frequency list T2 for undesirably long periods. In addition, due to the nature of reordering algorithms known in the art, a large number of write commands assigned to specific regions ofstorage disk110 can prevent the storage of certain write commands ondisk110 for an undesirable period of time. Specifically, write commands stored inflash memory device135 that are to be written to regions remote from the current position of the read/write head may remain “dirty” for a very long time. Consequently, in some embodiments of the invention, an eviction algorithm is periodically reset to execute the least-recently-used write commands stored inflash memory device135. One such embodiment is described below in conjunction withFIG. 8.
• FIG. 8 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention. Although the method steps are described in conjunction withdisk drive100 inFIG. 1, persons skilled in the art will understand that other disk drive systems configured to perform the method steps falls within the scope of the invention. Prior tomethod800, a reordering interrupt value M is selected, where M is a relatively large integer, e.g., on the order of 1000. Reordering interrupt value M dictates how often a write-reordering procedure used bydisk drive100 is interrupted and “reset” by forcingdisk drive100 to execute the least-recently-used write command in an LRU list associated withflash memory device135, i.e., write the least-recently-used dirty data in the LRU list tostorage disk110.
• As shown,method800 begins atstep801, where a write counter value is set to a suitable initial value, e.g., 1 or 0.
• Instep802,disk drive100 performs a write-reordering procedure to determine a write command sequence that optimizes how quickly write commands stored inflash memory device135 are executed tostorage disk110. The write-reordering procedure may include any write-reordering algorithm known in the art. In another embodiment, one of the write-re-ordering algorithms described above instep501 and502 ofmethod500 may be used instep802. In yet another embodiment, the servo-subzone-based write-reordering algorithm described below in conjunction withFIGS. 9 and 10 may be used instep802.
• Instep803, the first write command of the write command sequence determined instep802 is executed and the data associated therewith is written tostorage disk110.
• Instep804, the write counter value is incremented higher by a value of 1.
• Instep805, the value of the write counter incremented instep804 is compared to reordering interrupt value M. If the write counter is less than the value of reordering interrupt value M,method800 proceeds to step802, and another write command sequence is determined. If the write counter equals the value of reordering interrupt value M,method800 proceeds to step806.
• Instep806, the current write-reordering algorithm is interrupted. Rather than selecting a write command determined by an optimized write command sequence, the least-recently-used dirty write command stored inflash memory device135 is executed tostorage disk110. Specifically, the dirty write command located nearest the bottom of an LRU list associated withflash memory device135 is executed. In some embodiments, the LRU list used instep806 may be recency list T1, frequency list T2, or an LRU list that includes the combined cache entries of recency list T1 and frequency list T2. Once the dirty write command from the LRU list is executed tostorage disk110, the method proceeds back to step801, where the write counter value is set to 1.
• Thus, inmethod800, the least-recently-used data onflash memory device135 are written periodically to disk, so that the residence time of dirty write-commands onflash memory device135 is minimized for two reasons. First, the least-recently-used write command onflash memory device135 is automatically executed tostorage disk110 after every M write commands. Second, because the location of the current write command being executed strongly influences what write command will next be selected, when the location of read/write head127 is “reset” to the location of the least-recently-used dirty write command onflash memory device135, the write-reordering algorithm will continue to select write commands proximate that reset location. In this way, the write-reordering algorithm can “clean up” the write commands located near the reset location, which are likely relatively old data as well, i.e., data received fromhost10 before most other dirty data currently stored inflash memory device135. Furthermore, because the write-reordering algorithm is only interrupted at relatively large intervals, the efficiency of the write-reordering algorithm itself is only slightly impacted.
• According to some embodiments of the invention, a write-reordering algorithm is contemplated in which the write commands being reordered are selected from the same servo sub-zone in which read/write head127 is currently located. In this way, a manageable number of write commands can be quickly selected from the thousands or hundreds of thousands of write commands stored inflash memory device135. Advantageously, the write commands selected in this manner are guaranteed to be located proximate each other and read/write head127. Because of this proximity, the access time between the selected write commands and, consequently, the time required to execute most or all of the selected write commands, is minimized.
• FIG. 9 schematically illustrates a partial side-view of adisk drive900 configured withmultiple storage disks910,920, and930, and multiple read/write heads. Each read/write head ofdisk drive900 is associated with one surface of one ofstorage disks910,920, and930. Specifically, read/writeheads911A,912A,921A,922A,931A,932A are associated withdisk surfaces911,912,921,922,931, and932, respectively.Disk drive900 is otherwise substantially similar in organization and operation todisk drive100.
• Storage disks910,920, and930 are organized into data zones, where each data zone includes a group of tracks configured with the same number of data sectors. Each data zone is in turn subdivided into a plurality of servo subzones, each servo subzone being made up of approximately 100 to 200 data tracks. The portion ofstorage disks910,920,930 illustrated inFIG. 9 includesservo subzones950,960, and970. As shown, servo subzones951-953 each include a portion of disk surfaces911,912,921,922,931, and932 that has awidth901 of approximately 100-200 tracks. Each such portion of a disk surface associated with a single read/write head is herein referred to as a “subzone segment.” Thus,servo subzone950 includes subzone segments951-956,servo subzone960 includes subzone segments961-966, andservo subzone970 includes subzone segments971-976.
• FIG. 10 sets forth a flowchart of method steps for executing write commands that are stored in cache memory in a disk drive, according to another embodiment of the present invention. Although the method steps are described in conjunction withdisk drive900 inFIG. 9, persons skilled in the art will understand that other disk drive systems configured to perform the method steps fall within the scope of the invention. Prior tomethod1000, a write-command minimum K is selected based on the processing speed of microprocessor-basedcontroller133 and the typical access time of a write command when executed bydisk drive900. The value of write-command minimum K is chosen so that an adequate number of write commands are used in write-reordering calculations so that efficient write-command sequences are generated; a write-reordering algorithm using too few write commands generally provides less time-efficient write-command sequences. However, because the write commands being reordered inmethod1000 are already selected to be located proximate each other, the value of write-command minimum K may be substantially smaller than values preferably used for predetermined number N inmethods500 and600. For example, in some embodiments, K is on the order of 10 to 50.
• As shown,method1000 begins atstep1001, where the current subzone segment of the active read/write head ofdisk drive900 is determined. For example, read/write head921A inFIG. 9 may be in the process of executing a write command stored inflash memory device135 to one or more data tracks insubzone segment963. Thus, in this example, the current subzone segment is subzonesegment963.
• Instep1002, the LBA limits of the chosen subzone region is determined. Initially, the chosen subzone region is synonymous with the current subzone segment determined instep1001. Thus, considering the example of read/write head921A executing a write command insubsector segment963 duringstep1001, instep1002 the LBA limits of the data tracks contained insubsector segment963 are determined. In some situations, which are described below instep1005, the chosen subzone region also includes one or more subzone segments adjacent or proximate to the current subzone segment determined instep1001. Determination of the LBA limits of the chosen subzone region may involve consulting a look-up table, but typically an algorithm is used to determine such LBA limits based on track density, the LBA limits of the data zone containing the subsector segment or segments of interest, and the like.
• Instep1003, all write commands that are eligible for writing to a servo subzone indisk drive900 are determined. Eligible write commands include all dirty write commands that are stored inflash memory device135 and which have an LBA within the LBA limits (determined in step1002) of the chosen subzone region. The determination of eligible write commands is a computationally efficient procedure since write commands stored inflash memory device135 are generally tabulated and organized by LBA. Consequently, determining eligible write commands does not require searching through all cache entries inflash memory device135, which can number in the hundreds of thousands.
• Instep1004, the total number of eligible write commands determined instep1003 is compared to the value of write-command minimum K. If the number of eligible write commands is greater than or equal to the value of write-command minimum K,method1000 proceeds to step1006. If the number of eligible write commands is less than the value of write-command minimum K,method1000 proceeds to step1005 and then back tostep1002.
• Instep1005, the chosen subzone region is expanded to include one or more proximate and/or adjacent subzone segments, thenmethod1000 returns to step1002. For example, when the chosen subzone region instep1003 consists ofsubzone segment963, and instep1004 the number of eligible write commands is less than the value of write-command minimum K, the chosen subzone region may be expanded to includesubzone segment953 and/orsubzone segment973. When the chosen subzone region instep1003 already consists of several subzone segments, e.g.,subzone segments953,963, and973, the chosen subzone region may be expanded to include one or more additional subzone segments (not shown) onsurface921 ofstorage disk920. Because each of the subzone segments onsurface921 is made up of a relatively small number of tracks, e.g., typically 200 tracks or less, radial seek time between these subzone segments is very short. Consequently, write commands distributed across multiple subzone segments ondisk surface921 can be executed with relatively low latency between the write commands, which improves the effective data transfer rate fromflash memory device135 tostorage disk920.
• In some embodiments, when the chosen subzone region instep1003 already consists of a relatively large number of subzone segments on one disk surface, e.g.,surface921, the chosen subzone region may be expanded instep1005 to include one or more subzone segments on a neighboring disk surface, e.g.,disk surface912 or922. In such embodiments, the subzone segments on neighboring surfaces are included when the radial seek time across the chosen subzone region exceeds an estimated head switch time fordisk drive900. For example, when the chosen subzone region instep1003 consists of 10 or 12 subzone segments, the radial seek time between subzone segments disposed on opposite ends of the chosen subzone region can potentially exceed the head switch time between different read/write heads ofdisk drive900. Thus, when expanding the chosen subzone region instep1005, subzone segments on different disk surfaces can effectively be closer and have less associated latency than subzone segments on the same disk surface and adjacent to the currently defined chosen subzone region. For this reason, in some embodiments, expansion of the chosen subzone region instep1005 is not limited to subzone segments located on the same disk surface, and may include subzone segments located on other disk surfaces ofdisk drive900 as well.
• Instep1006, write reordering of the eligible write commands determined in steps1003-1005 is performed. In one embodiment, the write reordering ofstep1006 uses position optimization of each write command. Specifically, access time for each eligible write command is based on radial seek and rotational latency, so that optimal seek times are determined for each write command. This is in contrast to an LBA-based write-reordering scheme, which is essentially a track-based calculation that does not include rotational latency.
• Instep1007, the first write command of the write command sequence determined instep1006, i.e., the write command having the shortest access time, is executed and data associated with said write command is written tostorage disk110.
• Instep1008, the chosen subzone region is checked for depletion of write commands. In other words, the number of dirty write commands remaining inflash memory device135 having LBAs located in the chosen subzone region is determined. If this number is equal to or less than a predetermined limit, then the chosen subzone region is considered depleted of write commands andmethod1000 proceeds to step1009. If this number exceeds the predetermined limit, then the chosen subzone region is not considered depleted of write commands andmethod1000 proceeds to step1003 and write-reordering is performed again. In some embodiments, the predetermined limit is a number at which write reordering becomes relatively inefficient, e.g., 10 or 20. In other embodiments, the predetermined limit is 0, i.e., the chosen subzone region is not considered depleted of write commands until there are no remaining write commands stored inflash memory device135 having LBAs located in the chosen subzone region.
• Instep1009, after the chosen subzone region has been determined instep1008 to be depleted of write commands, read/write head127 is moved to a different subzone. In one embodiment, read/write head127 is moved to a subzone that is adjacent to the chosen subzone region. Thus, read/write head127 can be moved progressively across a surface ofstorage disk110 from one subzone to another subzone when executing a large number of write commands stored inflash memory device135. In this way, read/write head127 is guaranteed to pass over all subzones ofstorage disk110, which prevents write commands residing inflash memory device135 from remaining dirty for an undesirably long time. In addition, the process of executing write commands stored inflash memory135 is very time efficient. Because read/write head127 only traverses from one chosen subzone region to an adjacent subzone, read/write head127 is not executing write data to random locations acrossstorage disk110 ormultiple storage disks110. Consequently, very little time is spent repositioning read/write head127 from one subzone to another subzone upon completion ofmethod1000.
• In some embodiments, a “reset” procedure is periodically performed in which read/write head127 is moved to the subzone in which the location corresponding to the least-recently-used write command inflash memory135 is disposed. In such an embodiment,method1000 is then performed on a chosen subzone region that includes this subzone, i.e., write-reordering and writing is performed on the write commands stored inflash memory device135 having LBAs corresponding to this subzone. Thus, the least-recently-used write command inflash memory device135, as well as write commands having LBAs corresponding to same subzone as the least-recently-used write command, are then executed and the data associated therewith is written tostorage disk110. In this way, the least-recently-used write commands stored inflash memory device135 are executed periodically, which prevents write commands residing inflash memory device135 from remaining dirty for an undesirably long time.
• In some embodiments such a reset procedure is performed after a predetermined number of write commands stored inflash memory device135 have been executed. It is desirable for the predetermined number to be relatively large to minimize the introduction of inefficiency into performance ofmethod1000, e.g. once every 1000 write commands. Alternatively, such a reset procedure is performed after a predetermined number of iterations ofmethod100 has been performed, e.g. 50 to 100.
• In sum, embodiments of the invention provide systems and methods for increasing the rate at which data are transferred to a non-volatile medium in an HDD. By using a large nonvolatile solid state memory device as cache memory for a magnetic disk drive, a very large number of write commands can be cached and subsequently reordered and executed in an advantageously efficient manner. An additional advantage of the present invention is that by strategically selecting and reordering only a portion of the write commands stored in the nonvolatile solid state memory device, efficiency of the reordering process is further increased.
• While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.

Claims (62)

I claim:

1. A method of storing data in a hybrid drive having a control unit programmed to control storing of data into a nonvolatile solid state memory device and a magnetic storage disk, the control unit performing the steps of:

receiving data to be stored; and

writing the received data directly in the nonvolatile solid state memory device without storing the received data in a DRAM buffer associated with the magnetic storage disk.

2. The method ofclaim 1, wherein the control unit further performs the steps of reading the data stored in the solid state memory device and writing said data to the magnetic storage disk.

3. The method ofclaim 2, wherein said data is first stored in the DRAM buffer prior to writing said data to the magnetic storage disk.

4. The method ofclaim 3, further comprising the step of determining that the storage capacity of the solid state memory device is depleted, wherein the step of reading the data stored in the solid state memory device and writing said data to the magnetic storage disk is performed in response to the determining.

5. The method ofclaim 4, wherein depleted storage capacity comprises having substantially no storage capacity available for storing additional data.

6. The method ofclaim 5, wherein depleted storage capacity comprises having less than a predetermined quantity of storage capacity available for storing additional data.

7. The method ofclaim 2, further comprising the step of determining that the magnetic storage disk is idle, wherein the step of reading the data stored in the solid state memory device and writing said data to the magnetic storage disk is performed in response to the determining.

8. The method ofclaim 2, further comprising the step of designating locations in the solid state memory device corresponding to the data written to the magnetic storage disk to be available for data storage.

9. The method ofclaim 1, wherein writing the received data in the nonvolatile solid state memory device comprises transmitting the received data via a data bus that connects the control unit with the nonvolatile solid state memory device and the DRAM buffer associated with the magnetic storage disk.

10. The method ofclaim 1, wherein writing the received data in the nonvolatile solid state memory device comprises transmitting the received data via a NAND interface bus that connects a flash manager device to the nonvolatile solid state memory device.

11. The method ofclaim 10, wherein the flash manager device and the control unit are elements of a system-on-chip in the hybrid drive.

12. In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, the method comprising:

writing the data blocks to the nonvolatile solid state memory device;

selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device, where N is less than M;

ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk; and

writing the first of the ordered data blocks to the magnetic storage disk,

wherein selecting N data blocks comprises selecting the N least-recently-used data blocks from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk.

13. The method ofclaim 12, wherein the least-recently used list of data blocks comprises a recency list of data blocks written to the nonvolatile solid state memory device, a frequency list of data blocks written to the nonvolatile solid state memory device, or a combination of both.

14. The method ofclaim 13, wherein at least one of the recency list and the frequency list comprises a linked list of data blocks in which a data structure is associated with each data block included in the linked list and includes a pointer referencing the next less-recently-used data block in the linked list and a pointer referencing the next more-recently-used data block in the linked list.

15. The method ofclaim 13, wherein at least one of the recency list and the frequency list comprises a linked list of data block groups in which a data structure is associated with each data block group included in the linked list and includes a pointer referencing a next less-recently-used data block group in the linked list and a pointer referencing a next more-recently-used data block group in the linked list.

16. The method ofclaim 15, wherein a data block group in the linked list consists of a plurality of data blocks in which a least-recently-used data block of the plurality of data blocks has been used more recently than any data block in the next less-recently-used data block group and a most-recently-used data block of the plurality of data blocks has been used less recently than any data block in the next more-recently-used data block group.

17. The method ofclaim 12, further comprising:

selecting a second group of N data blocks out of the M data blocks stored in the nonvolatile solid state memory device;

ordering the selected second group of N data blocks prior to writing the selected data blocks to the magnetic storage disk; and

writing the first of the ordered second group of N data blocks to the magnetic storage disk.

18. The method ofclaim 12, further comprising writing the second of the ordered data blocks to the magnetic storage disk.

19. The method ofclaim 12, wherein N is substantially less than M.

20. The method ofclaim 19, wherein N is at least an order of magnitude less than M.

21. The method ofclaim 12, further comprising periodically writing the least-recently-used data block from the least-recently-used list of data blocks.

22. The method ofclaim 21, wherein periodically comprises after writing a predetermined number of ordered data blocks stored in the nonvolatile solid state memory device to the magnetic storage disk.

23. The method ofclaim 12, wherein writing the data blocks to the nonvolatile solid state memory device comprises writing the data blocks directly in the nonvolatile solid state memory device without storing the data blocks in a DRAM buffer associated with the magnetic storage disk.

24. The method ofclaim 12, wherein writing the data blocks to the nonvolatile solid state memory device comprises writing the data blocks directly in the nonvolatile solid state memory device without storing the data blocks in a DRAM buffer configured to buffer data for the magnetic storage disk.

25. The method ofclaim 12, further comprising the step of designating a location in the solid state memory device corresponding to the first of the ordered data blocks written to the magnetic storage disk to be available for data storage.

26. The method ofclaim 12, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a data bus that connects the control unit of the data storage device to a DRAM buffer configured to buffer data for the magnetic storage disk.

27. The method ofclaim 12, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a NAND interface bus that connects a flash manager device to the nonvolatile solid state memory device.

28. The method ofclaim 12, wherein the ordering of the selected blocks comprises calculating a rotational latency for each of the selected blocks.

29. In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, the method comprising:

writing the data blocks to the nonvolatile solid state memory device;

selecting N data blocks out of M data blocks stored in the nonvolatile solid state memory device, where N is less than M;

ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk;

writing the first of the ordered data blocks to the magnetic storage disk; and

periodically writing the least-recently-used data block stored in the nonvolatile solid state memory device from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk,

wherein selecting N data blocks comprises selecting N data blocks whose logical block addresses correspond to the N closest locations on the magnetic storage disk to the current location of an active read-write head of the magnetic storage disk.

30. The method ofclaim 29, wherein periodically comprises after writing a predetermined number of ordered data blocks stored in the nonvolatile solid state memory device to the magnetic storage disk.

31. The method ofclaim 29, wherein the least-recently used list of data blocks comprises a recency list of data blocks written to the nonvolatile solid state memory device, a frequency list of data blocks written to the nonvolatile solid state memory device, or a combination of both.

32. The method ofclaim 31, wherein at least one of the recency list and the frequency list comprises a linked list of data block groups in which a data structure is associated with each data block group included in the linked list and includes a pointer referencing a next less-recently-used data block group in the linked list and a pointer referencing a next more-recently-used data block group in the linked list.

33. The method ofclaim 32, wherein a data block group in the linked list consists of a plurality of data blocks in which a least-recently-used data block of the plurality of data blocks has been used more recently than any data block in the next less-recently-used data block group and most-recently-used data block of the plurality of data blocks has been used less recently than any data block in the next more-recently-used data block group.

34. The method ofclaim 29, further comprising:

selecting a second group of N data blocks out of the M data blocks stored in the nonvolatile solid state memory device;

ordering the selected second group of N data blocks prior to writing the selected data blocks to the magnetic storage disk; and

writing the first of the ordered second group of N data blocks to the magnetic storage disk.

35. The method ofclaim 29, further comprising writing the second of the ordered data blocks to the magnetic storage disk.

36. The method ofclaim 29, wherein N is substantially less than M

37. The method ofclaim 36, wherein N is at least an order of magnitude less than M.

38. The method ofclaim 29, further comprising, prior to writing the data blocks to the nonvolatile solid state memory device, receiving the data blocks to be written to the magnetic storage disk from a host device for the data storage device.

39. The method ofclaim 29, wherein writing the data blocks to the nonvolatile solid state memory device comprises writing the data blocks directly in the nonvolatile solid state memory device without storing the received data in a DRAM buffer configured to buffer data for the magnetic storage disk.

40. The method ofclaim 29, further comprising the step of designating a location in the solid state memory device corresponding to the first of the ordered data blocks written to the magnetic storage disk to be available for data storage.

41. The method ofclaim 29, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a data bus that connects the control unit of the data storage device to a DRAM buffer configured to buffer data for the magnetic storage disk.

42. The method ofclaim 29, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a NAND interface bus that connects a flash manager device to the nonvolatile solid state memory device.

43. The method ofclaim 29, wherein the ordering of the selected blocks comprises calculating a rotational latency for each of the selected blocks.

44. In a data storage device having a nonvolatile solid state memory device, a magnetic storage disk, and a control unit, a method of ordering data blocks to be written to the magnetic storage disk, the method comprising:

writing the data blocks to the nonvolatile solid state memory device;

selecting data blocks stored in the nonvolatile solid state memory device whose logical block addresses correspond to locations disposed in a subzone region of the magnetic storage disk in which an active read-write head of the magnetic storage disk is located;

ordering the selected data blocks prior to writing the selected data blocks to the magnetic storage disk; and

writing the first of the ordered data blocks to the magnetic storage disk.

45. The method ofclaim 44, wherein the subzone region consists of a single servo subzone of the magnetic storage disk.

46. The method ofclaim 45, wherein the servo subzone comprises a portion of a data zone of the magnetic storage disk.

47. The method ofclaim 44, wherein selecting data blocks stored in the nonvolatile solid state memory device further comprises:

comparing the number of selected data blocks disposed in the subzone region to a predetermined minimum value; and

in response to the comparing, redefining the subzone region to include an additional servo subzone, wherein the additional servo subzone is adjacent to the subzone region.

48. The method ofclaim 47, wherein the predetermined minimum value is substantially less than the number of data blocks stored in the nonvolatile solid state memory device.

49. The method ofclaim 48, wherein the predetermined minimum value is at least an order of magnitude less than the number of data blocks stored in the nonvolatile solid state memory device.

50. The method ofclaim 44, further comprising periodically writing the least-recently-used data block stored in the nonvolatile solid state memory device from a least-recently-used list of data blocks that are stored in the nonvolatile solid state memory device and have not been written to the magnetic storage disk.

51. The method ofclaim 50, wherein periodically comprises after writing a predetermined number of ordered data blocks stored in the nonvolatile solid state memory device to the magnetic storage disk.

52. The method ofclaim 50, wherein the least-recently used list of data blocks comprises a recency list of data blocks written to the nonvolatile solid state memory device, a frequency list of data blocks written to the nonvolatile solid state memory device, or a combination of both.

53. The method ofclaim 44, further comprising writing the second of the ordered data blocks to the magnetic storage disk.

54. The method ofclaim 53, further comprising writing remainder data blocks of the ordered data blocks to the magnetic storage disk until the number of remainder ordered data blocks is depleted.

55. The method ofclaim 54, wherein the remainder ordered data blocks are depleted when the number of ordered data blocks that have not been written to the magnetic storage disk is less than a predetermined number ordered data blocks.

56. The method ofclaim 55, wherein the predetermined number of ordered data blocks is 1.

57. The method ofclaim 44, further comprising, prior to writing the data blocks to the nonvolatile solid state memory device, receiving the data blocks to be written to the magnetic storage disk from a host device for the data storage device.

58. The method ofclaim 44, wherein writing the data blocks to the nonvolatile solid state memory device comprises writing the data blocks directly in the nonvolatile solid state memory device without storing the received data in a DRAM buffer configured to buffer data for the magnetic storage disk.

59. The method ofclaim 44, further comprising the step of designating a location in the solid state memory device corresponding to the first of the ordered data blocks written to the magnetic storage disk to be available for data storage.

60. The method ofclaim 44, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a data bus that connects the control unit of the data storage device to a DRAM buffer configured to buffer data for the magnetic storage disk.

61. The method ofclaim 44, wherein writing the data blocks to the nonvolatile solid state memory device comprises transmitting the data blocks via a NAND interface bus that connects a flash manager device to the nonvolatile solid state memory device.

62. The method ofclaim 44, wherein the ordering of the selected blocks comprises calculating a rotational latency for each of the selected blocks.

Images