System and method for prediction of random read commands in virtualized multi-queue memory systems

Patent metadata

Field	Value
Publication number	US-2020242037-A1
Application number	US-201916259481-A
Country	US
Kind code	A1
Filing date	Jan 28, 2019
Priority date	Jan 28, 2019
Publication date	Jul 30, 2020
Grant date	—

Abstract

Systems and methods for predicting read commands and pre-fetching data when a storage device is receiving random read commands to non-sequentially addressed data locations from a plurality of host sources are disclosed. A storage device having a memory with a plurality of separate prior read command data structures includes a controller having a next read command prediction module that separately predicts a next read command based on a received read command from the one of the plurality of prior read command data structures associated with the host from which the received command originated. The storage device then pre-fetches the data identified in the predicted next read command.

First claim

We claim:

1 . A storage device comprising:
a first memory; a second memory comprising: a plurality of search sequence buffers; and a plurality of prior read command data structures each having a plurality of entries representing a read command history of a respective one host source of a plurality of host sources in communication with the storage device; and a controller in communication with the first memory and the second memory, the controller configured to:
receive a current read command comprising read command data including an address, wherein the address of the current read command is discontiguous with an address range associated with a last read command received prior to the current read command;
identify which host source of the plurality of host sources is associated with the current read command;
generate a search sequence in a search sequence buffer associated with the identified host source based on at least the current read command;
retrieve, from a prior read command data structure associated with the identified host source, address data for a historical next read command associated with the search sequence; and
pre-fetch data for the historical next read command from the first memory to the second memory based on the retrieved address data.

2 . The storage device of claim 1 , wherein:
the plurality of host sources comprise virtual hosts; and the controller is further configured to identify the host source associated with the current read command based on a virtual host identifier received with the current read command.

3 . The storage device of claim 1 , wherein:
at least one of the plurality of host sources comprises a host group having a predetermined group of host sources; and the controller is further configured to identify the current read command as belonging to the host group having the predetermined group of host sources responsive to a host identifier received with the current read command identifying any one host source of the predetermined group of host sources.

4 . The storage device of claim 1 , wherein:
the search sequence comprises only the current read command; the prior read command data structure associated with the identified host source comprises a predetermined number of entries that are each indexed with a respective index value within a predetermined range of index values; and the controller is further configured to:
calculate an index value, based on the search sequence, within the predetermined range of index values; and
retrieve, from an entry in the prior read command data structure indexed by the calculated index value, the address data for a historical next read command associated with the calculated index value.

5 . The storage device of claim 1 , wherein:
the search sequence comprises:
the current read command; and
at least one read command for the identified host source received prior to the current read command;
the prior read command data structure for the identified host source comprises a predetermined number of entries that are each indexed with a respective index value within a predetermined range of index values; and the controller is further configured to:
calculate an index value, based on the search sequence, within the predetermined range of index values; and
retrieve, from an entry in the prior read command data structure for the identified host source indexed by the calculated index value, the address data for at least one historical next read command associated with the calculated index value.

6 . The storage device of claim 1 , wherein:
the first memory comprises non-volatile memory; and the second memory comprises volatile memory.

7 . The storage device of claim 6 , wherein the non-volatile memory comprises a substrate formed with a three-dimensional memory structure.

8 . The storage device of claim 5 , wherein the search sequence comprises:
a start logical block address (LBA) of the current read command; and a respective start LBA of each of a predetermined number of prior read commands from the identified host source arranged chronologically in order of read command receipt at the controller.

9 . The storage device of claim 5 , wherein:
the search sequence comprises a list, arranged chronologically by time of read receipt at the controller, of differential logical block address (DLBA) information for the current read command and each other of a predetermined number of prior read commands for the identified host source; and each DLBA comprises a difference between a start logical block address (LBA) of a respective read command and a start LBA of a last read command received for the identified host source prior to the respective read command.

10 . A method for predicting a random read command in a storage device in communication with a plurality of host sources, the method comprising:
receiving from one host source of the plurality of host sources, at a storage device, a current read command for data located at a starting address; identifying which host source of the plurality of host sources is associated with the current read command; determining a prior read command pattern including the current read command specific to the identified host source; and in a volatile memory of the storage device having a plurality of prior read command data structures each associated with prior read commands for a respective group of the plurality of host sources:
identifying a predicted next read command from the prior read command data structure for the group of the plurality of host sources that includes the identified host source based on the determined prior read command pattern;
prefetching data identified by the predicted next read command; and
updating the prior read command data structure for the group of the plurality of host sources that includes the identified host source in response to receiving an actual next read command from the identified host source.

11 . The method of claim 10 , wherein the plurality of host sources comprise a plurality of virtual hosts.

12 . The method of claim 10 , wherein each host source of the plurality of host sources comprises one of a virtual host, a physical host device, a host queue, or a namespace identifier.

13 . The method of claim 10 , wherein:
each of the plurality of prior read command data structures is exclusively associated with a respective host group; and each host source of the plurality of host sources is exclusively associated with only one host group of the plurality of host groups.

14 . The method of claim 13 , further comprising:
determining whether to reassign a host source from a first host group to a second host group in response to a host reallocation trigger; and in response to determining to reassign the host source to the second host group, storing subsequently-received read command information from the host source in a prior read command data structure exclusively associated with the second host group.

15 . The method of claim 10 , further comprising:
determining whether to adjust a relative amount of memory in the storage device allocated among the plurality of prior read command data structures based on a prediction accuracy of the plurality of prior read command data structures; and adjusting the relative amount of memory in the storage device allocated among the plurality of prior read command data structures based on the determination.

16 . The method of claim 10 , wherein adjusting the relative amount of memory is initiated in response to a rebalancing trigger.

Assignees

• Western Digital Tech Inc

Inventors

• Navon Ariel
• Benisty Shay
• Bazarsky Alex

Classifications

• G06F2212/6026

  Prefetching based on access pattern detection, e.g. stride based prefetch · CPC title

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F12/0862 Primary

  with prefetch · CPC title

• G06F2212/6024

  History based prefetching · CPC title

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title