Queueing storage operations

Patent metadata

Field	Value
Publication number	US-12242896-B2
Application number	US-202318400952-A
Country	US
Kind code	B2
Filing date	Dec 29, 2023
Priority date	Sep 7, 2016
Publication date	Mar 4, 2025
Grant date	Mar 4, 2025

Abstract

A method of scheduling input/output operations for a storage system including determining a deadline for a storage operation, wherein the deadline is dependent on an expected latency of the storage operation; adding the storage operation to a queue of storage operations; and reordering the queue dependent upon the deadline of the storage operation and one or more deadlines of one or more storage operations in the queue of storage operations.

First claim

What is claimed is:

1. A method comprising:
determining, for a storage operation in a queue that includes one or more other storage operations, a deadline based on expected latency, wherein the storage operation and the one or more other storage operations are associated with a same entity; and
reordering the queue based on the determined deadline for the storage operation and one or more other deadlines for the one or more other storage operations in the queue.

2. The method of claim 1 , wherein determining a deadline comprises combining the expected latency of the storage operation and a current time.

3. The method of claim 2 , wherein the current time is a proxy for time.

4. The method of claim 1 , wherein the queue of storage operations comprises storage operations of a single storage operation type.

5. The method of claim 1 , wherein the queue of storage operations comprises storage operations for a single storage die of a storage device.

6. The method of claim 1 , wherein the queue of storage operations comprises storage operations for a single communication channel of a storage device.

7. The method of claim 1 , wherein the queue is reordered in an ascending order of deadlines for the storage operation and the one or more other storage operations.

8. A non-transitory computer readable storage medium storing instructions, which when executed, cause a processing device of a storage controller to:
determine, for a storage operation in a queue that includes one or more other storage operations, a deadline based on expected latency, wherein the storage operation and the one or more other storage operations are associated with a same entity; and
reorder the queue based on the determined deadline for the storage operation and one or more other deadlines for the one or more other storage operations in the queue.

9. The non-transitory computer readable storage medium of claim 8 , wherein determining a deadline comprises combining the expected latency of the storage operation and a current time.

10. The non-transitory computer readable storage medium of claim 9 , wherein the current time is a proxy for time.

11. The non-transitory computer readable storage medium of claim 8 , wherein the queue of storage operations comprises storage operations of a single storage operation type.

12. The non-transitory computer readable storage medium of claim 8 , wherein the queue of storage operations comprises storage operations for a single storage die of a storage device.

13. The non-transitory computer readable storage medium of claim 8 , wherein the queue of storage operations comprises storage operations for a single communication channel of a storage device.

14. The non-transitory computer readable storage medium of claim 8 , wherein the queue is reordered in an ascending order of deadlines for the storage operation and the one or more other storage operations.

15. A storage system comprising:
a plurality of storage devices; and
a storage controller operatively coupled to the storage devices, the storage controller comprising a processing device, the processing device configured to:
determine, for a storage operation in a queue that includes one or more other storage operations, a deadline based on expected latency, wherein the storage operation and the one or more other storage operations are associated with a same entity y; and
reorder the queue based on the determined deadline for the storage operation and one or more other deadlines for the one or more other storage operations in the queue.

16. The storage system of claim 15 , wherein determining a deadline comprises combining the expected latency of the storage operation and a current time.

17. The storage system of claim 16 , wherein the current time is a proxy for time.

18. The storage system of claim 15 , wherein the queue of storage operations comprises storage operations of a single storage operation type.

19. The storage system of claim 15 , wherein the queue of storage operations comprises storage operations for a single storage die of a storage device.

20. The storage system of claim 15 , wherein the queue is reordered in an ascending order of deadlines for the storage operation and the one or more other storage operations.

Assignees

• Pure Storage Inc

Inventors

• Wang Vincent
• Fay Mark
• He Jun
• Fan Renjie
• Vijayasankar Kiron
• Frandzel Yuval

Classifications

• G06F13/1642

  with request queuing · CPC title

• G06F13/16 Primary

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06F9/4887

  involving deadlines, e.g. rate based, periodic · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title