System and method of application aware efficient io scheduler

Patent metadata

Field	Value
Publication number	US-2017242596-A1
Application number	US-201615143238-A
Country	US
Kind code	A1
Filing date	Apr 29, 2016
Priority date	Feb 24, 2016
Publication date	Aug 24, 2017
Grant date	—

Abstract

An input output scheduler. The scheduler runs in user space and is associated with one core of a multi-core central processing unit. Applications submit input output commands to the scheduler, which queues the input output commands and submits them in batches to a mass storage device. The input output scheduler may include a plurality of command queues with different batching strategies configured to provide, e.g., different performance characteristics as measured, for example, by latency or input output throughput.

First claim

1 . A non-transitory computer-readable medium, having stored in it instructions that when executed by a computing device, cause the computing device to instantiate an input output (IO) scheduler for scheduling input from, and output to, a mass storage device, the scheduler comprising:
a first command queue; a second command queue; and an IO sequencer, the first command queue being configured to accumulate IO commands, the IO sequencer being configured to dispatch the accumulated IO commands of the first command queue to the mass storage device, when a number of IO commands in the first command queue reaches a first threshold, the scheduler being configured to run in user space on a core of a computer comprising a multi-core central processing unit, the second command queue being configured to accumulate IO commands, the IO sequencer being configured to dispatch the accumulated IO commands of the second command queue to the mass storage device, when a number of IO commands in the second command queue reaches a second threshold, wherein the scheduler is further configured:
to receive, from a first application, a first IO command and first storage performance priorities,
to place the first IO command in the first command queue when the first storage performance priorities prioritize low latency, and
to place the first IO command in the second command queue when the first storage performance priorities prioritize high throughput.

2 . (canceled)

3 . (canceled)

4 . (canceled)

5 . (canceled)

6 . The medium of claim 1 , further comprising a third command queue, wherein the scheduler is configured to place a first IO command received from the first application in the third command queue when
the first storage performance priorities prioritize completion of command execution before a respective command completion deadline.

7 . The medium of claim 6 , wherein the IO sequencer is further configured to dispatch, to the mass storage device:
a first IO command in the third command queue, and a second IO command in the third command queue, when:
the separation in time between:
a command completion deadline of the first IO command, and
a command completion deadline of the second IO command is less than a third threshold.

8 . A computer system, comprising:
a central processing unit comprising a first core; and a first mass storage device associated with the first core, the first core being configured to instantiate, in user space, a first input output (IO) scheduler for scheduling input from, and output to, the first mass storage device, the first IO scheduler comprising:
a first command queue;
a second command queue; and
an IO sequencer,
the first command queue being configured to accumulate IO commands, the IO sequencer being configured to dispatch the accumulated IO commands of the first command queue to the first mass storage device, when a number of IO commands in the first command queue reaches a first threshold,
the second command queue being configured to accumulate IO commands,
the IO sequencer being configured to dispatch the accumulated IO commands of the second command queue to the first mass storage device, when a number of IO commands in the second command queue reaches a second threshold,
wherein the scheduler is further configured:
to receive, from a first application, a first IO command and first storage performance priorities,
to place the first IO command in the first command queue when the first storage performance priorities prioritize low latency, and
to place the first IO command in the second command queue when the first storage performance priorities prioritize high throughput.

9 . (canceled)

10 . (Canceled)

11 . The system of claim 8 , wherein the central processing unit further comprises:
a second core; and a second mass storage device associated with the second core, wherein the second core is configured to instantiate, in user space, a second IO scheduler for scheduling input from, and output to, the second mass storage device.

12 . The system of claim 11 ,
wherein the first core and the second core are configured to instantiate, in user space, a lockless message queue having a first end and a second end, and wherein:
the first IO scheduler is configured
to enqueue a first request object on the first end of the message queue, and
to enqueue a second request object on the first end of the message queue without waiting for a response to the first request object, and

the second IO scheduler is configured
to dequeue the first request object from the first end of the message queue,
to execute the first request object,
to store, in the first request object, a result from executing the first request object, and
to enqueue the first request object on the second end of the message queue.

13 . The system of claim 12 , wherein the first IO scheduler is further configured to dequeue the first request object from the second end of the message queue.

14 . (canceled)

15 . (canceled)

16 . The system of claim 12 , wherein the first IO scheduler further comprises a third command queue, wherein the first IO scheduler is further configured to place the first IO command received from the first application in the third command queue when
the first storage performance priorities prioritize completion of command execution before a respective command completion deadline, wherein the IO sequencer is further configured to dispatch, to the first mass storage device: a first IO command in the third command queue, and a second IO command in the third command queue, when:
a command completion deadline of the first IO command is the same as
a command completion deadline of the second IO command.

17 . A method for scheduling input and output, the method comprising:
storing IO commands in a first command queue; dispatching the IO commands stored in the first command queue to a mass storage device, when a number of IO commands in the first command queue reaches a first threshold; storing IO commands in a second command queue; dispatching the IO commands stored in the second command queue to the mass storage device, when a number of IO commands in the second command queue reaches a second threshold; receiving:
from a first application having a first service level agreement, IO commands and first storage performance priorities associated with the first service level agreement, and
from a second application having a second service level agreement, IO commands and second storage performance priorities associated with the second service level agreement; and
storing a first received IO command of the IO commands
in the first command queue when storage performance priorities received with the first received IO command prioritize low latency, and
in the second command queue when storage performance priorities received with the first received IO command prioritize high throughput.

18 . (canceled)

19 . (canceled)

20 . The method of claim 17 , further comprising storing the first received IO command in a third command queue when storage performance priorities received with the first received IO command prioritize completion of command execution before a respective command completion deadline.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Liu Fei
• Ki Yang Seok
• Pudipeddi Aakanksha

Classifications

• G06F3/0613 Primary

  in relation to throughput · CPC title

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F13/161

  with latency improvement · CPC title

• G06F3/0683

  Plurality of storage devices · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title