System and method for prediction of multiple read commands directed to non-sequential data

A method for predicting multiple random read commands, the method comprising:

• receiving, at a memory device, a current read command for data located at a starting address discontiguous with an address range associated with a last read command received prior to the current read command;
• generating, with a controller of the memory device, a search sequence comprising a predetermined plurality of prior read commands including at least the current read command and the last read command, wherein generating the search sequence comprises storing a start logical block address (LBA) for each of the predetermined plurality of prior read commands, arranged chronologically in order of read command receipt at the controller, in a search sequence buffer in the memory device;
• calculating, with the controller, based on the search sequence, an index value within a predetermined range of index values, the calculated index value representative of the search sequence, wherein calculating the index value comprises:
• applying a value of the search sequence as input for a many-to-one mapping operation and,
• processing a result of the many-to-one mapping operation with a modulo operation having an output limited to index values in the predetermined range of index values;
• retrieving, from an entry in a prior read command data structure stored in a first memory of the memory device and indexed by the calculated index value, data representative of a predetermined plurality of historical next read commands associated with the calculated index value;
• and
• pre-fetching data for each of the predetermined plurality of historical next read commands from a second memory of the memory device to the first memory of the memory device based on the retrieved data representative of the predetermined plurality of historical next read commands associated with the calculated index value.

A memory device comprising:

• a first memory;
• a second memory comprising:
• a search sequence buffer;
• and
• a prior read command data structure having a plurality of entries representing a read command history of the memory device;
• means for receiving a current read command comprising read command data including a start logical block address (LBA) and a data length, wherein the start LBA of the current read command is discontiguous with an address range associated with a last read command received prior to the current read command;
• means for generating a search sequence in the search sequence buffer based on at least the current read command, wherein the search sequence comprises the current read command and at least one read command received prior to the current read command;
• means for calculating an index value based on the search sequence;
• means for retrieving from an entry of a prior read command data structure indexed by the calculated index value address data for a sequence of historical next read commands with the calculated index value;
• and
• means for pre-fetching data for the sequence of historical next read commands from the first memory to the second memory based on the retrieved address data.