Storage system and sorting-based method for random read command prediction in a multi-queue system
A storage system and sorting-based method for random read command prediction in a multi-queue system are provided. In one embodiment, a method for command prediction is performed in a storage system comprising a memory and being in communication with a host. The method comprises receiving a read command sequence from the host, wherein read commands in the read command sequence originate from a plurality of command queues in the host such that read commands in the read command sequence received from the host are out of order; sorting read commands in the read command sequence received from the host based on logical block addresses; and predicting a next read command from the sorted read commands. Other embodiments are provided.
1. A method for command prediction, the method comprising:
performing the following in a storage system comprising a memory and being in communication with a host:
receiving a read command sequence from the host, wherein read commands in the read command sequence originate from a plurality of command queues in the host such that read commands in the read command sequence received from the host are out of order;
sorting read commands in the read command sequence received from the host based on logical block addresses; and
predicting a next read command from the sorted read commands.
2. The method of claim 1 , wherein the read command sequence originates from a single thread in the host.
3. The method of claim 2 , wherein the single thread comprises one of the following: a submission/completion queue pair, a namespace identifier, a host port, a virtual function, and a stream identifier.
4. The method of claim 1 , wherein the read commands in the read command sequence are sorted by directing different permutations of logical block addresses to a same sort pattern.
5. The method of claim 1 , wherein the memory comprises a three-dimensional memory.
6. The method of claim 1 , wherein the storage system is configured to be integrated in the host.
7. The method of claim 1 , wherein the storage system is configured to be removably connected with the host.
8. A storage system comprising:
a memory; and
a controller configured to be in communication with the memory, wherein the controller is further configured to:
maintain, for each previously-received read command logical block address, a list of associated read command logical block addresses and frequency of use of each of the associated read command logical block addresses;
update a current-command logical block address at each logger address in a history logger that is associated with each command in a command sequence; and
predict a next command by accessing the history logger to extract a set of lists of associated logical block addresses to each logical block address in the command sequence.
9. The storage system of claim 8 , wherein the updating comprises adding the current-command logical block address to a list of logical block addresses associated with a hash function in the history logger.
10. The storage system of claim 8 , wherein the updating comprises incrementing a frequency counter associated with the current-command logical block address.
11. The storage system of claim 8 , wherein a predicted logical block address is determined as a most-frequent logical block address in the set of logical block address lists.
12. The storage system of claim 8 , wherein the current command sequence originates from multiple threads in a host.
13. The storage system of claim 12 , wherein the multiple threads comprise two or more of the following: a submission/completion queue pair, a namespace identifier, a host port, a virtual function, and a stream identifier.
14. The storage system of claim 8 , wherein the memory comprises a three-dimensional memory.
15. The storage system of claim 8 , wherein the storage system is configured to be integrated in a host.
16. The storage system of claim 8 , wherein the storage system is configured to be removably connected with the host.
17. A storage system comprising:
a memory;
means for maintaining, for each previously-received read command logical block address, a list of associated read command logical block addresses and frequency of use of each of the associated read command logical block addresses;
means for updating a current-command logical block address at each logger address in a history logger that is associated with each command in a command sequence; and means for predicting a next command by accessing the history logger to extract a set of lists of associated logical block addresses to each logical block address in the command sequence.
18. The storage system of claim 17 , wherein the command sequence originates from a single thread in the host.
19. The storage system of claim 17 , wherein the command sequence originates from multiple threads in the host.
20. The storage system of claim 17 , wherein the memory comprises a three-dimensional memory.