Data management in a data storage system

The present disclosure provides a method in a data storage system. The method includes defining a plurality of jobs for a command received from a host. Each of the plurality of jobs is associated with one or more of a plurality of data storage resources of the data storage system. The plurality of jobs have a defined order that is a function of addresses of data in the plurality of data storage resources. The method also includes issuing the plurality of jobs to the associated data storage resources and receiving information from the data storage resources for the plurality of jobs. The information is received by a controller of the data storage system for the jobs in an order that is different than the defined order. The method includes transmitting the received information to the host for the plurality of jobs in the defined order.

BACKGROUND

A data storage system is an example of a system having data resources. For example, a data storage system includes one or more devices having at least one medium for data storage. The data storage system can include one or more types of storage mediums such as, but not limited to, hard discs, floppy discs, magnetic discs, optical discs, magnetic tapes, solid-state storage components, and/or combinations thereof. For instance, an exemplary data storage system can comprise a hard disc drive (HDD), a solid-state drive (SDD), a “hybrid” drive (e.g., a hybrid hard drive (HHD)), to name a few.

In one example, the data storage system includes a controller that is configured to receive data and commands from a host and implement data operations to the storage media in the data storage system based on the commands. The data storage system can include a plurality of devices and components having memory accessible by the controller. For instance, a solid-state drive (SDD) can include a plurality of data memory devices, such as flash memory chips, having solid-state memory accessible by a controller of the solid-state drive (SDD).

SUMMARY

In one exemplary embodiment, a method in a data storage system is provided. The method includes defining a plurality of jobs for a command received from a host. Each of the plurality of jobs is associated with one or more of a plurality of data storage resources of the data storage system. The plurality of jobs have a defined order that is a function of addresses of data in the plurality of data storage resources. The method includes issuing the plurality of jobs to the associated data storage resources and receiving information from the data storage resources for the plurality of jobs. The information is received by a controller of the data storage system for the plurality of jobs in an order that is different than the defined order. The method includes transmitting the received information to the host for the plurality of jobs in the defined order.

In one exemplary embodiment, a data storage system is provided. The data storage system includes an interface for receiving a command for a data operation, a plurality of data memory devices, and a controller. The controller is configured to generate a plurality of jobs for the command, issue the plurality of jobs to the data memory devices, and receive information from the data memory devices for the plurality of jobs. Each of the plurality of jobs are associated with one or more of the data memory devices. The plurality of jobs have a defined order that is a function of addresses of data in the data memory devices. The information is received at the controller from the data memory devices for the jobs in an order that is different than the defined order.

In one exemplary embodiment, a data storage device is provided. The data storage device includes a plurality of data storage resources and a controller configured to identify at least one command for a data operation and generate a plurality of jobs for the data operation based on the at least one command and the plurality of data storage resources. The controller is configured to issue the plurality of jobs to the plurality of data storage components and includes a data management component configured to concurrently manage completion information pertaining to completion of the plurality of jobs.

DETAILED DESCRIPTION

Aspects of the present disclosure relate generally to systems having concurrent data resources and more specifically, but not by limitation, to concurrent data management in a data storage system.

One aspect of data management in a data storage system, for example, generally relates to management of data flows from/to data resources, such as data storage media. For instance, data management can comprise tracking completion of data write operations to one or more data storage media. In another instance, for data read operations data management can comprise tracking data retrieved from one or more data storage resources and transferring the data to a host.

Data commands received from a host system or device, for example, can include constraints related to completion of the associated data operation(s). For example, for a read command, communication of read data from the data storage system to the host can require that the read data is transmitted to the host in an order and manner that is expected by and acceptable to the host. For instance, the order of data can be based on a function of logical block addresses of the data. In such cases, data management can comprise ensuring that the data is retrieved from the data storage devices and “throttled” to the host appropriately. The terms “throttled” or “throttling” refer to a process of ensuring that the data is retrieved from the data storage devices and transferred to the host in an order acceptable to the host. For example, in one embodiment data retrieved from the data storage devices is only transferred to the host when each respective part of the command is completely ready to be transferred to the host. The host may require that the data is received from the data storage system in an order based on the logical block addresses of the retrieved data.

In some data storage systems, data management is essentially “single-threaded” in that there is a single data resource (e.g., a read/write head) that can deliver data to/from a controller, buffer, cache, host interface, etc., at a time. On the other hand, some data storage systems include a plurality of data resources that are “concurrent” in that multiple data resources can be instructed to carry out data operations (or portions thereof) at substantially the same time and/or during overlapping time intervals. For instance, in a data storage system comprising an exemplary solid-state drive there can be tens to hundreds (or more) of concurrent data resources. For example, the solid-state drive can include a plurality of independent solid-state data memory devices (e.g., flash chips). Data commands (or portions thereof) can be provided from a drive controller to a number of the data memory devices concurrently. To illustrate, in one example the solid-state drive employs a mapping of host logical block addresses (LBAs) to physical locations. A set of LBAs for a single read command, for example, may be mapped to locations distributed across multiple data memory devices allowing the multiple data memory devices to service the single read command. Likewise, LBAs for multiple received read commands can also be mapped to locations distributed across the multiple data memory devices.

As mentioned above, the one or more read commands can include associated constraints (i.e., a host-expected data order) related to gathering of the read data from the data memory devices. In such cases, data management can comprise ensuring that the retrieved data is throttled to the host appropriately (i.e., held up until it can be delivered in the host-expected data order). However, retrieving the data from the data memory devices in-order can significantly limit performance of the data storage system.

In accordance with one aspect described herein, data management in a data storage system having a plurality of concurrent resources is provided. As used herein, the management of data across “concurrent” resources is referred to as concurrent data management. In one embodiment, concurrent data management enables data to be retrieved from the plurality of concurrent resources for one or more read operations, for example, in an order that is different (i.e., “out-of-order”) than a data order defined for the read operation(s).

FIG. 1is a schematic diagram of an exemplary data computing system100including a data storage system108having a plurality of concurrent data resources112. As illustrated, a host system101includes a processor102connected to a system bus103which also can be connected to input/output (I/O) devices104, such as a keyboard, monitor, modem, storage device, or pointing device. The system bus103is also coupled to a memory106, which can include a random access volatile memory, such as dynamic random access memory (DRAM). The system bus103is also coupled to the data storage system108for communicating data and/or commands between data storage system108and host system101.

Data storage system108includes a controller110, which can be coupled to the processor102via a connection through the system bus103. It is noted that in some systems this connection is made through one or more intermediary devices, such as a host bus adapter or a bridge.

Controller110communicates with the plurality of data resources112over one or more channels (i.e., buses)114. In the illustrated embodiment, the data resources112comprise a plurality of data storage devices (illustratively, solid-state data memory devices). In one example, data storage system108comprises a solid-state drive and devices112comprise semi-conductor based devices, such as flash memory. In other embodiments, the data storage system108can also include volatile and/or non-solid-state memory. For example, data storage system108can comprise a disc drive and/or a “hybrid” drive including solid-state components and hard disc components.

FIG. 2is a schematic diagram illustrating one embodiment of data storage system108. Data storage system108includes controller110that is configured to store information to and retrieve information from the plurality of solid-state data memory devices (illustratively flash memory)112.

In one embodiment, each of the devices112comprise an independent flash agent that is able to perform a data operation, or portion thereof, associated with a command received by the controller. For example, each flash agent112is configured to perform all, or a portion of, a data read, a data write operation, etc. Further, the data operation does not have to include a data transfer. For example, the data operation can include a data erase operation, such as an erase operation on a flash chip.

In one embodiment, each device112is identified by an assigned logical unit number (LUN). Each flash agent112can comprise one or more flash chips, for example. Alternatively, or in addition, one or more flash agents112can be provided on the same flash chip. In this manner, multiple logical storage units can be provided within a single die or package, for example. For instance, each flash agent112can include a separate flash chip comprising a semiconductor package having one or more semiconductor dice provided in a housing, for example.

Each device112can include an interface for communicating information with memory interface220, control circuitry, and a storage area (having a particular capacity based on the design of the device components). For example, in one embodiment the storage area of one or more flash agent(s)112is capable of storing 1 mebibyte (MiB). In another embodiment, one or more flash agent(s)112are configured to store more than or less than 1 MiB.

However, it is noted that data memory devices112can have any suitable physical structure. For instance, each of data memory devices112can be provided on the same semiconductor die (e.g., the same piece of silicon). In another instance, one or more of data memory devices112are provided on different semiconductor die (e.g., different pieces of silicon). Further, it is noted that data storage system108can include any number of data memory devices112. For example, in one embodiment data storage system108includes 4 to 256 data memory devices112. However, less than 4 or more than 256 data memory devices112can be utilized.

Controller110includes memory interface220(illustratively a flash memory interface) that is coupled to the data memory devices112via one or more channels (i.e., busses)114for communicating commands and/or data. In one embodiment, channels114comprise 1 to 24 flash channels. However, any number of channels and/or connection topologies can be utilized. Channels114can comprise data busses, address busses, and/or chip select busses, for example.

WhileFIG. 2illustrates a particular channel configuration, it is noted that the attachment methodology between the controller110and data memory devices112can be of any suitable form.

The controller110is communicatively coupled to a host, such as host system101illustrated inFIG. 1, via a host interface216that can receive and send commands, status information, and data to the host. The host interface216can pass commands to a control circuit230of controller110for processing and also store received data in a buffer memory232. The buffer memory232provides the received data to the memory interface220.

The memory interface220can receive data from the buffer memory232to be written to one or more of the data memory devices112and receive address bits from the control circuit230. The memory interface220can assert corresponding data and address bits with appropriate timing and format to a selected data memory device112. Memory interface220can also receive previously stored data from any storage locations (e.g., pages, blocks, etc.) of data memory devices112.

In the flash memory example ofFIG. 2, when a logical sector of data (i.e., a portion of data from host system101having an associated logical block address (LBA)) is to be written to memory112, flash controller110identifies the physical address of the physical block to which the data will be written. The logical block address (LBA) is the address that the host system uses to read or write a block of data to data storage system108. The physical block address is the fixed, physical address of a block in the storage component. In one example, the controller110can store a mapping of the logical addresses to the corresponding physical addresses in a translation/mapping component238. The mapping information is utilized for data access operations to locate requested data in the memory devices112. In another example, component238can operate as a cache for the mapping information. For instance, the mapping information can be stored to or otherwise associated with data memory devices112. In this manner, the mapping information can be fetched from (on a read) or updated to (on a write) the solid-state data memory device(s) associated with the command.

Data memory devices112are independently addressable by controller110. For example, controller110can issue commands (or portions thereof) and any associated data to/from each of two or more data resources112to be carried out during the same or overlapping time periods. In accordance with one embodiment, the controller110is configured to receive at least one command and decompose the at least one command into a plurality of subcommands or “jobs.” A job can comprise a complete data operation for a command and/or can comprise a portion of an overall data operation for a command. For example, a single read or write command can be decomposed into a plurality of jobs to be performed by the data memory devices112.

In one embodiment, the plurality of jobs are issued to a number of the data memory devices112in a parallel manner. For instance, an exemplary read command is decomposed into at least a first job and a second job. The first job pertains to a data access request for data stored in a first data memory device112and the second job pertains to a data access request for data stored in a second data memory device112that is different than the first data memory device112. The first and second jobs are issued by the controller110to the first and second data memory devices112, respectively, and are performed by the devices112during the same time period (or substantially the same time period) or during overlapping time periods, in one example. The number of jobs generated by the controller110for a command can be a function of, for example, the physical addresses of the data and the number of data memory devices112to be accessed for the particular command.

Controller110is also configured to concurrently manage completion information for each of the issued jobs and any data associated with the completed jobs. For example, for a read command controller110is configured to track a number of data blocks required for completion of each job and to track a number of data blocks that have been obtained for each job. Further, for a particular job controller110can also be configured to track a completion status of at least one other job in the plurality of jobs. For example, as discussed above a command (and the corresponding job decomposition) can have a defined or sequential order that is based on host requirements for the completion of the command (e.g., an order that the data is to be delivered to the host). Controller110is configured to concurrently manage the data memory devices112such that data can be received from the data memory devices112in the defined order and/or in an order that is different than the defined order.

To illustrate,FIG. 3is a diagram of an exemplary data structure300that represents an exemplary command302. While command302is illustrated as a single command, it is noted that command302can comprise multiple commands for data operations, such as read and/or write operations.

Data structure300can be implemented in hardware, software and/or firmware associated with controller110. In one particular example, data structure300comprises one or more linked-lists implemented in firmware of controller110.

The command302has been decomposed, for example by controller110, into a plurality of jobs (illustratively four jobs). Data structure300includes a plurality of nodes304-1,304-2,304-3, and304-4(collectively referred to as “nodes304” or “jobs304”). In the illustrated embodiment, each of nodes304corresponds to a data access request to a particular data memory device112. For example, node304-1represents a first job comprising a data access request for a first portion of data stored in a first data memory device. Node304-2represents a second job comprising a data access request for a second portion of data stored in a second data memory device. Likewise, node304-3and304-4represent third and fourth jobs for command302. As illustrated, command302requires a total of 14 blocks of data stored across multiple data storage devices112. Further, it is noted that each of the jobs can pertain to data at different data storage devices112and/or a plurality of the jobs can pertain to data at the same data storage device112.

Data structure300is illustratively a linked-list of job completion information, is utilized to manage completion of the jobs for command302, and is stored in controller110, for example. In one example, the jobs for command302have an order that is defined based on the command302and/or constraints on the subsequent transfer of data to the host. For example, in the illustrated embodiment the data for the first job (node304-1) is to be released from the controller110to the host before (or at least with) the data for the second job (node304-2). Similarly, the data for the second job is to be release before (or at least with) the data for the third job, etc.

The first node (e.g., node304-1) in the data structure300is referred to as the “head” node. In accordance with one embodiment, the controller110is configured to release data to the host when the job represented by the “head” node completes. On the other hand, when a job represented by a “non-head” node completes, the controller110does not release the data to the host and instead stores the data (for example, in buffer memory232) and indicates the stored data by modifying a preceding node in the data structure300.

Data structure300can thus be utilized by controller110to manage completion of the jobs “out-of-order.” For example, using data structure300controller110can receive and track data for the jobs in an order that is different than the order of the jobs illustrated inFIG. 3. For instance, controller110can receive and store the data for the second job (node304-2) before the controller110receives any data for the first job (node304-1). Subsequently, when the first job (node304-1) completes (i.e., all the data for the first job is ready at the controller110) the controller110can release the data for the first and second job to the host at the same (or substantially the same) time.

In the illustrated embodiment, each node304in the linked-list pertains to one of the jobs and can include fields such as, but not limited to, the following:

1) Requested// Number of total data blocks in the job2) Complete// A running total of the number of datablocks completed (i.e., received at thecontroller 110) for the job3) ExtraRelease//Number of extra blocks (i.e., blocks in otherjobs) to be released when the job is completed4) JobStatus// Status of the job (i.e., InProgress, Done,Error, etc.)5) Nextjob// Pointer to the next job in the list6) JobInfo// Additional information needed to completethe job

In the context ofFIG. 3, node304-1includes a “requested” field306that indicates the number of data blocks requested for the first job and includes a “complete” field308that indicates the number of data blocks that have been completed (i.e., received from the appropriate data storage device112) for the first job. Fields306and308can also be recorded in units of LBAs, pages, bytes, etc. When controller110receives some or all of the data for the first job (node304-1) from the data storage device112, controller110can store the data (for example, in buffer memory232) and adjust the “complete” field308. Once all of the data for the job has been received, the job status flag312is changed to indicate that the job is done.

Node304-1also includes an “ExtraRelease” field310that represents data for at least one other job (nodes304-2,304-3, and/or304-4). In accordance with one embodiment, the “ExtraRelease” field310indicates the number of blocks of data acquired for completed jobs. In one embodiment, the “ExtraRelease” field310for the first job (node304-1) indicates the number of blocks of data acquired for completed jobs that are immediately after the first job (node304-1) in the defined job order. In this manner, field310indicates the number of additional data blocks that are to be released with the data for the first job (node304-1) when the first job also completes.

Further, each node304can also include additional fields such as, but not limited to, the number of sectors of data transferred to the host, the logical block addresses (LBAs) associated with the requested data, the physical block addresses associated with the requested data, etc.

FIGS. 4A and 4Billustrate a flow diagram400of an exemplary method for concurrent data management using the exemplary data structure300illustrated inFIG. 3. In the context ofFIGS. 4A and 4B, each row of nodes304illustrates a particular snapshot or instance in time. It is noted that snapshots420-432have been chosen to highlight the data structure300and are not intended to show every instance or data release opportunity.

At snapshot420, the command has been decomposed into the plurality of jobs represented by nodes304; however, data has not yet been received for any of the jobs. At snapshot422, data for some of the jobs has been received from the data memory devices. For instance, three blocks of data of the four requested blocks have been obtained for the first job (node304-1). Four blocks of data of the four requested blocks have been received for the second job (node304-2). Two blocks of data of the four requested blocks have been received for the third job (node304-3). No blocks of data have been obtained for the fourth job (node304-4). Node304-2is modified to indicate that the second job has completed. The completed non-head node304-2can be removed or collapsed into the preceding node (head node304-1). For instance, as can be seen at snapshot424, the node304-2has been removed and the “ExtraRelease” field of node304-1has been changed to indicate the four blocks of data that were obtained for the completed second job (node304-2).

At snapshot426, all four data blocks for the third job (node304-3) have been obtained. As illustrated in snapshot428, node304-3is collapsed into the preceding node (in this instance the head node304-1). The “ExtraRelease” field of node304-1is changed to indicate that the job for node304-3has also been completed.

At snapshot430, all four of the requested blocks of data for the first job (node304-1) have been received. Because node304-1comprises the head node, node304-1is removed and the data for the first job along with the data indicated in the “ExtraRelease” field (i.e., the data for the second and third jobs) is released (e.g., transferred from the data storage system to the host that issued the command) in an appropriate order.

At snapshot432, only the fourth job (node304-4) remains; node304-4comprises the head node. The data for the preceding jobs in the order have already been released to the host. At snapshot432, the two requested blocks of data have been obtained for the fourth job (node304-4). Because node304-4is now the head node, the data for the fourth job is also released (i.e., transmitted to the host) along with any data indicated in the “ExtraRelease” field. In this case, there is no extra data to release. Node304-4is removed.

In the embodiment ofFIGS. 4A and 4B, a single read command is illustrated. In accordance with another embodiment, a plurality of commands can be concurrently managed.FIGS. 5A and 5Billustrate a flow diagram500of an exemplary method for concurrent data management of multiple data commands.

Flow diagram500illustrates a first command502and a second command552. In the context ofFIGS. 5A and 54B, boxes522,524,526, and528illustrate particular snapshots or instances in time. It is noted that snapshots522,524,526, and528have been chosen to highlight the data structure and are not intended to show every instance or data release opportunity.

As illustrated at snapshot522, command A502has been decomposed into a plurality of jobs represented by nodes504-1,504-2, and504-3. Command B552has been decomposed into a plurality of jobs represented by nodes554-1and554-2. It is noted that each of the jobs represented by nodes504-1,504-2,504-3,554-1, and554-2can comprises data access requests for different data memory devices. Alternatively, or in addition, two or more of the jobs can comprise data access requests to the same data memory device. For instance, the jobs represented by nodes504-2and554-1can be issued to the same data memory device.

At snapshot524, the job represented by node504-2has completed and the node504-2is collapsed into the preceding node, in this case head node504-1. Similarly, the job represented by node554-2has completed and the node554-2is collapsed into the preceding node, in this case head node554-1.

At snapshot526, the jobs represented by nodes504-3and554-1have completed. Because node554-1is the head node, the data blocks for the job represented by node554-1are released, along with the data indicated in the “ExtraRelease” field (in this case, the two blocks of data from node554-2). At this point, command B552has completed and all the data for command B552has been transferred to the host. Because the data blocks for node554-2were already received and stored by the controller (and represented by the “ExtraRelease” field in node554-1), the data storage system can transfer all of the data for the command without having to wait for the data to be acquired from the data storage devices for jobs554-1and554-2“in-order”.

At snapshot528, the job represented by node504-1has completed. Because node504-1is the head node, the data for job504-1is released along with the data indicated in the ExtraRelease field (in this case the data for nodes504-2and504-3). Likewise, the controller110is not required to wait for the data for the subsequent nodes504-2and504-3to be transferred from the data memory devices as this data has already been transferred to the controller and is represented in the ExtraRelease field of the head node.

In one embodiment, although command A502arrived at the controller before command B552, the data handling required by command A502causes command A502to take longer to complete than command B552. Thus, although commands are received (e.g., enqueued) in a particular order, their order to “attach” to the host bus for data transfer can be different. This can allow for a more efficient transmittal of data as an earlier received command that takes a significant time to complete does not monopolize the host bus.

In accordance with one embodiment, one or more write commands are received by the controller and a plurality of jobs are generated for the write command(s). For the jobs generated for write command(s), the ExtraRelease field generally relates to the amount of buffer space that can be reallocated for other uses after the data for the job has been written to the appropriate data memory devices and the job has completed.

In some systems, the host bus protocol may not allow multiple connections for data transfers for a particular command. Thus, when a data transfer for a first command begins, all of the data for the first command must be transferred before a data transfer for a second command begins. In accordance with one embodiment, in the constrained case (where the host bus protocol does not allow multiple connections for a command) the controller is configured to connect the command to the bus for data transfer that is most likely to maximize the number releases of data per unit time until the end of the command. In one example, this is implemented by assuming that all commands are similarly sized, and attaching the command for data transfer whose data operation was started first on the back-end data storage resources. The system then gives preferential treatment to that command to limit or prevent the command from stalling the host bus, for example while the back-end data storage resources are accessed for the command. In another embodiment, a particular read command is not selected for attachment to the host bus for data transfer if the particular read command still requires more than one data transaction per back-end data storage resource to complete the read command.

In one embodiment, in the constrained case (where the host bus protocol does not allow multiple connections for a command, for example zero-buffer offset mode of first-party DMA in SATA) the queue entry for each command includes a pointer to the data structure (for example, data structure300,500) representing completion information for the command. The system hardware can utilize the pointer to keep track of the completion information for the command that is currently attached to the host bus and use the completion information to throttle transmission of data packets to the host. In one example, the system hardware uses the command completion information to throttle automatic transmission of data packet that must be equal to a maximum packet payload (e.g., 8 Kibibytes (KiB)) or the remainder of the host command, whichever is smaller.

In one embodiment, system firmware can pre-emptively make the selection of the command to connect to the host bus using the completion information (for example, if the firmware determines that a particular read command is not going to need more than a single data operation per back-end resource and that none of the resources are busy servicing other requests). In one example, the system firmware selects a command to connect to the host bus when the completion information for the command indicates that the head node of the linked-list associated with the command has completed.

In one embodiment, in the unconstrained case (where the host bus protocol allows multiple connections for a command), a command can be connected to the host bus for data transfer whenever a head node for a command completes and the “Complete”+“ExtraRelease” fields for the head node indicate an amount of data exceeding a threshold established by the firmware, or is equal to the remainder of the requested data blocks for the command, whichever is smaller.

In accordance with one embodiment, the data storage system is configured to prioritize read commands ahead of write commands. In this manner, the read commands may be easier to predict with respect to their readiness to attach to the host bus. The write operations can be utilized to fill in the host bus bandwidth between the read command data transfers, as available.

In one embodiment, the data storage system is configured to abort a write operation that is in progress if the abort is issued before the write operation has reached as particular point. For instance, to reduce read latency a write operation can be aborted in favor of a data read operation as long as the actual “program” flash command for the write operation has not been issued. However, this may cause some wasted processing or bus-transferring capacity on the back-end. Thus, in one embodiment a threshold can be tuned to adjust how far into the write operation an abort may be affected. In one example, the threshold is adaptively tuned based on the amount of write operations and/or read operations in the command queue. For instance, if there are a large number of write operations in the queue, but very few read operations, the controller can be configured to increase the read latency to more-preferentially process the write operations. This can be advantageous in situations where the host is waiting for write operation(s) to complete.

FIG. 6is a diagram illustrating another embodiment of a data structure600representing command completion information for an exemplary command602. While command602is illustrated as a single command, it is noted that command602can comprise multiple commands for data operations, such as read and/or write operations.

Data structure600can be implemented in hardware, software, and/or firmware associated with controller110, for example. In one particular embodiment, data structure600is implemented in hardware of controller110and includes a fixed number of entries for a predefined or maximum number of allowed jobs. The fixed number of entries of structure600relates to the number of jobs that can be outstanding and concurrently managed by controller110at a time. The number of entries of structure600can be based on constraints of the data storage system, such as the physical architecture of the controller, channels, and/or storage devices, for example.

To illustrate, in the embodiment ofFIG. 6data structure600includes a command descriptor604and a fixed number of available job descriptors606(illustratively four job descriptors606). The command descriptor604is indicative of the overall command602while each job descriptor606is indicative of a particular job for the command602. The number of available job descriptors606can be based on a number of hardware resources for carrying out data command602(e.g., a number of data memory devices112, a number of channels114, etc.). The number of jobs that can be concurrently managed by data structure600is, in one embodiment, equal to the number of available job descriptors606. Additional jobs for the command (for example, when the number of total jobs for command602exceeds the number of available job descriptors606) can re-use job descriptors606from completed jobs. This can be advantageous when the command602requires more jobs than can be tracked at one time with the available job descriptors606.

While four job descriptors606are illustrated, it is noted that in other embodiments data structure600can include more than or less than four job descriptors606. For example, data structure600can include tens, hundreds and/or thousands of job descriptors606. Each one of job descriptors606is associated with (e.g., mapped to) a particular one of data memory device (e.g., logical unit number (LUN)). For instance, job descriptor606-0is associated with LUN0, job descriptor606-1is associated with LUN1, job descriptor606-2is associated with LUN2, and so forth.

Upon reception of data command602that requires transfer to or from the data memory devices (e.g., data memory devices112), the controller110generates the command descriptor604. In the illustrated embodiment, the command descriptor604includes fields such as, but not limited to, the following:

1) StartAddress// Address (e.g., LBA) associated with the startof the command2) TotalBlocks// Number of blocks (e.g., sectors, 8-byte units,bytes, etc.) in the command3) BlocksRemaining// Number of blocks remaining to berequested as jobs4) BlocksAvailable// Number of blocks available from the headof the command (e.g., the head jobdescriptor node)5) JobReadPointer// Pointer to oldest uncompleted jobdescriptor6) NextJobPointer// Pointer to job descriptor to be filled in next

The StartAddress and TotalBlocks fields are initialized based on the received command602. The BlocksRemaining field is initialized to the same value as the TotalBlocks. The BlocksAvailable, JobReadPointer, and NextJobPointer fields are all initialized to zero. In the example illustrated inFIG. 6, command602includes a start address of LBA0and has a total number of requested blocks equal to 14.

Next, hardware and/or firmware of the controller110, for example, perform mapping lookups sequentially through the transfer address range of command602to calculate the size in blocks of each required job. For instance, the controller110determines the number of jobs needed (and the number of required blocks for each job) to complete the command602based on the manner in which the data storage devices112need to be accessed for the command602. In one example, the controller110decomposes the command602into a plurality of jobs based on the addresses of the data in the plurality of data storage devices112. Each job descriptor606pertains to a particular logical unit number (LUN) for the job associated with that job descriptor606.

As each job size is determined, the job descriptor606is initialized. The “Required” field of the job descriptor606is set to the size of the job (for example, the number of requested data blocks for the job) and the “Complete” field for the job descriptor606is initialized to 0. The “Complete” field indicates the amount of data (e.g., number of data blocks) that has been acquired by the data memory device for the job and/or has been transmitted from the data memory device to the controller110. Data received by the controller110can be stored in a buffer or cache, for example.

FIGS. 7A and 7Billustrate a process of initializing the job descriptors606and utilizing the data structure600to concurrently manage the jobs issued to the data resources.

As illustrated at snapshot620, controller110issues the first job (job0) for the command602and initializes the job descriptor606-0for the first job (job0). Because job0requires four blocks of data, the Required field of job descriptor606-0is set to 4. The Completed field of job descriptor606-0is initialized to 0 and the BlocksRemaining field of the command descriptor604is decreased by the size of the initialized job0. The NextJobPointer field is incremented to indicate that job descriptor606-1is the next job descriptor to be filled in (i.e., job1is the next job to be issued). In one embodiment, when the NextJobPointer field of command descriptor604reaches the end of the available job descriptors606, the NextJobPointer is wrapped to 0 to point to job descriptor606-0. In this instance, all available job descriptors606have been initialized and the controller is configured to reuse job descriptors606for any additional jobs required for the command602. The loading of the job descriptors606continues until the BlocksRemaining field of the command descriptor604reaches 0 or the NextJobPointer equals the JobReadPointer (all job descriptors606for the command are in use).

Once a job descriptor606is initialized, a media transfer associated with that job descriptor can be initiated. For example, at snapshot620the data transfer associated with job0can initiate even though other jobs for the command have not been issued.

At snapshot622, the job descriptors606-1,606-2, and606-3, associated with jobs1,2, and3, respectively, have been initialized. Thus, all of the jobs have been issued and all of the command descriptors606have been initialized. However, no data blocks have been acquired for the jobs. The NextJobPointer of command descriptor604has been incremented to the next job pointer, in this case job4. However, in the case where only four job descriptors are available, the NextJobPointer can be configured to wrap to the first job descriptor606-0.

At snapshot624, some of the data for the command has been acquired from the data memory devices. The data memory device associated with job0has acquired 3 blocks of data, the data memory device associated with job1has acquired 4 blocks of data, and the data memory device associated with job2has acquired 2 blocks of data. As the data is acquired, the data is transferred to the controller for storage, for example in a buffer, while additional data is obtained from the data memory devices. The job descriptors606are updated accordingly to reflect the number of acquired data blocks for the jobs. As illustrated at snapshot624, the BlocksAvailable field of command descriptor604is updated to indicated that the 3 blocks of data have been acquired for the head job descriptor (in this case job0). These 3 blocks of data can be transferred to the host at snapshot624or can be held until more data is acquired.

At snapshot626, the jobs associated with job descriptors606-1(job1) and606-2(job2) have completed. In one embodiment, the data for jobs1and2is provided to the controller before the completion of job0.

At snapshot628, job0associated with the job descriptor606-0(which in this case is the head job descriptor) has completed as all 4 required data blocks have been acquired from the associated data memory device and provided to the controller110. At this point, the BlocksAvailable field of the command descriptor604is updated to reflect that 13 blocks of data (4 blocks from job0, 4 blocks from job1, 4 blocks from job2, and 1 block from job3) have been acquired by the controller110and are available for transfer to the host, for example. In one embodiment, these 13 available blocks of data are “released” or transferred from the controller110. Alternatively, the controller110can be configured to delay the data transfer to the host until the remaining data for the command has been acquired. At snapshot628, the JobReadPointer field has also been updated to reflect that the next or oldest uncompleted job descriptor is now job descriptor606-3.

At snapshot630, the last block(s) of data for job descriptor606-3are acquired by controller110and the data is “released” from the controller110. The JobReadPointer field is updated to reflect that job descriptor606-3has completed and to indicate the next uncompleted job descriptor (in this case the JobReadPointer wraps to 0).

In accordance with one embodiment, each job descriptor606is mapped to and associated with a particular data memory device having a particular logical unit number (LUN), for example. If the command(s)602do not comprise a job for one or more of the data memory devices, the corresponding job descriptors606for those data memory devices include a “next job” pointer. The “next job” pointer operates as a placeholder and instructs the controller to advance or skip that job descriptor. Alternatively, or in addition, the Required and Completed fields for the job descriptors that are not being used for the command(s) can be set to “0”'s to indicate that the job descriptors are not being used and should be skipped.

In accordance with one embodiment, the described data structures (e.g., data structures300and600) enable tracking and management of jobs across a plurality of concurrent resources. In one aspect, one or more received commands are decomposed into a plurality of jobs, each job being indicative of a portion of the command(s). The jobs have an order that is defined based on, for example, the addresses of the data in the data storage devices. In one example, the order of the jobs is a function of a host-expected or host-acceptable order of the data. For instance, host protocol can require that the data for the jobs of the command are received by the host in the defined order. The data structure(s) are utilized by the controller110of the data storage system to concurrently manage the jobs such that the controller110can receive the data for the jobs in an order that different (e.g., out-of-order) than the defined order for the jobs. This can be advantageous as the controller110can acquire the data from the data memory devices as the data is made available at the data memory devices; the controller does not have to wait for the jobs to complete at the data memory devices in the defined order.

The implementations described above and other implementations are within the scope of the following claims.