Methods, systems and computer readable media for intelligent fetching of data storage device commands from submission queues

Methods, systems, and computer readable media for intelligent fetching of storage device commands from submission queues are disclosed. On method is implemented in a data storage device including a controller and a memory. The method includes collecting submission queue command statistics; monitoring resource state of the data storage device. The method further includes using the submission queue command statistics and the resource state to select a submission queue from which a next data storage device command should be fetched. The method further includes fetching the command from the selected submission queue. The method further includes providing the command to command processing logic.

TECHNICAL FIELD

The subject matter described herein relates to storage devices, such as nonvolatile memory devices. More particularly, the subject matter described herein relates to intelligent fetching of data storage device commands from host-side submission queues by a nonvolatile storage device.

BACKGROUND

In the nonvolatile memory express (NVMe) system, a host device writes data storage device commands, such as read commands, write commands, and administrative commands, in submission queues, which are implemented in host memory. The nonvolatile storage device fetches the commands from the submission queues, executes the commands, and places entries in completion queues, which are also implemented in host memory, to notify the host of completion of the commands. There are typically multiple submission queues allocated by the host. Accordingly, the device controller must select from which submission queue to select the next command to be processed.

The NVMe standard, the current version of which is NVM Express, Revision 1.2, Nov. 3, 2014, the disclosure of which is incorporated herein by reference in its entirety, describes two mechanisms by which a device controller may select commands from submission queues. One mechanism is a round robin mechanism, in which the device controller selects commands from the submission queues in round robin order. Another mechanism is a weighted round robin mechanism where the submission queues are assigned static priorities or weights, and commands are selected from submission queues in round robin order using weights to determine the selection order in each round.

In either case, the next command to be fetched from a submission queue is based on static arbitration logic that either implements no priorities, as in the round robin case, or that implements only static, host-defined priorities, as in the weighted round robin case. Such static arbitration logic may be sufficient if the storage device has sufficient resources to handle all host I/O requests. However, because storage device resources may be limited and host demands on those resources may exceed the device's ability to promptly process host commands, it may be desirable to select commands to improve utilization of storage device resources.

Accordingly, there exists a need for methods, systems, and computer readable media for intelligent fetching of storage device commands from submission queues.

SUMMARY

Methods, systems, and computer readable media for intelligent fetching of storage device commands from submission queues are disclosed. On method is implemented in a data storage device including a controller and a memory. The method includes collecting submission queue command statistics; monitoring resource state of the data storage device. The method further includes using the submission queue command statistics and the resource state to select a submission queue from which a next data storage device command should be fetched. The method further includes fetching the command from the selected submission queue. The method further includes providing the command to command processing logic.

DETAILED DESCRIPTION

As stated above, according to the NVMe standard, a host device communicates memory device commands, such as read commands, write commands, and admin commands, to a nonvolatile storage device using submission queues.FIG. 1illustrates the NVMe architecture in which the subject matter described herein for intelligent submission queue command fetching may be implemented. InFIG. 1, host device100may be any suitable computing platform that is capable of accessing memory on a storage device. For example, host device100may be a desktop personal computer, a laptop computer, a tablet computer, a mobile telephone, or a front end to a storage array. Host device100includes a processor102and memory104, which in the illustrated example is DRAM. Host device100may store data in nonvolatile storage device106. Nonvolatile storage device106may be any suitable device that provides nonvolatile memory storage for host device100. Nonvolatile storage device106may be a removable storage device, such as a solid state drive (SSD) that is removably connectable to host device100. In an alternate example, nonvolatile storage device106may be non-removable or integrated within host device100.

Nonvolatile storage device106includes a device controller108and nonvolatile memory110. Device controller108controls access to nonvolatile memory110. In one embodiment, device controller108may be a nonvolatile memory controller that implements or supports the NVMe protocol, and nonvolatile memory110may be 2D or 3D NAND flash memory.

In order for host device100to read data from or write data to nonvolatile storage device106, host processor102creates and writes commands in submission queues1121,1122, and1123. Three submission queues are shown for illustrative purposes. It is understood that there may be more or fewer than three submission queues at any given time depending on NVMe device usage by the host system. Device controller108fetches the commands from submission queues1121,1122, and1123and executes the commands. Upon completion of the commands, device controller108writes completion entries to completion queues1141,1142, and1143.

As set forth above, one mechanism by which device controller108may select or fetch commands from submission queues from1121,1122, and1123is round robin selection. This mechanism is illustrated inFIG. 2. InFIG. 2, a round robin arbiter200statically selects a command from one of submission queues1121through112nbased on a round robin selection algorithm regardless of device state, the status of the corresponding completion queues, or any other information. Round robin selection involves selecting from each queues1121through112nin order from 1 to n and continually repeating the selection in the same order. Round robin arbiter200instructs command fetching logic202to select each command. Command fetching logic202provides the command to command processing logic (not shown inFIG. 2), which processes the command. While round robin selection can ensure equal serving of submission queues, storage device resources may not be optimally utilized, especially when commands from the submission queues are fetched but cannot be processed due to storage device resource constraints. For example, if a write command is fetched from a submission queue and the nonvolatile storage device is unable to process the write command, then the storage device may wait until resources are available to process the write command. If the storage device processing resources for processing a read command were available but not used during the wait period, then such resources are not being efficiently utilized.

Another mechanism for statically selecting commands from submission queues is illustrated inFIG. 3. InFIG. 3, weighted round robin selection is illustrated. Submission queues1121through112nare grouped according to priorities. Round-robin arbiters2001through200meach implement round robin selection for their respective queues and pass the selected queue to the next level in the hierarchy. A weighted round robin arbiter300selects commands from the candidates selected by round robin arbiters2002,2003, and200mat the previous level using assigned weights to order the candidates in each round of round robin selection. Weighted round robin arbiter300passes its selected queue as a selection candidate to the next level in the hierarchy, which is the highest level. A priority arbiter302at the highest level in the hierarchy selects from the output of arbiter300, admin queue112, and the output of arbiter200, using host assigned priorities. While the mechanism illustrated inFIG. 3allows for prioritization of commands, the priorities are statically set by the host and do not consider submission queue command statistics or nonvolatile storage device resource state. As a result, commands that cannot be immediately processed may be fetched while other commands that could be immediately processed remain enqueued in the submission queues.

FIG. 4is a block diagram illustrating intelligent fetching of commands from submission queues according to an embodiment of the subject matter described herein. InFIG. 4, device controller108includes a command monitor400that collects submission queue statistics and a storage device resource monitor402that monitors storage device resource state. Examples of submission queue statistics that may be collected are illustrated inFIG. 5. InFIG. 5, the submission queue statistics include, for each submission queue, the number of pending commands, the number of commands fetched from the queue, the number of read commands fetched from the queue, the ratio of read commands to write commands fetched from the queue, the average command size, the smallest command size, and the largest command size.

Statistics such as those illustrated inFIG. 5may be used to determine the type of commands that are likely to come from a particular submission queue, given statistics on commands that have historically been fetched from the submission queue. For example, it may be determined that a particular submission queue historically contains read commands 90% of the time or write commands 90% of the time and thus the submission queue is likely to contain read or write commands in the future. In another example, the statistics may be used to determine that a particular queue historically contains a majority of random I/O commands or a majority of sequential I/O commands and thus is likely to contain a majority of random or sequential I/O commands in the future. In yet another example, the statistics may indicate commands of a particular size are historically present in a given queue, where the size of the commands refers to the amount of data written or read by a particular command. This command size information may be used by device controller108to predict that the next command from a particular submission queue is likely to be of a certain size or within a certain size range.

Information about the commands can be learned by device controller108as commands are fetched from the submission queues by reading the values of predetermined fields in the command structure.FIG. 6illustrates an exemplary structure for an NVMe command. InFIG. 6, the opcode field specifies the type of command to be executed, i.e., read, write or admin. In the NVMe standard, a read command has opcode h1and a write command has opcode h2. Other information that may be useful to device controller108in intelligent command fetching includes the size of the command, which is specified by the number of logical blocks (NLB) field in the opcode of the command. Thus, device controller108may read the NLB value in commands that it fetches to determine command size.

Information such as that illustrated inFIG. 5can be used in combination with storage device resource state information to intelligently fetch commands. Returning toFIG. 4, submission queue selector404receives input from command monitor400regarding submission queue statistics and input from storage device resource monitor402regarding storage device resource state. Examples of storage device resource state information include the status of a read or write pipeline in the storage device, i.e., whether the pipeline is currently available to receive additional read or writhe commands. The terms “read pipeline” and “write pipeline” refer to components of nonvolatile storage device106respectively associated with reading data from and writing data to nonvolatile memory110. Such components may include queues and circuitry internal to device controller108, external to device controller108, internal to nonvolatile memory110, and/or external to nonvolatile memory110. Submission queue selector404may utilize the submission queue statistics and the storage device resource state to identify one of submission queues1121-112nfrom which the next command to be processed is selected and provide input to fetcher406that identifies the selected queue. Fetcher406receives the selection input from submission queue selector404and may also receive input from arbitration logic408. Arbitration logic408may implement round robin, weighted round robin, or other selection algorithm as described above. In one example, the intelligent selection from submission queue selector404may override round robin or weighted round robin selection provided by arbitration logic408. In another example, the selection input from command submission queue selector404may mask a particular queue from the current round of round robin or weighted round robin selection so that the queue is not included or passed over in the current round of round robin or weighted round robin selection.

One specific example of intelligent command fetching may be that the command monitor400determines that submission queue1121has historically contained mostly read commands and submission queue1122has historically contained mostly write commands. Storage device resource monitor402may determine that the storage device is currently incapable of processing write commands because the internal write pipeline is full, but the read pipeline is capable of processing read commands. In such a case, submission queue selector404will select submission queue1121as the submission queue from which the next command will be selected, which, based on the statistics is likely to be a read command. A similar selection may be performed from submission queue1122if it is determined that the read pipeline is full but that the write pipeline is available.

In another example, it may be desirable to select a number of random writes to fill a page of storage device memory with random writes. In such an example, command monitor400may determine that one of submission queues1121through112nhas historically contained mostly random writes of small size, such as 4 kilobytes. Submission queue selector404may then fetch enough random writes from the identified queue to fill a page and may select a number of random writes from that queue to fill the page.

FIGS. 7A and 7Billustrate intelligent submission queue command fetching according to an embodiment of the subject matter described herein. Referring toFIG. 7A, in step700, the storage device may initially operate in a static submission queue selection mode. Static submission queue selection mode may be round robin, weighted round robin or any other mode specified by the NVMe or other protocol where commands are fetched from submission queues in a static order. In steps702and704, the device collects submission queue command statistics and monitors storage device resource state. Steps702and704may be performed continually, whether static command fetching, dynamic command fetching, or a combination of static and dynamic command fetching is being implemented. In step706, it is determined whether to switch to dynamic mode. Switching to dynamic mode may be implemented, for example, when storage device resource state information indicates that one or more storage device resources are over- or under-utilized. In another example, dynamic mode may be implemented continually and step706may be omitted.

Referring toFIG. 7B, once the storage device is in dynamic submission queue selection mode, control proceeds to step708where the storage device uses submission queue command statistics and storage device resource state to select the submission queue from which the next command or commands should be fetched. This step may be performed by device controller108using the statistics collected by command monitor400and the storage device resource state information collected by storage device resource monitor402. In step710, the command is fetched from the selected submission queue. For example, submission queue selector404may provide a selection input to fetcher406which fetches the command from the identified submission queue. In step712, the command is provided to command processing logic410. For example, submission queue selector404may provide the command to command processing logic410. Command processing logic410may process the command, which may be a memory read, a memory write, or an admin command, and perform the selected operation on the nonvolatile memory device106. Command processing logic410or a separate process may write an entry to a completion queue indicating completion of command and an indication of whether the command was completed with or without error.

Device controller108may operate in dynamic submission queue selection mode as long as there is a constraint or limitation on available storage device resources. If the constraint or limitation is removed, device controller108may switch back into static submission queue selection mode. Thus, device controller108may control the switching of storage device106between static and dynamic submission queue selection modes depending on device resource state.

Intelligent memory device command fetching according to the subject matter described herein improves utilization of nonvolatile storage devices by selecting or fetching commands from submission queues when storage device resources are available to process the commands. Such intelligent fetching also improves host utilization of a nonvolatile storage device because the nonvolatile storage device may process commands from the host faster than in implementations where round robin or weighted round robin command fetching only is used. It should also be noted that any of the intelligent command fetching methods or systems described herein may be used in combination with round robin, weighted round robin selection, or other host-defined command fetching algorithm without departing from the scope of the subject matter described herein.

The subject matter described herein can be implemented in any suitable NAND flash memory, including 2D or 3D NAND flash memory. Semiconductor memory devices include volatile memory devices, such as dynamic random access memory (“DRAM”) or static random access memory (“SRAM”) devices, nonvolatile memory devices, such as resistive random access memory (“ReRAM”), electrically erasable programmable read only memory (“EEPROM”), flash memory (which can also be considered a subset of EEPROM), ferroelectric random access memory (“FRAM”), and magnetoresistive random access memory (“MRAM”), and other semiconductor elements capable of storing information. Each type of memory device may have different configurations. For example, flash memory devices may be configured in a NAND or a NOR configuration.

One of skill in the art will recognize that the subject matter described herein is not limited to the two dimensional and three dimensional exemplary structures described but cover all relevant memory structures within the spirit and scope of the subject matter as described herein and as understood by one of skill in the art.