Patent Description:
The following background is intended solely to provide information necessary to understand the context of the inventive ideas and concepts disclosed herein. Thus, this background section may contain patentable subject matter and should not be regarded as a disclosure of prior art.

From the perspective of a storage device, there is generally no guarantee that a given I/O command will be performed before any other given I/O command. There are a variety of reasons for this, but three important ones of note are, first, that I/O commands may be of differing size and complexity (e.g., a small write is generally faster than a large write, and for some media, reads are considerably faster than writes); second, that there are multiple internal channels for processing commands, each associated with storage media in the storage device, and each channel has a processing queue independent of the host's processing queues (e.g., multiple channels to multiple NAND flash chips, each individual channel servicing specific physical addresses); and third, that some storage devices have background operations which may occupy one or more internal processing channels at uncontrollable intervals (e.g., garbage collection in NAND flash).

When utilizing a storage system, write coherency and consistency may be essential properties that should be maintained. For example, when a computer system requests that a datum first be written, and then later read, in that order, the computer system should ensure that the commands are in fact processed in that order. Otherwise, if the read command were to be executed before the write command, the read command would return incorrect (old) data. As a further example, if an older write request were processed after a newer write request, an illegal overwrite would occur, and the data recorded on the device would be incorrect. This managerial problem is amplified if multiple applications are allowed to access the same datum, and if there are multiple queues by which the host can issue I/O commands.

<CIT> discloses to receive memory access commands at a memory controller, to adjust timing in connection with read command or write command and to send a completion message to the host after writing the data to the memory.

Thus, there is a desire for mechanisms to enhance the ability of storage devices to manage write scheduling.

The scope of protection is defined in the appended claims.

Aspects of embodiments of the concepts of the present disclosure relate to systems and methods by which a computing system, and, more specifically, a storage device, may perform I/O command processing and notification in order with minimal effort by a host. A sequence tag generator logic is used to provide sequence tags to I/O commands. The storage device comprises a command handler logic to initiate the processing of I/O commands in an order dependent upon their sequence tags. The storage device comprises a notification logic that is configured to coalesce I/O command notifications and return them to a host in the order of their sequence tags.

According to a first aspect, provided is a method as defined by claim <NUM>.

According to a second aspect, provided is a storage device as defined by claim <NUM>.

These and other features and aspects of the present disclosure will be appreciated and understood with reference to the specification, claims, and appended drawings wherein:.

Various example embodiments will be described more fully hereinafter with reference to the accompanying drawings, in which some example embodiments are shown. The presently disclosed subject matter may, however, be embodied in many different forms. These example embodiments are provided so that this disclosure will be thorough anc complete, and will fully convey the scope of the presently disclosed subject matter to those skilled in the art. In the drawings, the sizes and relative sizes of layers and regions may be exaggerated for clarity.

It will be understood that when an element or layer is referred to as being "on," "connected to," or "coupled to" another element or layer, it may be directly on, connected to, or coupled to the other element or layer, or intervening elements or layers may be present. When an element is referred to as being "directly on," "directly connected to," or "directly coupled to" another element or layer, there are no intervening elements or layers present. As used herein, the term "and/or" comprises any and all combinations of one or more of the associated listed items.

It will be understood that, although the terms first, second, third, and so on may be used herein to describe various elements, components, regions, layers, and/or sections, these elements, components, regions, layers, and/or sections should not be limited by these terms. These terms are used only to distinguish one element, component, region, layer, or section from another region, layer, or section. Thus, a first element, component, region, layer, or section discussed below could be termed a second element, component, region, layer, or section without departing from the teachings of the presently disclosed subject matter.

Spatially relative terms, such as "beneath," "below," "lower," "above," "upper," and the like, may be used herein for ease of description to describe one element or feature's relationship to another element(s) or feature(s) as illustrated in the figures. Thus, the term "below" may encompass both an orientation of above and below. The device may be otherwise oriented (e.g., rotated <NUM> degrees or at other orientations), and the spatially relative descriptors used herein should be interpreted accordingly.

The terminology used herein is for the purpose of describing particular example embodiments only. As used herein, the singular forms "a," "an" and "the" are intended to comprise the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, integers, processes, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, processes, operations, elements, components, and/or groups thereof.

Example embodiments are described herein with reference to cross-sectional illustrations that are schematic illustrations of idealized example embodiments (and intermediate structures). Thus, example embodiments should not be construed as limited to the particular shapes of regions illustrated herein but are to comprise deviations in shapes that result, for example, from manufacturing. For example, an implanted region illustrated as a rectangle will, typically, have rounded or curved features and/or a gradient of implant concentration at its edges rather than a binary change from implanted to non-implanted region. Likewise, a buried region formed by implantation may result in some implantation in the region between the buried region and the surface through which the implantation takes place. Thus, the regions illustrated in the figures are schematic in nature and their shapes are not intended to illustrate the actual shape of a region of a device.

Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosed subject matter belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having meanings that are consistent with their respective meanings in the context of the relevant art and are not to be interpreted in an idealized or overly formal sense unless expressly so defined herein.

Hereinafter, example embodiments will be explained in detail with reference to the accompanying drawings.

<FIG> is a schematic block diagram of an information processing system <NUM>, which may comprise semiconductor devices formed according to principles of the disclosed subject matter.

Referring to <FIG>, an information processing system <NUM> may comprise one or more of devices constructed according to the principles of the disclosed subject matter. In one or more other embodiments, the information processing system <NUM> may employ or execute one or more techniques according to the principles of the disclosed subject matter.

In various embodiments, the information processing system <NUM> may comprise a computing device, such as, for example, a laptop, desktop, workstation, server, blade server, personal digital assistant, smartphone, tablet, and other appropriate computers or a virtual machine or virtual computing device thereof. In various embodiments, the information processing system <NUM> may be used by a user.

The information processing system <NUM> according to the disclosed subject matter may further comprise a central processing unit (CPU), logic, or processor <NUM>. In some embodiments, the processor <NUM> may comprise one or more functional unit blocks (FUBs) or combinational logic blocks (CLBs) <NUM>. In such an embodiment, a combinational logic block may comprise various Boolean logic operations (e.g., NAND, NOR, NOT, XOR), stabilizing logic devices (e.g., flip-flops, latches), other logic devices, or a combination thereof. These combinational logic operations may be configured in simple or complex fashion to process input signals to achieve a desired result. It is to be understood that while a few illustrative examples of synchronous combinational logic operations are described, the disclosed subject matter is not so limited and may comprise asynchronous operations, or a mixture of synchronous and asynchronous operations. In one embodiment, the combinational logic operations may comprise a plurality of complementary metal-oxide-semiconductor (CMOS) transistors. In various embodiments, these CMOS transistors may be arranged into gates that perform logical operations, although it is understood that other technologies may be used and are within the scope of the disclosed subject matter.

The information processing system <NUM> according to the disclosed subject matter may further comprise a volatile memory <NUM> (e.g., a Random Access Memory (RAM)). The information processing system <NUM> according to the disclosed subject matter may further comprise a non-volatile memory <NUM> (e.g., a hard drive, an optical memory, a NAND or flash memory, and/or other solid-state memories). In some embodiments, either the volatile memory <NUM>, the non-volatile memory <NUM>, or a combination or portions thereof may be referred to as a "storage medium. " In various embodiments, the volatile memory <NUM> and/or the non-volatile memory <NUM> may be configured to store data in a semi-permanent or substantially permanent form.

In various embodiments, the information processing system <NUM> may comprise one or more network interfaces <NUM> configured to allow the information processing system <NUM> to be part of and communicate via a communications network via a wired and/or wireless and/or cellular protocol. Examples of a wireless protocol may comprise, but are not limited to, Institute of Electrical and Electronics Engineers (IEEE) <NUM>, IEEE <NUM>. Examples of a cellular protocol may comprise, but are not limited to: IEEE <NUM> (a. Wireless-MAN (Metropolitan Area Network) Advanced, Long Term Evolution (LTE) Advanced, Enhanced Data rates for GSM (Global System for Mobile Communications) Evolution (EDGE), Evolved High-Speed Packet Access (HSPA+)). Examples of a wired protocol may comprise, but are not limited to, IEEE <NUM> (a. Ethernet), Fibre Channel, Power Line communication (e.g., HomePlug, IEEE <NUM>). It is understood that the above are merely a few illustrative examples to which the disclosed subject matter is not limited. As a result of being connected to a network via the network interfaces <NUM>, the information processing system <NUM> may have access to other resources, for example, external volatile memories, non-volatile memories, processors/logic, and software, whether as stand-alone network resources or as components of an external additional system.

The information processing system <NUM> according to the disclosed subject matter may further comprise a user interface unit <NUM> (e.g., a display adapter, a haptic interface, and/or a human interface device). In various embodiments, this user interface unit <NUM> may be configured to either receive input from a user and/or provide output to a user. Other kinds of devices may be used to provide for interaction with a user as well; for example, feedback provided to the user may be any form of sensory feedback, e.g., visual feedback, auditory feedback, and/or tactile feedback; and input from the user may be received in any form, including acoustic, speech, and/or tactile input.

In various embodiments, the information processing system <NUM> may comprise one or more other devices or hardware components <NUM> (e.g., a display or monitor, a keyboard, a mouse, a camera, a fingerprint reader, and/or a video processor). It is understood that the above are merely a few illustrative examples to which the disclosed subject matter is not limited.

The information processing system <NUM> according to the disclosed subject matter may further comprise one or more system buses <NUM>. In such an embodiment, the system bus <NUM> may be configured to communicatively couple the processor <NUM>, the volatile memory <NUM>, the non-volatile memory <NUM>, the network interface <NUM>, the user interface unit <NUM>, and one or more hardware components <NUM>. Data processed by the processor <NUM> or data inputted from outside of the non-volatile memory <NUM> may be stored in either the non-volatile memory <NUM> or the volatile memory <NUM>.

In various embodiments, the information processing system <NUM> may comprise or execute one or more software components <NUM>. In some embodiments, the software components <NUM> may comprise an operating system (OS) and/or an application. In some embodiments, the OS may be configured to provide one or more services to an application and manage or act as an intermediary between the application and the various hardware components (e.g., the processor <NUM> and/or a network interface <NUM>) of the information processing system <NUM>. In such an embodiment, the information processing system <NUM> may comprise one or more native applications, which may be installed locally (e.g., within the non-volatile memory <NUM>) and configured to be executed directly by the processor <NUM> and directly interact with the OS. In such an embodiment, the native applications may comprise pre-compiled machine-executable code. In some embodiments, the native applications may comprise a script interpreter (e.g., C shell (csh), AppleScript, AutoHotkey) and/or a virtual execution machine (VM) (e.g., the Java Virtual Machine, the Microsoft Common Language Runtime) that are configured to translate source or object code into executable code which is then executed by the processor <NUM>.

As discussed herein, devices may comprise logics configured to perform various tasks. The logics may be embodied as hardware, software, or a combination thereof. When a logic comprises hardware, the hardware may be in the form of specialized circuit arrangements (e.g., ASICS), programmable arrays of gate logics and memories (e.g., FPGAs), or specially programmed general-purpose logic (e.g., CPUs and GPUs). When the logic comprises software, the software may be configured to operate specialized circuits, or to program arrays of circuits, memories, or operate general-purpose processors. Logic embodied in software may be stored on any available storage medium, such as DRAM, flash, EEPROM, Resistive memories, and/or the like.

<FIG> illustrates an embodiment of a mechanism <NUM> for a Host <NUM> to communicate with a solid-state drive (SSD) <NUM> to coordinate the processing of I/O commands. <FIG> illustrates a block diagram of an embodiment <NUM> of the Host <NUM> and the SSD <NUM> capable of performing the method described in <FIG>. In some embodiments, the Host <NUM> may be similar to the computing system as information processing system <NUM> of <FIG>. The SSD <NUM> may function as the volatile memory <NUM> or the non-volatile memory <NUM>, or as a resource available over the network interface <NUM> of <FIG>. The I/O commands may be any sort of I/O commands, including key-value based commands, logical block address (LBA) based commands, and/or others.

Turning now to <FIG>, according to an example mechanism, the Host <NUM> is responsible for tracking I/O commands issued by the operating system or various applications <NUM>, running on the Host <NUM> as threads <NUM>. As disclosed more thoroughly below, the Host <NUM> is responsible for preventing I/O errors caused by the possible out-of-order processing of commands by the SSD <NUM>. Such errors comprise, but are not limited to: illegal over-writes (where older data over-writes newer data), reading stale data (where a read is issued after a write, but is processed before the write), and out-of-order notifications to applications (where an application is informed of a sequence of actions that is different from what actually occured, leading the application to believe that an error has occurred when it has not, or to not believe an error has occurred when it has). As described more thoroughly below, the host may do this by, amongst other things, issuing locks on SSD resources (e.g., locking queues), and delaying the issuance of dependent commands (e.g., a read that follows, and therefore depends on, an earlier write) until the host has received a completion notice of the command upon which it depends.

At process <NUM>, the Host <NUM> prepares to issue I/O commands (which ultimately mature as commands 345a-d), such as I/O commands issued by the OS or any applications <NUM> using the Host <NUM>, and tracks the order in which the I/O commands were issued, and the identity of the applications issuing the I/O commands. During process <NUM>, the I/O commands (along with an indication of receipt order and issuing application) may be staged in a memory, such as the volatile memory <NUM> of <FIG>, for processing.

At process <NUM>, the I/O commands are sent, in order, to an SSD. The act of sending may be through placing I/O commands into one or more host-side I/O submission queues <NUM>, which may be read into, and associated with, command queues <NUM> on the SSD <NUM>. The I/O commands may be placed in a plurality of I/O submission queues 320a-b; two queues are shown, but any number greater than two are also possible. The I/O commands may be placed in the I/O queues 320a-b by various mechanisms, including by association of a particular queue with a processor core/threads <NUM>, association of a particular queue with an application/OS <NUM>, and/or via a hash logic <NUM> (such as by hashing a key of a key-value pair to determine an I/O queue <NUM>). The act of sending an I/O command in order may involve waiting until the I/O command upon which the sent I/O command depends is completed, or until a lock on resources is released.

At process <NUM>, the SSD <NUM> receives and buffers the I/O commands, shown as I/O commands 345a-d. Four commands are illustrated, but any suitable number are possible, as those of ordinary skill in the art would appreciate. I/O commands 345a-d are shown with respective time markers (t1-t4), but this is for conceptual illustration purposes and is not meant to be a process of the system. The commands are also marked with labels W2, W1, R1, and W3, respectively, to indicate the nature of the command (Read or Write) and the address they are associated with. This marking is merely descriptive of the example commands 345a-d, and is not meant to indicate a process of the system. The commands 345a-d may be buffered or stored internally to the SSD <NUM> in one or more command queues 325a-b, which may correspond to a respective set of I/O submission queues 320a-b on the Host <NUM>. As with the host, <NUM> queues are shown, but more are also possible. The command queues 325a-b may have their I/O commands 345a-d fetched for processing by a command handler logic <NUM> (e.g., for actual retrieval from the solid-state memory) in the storage device in a round-robin manner. This command handler logic <NUM> may be embodied in a storage device's controller circuitry (not shown). This round-robin processing prevents or substantially prevents any given queue (and associated application) from monopolizing the SSD <NUM>.

At process <NUM>, commands 340a-d that were fetched from the SSD's command queues 325a-b may be issued, by the command handler logic <NUM>, to a plurality of the SSD <NUM>'s memory device channel queues 340a-b for actual performance by the flash memory chips located on channels 335a-b (flash memory being one example of many possible solid-state storage memories that one or more embodiments may use).

By way of example, in some embodiments, within the SSD <NUM>, physical solid-state memories (e.g., flash memory chips) are placed into multiple parallel physical channels on an SSD, in order to allow for parallel processing of I/O commands. This is illustrated with the flash chips occupying physical channels (e.g., physical channels or flash channels) 335a,b (two channels 335a-b with four chips shown, but more channels and differing numbers of chips are possible). When I/O commands such as 345a-b are sent to physical memory for processing, they may be placed into a set of memory device channel queues 340a-b, associated with respective physical channels 335a,b. I/O commands may be sent to one or more specific memory device channel queues 340a-b based on the physical address(es) associated with each I/O command. By way of example, when an I/O command such as one of 345a-d is to be processed, the command handler logic <NUM> may determine physical addresses associated with the command, determine one or more memory device channel queues 340a-b housing memory (such as flash chips on the channels 335a-b) containing the physical addresses, and place the I/O command in the channel queues 340a-b that are associated with the memories having those addresses.

In the example of <FIG>, it should be noted that the physical processing of the commands 345a-d may be done out of order due to the combination of round-robin command queue fetching by command handler logic <NUM>, combined with physical address determined placement in the channel queues 340a-b. For example, it should be noted that the channel queue 340a receives command 345a (t1, W2), and the channel queue 340b receives commands 345b (t2, W1) and 345d (t4, W3), with command 345d ahead of command 345b, due to the round-robin fetching. Thus, the commands 345a and 345d are at the head of their respective channel queues 340a-b. Therefore, it is quite possible (especially if command 345d is a "small" write command) for command 345d to be completed before command 345a. This out-of-order processing may be exacerbated by certain background operations required of the solid-state memory. For example, if garbage collection must be performed on a flash chip in the channel 335a, then the entirety of the channel 335a and the associated channel queue 340a (and possibly other channels) may be unavailable for processing commands, whereas other channels not occupied with garbage collection are free to process their respective queues <NUM>.

Returning now to <FIG>, at process <NUM>, the SSD <NUM>, via notification logic <NUM>, notifies the Host <NUM> of completed I/O commands 345a-d in the order in which the SSD completes them (that is, potentially out of order, as described above). In the illustrated embodiment, the order of notifications would be 345d, then 345a, then 345b (with 345c still not completed). The notification logic <NUM> may be comprised within a storage controller (not shown) of the SSD <NUM>.

At process <NUM>, the Host <NUM> receives the I/O completion notifications sent from the SSD <NUM> in the order in which the SSD sends them (that is, potentially out of order). For example, as illustrated in <FIG>, the order of command completion notification is 345d, 345a, then 345b, with command 345c yet to be processed. The host may then accumulate the completion notifications necessary to confirm that no timing/consistency errors have occurred, destage the I/O command requests, and send the I/O completion notifications to the application/OS <NUM> in the order in which the application/OS <NUM> requested them (that is, in order: 345a, 345b, and awaiting 345c before notifying on 345d). Locks on resources may be released. If potential consistency errors are detected, then the I/O requests may be repeated rather than destaged, and the application/OS <NUM> is not informed of the completion notifications.

As may be observed from examining <FIG> and their associated discussion, the mechanism described above may generally avoid the most serious forms of consistency errors because a series of I/O commands from a given application to a given address will be restricted to a single host-side I/O queue <NUM>, a single SSD command queue <NUM>, and a predetermined set of channel queues <NUM>. Further, inter-application consistency errors may be reduced via the locking of one or more queues. Still, this mechanism requires substantial resource utilization from the host, and invokes inefficiencies within the SSD. Specifically, the host must stage and destage all I/O requests according to the order in which they were received, and must track completion notifications sufficiently to ensure that no consistency errors have occurred. Further, the locking of a queue reduces the overall number of I/Os that may be processed by the queue in a given time, and the round-robin issuance of I/O commands 345a-d from command queues 325a-b to channel queues <NUM> may leave one or more of such queues being underutilized.

<FIG> illustrates an embodiment of a mechanism <NUM> for a Host <NUM>' to communicate with a solid-state drive (SSD) <NUM>' to coordinate the processing of I/O commands with reduced host overhead. <FIG> illustrates a block diagram of an embodiment <NUM> of the Host <NUM>' and the SSD <NUM>' capable of performing the method described in <FIG>. In some embodiments, the Host <NUM>' may be similar to the computing system as information processing system <NUM> of <FIG>. In some embodiments, the SSD <NUM>' may function as the volatile memory <NUM> or the non-volatile memory <NUM> of <FIG>, or as a resource available over the network interface <NUM>. The I/O commands may be any sort of I/O commands, including key-value based commands, logical block address (LBA) based commands, or others.

As will be shown further below, the example embodiments illustrated in <FIG> are structured to allow the SSD <NUM>' to receive I/O commands from the Host <NUM>' in a defined order, and notify the Host <NUM>' of command completions in that same order. This allows the Host <NUM>' to forego much of the host-side I/O management discussed above with regard to <FIG>, and allows the SSD <NUM>' to more efficiently use its own internal resources.

Turning to <FIG>, at process <NUM>, the Host <NUM>' sends I/O commands to the SSD <NUM>' in the order that they are generated by an application/OS <NUM>. The act of sending may be through one or more host-side I/O submission queues 520a-c, which may be read into, and associated with, command queues 525a-c on the SSD <NUM>'. The I/O commands may be placed in a plurality of I/O submission queues 520a-c; three queues are shown, but any number greater than two are possible. The I/O requests may be placed in the I/O submission queues 520a-c directly by association of a particular queue with a processor core/threads <NUM>, and/or association of a particular queue with an application/OS <NUM>. As a result of the sending of process <NUM>, commands 545a-h are placed in the command queues 525a-c of the SSD <NUM>'.

As will be made more readily apparent below, in this embodiment, the Host <NUM>' may simply queue I/O commands directly with minimal processing, and need not stage I/O requests (including tracking the issuing sequence and identity of an issuer), lock resources, destage the I/O requests upon completion, or monitor the order and/or consistency of I/O completion notifications, thereby freeing up host resources.

In some embodiments, at process <NUM>, each I/O command is associated with a timestamp or other sequential number (such as an ordinal integer) that is determined by the order in which each I/O command is sent, which may be called a sequence tag. The timestamp or sequential number (sequence tag) may be generated by a sequence tag generator logic <NUM>. The sequence tag generator logic <NUM> may be located on either the Host <NUM>' or the SSD <NUM>'. In embodiments where the Host <NUM>' comprises the sequence tag generator logic <NUM>, the sequence tag is sent along with the I/O command to the SSD <NUM>'. In embodiments where the Host <NUM>' comprises the sequence tag generator logic <NUM>, the sequence tag generator may be used to ensure that, if an I/O command may be decomposed into a set of logical block address (LBA) directed operations, all of the decomposed commands utilize consecutive sequence tags. In embodiments where the SSD <NUM>' comprises the sequence tag generator logic <NUM>, I/O commands need not be sent from the Host <NUM>' with sequence tags; sequence tags are added to the I/O commands when they are received by the SSD <NUM>'. The sequence tags are illustrated on commands 545a-h as tags t1 through t8. In various embodiments where the sequence tag generator logic <NUM> is located on the SSD <NUM>', the sequence tag generator logic <NUM> may be in communication with the index logic, the command handler logic, and/or the command queues, depending in part on where the sequence tag (and/or its association with an I/O command) is stored.

Turning now to <FIG>, it should be noted that I/O commands 545a-h are associated with respective sequence tags t1-t8. It should also be noted that the commands have been placed in the command queues 525a-c associated with respective I/O command submission queues 520a-c, which in turn are associated with user/OS I/O threads <NUM>. It should further be noted that within each queue, the I/O commands 545a-h are in temporal order, but, across queues, there is no specific order. It should also be noted that each I/O command 545a-h is illustrated with an example operation type (read or write) and address (EG <NUM>-<NUM>). This is for purposes of illustrating the effects of the embodiments, and is not reflective of any action of the embodiments.

Further with regard to <FIG>, the SSD <NUM>' comprises an index logic <NUM>. The index logic <NUM> indexes all I/O commands 545a-h in the command queues 525a-c in sequence tag order, and may be the mechanism by which sequence tags are associated with specific I/O commands 545a-h. The index logic <NUM> may comprise a min-heap index; however, many other indexes would also suffice. In some embodiments, the index logic <NUM> may also track the activities of the physical memory channels 535a-b and their associated queues 540a,b, as will be discussed below; however, in other embodiments, other logics may track these activities (also discussed below). The SSD <NUM>' also comprises a command handler logic <NUM>. The index logic <NUM> may additionally comprise, or be in communication with, an index memory for housing the index (not shown). The index logic <NUM> may also be in communication with the sequence tag generator logic <NUM>, the command handler logic <NUM>, and/or the command queues 525a-c.

Returning now to <FIG>, at process <NUM>, the command handler logic <NUM> fetches I/O commands 545a-h from the command queues 525a-c in sequence tag order, determines the physical block addresses associated with each specific I/O command 545a-h, and places (in fetching order) each specific I/O command 545a-h into one or more physical channel queues 540a-b associated with respective physical storage channels (i.e., physical channels) 535a,b, each in turn including the solid-state memory chips associated with the determined physical addresses.

By way of example, in some embodiments, within the SSD <NUM>', physical solid-state memories (e.g., flash memory chips) are placed into multiple parallel physical channels on an SSD in order to allow for parallel processing of I/O commands. This is illustrated with the flash chips occupying the physical channels 535a,b (two channels 535a-b, with four chips, are shown; however, more channels and differing numbers of chips are possible). When I/O commands such as 545a-h are sent to physical memory for processing, they may be placed into a set of memory device physical channel queues 540a-b. I/O commands may be sent to one or more specific memory device physical channel queues 540a-b based on the physical address(es) associated with each I/O command. By way of example, when an I/O command such as one of 545a-d is to be processed, the command handler logic <NUM> may determine physical addresses associated with the command, determine one or more memory device channel queues 540a-b housing memory (such as flash chips on the physical channels 535a-b) containing the physical addresses, and place the I/O command in the channel queues 540a-b that are associated with the memories having those addresses.

The command handler logic <NUM> may utilize a sequence ID based command fetcher <NUM>,in turn utilizing the index logic <NUM> to ensure that it processes commands from the I/O command queues 525a-c into the physical channel queues 540a,b in tag sequence order. Upon issuing a specific I/O command 545a-h to the channel queues 540a,b, the I/O command is removed from the index <NUM> and from the command queues 525a-c. When an I/O command is placed within the channel queues 540a,b, it may be indexed by an index (not shown) in the I/O sequencer logic <NUM> of a notification manager logic <NUM>, as will be discussed further below.

With regard to <FIG>, it should be noted that because the command handler logic <NUM> has sent I/O commands 545a-h to the physical channel queues 540a,b in order, this results in each of the individual channel queues 540a,b having all commands listed therein in order. This may prevent any data-consistency errors: all operations on a given physical address will be processed in order, so there is no possibility (or substantially no possibility) of write-after-read errors, or old-write-after-new-write errors, etc. The following non-illustrated circumstance should further be noted: If a command comprises operations on an address range that spans multiple channels (for example, a write to a very large key-value, or a command whose LBA range may be translated to disparate physical addresses), then that command would be dispatched to multiple channels concurrently (e.g., simultaneously) and in the order it was given, maintaining consistency even for data items that span channels. However, the fact that each physical channel 535a,b may process requests at differing rates (for reasons similar to those discussed above, such as garbage collection), there can still be limited out-of-order I/O completions. However, as mentioned above, this out-of-order processing does not result in data-consistency errors or significant data-consistency errors.

Returning now to <FIG>, at process <NUM>, the SSD <NUM>' processes the I/O requests out of order. By way of example, as described above, the command handler logic <NUM>, utilizing sequence ID based command fetcher <NUM> may fetch I/O commands 545a-h from the command queues 525a-c in order, and place them into respective physical channel queues 540a,b in order, and each physical channel 535a,b will process it's respective channel queues 540a,b at it's own rate, possibly out of order.

At process <NUM>, the SSD <NUM>' may notify the Host <NUM>' of the I/O command completions in the same order in which the Host <NUM>' issued the I/O commands. By way of example, the SSD <NUM>' may comprise the notification manager logic <NUM>. The notification manager logic <NUM> may comprise an I/O sequencer logic <NUM>, a notification buffer <NUM>, and a host notification logic <NUM>. The notification buffer <NUM> may receive command completion notifications from the flash chips of the physical channels 535a,b for respective completed commands 545a-h. The I/O sequencer logic <NUM> may associate the completion notifications with the respective I/O commands 545a-h, and their associated sequence tags.

The I/O sequencer logic <NUM> may contain an index logic similar to index logic <NUM>, except that it tracks commands that have been issued to the physical channel queues 540a,b, rather than the I/O command queues 525a-c (index logic not shown). In other embodiments, the I/O sequencer logic is in communication with index logic <NUM>, which in some embodiments may track both the command queues 525a-c and the physical channel queues 540a,b. When the notification manager logic <NUM> receives a command completion notice from the physical channels 535a,b, the command completion notice is buffered in the notification buffer <NUM>, and the I/O sequencer logic <NUM> associates the notification with a respective I/O command 545a-h and a sequence tag. The notification manager logic <NUM> may check the I/O sequencer logic <NUM> to see if a command completion notification pending in the notification buffer <NUM> is for the I/O command 545a-h having the lowest sequence tag. Based on finding that a command completion notification in the notification buffer <NUM> is associated with an <NUM> command having the lowest sequence tag, the notification manager logic <NUM> may invoke the host notification logic <NUM> to notify the Host <NUM>' that the I/O command having the lowest sequence tag has been completed. In certain embodiments, the notification logic <NUM> may also notify the Host <NUM>' of any subsequent I/O command completions in the notification buffer <NUM> having sequence tags immediately following/sequential to the I/O command having the lowest sequence tag. Upon the sending of a command completion notification to the Host <NUM>', the command completion notice and associated I/O command listing and sequence tag are removed from the notification buffer <NUM> and the I/O sequencer logic <NUM> (e.g., by clearing the items from the buffer and index structure). Thus, the command completion notifications sent to the Host <NUM>' are returned in the same order as the original I/O commands were sent.

Returning now to <FIG>, at process <NUM>, the Host <NUM>' receives I/O command completion notifications in an order that corresponds to the order in which the original I/O commands 545a-h were sent to the SSD <NUM>'. The Host <NUM>' may then notify the various applications/OS <NUM> and/or user threads <NUM> of the I/O command completions. The applications/OS <NUM> and user threads <NUM> thereby are informed of the success of their operations in proper order.

Upon examining <FIG>, it is apparent that, in some embodiments, the use of host resources are greatly reduced. More specifically, I/O commands need not undergo extensive staging and destaging, and associated completion tracking and ordering, on the Host <NUM>'. Furthermore, the individual I/O queues 520a-c, nor any given address ranges, need incur any form of locking to prevent or reduce consistency errors. Furthermore, the Host <NUM>' need not operate any I/O distribution mechanism, such as the hash logic <NUM> of <FIG>. Finally, processor cycles and memory otherwise devoted to these tasks may be freed for other uses.

Turning now to <FIG>, <FIG> provides a flow chart for an embodiment of a process for the notification manager logic <NUM> of <FIG> to use when determining to issue command completion notices to the Host <NUM>' of <FIG>. At process <NUM>, the notification manager logic <NUM> receives a subject I/O command completion notification from a flash chip residing on the physical channels (e.g., a flash channel) 535a,b, and stores it in the notification buffer <NUM>.

At process <NUM>, the subject I/O command completion notification is associated with a particular I/O command (e.g., a KV request) of the I/O commands 545a-h, and its associated sequence tag. This may be done by referencing the command completion notice with an index logic associated with the I/O sequencer logic <NUM> (e.g., an internal index, or index logic <NUM>), as described above. In some embodiments, if an I/O command 545a-h has been distributed amongst multiple channels as described above, it is at this process that the individual channel completions are coalesced into a single "completion" for the I/O command.

At process <NUM>, the sequence tag of the subject I/O command completion notice is checked to see if it is the lowest sequence tag of the currently pending I/O commands' completion notices in the I/O sequencer logic <NUM>'s associated indexer logic (e.g., an internal index, or index logic <NUM>). In some embodiments, this may be done by comparing the sequence tag of the subject I/O command completion notice to a sequence tag number of that last-notified sequence tag. By way of example, in embodiments where the sequence tag is a sequential integer, the notification manager logic <NUM> may check to see if the sequence tag of the subject I/O command completion notice is one greater than sequence ID of the most recent I/O command completion notice sent to the host; if it is, then the subject command is the lowest-tagged pending I/O command completion notice. In other embodiments, such as where the sequence tag is a timestamp, the notification manager logic <NUM> may utilize the index logic associated with the I/O sequencer logic <NUM> (e.g., an internal index, or index logic <NUM>) to determine if the subject I/O command completion notification is the lowest-tagged such notification. More specifically, for example, if the subject I/O command completion notification is at the root of a min-heap index, then it is the lowest-tagged notification.

At process <NUM>, based on the subject I/O command completion notification not being the lowest-tagged of the associated outstanding I/O commands, the notification may be staged in the notification buffer for future notification (e.g., when I/O command completions with earlier sequence tags are processed, as illustrated below), and the process returns to process <NUM> ready to receive more I/O command completion notifications.

At process <NUM>, based on the subject I/O command completion notification being associated with the lowest outstanding command, the notification manager logic <NUM> may search through the notification buffer <NUM> to locate any buffered I/O command completion notifications that may be sequential to the subject I/O command completion notification. In some embodiments, this may be done by comparing the contents of the notification buffer <NUM> to the order provided in the index of the I/O sequencer logic <NUM>. In some alternative embodiments, this may be done by checking the sequence tags of the buffer contents for numerical sequentiality to the subject I/O command completion notification. The subject I/O command completion notification and any sequential I/O command completion notifications so identified may be sent to the host notification logic <NUM>, cleared from the notification buffer <NUM>, and removed from an index associated with the I/O sequencer logic <NUM> (e.g., an internal index, or index logic <NUM>), and the last sequence ID notified (of process <NUM>) may be updated.

At process <NUM>, the host notification logic <NUM> issues the subject I/O command completion notification and any sequential I/O command completion notifications identified in process <NUM> to the Host <NUM>'. The processes of <FIG> may then begin anew as needed.

<FIG> presents a method <NUM> for an SSD such as the SSD <NUM>' to receive I/O commands in order from the Host <NUM>', and to notify the Host <NUM>' of completed I/O commands in that same order. One of ordinary skill in the art would recognize that the processes in <FIG> may be done in alternate orders, or that certain processes can be added or removed without departing from the concepts disclosed herein.

At process <NUM>, I/O commands associated with respective sequence tags may be placed in one or more command queues, such as the command queues 525a-c of <FIG>, on the SSD <NUM>'. The sequence tags may be associated with the I/O commands either at the Host <NUM>' or at the SSD <NUM>' by a sequence tag generator logic such as the sequence tag generator logic <NUM> of <FIG>.

At process <NUM>, the I/O commands may be indexed in an I/O command queue index, such as the index logicindex logic <NUM> of <FIG>, whereby the index tracks the association of the I/O commands and the sequence tags, and orders the entries according to sequence tag sequentiality.

At process <NUM>, the I/O commands may be moved from an I/O command queue to one or more physical channel queues, such as the channel queues 540a,b of <FIG>, according to the sequential order of their sequence tags. The physical channel queue(s) may correspond to physical channels housing solid-state memory chips containing the physical addresses to which the I/O commands correspond. By way of example, in some embodiments, this may be done by: determining the I/O command with the lowest sequence tag, determining one or more storage channels associated with an address of the I/O command determined to have the lowest sequence tag, and placing the determined I/O command into one or more storage channel queues for storage channels associated with the determined address of the I/O command. More specifically still, in some embodiments, the physical addresses may be derived from a key of a key-value pair. For example, in some embodiments, a key may be mapped to one or more physical addresses. In other embodiments, the physical addresses may be derived from one or more logical block addresses (LBAs), for example, in some embodiments, the one or more LBAs may be mapped to one or more physical addresses.

At process <NUM>, I/O commands that have been moved to a physical channel queue are removed from the I/O command queues, and the I/O command queue index is updated.

At process <NUM>, the flash channel queues each process their respective I/O commands. When an I/O command is completed, a corresponding I/O command completion notification may be sent to a notification manager logic, such as the notification manager logic <NUM> of <FIG>.

At process <NUM>, I/O command completion notices are collected. They may be collected in a notification buffer, such as the notification buffer <NUM> of the notification manager <NUM> of <FIG>.

At process <NUM>, I/O command completion notices are issued to the host in the same order in which the corresponding I/O commands were received. Process <NUM> may be accomplished through processes similar to those discussed above with respect to <FIG>.

Method processes may be performed by one or more programmable processors executing a computer program to perform functions by operating on input data and generating output. Method processes also may be performed by, and an apparatus may be implemented as, special-purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

In various embodiments, a computer-readable medium may comprise instructions that, when executed, cause a device to perform at least a portion of the method processes or processes. In some embodiments, the computer-readable medium may be comprised in a magnetic medium, optical medium, other medium, or a combination thereof (e.g., CD-ROM, hard drive, a read-only memory, a flash drive). In such an embodiment, the computer-readable medium may be a tangibly and non-transitorily embodied article of manufacture.

Claim 1:
A method (<NUM>) for processing IO requests in order by a storage device (<NUM>), the method (<NUM>) comprising:
receiving (<NUM>) a first I/O command and a second I/O command, the first I/O command and the second I/O command being assigned a sequence tag;
issuing (<NUM>) the first I/O command and the second I/O command to one or more storage channels based on their respective sequence tags;
collecting (<NUM>) a command completion notice of the first I/O command or the second I/O command when the first I/O command or the second I/O command has been respectively completed; and
issuing (<NUM>) a command completion notification to a host (<NUM>) based on the sequence tag of the associated completed first I/O command or second I/O command,
characterized in that:
the issuing of the command completion notification to the host (<NUM>) comprises:
determining if the sequence tag associated with a completed I/O command is the lowest sequence tag of all of the sequence tags associated with I/O commands awaiting processing,
based on determining that the sequence tag of the completed I/O command is the sequence tag of the lowest outstanding I/O command, issuing to the host (<NUM>) all command completion notifications for completed I/O commands having sequence tags that are sequential to the determined lowest sequence tag, including the completed I/O command having the lowest sequence tag, and
based on determining that the sequence tag of the completed I/O command is not the sequence tag of the lowest outstanding I/O command, placing the command completion notice in a buffer.