Context-aware dynamic command scheduling for a data storage system

Patent metadata

Field	Value
Publication number	US-11061842-B2
Application number	US-202016827591-A
Country	US
Kind code	B2
Filing date	Mar 23, 2020
Priority date	May 19, 2017
Publication date	Jul 13, 2021
Grant date	Jul 13, 2021

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 storage device, the method comprising:
allocating a high priority command to a high priority queue;
allocating a low priority command to a low priority queue; wherein the low priority queue is configured to contain two or more different command types;
executing commands from the high priority queue and the low priority queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the high priority queue to be processed and a number of one or more commands from the low priority queue to be processed;
determining a write amplification factor of the storage device;
determining a number of read commands and a number of write commands received during a respective period of time; and
executing additional commands from the high priority queue and the low priority queue based on an updated scheduling ratio,
wherein the updated scheduling ratio increases as the number of read commands increases,
wherein the updated scheduling ratio decreases as the number of write commands or the write amplification factor increases, and
wherein the updated scheduling ratio is generated based on the following equation:

A

B
·
C

·
D

=
E

wherein:

A is the number of read commands received during the respective period of time,
B is the number of write commands received during the respective period of time,
C is the 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.

2. The method of claim 1 ,
wherein the updated scheduling ratio decreases as the number of write commands increases, and
wherein the updated scheduling ratio decreases as the write amplification factor increases.

3. The method of claim 2 ,
wherein the scheduling ratio factor depends on the scheduling ratio, the number of read commands, the number of write commands, and the write amplification factor, and
wherein the updated scheduling ratio increases as the scheduling ratio factor increases.

4. The method of claim 1 , wherein the two or more different command types include a write command and a command that is not the write command.

5. The method of claim 1 , further comprising:
maintaining, in memory, a log of the number of read commands and the number of write commands received from a host device during the respective period of time.

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

7. The method of claim 1 , wherein the write amplification factor of the storage device is determined based on an amount of over provisioning of the storage device.

8. A storage device, comprising:
non-volatile memory; and
one or more controllers configured to cause:
allocating a high priority command to a high priority queue;
allocating a low priority command to a low priority queue; wherein the low priority queue is configured to contain two or more different command types;
executing commands from the high priority queue and the low priority queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the high priority queue to be processed and a number of one or more commands from the low priority queue to be processed;
determining a write amplification factor of the storage device;
determining a number of read commands and a number of write commands received during a respective period of time; and
executing additional commands from the high priority queue and the low priority queue based on an updated scheduling ratio,
wherein the updated scheduling ratio increases as the number of read commands increases,
wherein the updated scheduling ratio decreases as the number of write commands or the write amplification factor increases, and
wherein the updated scheduling ratio is generated based on the following equation:

A

B
·
C

·
D

=
E

wherein:
A is the number of read commands received during the respective period of time,
B is the number of write commands received during the respective period of time,
C is the 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.

9. The storage device of claim 8 ,
wherein the updated scheduling ratio decreases as the number of write commands increases, and
wherein the updated scheduling ratio decreases as the write amplification factor increases.

10. The storage device of claim 9 ,
wherein the scheduling ratio factor depends on the scheduling ratio, the number of read commands, the number of write commands, and the write amplification factor, and
wherein the updated scheduling ratio increases as the scheduling ratio factor increases.

11. The storage device of claim 8 , wherein the two or more different command types include a write command and a command that is not the write command.

12. The storage device of claim 8 , further comprising:
maintaining, in memory, a log of the number of read commands and the number of write commands received from a host device during the respective period of time.

13. The storage device of claim 8 , wherein the write amplification factor of the storage device is determined based on a number of program/erase cycle performed on the storage device.

14. The storage device of claim 8 , wherein the write amplification factor of the storage device is determined based on an amount of over provisioning of the storage device.

15. An apparatus, comprising:
means for allocating a high priority command to a high priority queue;
means for allocating a low priority command to a low priority queue; wherein the low priority queue is configured to contain two or more different command types;
means for executing commands from the high priority queue and the low priority queue based on a scheduling ratio, wherein the scheduling ratio indicates a ratio between a number of one or more commands from the high priority queue to be processed and a number of one or more commands from the low priority queue to be processed;
means for determining a write amplification factor of the apparatus;
means for determining a number of read commands and a number of write commands received during a respective period of time;
means for executing additional commands from the high priority queue and the low priority queue based on an updated scheduling ratio; and
means for generating the updated scheduling ratio based on the following equation:

A

Assignees

• Western Digital Tech Inc

Inventors

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

Classifications

• G06F9/4881 Primary

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

• H04W74/002

  Transmission of channel access control information · CPC title

• G06F2209/484

  Precedence · CPC title

• G06F13/374 Primary

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

• G06F13/26

  with priority control · CPC title