Patent Publication Number: US-9846650-B2

Title: Tail response time reduction method for SSD

Description:
RELATED APPLICATION DATA 
     This application claims the benefit of U.S. Provisional Patent Application Ser. No. 62/130,597, filed Mar. 9, 2015, which is hereby incorporated by reference for all purposes. 
    
    
     FIELD 
     The inventive concept pertains to reducing data access times, and more particularly to reducing data access time from Solid State Drives (SSDs). 
     BACKGROUND 
     Solid State Drives (SSDs) can utilize multiple flash memory chips organized using multiple channels. This architecture can result in data requests being satisfied in a different order than the order in which the requests were made. For example, if an SSD receives two data requests that can be satisfied using a first memory channel and then a third data request that can be satisfied using a second memory channel, the third data request can be returned from the appropriate flash memory chip before the second data request is satisfied. 
     This architecture introduces parallelism into the system, allowing more than one data request to be satisfied at a time. This parallelism can be beneficial: in general, data can be returned faster in such a parallel architecture than in a serial architecture where each request must be satisfied before the next request can be satisfied. As a result, the average response time of the SSD is improved. 
     But a bottleneck still exists in the system. All data requests and responses pass through the interface that exists between the SSD and the host computer that issued the data requests, and the host computer needs to process one datum before it can process the next datum. If that interface is busy sending one datum back to the host computer, that interface cannot be used to send another datum back to the host computer. Continuing the earlier example, if the interface is busy sending the data from the second data request back to the host computer, the interface cannot send the data from the third data request back to the host computer. Put another way, the time required to send data from the SSD back to the host computer includes the latency of the host computer in processing data it receives from the SSD. The data from the third data request can end up waiting a long time before it is sent back to the host computer. Thus, while parallelism can reduce the average response time of the SSD, parallelism can increase the worst case response time of the SSD. 
     A need remains for a way to improve the worst case response time of data requests. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a Solid State Drive (SSD) to reduce tail response time, according to an embodiment of the inventive concept. 
         FIG. 2  shows a computer system including the SSD of  FIG. 1 . 
         FIG. 3  shows data requests being received by the data input buffer of the SSD of  FIG. 1 . 
         FIG. 4  shows data returned from the flash memory chips to the data output buffer of the SSD of  FIG. 1 . 
         FIG. 5  shows the buffer manager of the SSD of  FIG. 1  selecting data for transmission to the host computer based on how long the data has been in the data output buffer, according to an embodiment of the inventive concept. 
         FIG. 6  shows the buffer manager of the SSD of  FIG. 1  selecting data for transmission to the host computer based on how full the data output buffer is, according to an embodiment of the inventive concept. 
         FIG. 7A  shows the tail response time of example data requests using an SSD without an embodiment of the inventive concept. 
         FIG. 7B  shows the tail response time of the example data requests of  FIG. 7A  using an SSD with an embodiment of the inventive concept. 
         FIG. 8  shows a data management device to manage data returned from a number of data sources, according to an embodiment of the inventive concept. 
         FIGS. 9A-9B  show a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to process data requests to reduce tail response time, according to an embodiment of the inventive concept. 
         FIGS. 10A-10B  show a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to manage the data output buffer based on how long data has been resident in the data output buffer, according to an embodiment of the inventive concept. 
         FIGS. 11A-11B  show a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to manage the data output buffer based on how full the data output buffer is, according to an embodiment of the inventive concept. 
         FIG. 12  shows a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to select a next data for output, according to an embodiment of the inventive concept. 
     
    
    
     DETAILED DESCRIPTION 
     Solid State Drives (SSDs) can have good average response times, but terrible tail response (that is, worst case response) times. With better tail response times, SSDs could provide a higher quality of service and a better user experience. 
       FIG. 1  shows a Solid State Drive (SSD) to reduce tail response time, according to an embodiment of the inventive concept. In  FIG. 1 , SSD  105  is shown. SSD  105  can include host interface logic  110 , which can provide an interface between SSD  105  and a host computer (such as computer system  205 , shown in  FIG. 2  below). SSD  105  can also include SSD controller  115 , various channels  120 - 1 ,  120 - 2 ,  120 - 3 , and  120 - 4 , along which various flash memory chips  125 - 1 ,  125 - 2 ,  125 - 3 ,  125 - 4 ,  125 - 5 ,  125 - 6 ,  125 - 7 , and  125 - 8  can be arrayed. Although  FIG. 1  shows four channels and eight flash memory chips, a person skilled in the art will recognize that there can be any number of channels including any number of flash memory chips. 
     SSD controller  115  can include data input buffer  130 , data output buffer  135 , buffer manager  140 , and re-order logic  145 . Data input buffer  130  can receive data requests from host interface logic  110  (which data requests can originate from host computer system  205 ). Data output buffer  135  can receive data from flash memory chips  125 - 1 ,  125 - 2 ,  125 - 3 ,  125 - 4 ,  125 - 5 ,  125 - 6 ,  125 - 7 , and  125 - 8 : the data received can be responsive to the data requests received by data input buffer  130 . The data in data output buffer  135  can be sent via host interface logic  110  back to host computer system  205 . 
     Buffer manager  140  can manage data input buffer  130  and data output buffer  135 . Buffer manager  140  can select a data request from data input buffer  130  to send to a flash memory chip. Generally, the request closest to the “top” of data input buffer  130  that requests data from an open memory channel can be selected. (The term “top” was put in quotation marks because data input buffer  130  can be implemented, for example, using a circular queue, which does not have a literal “bottom” or “top” from which data requests can be inserted or deleted. This also applies to data output buffer  135 : either or both of data input buffer  130  and data output buffer  135  can be implemented using any desired buffer technology.) 
     An example might help to clarify how buffer manager  140  can manage data input buffer  130 . Assume that host computer system  205  sends three data requests. The first and second data requests request data from flash memory chip  125 - 1 , and the third data request requests data from flash memory chip  125 - 3 . As can be seen, the first two data requests are on channel  120 - 1 , and the third data request is on channel  120 - 2 . (The channel of the data request can be determined in any desired manner. For example, the channel can be determined by masking out certain bits from the address of the data request.). Buffer manager  140  can select the first data request for transmission to channel  120 - 1 . But as channel  120 - 1  is now in use, the second data request cannot currently be satisfied. On the other hand, the third data request, using channel  120 - 2 , can be satisfied. So buffer manager  140  can select the third data request to send on channel  120 - 2  before the second data request. 
     Buffer manager  140  can also select which data request to remove from data output buffer  135  and send to host computer system  205 . In SSDs that do not include embodiments of the inventive concept, buffer manager  140  can select the data that was added to data output buffer  135  the earliest (that is, the data that has been waiting in data output buffer  135  the longest, which can be described as the “longest resident data” in data output buffer  135 ). But in SSDs that include embodiments of the inventive concept, SSD controller  115  can include re-order logic  145 , which provides information to buffer manager  140  as to which data to return from data output buffer  135  to host computer system  205 . 
     In some embodiments of the inventive concept, re-order logic  145  can review the data in data output buffer  135  and identify data in data output buffer  135  that was returned from the oldest data request. To distinguish this concept from the “longest resident data”, the data from the oldest data request can be termed the “earliest requested data”. Continuing the earlier example, if the flash memory chips take on average the same amount of time to return data, then the data satisfying the second data request would be put into data output buffer  135  after the data satisfying the third data request. But since the second data request is the earliest requested data, re-order logic  145  can suggest the data satisfying the second data request be returned before the data satisfying the third data request. (Note that, as shown in this example, the longest resident data is not necessarily the earliest requested data.) There are also other ways in which data can be re-ordered, such as those described below with reference to  FIGS. 5-6 . 
       FIG. 2  shows a computer system including SSD  105  of  FIG. 1 . In  FIG. 2 , computer system  205  is shown as including computer  210 , monitor  215 , keyboard  220 , and mouse  225 . A person skilled in the art will recognize that other components can be included with computer system  205 : for example, other input/output devices, such as a printer, may be included. In addition, computer system  205  can include conventional internal components such as central processing unit  230  and memory  235 . Computer system  205  can also include SSD  105 . Although not shown in  FIG. 2 , a person skilled in the art will recognize that computer system  205  can interact with other computer systems, either directly or over a network (not shown) of any type. Finally, although  FIG. 2  shows computer system  205  as a conventional desktop computer, a person skilled in the art will recognize that computer system  205  can be any type of machine or computing device, including, for example, a laptop computer, a tablet computer, a personal digital assistant (PDA), or a smart phone, among other possibilities. 
       FIG. 3  shows data requests being received by data input buffer  130  of SSD  105  of  FIG. 1 . In  FIG. 1 , data requests are received from host computer system  205 . In  FIG. 3 , data input buffer  130  is shown as a first in, first out (FIFO) queue, but as discussed above, data input buffer  130  can be designed as any type of buffer. The three oldest entries in data input buffer  130 , therefore, are the (example) data address 0x1400 (data request  305 - 1 ), data address 0x3400 (data request  305 - 2 ), and data address 0x1800 (data request  305 - 3 ). 
     Re-order logic  145  (not shown in  FIG. 3 ) can then assign transaction IDs to the data requests. Thus, in this example, data request  305 - 1  can be assigned transaction ID  9  (transaction ID  310 - 1 ), data request  310 - 2  can be assigned transaction ID  10  (transaction ID  310 - 2 ), data request  305 - 3  can be assigned transaction ID  11  (transaction ID  310 - 3 ), and so on. Note that in  FIG. 3  transaction IDs have been assigned sequentially, but re-order logic  145  can assign the transaction IDs in any desired manner as long as re-order logic  145  can determine the order in which data requests were received. Further, provided that re-order logic  145  can determine the order in which data requests were received, the transaction IDs do not need to be stored in data input buffer  130  (or data output buffer  135  in  FIGS. 4-6 ), or even be used at all. For example, re-order logic  145  can store the data requests in the order received in storage internal to re-order logic  145 . 
     While the above description assigns re-order logic  145  the responsibility to assign the transaction IDs, a person skilled in the art will recognize that transaction IDs can be assigned by other components. For example, buffer manager  140  can be responsible for assigning transaction IDs to data requests. 
       FIG. 4  shows data returned from flash memory chips  125 - 1  through  125 - 8  to data output buffer  135  of SSD  105  of  FIG. 1 . In  FIG. 4 , data output buffer  135  is shown as including, among others, data requests  405 - 1 ,  405 - 2 ,  405 - 3 , and  405 - 4 , with associated transaction IDs  410 - 1 ,  410 - 2 ,  410 - 3 , and  410 - 4 . Note that the data requests as returned from flash memory chips  125 - 1  through  125 - 8  are not necessarily returned in the same order the requests were made. As can be seen, longest resident data has transaction ID  3  (transaction ID  410 - 1 ), whereas the earliest requested data (transaction ID  410 - 4 ) was the fourth data request returned. As discussed above with reference to  FIG. 3 , re-order logic  145  can determine which data to suggest buffer manager  140  without data output buffer  135  storing the transaction IDs. For example, re-order logic  145  can store information about the order of the data requests internally to re-order logic  145 . 
       FIG. 5  shows buffer manager  140  of SSD  105  of  FIG. 1  selecting data for transmission to the host computer based on how long the data has been in data output buffer  135 , according to an embodiment of the inventive concept. In the embodiment of the inventive concept shown in  FIG. 5 , data output buffer  135  can include a Time In field. The Time In field can specify the time that a particular data request was added to data output buffer  135 . For example, data request  405 - 1  is shown as having Time In  63  (time in field  505 ), data request  405 - 2  is shown as having Time In  77  (time in field  510 ), data request  405 - 3  is shown as having Time In  82  (time in field  515 ), and so on. Note that the data requests in data output buffer  135  are in Time In order. This makes sense, since the longest resident data in data output buffer  135  would have the earliest Time In. In another embodiment of the inventive concept, the Time In entries for various data requests can be stored elsewhere, such as in buffer manager  140 . 
     Buffer manager  140  can also include timer  520  and timer threshold  525 . Timer  520  can determine how long a particular data request has been in data output buffer  135 . For example, timer  520  can include circuitry to calculate the difference between the current value of clock  530  and the Time In value for a particular data in data output buffer  140 , and can compare this calculation with timer threshold  525 . If a data has been in data output buffer  135  for longer than timer threshold  525 , then buffer manager  140  can burst data out of data output buffer  135 , rather than outputting the earliest requested data. Thus, for example, if data request  405 - 1  has been in data output buffer  135  for longer than timer threshold  525 , buffer manager  140  can select data request  405 - 1  for output rather than data request  405 - 4  (which has the lowest transaction ID, and therefore would be the earliest requested data). A person skilled in the art will recognize that when buffer manager  140  opts to burst data, buffer manager  140  can select any data for output, and does not have to select the longest resident data in data output buffer  135 . 
       FIG. 6  shows buffer manager  140  of SSD  105  of  FIG. 1  selecting data for transmission to the host computer based on how full data output buffer  135  is, according to an embodiment of the inventive concept. In the embodiment of the inventive concept shown in  FIG. 6 , buffer manager  140  can include minimum fullness threshold  605 . If data output buffer  135  has less than minimum fullness threshold  605 , then rather than outputting any data, buffer manager  140  can wait until data output buffer  135  has a minimum fullness before selecting a data request to output. Minimum fullness threshold  605  can be represented either as a raw number (i.e., data output buffer  135  must include at least that many data requests before data can be output) or a percentage (data output buffer  135  must be at least that percentage full before data can be output), among other possibilities. 
     In another embodiment of the inventive concept, buffer manager  140  can include maximum fullness threshold  610 . As with minimum fullness threshold  615 , maximum fullness threshold  610  can be represented either as a raw number (i.e., data output buffer  135  must include at least that many data requests before data can be output) or a percentage (data output buffer  135  must be at least that percentage full before data can be output), among other possibilities. If data output buffer  135  has more than maximum fullness threshold  610 , then buffer manager  140  can burst data from data output buffer  135 . As described above with reference to  FIG. 3 , bursting data can include selecting any data from data output buffer  135  to send back to host computer system  205 . 
     In yet another embodiment of the inventive concept, aspects of the embodiments of the inventive concepts shown in  FIGS. 5-6  can be combined. For example, if data output buffer  135  has less than minimum fullness threshold  605 , buffer manager  140  can wait until either data output buffer  135  has a minimum fullness, or until some data in data output buffer  135  has been resident in data output buffer  135  for longer than timer threshold  525 . 
     In yet another embodiment of the inventive concept, buffer manager  140  can track which data request (by transaction ID) was last output, using counter  615 . Buffer manager  140  can wait until the sequentially next data request submitted to SSD  105  has been buffered in data output buffer  135 ; when that data is received by data output buffer  135 , buffer manager  515  can output that data request. Buffer manager  140  can then increment counter  615  to reflect that another data request was output. 
     But waiting until the sequentially next data is received by data output buffer  135  could result in too much data waiting for output (for example, data output buffer  135  might be filled before the sequentially next data request is actually ready for output). To address this concern, buffer manager  140  can include maximum fullness threshold  610 . If data output buffer  135  has more entries than maximum fullness threshold  610  specifies, buffer manager  140  can burst data even if the sequentially next data for which buffer manager  140  has been waiting is not yet in data output buffer  135 . Buffer manager  135  can output whatever data is desired. For example, buffer manager  140  can output the earliest requested data (based on transaction ID) in data output buffer  135 , or buffer manager  140  can output the longest resident data (based on Time In, not shown in  FIG. 6 , or based on the data at the “top” of data output buffer  135 ). 
       FIGS. 7A and 7B  compare the tail response time of example data requests using an SSD with and without an embodiment of the inventive concept. Some assumptions used in  FIGS. 7A and 7B  are that it takes 50 cycles for a channel to return data from a flash memory chip, and 25 cycles to transfer data from the SSD to the host. 
     In  FIG. 7A , data requests were returned to host computer system  205  in the order in which the data requests were input to data output buffer  135 . Data requests  705 ,  710 ,  715 ,  720 ,  725 ,  730 ,  735 , and  740  are shown in data output buffer  135 . But the host computer did not send the data requests in this order. Table  745  shows the calculation of the tail response times, and shows the cycle in which the requests were received by the SSD. Thus, for example, data request  705  was the first data request, received by the SSD in cycle  0 ; data request  710  was the second data request, received by the SSD in cycle  1 ; data request  725  was the third data request, received by the SSD in cycle  2 , and so on. Rather than showing the complete memory address, the data requests in data output buffer  135  are shown by channel. 
     Data request  705  was the first data request, received in cycle  0  and requesting data from channel  0 . Data request  705  therefore could be immediately sent to the flash memory chip to be satisfied. Since it took 50 cycles to receive back the data, data request  705  was put in data output buffer  135  in cycle  50 . With an additional 25 cycles needed to return the data to host computer system  205 , the data was received by host computer system  205  in cycle  75 , for a total latency of 75 cycles (tail response time  750 ). 
     Data request  710  was the second data request, received in cycle  1  and requesting data from channel  3 . Data request  710  therefore could be immediately sent to the flash memory chip to be satisfied. Since it took 50 cycles to receive back the data, data request  710  was put in data output buffer  135  in cycle  51 . But during that cycle, host interface logic  110  was occupied with returning the data from data request  705 . So data request  710  had to wait until cycle  75  before it could be returned to host computer system  205 . Therefore, data request  710  was returned to host computer system  205  in cycle  100 , for a total latency of 99 cycles (tail response time  755 ). 
     Data requests  725  and  740  were the third and fourth data requests, received in cycles  2  and  3 , respectively. But data requests  725  and  740  both requested data from channel  0 , which was occupied with returning the data from data request  705 . So data request  715 , requesting data from channel  1  in cycle  4 , was the third data request returned to data output buffer  135  (returned in cycle  54 ). During that cycle, host interface logic  110  was occupied with returning the data from data request  705 , and after that, host interface logic  110  was occupied with returning the data from data request  710 . So data request  715  had to wait until cycle  100  before it could be returned to host computer system  205 . Therefore, data request  715  was returned to host computer system  205  in cycle  125 , for a total latency of 121 cycles (tail response time  760 ). 
     Reviewing table  745 , the worst tail response time is for data request  740 , with a total of 247 cycles (tail response time  765 ) between when the data was requested and when it was returned to host computer system  205 . The worst tail response time occurred for the fourth data request issued by host computer system  205 , which was the last data request returned from the flash memory chips. 
     In contrast, in  FIG. 7B , the data requests were issued by host computer system  205  in the same order, in the same cycles, and using the same channels. Data requests  705  and  710  are still the first two data requests returned to host computer system  205 , with the same tail response times. But the third data request returned by the SSD in  FIG. 7B  was data request  725 , returned to host computer system  205  in cycle  125 . Data request  725  was selected to be returned to host computer system  205  because it had the lowest transaction ID (and therefore was the earliest requested data in data output buffer  135 ) at cycle  100  (when host interface logic  110  was finished sending the data from data request  710  back to host computer system  205 ). Continuing the process, the worst tail response time was for data request  730 , issued in cycle  7  and returned to host computer system  205  in cycle  250 , for a tail response time of 243 cycles (tail response time  770 ). This is an improvement over the 247 cycle tail response time for data request  740  in  FIG. 7A . 
     It is worth noting that the average response time in  FIG. 7B  is no worse than the average response time in  FIG. 7A  (both have average response times of 159 cycles). But the tail response time of  FIG. 7B  is better than that of  FIG. 7A , showing that embodiments of the inventive concept can improve the operation of SSDs. 
     While the above description focuses on how embodiments of the inventive concept can improve the tail response time of SSDs, embodiments of the inventive concept are applicable in any situation in which data can be returned in a different order than the data was requested. For example, consider what happens when a computer, such as computer system  205 , requests a web page from a web site on the Internet. The web page might include images drawn from a variety of web sites, each image requiring a separate request from the appropriate data source. The images might be returned in a different order than requested. If the page has a significant number of images and images lower on the web page are loaded first, viewing the web page before all the images are loaded would be awkward: later loaded images would shift what information is on screen. Other possible applications for embodiments of the inventive concept can include USB flash drives and other data storage devices that include multiple data channels, distributed storage (such as Network Attached Storage (NAS) or cloud storage). 
     To improve tail response time for requests from data sources other than SSDs, another embodiment of the inventive concept can be employed.  FIG. 8  shows data management device  805 , which can manage data returned from a number of data sources, according to an embodiment of the inventive concept. Data management device  805  is similar to SSD  105 , except that data management device  805  does not include the sources of data or the channels coupled to controller  810 : data sources  815 - 1 ,  815 - 2 ,  815 - 3 ,  815 - 4 ,  815 - 5 ,  815 - 6 ,  815 - 7 , and  815 - 8  and channels  820 - 1 ,  820 - 2 ,  820 - 3 , and  820 - 4  can be external to data management device  805 . Data sources  815 - 1  through  815 - 8  can be any data sources and channels, located anywhere appropriate; channels  820 - 1  through  820 - 4  can be any channels that connect the data sources with data management device  805 . (The embodiment of the inventive concept shown in  FIG. 8  is merely exemplary: there can be any number of data sources, organized along any number of channels.) 
     Data management device  805  includes host interface logic  110 , which manages receiving data requests from host computer system  205 , just as with SSD  105 . Data management device  805  also includes controller  810 , which can store data requests from host computer system  205  in data input buffer  130 , store data from the data sources in data output buffer  135 , and use buffer manager  140  and re-order logic  145  to manage data input and output as described earlier. 
     As an example of how data management device  805  might be implemented, data management device  805  can be included in a network interface card. Since network interface cards can include a networking port and can provide an interface between the computer and a network, a network interface card represents a logical place to include controller  810 , in addition to host interface logic  110 . 
     As described above, embodiments of the invention look for the earliest requested data, the longest resident data, or the lowest transaction ID. In general, these embodiments of the invention most reduce the tail response time. But tail response time can be reduced by selecting an earlier requested data even if not the earliest requested data, or by selecting a longer resident data, even if not the longest resident data, or by selecting a lower transaction ID, even if not the lowest transaction ID. 
       FIGS. 9A-9B  show a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to process data requests to reduce tail response time, according to an embodiment of the inventive concept. In  FIG. 9A , at block  905 , SSD  105  (via host interface logic  110 ) receives a data request from host computer system  205 . (In the flowcharts, reference is made to operations by SSD  105 , but these operations could equally be made by data management device  805 . Any reference to SSD  105  is intended to also include a reference to data management device  805 ). At block  910 , re-order logic  145  associates a transaction ID with the data request. As discussed above, associating a transaction ID with a data request can also be done by other components, such as buffer manager  140 . Nor is a transaction ID actually required, provided re-order logic  145  can determine an order for various data requests. At block  915 , controller  115  stores the data request (and associated transaction ID) in data input buffer  130 . At block  920 , buffer manager  140  selects the data request to be processed by the appropriate flash memory chip. At block  925 , controller  115  receives the data responsive to the data request. 
     At block  930  ( FIG. 9B ), controller  115  stores the data in data output buffer  135 . At block  935 , buffer manager  140  waits until host computer system  205  is ready to receive data. At block  940 , buffer manager  140  (advised by re-order logic  145 ) selects a data from data output buffer  135 . And at block  945 , SSD  105  (via host interface logic  110 ) sends the selected data back to host computer system  205 . 
     In  FIGS. 9A-9B  (and in the other flowcharts below), one embodiment of the inventive concept is shown. But a person skilled in the art will recognize that other embodiments of the inventive concept are also possible, by changing the order of the blocks, by omitting blocks, or by including links not shown in the drawings. In addition, embodiments of the inventive concept can combine aspects of the described individual embodiments. All such variations of the flowcharts are considered to be embodiments of the inventive concept, whether expressly described or not. 
       FIGS. 10A-10B  show a flowchart of a procedure for SSD  105  of  FIG. 1  or data management device  805  of  FIG. 8  to manage data output buffer  135  based on how long data has been resident in data output buffer  135 , according to an embodiment of the inventive concept. In  FIG. 10A , at block  1005 , re-order logic  145  identifies an earliest requested data in data output buffer  135 : for example, by identifying the data with the lowest transaction ID. At block  1010 , buffer manager  145  identifies the longest resident data in data output buffer  135 . Typically, the longest resident data in data output buffer  135  is the data at the head of data output buffer  135 . At block  1015 , buffer manager  140  compares how long the longest resident data has been in data output buffer  135  with timer threshold  525 . 
     At block  1020  ( FIG. 10B ), buffer manager  140  determines whether the longest resident data has been in data output buffer  135  too long. If not, then at block  1025 , buffer manager  140  selects the earliest requested data suggested by re-order logic  145  for output. Otherwise, at block  1030 , buffer manager  145  selects the longest resident data in data output buffer  135  for output. 
       FIGS. 11A-11B  show a flowchart of a procedure for SSD  105  of  FIG. 1  or data management device  805  of  FIG. 8  to manage data output buffer  135  based on how full data output buffer  135  is, according to an embodiment of the inventive concept. In  FIG. 11A , at block  1105 , re-order logic  145  identifies an earliest requested data in data output buffer  135 : for example, by identifying the data with the lowest transaction ID. At block  1110 , buffer manager  145  determines how full data output buffer  135  is. At block  1115 , buffer manager  140  compares the fullness of data output buffer  135  with minimum fullness threshold  605 . 
     At block  1120  ( FIG. 11B ), buffer manager  140  determines if data output buffer  135  is less full than minimum fullness threshold  605 . If so, then at block  1125  buffer manager  140  does not select any data for output. Otherwise, at block  1130 , buffer manager  140  determines if data output buffer  135  is fuller than maximum fullness threshold  610 . If not, then buffer manager  1135  selects the data suggested by re-order logic  145  for output. Otherwise, at block  1140 , buffer manager  140  selects any desired data (for example, the longest resident data) for output (to burst data). 
       FIG. 12  shows a flowchart of a procedure for the SSD of  FIG. 1  or the data management device of  FIG. 8  to select a next data for output, according to an embodiment of the inventive concept. At block  1205 , buffer manager  140  determines the transaction ID of the most recently output data (for example, using counter  615 ). At block  1210 , buffer manager  140  waits until data associated with the next transaction ID is added to data output buffer  135 . At block  1215 , buffer manager  140  selects that data for output. And at block  1220 , buffer manager  140  updates what transaction ID was associated with the most recently output data. 
     The various embodiments of the inventive concept described above can be combined. For example, an embodiment of the inventive concept can include re-order logic  145 , with buffer manager  140  equipped to burst data if data has been in data output buffer  135  too long (as shown in  FIG. 5  and operationally described in  FIGS. 10A-10B ) and to manage the fullness of data output buffer  135  (as shown in  FIG. 6  and operationally described in  FIGS. 11A-11B ). A person skilled in the art will also recognize other combinations of embodiments of the inventive concept that are possible. 
     Embodiments of the inventive concept can extend to the following statements, without limitation: 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host so that an earlier data request has a lower transaction ID than higher transaction ID assigned to a later data request and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data using the transaction ID. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a counter to store a most recently output transaction ID; a buffer manager to wait to send data from the data output buffer until a data associated with a next transaction ID is stored in the data output buffer and to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a counter to store a most recently output transaction ID; a buffer manager to wait to send data from the data output buffer until a data associated with a next transaction ID is stored in the data output buffer, to select data from the data output buffer to send to the host via the interface, and to increment the counter; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select the earlier requested data from the data output buffer to send to the host via the interface; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select a second data from the data output buffer to send to the host via the interface that has been in the data output buffer for more than a timer threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select a second data from the data output buffer to send to the host via the interface that has been in the data output buffer for more than a timer threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data, wherein the buffer manager includes a timer, the buffer manager is operative to assign a time from the timer to each data in the data output buffer when the data was received by the data output buffer, and the difference between a current time and the time assigned to each data identifies how long each data has been in the data output buffer. 
     An embodiment of the inventive concept includes a solid state drive, comprising: an interface with a host; and a controller coupled to a plurality of channels, each channel coupled to a plurality of flash chips, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of flash chips; a buffer manager to select any data from the data output buffer to send to the host via the interface when the data output buffer has a fullness that is greater than a first fullness threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: associating a transaction ID with a data request when the data request enters a data input buffer of the SSD; receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: associating a transaction ID with a data request when the data request enters a data input buffer of the SSD, the transaction ID greater than a second transaction ID for an earlier data request and less than a third transaction ID for a later data request; receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer, including identifying a second data which is a longer resident data in the data output buffer, comparing the longest amount of time for the second data with a timer threshold, and if the longest amount of time for the second data is greater than the timer threshold, selecting the second data instead of the first data for output; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a fullness percentage for the data output buffer, comparing the fullness percentage to a first threshold, and if the fullness percentage is less than the first threshold, not selecting any data for output; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a fullness percentage for the data output buffer, comparing the fullness percentage to a first threshold, if the fullness percentage is less than the first threshold, not selecting any data for output, and if the fullness percentage is greater than a second threshold, selecting a second data that is a longer resident data in the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a most recently output transaction ID, waiting until the data output buffer stores a next transaction ID, selecting a data associated with the next transaction ID as the first data, and updating the most recently output transaction ID; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a flash chip of a Solid State Drive; waiting until a host is ready to receive data from the data output buffer of the SSD; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host so that an earlier data request has a lower transaction ID than higher transaction ID assigned to a later data request and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data using the transaction ID. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a counter to store a most recently output transaction ID; a buffer manager to wait to send data from the data output buffer until a data associated with a next transaction ID is stored in the data output buffer and to select data from the data output buffer to send to the host via the interface; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a counter to store a most recently output transaction ID; a buffer manager to wait to send data from the data output buffer until a data associated with a next transaction ID is stored in the data output buffer, to select data from the data output buffer to send to the host via the interface, and to increment the counter; and a re-order logic to assign a transaction ID to each data request received from the host and to select a data from the data output buffer with an oldest transaction ID to advise the buffer manager which data is an earlier requested data, wherein the buffer manager is operative to send no data to the host via the interface is the data output buffer has a fullness that is less than a second fullness threshold. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select the earlier requested data from the data output buffer to send to the host via the interface; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select a second data from the data output buffer to send to the host via the interface that has been in the data output buffer for more than a timer threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select a second data from the data output buffer to send to the host via the interface that has been in the data output buffer for more than a timer threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data, wherein the buffer manager includes a timer, the buffer manager is operative to assign a time from the timer to each data in the data output buffer when the data was received by the data output buffer, and the difference between a current time and the time assigned to each data identifies how long each data has been in the data output buffer. 
     An embodiment of the inventive concept includes a data management device, comprising: an interface with a host; and a controller coupled to a plurality of data sources, the controller including: a data input buffer to store data requests received from the host; a data output buffer to store data received from one of the plurality of data sources; a buffer manager to select any data from the data output buffer to send to the host via the interface when the data output buffer has a fullness that is greater than a first fullness threshold; and a re-order logic to advise the buffer manager which data is an earlier requested data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: associating a transaction ID with a data request when the data request enters a data input buffer of a data management device; receiving a data at the data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: associating a transaction ID with a data request when the data request enters a data input buffer of a data management device, the transaction ID greater than a second transaction ID for an earlier data request and less than a third transaction ID for a later data request; receiving a data at the data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data at a data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer, including identifying a second data which is a longer resident data in the data output buffer, comparing the longest amount of time for the second data with a timer threshold, and if the longest amount of time for the second data is greater than the timer threshold, selecting the second data instead of the first data for output; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data at a data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a fullness percentage for the data output buffer, comparing the fullness percentage to a first threshold, and if the fullness percentage is less than the first threshold, not selecting any data for output; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data at a data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a fullness percentage for the data output buffer, comparing the fullness percentage to a first threshold, if the fullness percentage is less than the first threshold, not selecting any data for output, and if the fullness percentage is greater than a second threshold, selecting a second data that is a longer resident data in the data output buffer; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data at a data management device for a transaction in a data output buffer from a data source; selecting a first data associated with a lower associated transaction ID from the data output buffer, including determining a most recently output transaction ID, waiting until the data output buffer stores a next transaction ID, selecting a data associated with the next transaction ID as the first data, and updating the most recently output transaction ID; and outputting the selected data. 
     An embodiment of the inventive concept includes a method, comprising: receiving a data at a data management device for a transaction in a data output buffer from a data source; waiting until a host is ready to receive data from the data output buffer of the data management device; selecting a first data associated with a lower associated transaction ID from the data output buffer; and outputting the selected data. 
     The following discussion is intended to provide a brief, general description of a suitable machine or machines in which certain aspects of the inventive concept can be implemented. Typically, the machine or machines include a system bus to which is attached processors, memory, e.g., random access memory (RAM), read-only memory (ROM), or other state preserving medium, storage devices, a video interface, and input/output interface ports. The machine or machines can be controlled, at least in part, by input from conventional input devices, such as keyboards, mice, etc., as well as by directives received from another machine, interaction with a virtual reality (VR) environment, biometric feedback, or other input signal. As used herein, the term “machine” is intended to broadly encompass a single machine, a virtual machine, or a system of communicatively coupled machines, virtual machines, or devices operating together. Exemplary machines include computing devices such as personal computers, workstations, servers, portable computers, handheld devices, telephones, tablets, etc., as well as transportation devices, such as private or public transportation, e.g., automobiles, trains, cabs, etc. 
     The machine or machines can include embedded controllers, such as programmable or non-programmable logic devices or arrays, Application Specific Integrated Circuits (ASICs), embedded computers, smart cards, and the like. The machine or machines can utilize one or more connections to one or more remote machines, such as through a network interface, modem, or other communicative coupling. Machines can be interconnected by way of a physical and/or logical network, such as an intranet, the Internet, local area networks, wide area networks, etc. One skilled in the art will appreciate that network communication can utilize various wired and/or wireless short range or long range carriers and protocols, including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE) 802.11, Bluetooth®, optical, infrared, cable, laser, etc. 
     Embodiments of the present inventive concept can be described by reference to or in conjunction with associated data including functions, procedures, data structures, application programs, etc. which when accessed by a machine results in the machine performing tasks or defining abstract data types or low-level hardware contexts. Associated data can be stored in, for example, the volatile and/or non-volatile memory, e.g., RAM, ROM, etc., or in other storage devices and their associated storage media, including hard-drives, floppy-disks, optical storage, tapes, flash memory, memory sticks, digital video disks, biological storage, etc. Associated data can be delivered over transmission environments, including the physical and/or logical network, in the form of packets, serial data, parallel data, propagated signals, etc., and can be used in a compressed or encrypted format. Associated data can be used in a distributed environment, and stored locally and/or remotely for machine access. 
     Embodiments of the inventive concept can include a tangible, non-transitory machine-readable medium comprising instructions executable by one or more processors, the instructions comprising instructions to perform the elements of the inventive concepts as described herein. 
     Having described and illustrated the principles of the inventive concept with reference to illustrated embodiments, it will be recognized that the illustrated embodiments can be modified in arrangement and detail without departing from such principles, and can be combined in any desired manner. And, although the foregoing discussion has focused on particular embodiments, other configurations are contemplated. In particular, even though expressions such as “according to an embodiment of the inventive concept” or the like are used herein, these phrases are meant to generally reference embodiment possibilities, and are not intended to limit the inventive concept to particular embodiment configurations. As used herein, these terms can reference the same or different embodiments that are combinable into other embodiments. 
     The foregoing illustrative embodiments are not to be construed as limiting the inventive concept thereof. Although a few embodiments have been described, those skilled in the art will readily appreciate that many modifications are possible to those embodiments without materially departing from the novel teachings and advantages of the present disclosure. Accordingly, all such modifications are intended to be included within the scope of this inventive concept as defined in the claims. 
     Consequently, in view of the wide variety of permutations to the embodiments described herein, this detailed description and accompanying material is intended to be illustrative only, and should not be taken as limiting the scope of the inventive concept. What is claimed as the inventive concept, therefore, is all such modifications as may come within the scope and spirit of the following claims and equivalents thereto.