Method and system for input/output (IO) scheduling in a storage system

Patent metadata

Field	Value
Publication number	US-10216660-B1
Application number	US-201715649580-A
Country	US
Kind code	B1
Filing date	Jul 13, 2017
Priority date	Jul 13, 2017
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

According to some embodiment, a backup storage system receives a plurality of input/output (IO) requests at the storage system. The IO requests include random IO requests and sequential IO requests. The storage system determines whether there is a pending random IO request from the plurality of IO requests. In response to determining that there is a pending random IO request, the storage system determines whether a total latency of the sequential IO requests exceeds a predicted latency of the pending random IO request. The storage system services the pending random IO request in response to determining that the total latency of the sequential IO requests exceeds the predicted latency of the pending random IO request.

First claim

What is claimed is:

1. A computer-implemented method for input/output (IO) scheduling for a storage system, the method comprising:
receiving a plurality of input/output (IO) requests at the storage system, the IO requests including random IO requests and sequential IO requests;
determining whether there is a pending random IO request from the plurality of IO requests;
in response to determining that there is a pending random IO request, determining whether a total latency of the sequential IO requests exceeds a predicted latency of the pending random IO request; and
servicing the pending random IO request in response to determining that the total latency of the sequential IO requests exceeds the predicted latency of the pending random IO request.

2. The method of claim 1 , further comprising for each of the IO requests,
determining whether the IO request is a sequential IO request or a random IO request;
storing the IO request in an entry of a first data structure in response to determining that the IO request is a random IO request; and
storing the IO request in an entry of a second data structure in response to determining that the IO request is a sequential IO request.

3. The method of claim 1 , further comprising servicing the random IO requests and the sequential IO request(s) at an equal rate in response to determining that the total latency of the sequential IO requests does not exceed the predicted latency of the pending random IO request.

4. The method of claim 2 , wherein the pending random IO request is stored in a head entry of the first data structure.

5. The method of claim 1 , further comprising computing the total latency of the sequential IO requests based on seek time of one or more storage devices in the storage system.

6. The method of claim 1 , further comprising associating a predicted latency with each of the random IO requests.

7. The method of claim 1 , wherein the predicted latency of the pending random IO request is extracted from the pending random IO request.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for, the operations comprising:
receiving a plurality of input/output (IO) requests at the storage system, the IO requests including random IO requests and sequential IO requests;
determining whether there is a pending random IO request from the plurality of IO requests;
in response to determining that there is a pending random IO request, determining whether a total latency of the sequential IO requests exceeds a predicted latency of the pending random IO request; and
servicing the pending random IO request in response to determining that the total latency of the sequential IO requests exceeds the predicted latency of the pending random IO request.

9. The non-transitory machine-readable medium of claim 8 , wherein the operations further comprise:
for each of the IO requests,
determining whether the IO request is a sequential IO request or a random IO request;
storing the IO request in an entry of a first data structure in response to determining that the IO request is a random IO request; and
storing the IO request in an entry of a second data structure in response to determining that the IO request is a sequential IO request.

10. The non-transitory machine-readable medium of claim 8 , wherein the operations further comprise servicing the random IO requests and the sequential IO request(s) at an equal rate in response to determining that the total latency of the sequential IO requests does not exceed the predicted latency of the pending random IO request.

11. The non-transitory machine-readable medium of claim 9 , wherein the pending random IO request is stored in a head entry of the first data structure.

12. The non-transitory machine-readable medium of claim 8 , wherein the operations further comprise computing the total latency of the sequential IO requests based on seek time of one or more storage devices in the storage system.

13. The non-transitory machine-readable medium of claim 8 , wherein the operations further comprise associating a predicted latency with each of the random IO requests.

14. The non-transitory machine-readable medium of claim 8 , wherein the predicted latency of the pending random IO request is extracted from the pending random IO request.

15. A data processing system, comprising:
a processor; and
a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations comprising:
receiving a plurality of input/output (IO) requests at the storage system, the IO requests including random IO requests and sequential IO requests;
determining whether there is a pending random IO request from the plurality of IO requests;
in response to determining that there is a pending random IO request, determining whether a total latency of the sequential IO requests exceeds a predicted latency of the pending random IO request; and
servicing the pending random IO request in response to determining that the total latency of the sequential IO requests exceeds the predicted latency of the pending random IO request.

16. The data processing system of claim 15 , wherein the operations further comprise:
for each of the IO requests,
determining whether the IO request is a sequential IO request or a random IO request;
storing the IO request in an entry of a first data structure in response to determining that the IO request is a random IO request; and
storing the IO request in an entry of a second data structure in response to determining that the IO request is a sequential IO request.

17. The data processing system of claim 15 , wherein the operations further comprise servicing the random IO requests and the sequential IO request(s) at an equal rate in response to determining that the total latency of the sequential IO requests does not exceed the predicted latency of the pending random IO request.

18. The data processing system of claim 16 , wherein the pending random IO request is stored in a head entry of the first data structure.

19. The data processing system of claim 15 , wherein the operations further comprise computing the total latency of the sequential IO requests based on seek time of one or more storage devices in the storage system.

20. The data processing system of claim 15 , wherein the operations further comprise associating a predicted latency with each of the random IO requests.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Jonnala Uday Kiran
• Thomas Pradeep

Classifications

• G06F3/0659

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

• G06F13/20 Primary

  for access to input/output bus · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/0683

  Plurality of storage devices · CPC title