Storage system and method for performing random read
A storage system has a volatile memory, a non-volatile memory, and a controller. The controller of the storage system can implement various mechanisms for improving random read performance. These mechanisms include improved read prediction cache management, using a pattern length for read prediction, and a time-based enhancement for read prediction. Each of these mechanisms can be used alone on in combination with some or all of the other mechanisms.
1. A storage system comprising:
a volatile memory;
a non-volatile memory, and
a controller configured to:
predict a plurality of next read commands to be received from a host by selecting the plurality of next read commands from a plurality of sets of predicted next read commands based on prediction hit rate scores associated with the plurality of sets;
predict a time when the predicted plurality of next read commands will be received from the host;
at, but not before, the predicted time, read a plurality of data associated with the predicted plurality of next read commands from the non-volatile memory and cache the plurality of data in the volatile memory;
receive a next read command from the host;
compare the next read command received from the host with the predicted plurality of next read commands;
in response to the next read command received from the host matching one of the predicted plurality of next read commands, send cached data associated with the matched predicted next read command to the host;
in response to the next read command received from the host not matching any of the predicted plurality of next read commands, maintain the cached plurality of data in the volatile memory;
determine a prediction hit rate score for each of the cached plurality of data; and
evict cached data with a lowest prediction hit rate score from the volatile memory.
2. The storage system of claim 1 , wherein the prediction hit rate score comprises a combination of a prediction hit rate and an age of a predicted command.
3. The storage system of claim 1 , wherein the controller comprises a history pattern matcher (HPM) sub-system.
4. The storage system of claim 3 , wherein the history pattern matcher (HPM) sub-system comprises a history pattern matcher (HPM), the volatile memory, and a cache manager.
5. The storage system of claim 1 , wherein the controller is further configured to predict the plurality of next read commands using a history of prior read commands received from the host.
6. The storage system of claim 1 , wherein the predicted plurality of next read commands comprises start logical block addresses and lengths.
7. The storage system of claim 1 , wherein the non-volatile memory comprises a three-dimensional memory.
8. In a storage system comprising a non-volatile memory and a volatile memory, a method comprising:
generating a plurality of sets of predicted next read commands from a host, wherein each set is based on a different number of prior read commands actually received from the host;
generating a prediction hit rate score for each sets;
predicting a plurality of next read commands to be received from the host by selecting the plurality of next read command from the plurality of sets based on the generated prediction hit rate scores;
predicting a time when the predicted plurality of next read commands will be received from the host;
at, but not before, the predicted time, pre-fetching data from the non-volatile memory for the predicted plurality of next read commands and storing the pre-fetched data in the volatile memory; and
maintaining the pre-fetched data in the volatile memory even if a next read command received from the host does not match one of the predicted plurality of predicted next read commands, wherein the pre-fetched data is later evicted from the volatile memory in response to the pre-fetched data having a lowest prediction hit rate score among prediction hit rate scores of other pre-fetched data stored in the volatile memory.
9. The storage system of claim 1 , wherein the controller is further configured to use the plurality of predicted next read commands for calibration.
10. The storage system of claim 1 , wherein the controller is further configured to use the plurality of predicted next read commands for training.
11. The method of claim 8 , wherein the plurality of sets are generated in parallel.
12. The method of claim 8 , wherein the plurality of sets are generated using one or more history pattern matcher engines.
13. The method of claim 8 , wherein the plurality of sets are generated by identifying logical block address (LBA) patterns in the prior read commands actually received from the host.
14. The method of claim 8 , further comprising using the predicted plurality of next read commands for calibration.
15. The method of claim 8 , further comprising using the predicted plurality of next read commands for training.
16. A storage system comprising:
a non-volatile memory;
a volatile memory;
means for predicting a plurality of next read commands to be received from a host by selecting the plurality of next read commands from a plurality of sets of predicted next read commands based on prediction hit rate scores associated with the plurality of sets;
means for predicting an arrival time for the predicted plurality of next read commands;
means for pre-fetching at, but not before, the predicted arrival time, a plurality of data associated with the predicted plurality of next read commands from the non-volatile memory and caching the plurality of data in the volatile memory;
means for receiving a next read command from the host;
means for comparing the next read command received from the host with the predicted plurality of next read commands;
means for sending cached data associated with the matched predicted next read command to the host in response to the next read command received from the host matching one of the predicted plurality of next read commands;
means for maintaining the cached plurality of data in the volatile memory in response to the next read command received from the host not matching any of the predicted plurality of next read commands
means for determining a prediction hit rate score for each of the cached plurality of data; and
means for evicting cached data with a lowest prediction hit rate score from the volatile memory.
17. The storage system of claim 16 , further comprising means for predicting logical block addresses and lengths of the predicted plurality of next ead commands.
18. The storage system of claim 16 , wherein the means for predicting the plurality of next read commands comprises a history pattern matcher engine.
19. The storage system of claim 16 , further comprising means for updating a log only in response to the predicted arrival time being less than a threshold.
20. The storage system of claim 19 , wherein the threshold indicates whether one of the plurality of predicted next read commands is in a same thread or a different thread than a previous command actually received from the host.