Context-aware dynamic command scheduling for a data storage system

Patent metadata

Field	Value
Publication number	US-10635617-B2
Application number	US-201715600672-A
Country	US
Kind code	B2
Filing date	May 19, 2017
Priority date	May 19, 2017
Publication date	Apr 28, 2020
Grant date	Apr 28, 2020

Abstract

The subject technology provides for managing a data storage system. Commands are identified into as a first command type or a second command type. The commands identified as the first command type are assigned to a first queue, and the commands identified as the second command type are assigned to a second queue. After the commands from the first queue and the commands from the second queue are processed based on a scheduling ratio over a predetermined period of time, a write amplification factor, number of host read commands, and number of host write commands during the predetermined period of time are determined. The scheduling ratio is updated based on the write amplification, the number of host read commands, the number of host write commands, and a predetermined scheduling ratio factor. Subsequent commands are processed from the first queue and the second queue based on the updated scheduling ratio.

First claim

What is claimed is:

1. A method for managing a data storage device, the method comprising:
identifying a command as a high priority command or a low priority command;
when the command is the high priority command, assigning the command to a first queue, which is a high priority queue;
when the command is the low priority command, assigning the command to a second queue, which is a low priority queue, wherein the second queue is configured to contain at least two different command types comprising a first command type and a second command type, and wherein the first command type is a write command, and the second command type is different from the first command type;
processing one or more commands from the first queue and one or more commands from the second queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the first queue to be processed and a number of one or more commands from the second queue to be processed;
periodically determining a write amplification factor of the data storage device, and a total number of host read commands and a total number of host write commands received by the data storage device during a respective predetermined period of time;
periodically generating an updated scheduling ratio based on the following equation:

A

B
·
C

·
D

=
E

wherein:
A is the total number of host read commands received during the respective redetermined period of time,
B is the total number of host write commands received during the respective predetermined period of time,
C is the determined write amplification factor,
D is a scheduling ratio factor determined based on the scheduling ratio, A, B, and C, and
E is the updated scheduling ratio; and

processing subsequent commands from the first queue and the second queue based on the updated scheduling ratio.

2. The method according to claim 1 , wherein the first command type includes the write command received from a host device, wherein the second command type includes a command received from the host device that is not the write command, and wherein the host device is coupled to the data storage device.

3. The method according to claim 2 , further comprising:
maintaining, in memory, a log of the total number of host read commands and the total number of host write commands received from the host device during the respective predetermined period of time.

4. The method according to claim 1 , wherein the write amplification factor of the data storage device is determined based on a number of program/erase cycle performed on the data storage device.

5. The method according to claim 4 , wherein the write amplification factor of the data storage device is determined based on an amount of over provisioning of the data storage device.

6. The method according to claim 1 , wherein the subsequent commands are assigned to the first queue or the second queue based on priority.

7. A data storage device, comprising:
means for identifying a command as a high priority command or a low priority command;
when the command is the high priority command, means for assigning the command to a first queue, which is a high priority queue;
when the command is the low priority command, means for assigning the command to a second queue, which is a low priority queue, wherein the second queue is configured to contain at least two different command types comprising a first command type and a second command type;
means for processing one or more commands from the first queue and one or more commands from the second queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the first queue to be processed and a number of one or more commands from the second queue to be processed;
means for periodically determining a write amplification factor of the data storage device, and a total number of host read commands and a total number of host write commands received by the data storage device during a respective predetermined period of time;
means for generating an updated scheduling ratio based on the following equation:

A

B
·
C

·
D

=
E

wherein:
A is the total number of host read commands received during the respective predetermined period of time,
B is the total number of host write commands received during the respective predetermined period of time,
C is the determined write amplification factor,
D is a scheduling ratio factor determined based on the scheduling ratio, A, B, and C, and
E is the updated scheduling ratio; and

means for processing subsequent commands from the first queue and the second queue based on the updated scheduling ratio.

8. The data storage device according to claim 7 , further comprising:
means for maintaining, in memory, a log of the total number of host read commands and the total number of host write commands received from a host device during the respective predetermined period of time.

9. The data storage device according to claim 7 , comprising:
means for assigning the subsequent commands to the first queue or the second queue based on priority.

10. A data storage device, comprising:
a plurality of storage devices, each storage device comprising a plurality of non-volatile memory die; and
a controller coupled to the plurality of storage devices, wherein the controller is configured to:
identify a command as a high priority command or a low priority command;
when the command is the high priority command, assign the command to a first queue, which is a high priority queue;
when the command is the low priority command, assign the command to a second queue, which is a low priority queue, wherein the second queue is configured to contain at least two different command types comprising a first command type and a second command type;
process one or more commands from the first queue and one or more commands from the second queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the first queue to be processed and a number of one or more commands from the second queue to be processed;
periodically determine a write amplification factor of the data storage device, and a total number of host read commands and a total number of host write commands received by the data storage device during a respective predetermined period of time;
generating an updated scheduling ratio based on the following equation:

A

B
·
C

·
D

=
E

Assignees

• Western Digital Tech Inc

Inventors

• Jinn Scott
• Lai Yun-Tzuo
• Liu Haining
• Pavlenko Yuriy

Classifications

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• H04W74/0875

  with assigned priorities based access · CPC title

• G06F13/374 Primary

  using a self-select method with individual priority code comparator · CPC title

• G06F13/26

  with priority control · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title