Multi-level time decay storage queue

Patent metadata

Field	Value
Publication number	US-10613998-B2
Application number	US-201816049064-A
Country	US
Kind code	B2
Filing date	Jul 30, 2018
Priority date	Jul 30, 2018
Publication date	Apr 7, 2020
Grant date	Apr 7, 2020

Abstract

Techniques for processing I/O operations may include: receiving an I/O having an associated expected execution time (EET) and I/O service level; selecting, in accordance with the EET and service level of the I/O, a first I/O queue from multiple pending I/O queues; inserting the I/O into the first I/O queue; and performing I/O shifting. I/O shifting may include shifting I/Os from one pending I/O queue to another that is ranked immediately higher than the one pending I/O queue. The multiple I/O queues may be ranked from a highest priority queue to a lowest priority queue. I/O shifting may shift I/Os from the highest priority queue to execution and shifting I/Os from another queue into the highest priority queue. I/O shifting is subject to remaining credits available of the multiple I/O queues and time distance between source and target queues.

First claim

What is claimed is:

1. A method of processing input/output (I/O) operations comprising:
receiving, using a processor, an I/O operation having an associated expected execution time (EET) and an I/O service level;
selecting, using a processor and in accordance with the EET and the service level of the I/O operation, a first queue of a plurality of pending I/O operation queues, wherein the plurality of pending I/O operation queues has a ranking from a highest priority queue of the plurality of pending I/O operation queues to a lowest priority queue of the plurality of pending I/O operation queues;
responsive to said selecting, inserting, using a processor, the I/O operation into the first queue; and
performing, using a processor, I/O operation shifting for at least one of the plurality of pending I/O operation queues, wherein said I/O operation shifting for the at least one pending I/O operation queue includes shifting one or more I/O operations from the at least one pending I/O operation queue to another one of the plurality of pending I/O operation queues that is ranked immediately higher than the at least one pending I/O operation queue, wherein each queue of the plurality of pending I/O operation queues is associated with a different maximum time to expiry (max TTE) denoting a maximum wait time before which I/O operations of said each queue are scheduled for execution or servicing, and wherein said I/O operation shifting includes performing I/O operation shifting for a particular queue of the at least one pending I/O operation queues responsive to a timer associated with said particular queue reaching a specified maximum value associated with said particular queue, wherein the timer indicates an amount of elapsed time, and wherein the specified maximum value of the timer for the particular queue is a mathematical difference between a max TTE for the particular queue and another max TTE of another particular queue of the plurality of pending I/O operation queues, wherein the another particular queue is ranked in said ranking immediately higher than the particular queue in said ranking.

2. The method of claim 1 , wherein the I/O operation performs a data access operation with respect to data of a target logical device having a service level objective, and wherein the I/O service level is determined as the service level objective of the target logical device.

3. The method of claim 2 , wherein each queue of the plurality of pending I/O operation queues has an amount of remaining credits (RC) of said each queue available for consumption, and wherein each queue of the plurality of pending I/O operation queues has a current TTE (time to expiry) that decreases over time based on elapsed time, and wherein responsive to the highest priority queue having an associated current TTE that reaches zero, each of a plurality of current TTEs corresponding to a different one of the plurality of pending I/O operation queues is initialized to a particular max TTE associated with the different one of the plurality of pending I/O operation queues.

4. The method of claim 3 , wherein said selecting includes:
selecting an initial queue of the plurality of pending I/O operation queues in accordance with the service level objective and the max TTE associated with the initial queue;
determining whether the initial queue has an associated RC that is greater than or equal to the EET of the I/O operation and an associated current TTE that is greater than or equal to the EET of the I/O operation; and
if it is determined the initial queue does have an associated RC that is greater than or equal to the EET of the I/O operation and an associated current TTE that is greater than or equal to the EET of the I/O operation, determining the initial queue as the first queue wherein said inserting inserts the I/O operation into the initial queue and decreasing the associated RC of the initial queue in accordance with the EET of the I/O operation.

5. The method of claim 4 , further comprising:
if it is determined the initial queue does not have an associated RC that is greater than or equal to the EET of the I/O operation and an associated current TTE that is greater than or equal to the EET of the I/O operation, traversing remaining queues of the plurality of pending I/O operation queues in accordance with the ranking of the plurality of pending I/O operation queues to determine the first queue having an associated RC that is greater than or equal to the EET of the I/O operation and an associated current TTE that is greater than or equal to the EET of the I/O operation; and
decreasing the RC of the first queue in accordance with the EET of the I/O operation inserted into the first queue.

6. The method of claim 5 , wherein said performing I/O operation shifting, includes;
shifting one or more I/O operations from the highest priority queue of the plurality of pending I/O operation queues to one or more threads that execute the one or more I/O operations from the highest priority queue; and
for each of the one or more I/O operations shifted out of the highest priority queue, decreasing the RC of the highest priority queue in accordance with one or more EETs respectively associated with the one or more I/O operations shifted out of the highest priority queue.

7. The method of claim 6 , wherein a sum of the one or more EETs associated with the one or more I/O operations shifted out of the highest priority queue does not exceed a maximum the max TTE value of the highest priority queue.

8. The method of claim 6 , wherein a second queue of the plurality of pending I/O operation queues is ranked immediately lower than the highest priority queue in accordance with the ranking.

9. The method of claim 8 , wherein said performing I/O operation shifting includes:
shifting one or more I/O operations from the second queue to the highest priority queue; and
for each I/O operation of the one or more I/O operations shifted out of the second queue and into the highest priority queue, decreasing the RC of the second queue in accordance with one or more EETs respectively associated with the one or more I/O operations shifted out of the second queue and increasing the RC of the highest priority queue in accordance with the one or more EETs respectively associated with the one or more I/O operations shifted out of the second queue.

10. The method of claim 9 , wherein a distance denotes a time difference between a first max TTE of the second queue and a second max TTE of the highest priority queue.

11. The method of claim 10 , wherein a sum of the one or more EETs associated with the one or more I/O operations shifted out of the second queue does not exceed the distance.

12. The method of claim 10 , wherein a sum of the one or more EETs associated with the one or more I/O operations shifted out of the second queue does not exceed the RC of the highest priority queue.

13. A system comprising:
at least one processor; and
a memory comprising code stored thereon that, when executed, performs a method of processing input/output (I/O) operations, comprising:
receiving an I/O operation having an associated expected execution time (EET) and an I/O service level;
selecting, in accordance with the EET and the service level of the I/O operation, a first queue of a plurality of pending I/O operation queues, wherein the plurality of pending I/O operation queues has a ranking from a highest priority queue of the plurality of pending I/O operation queues to a lowest priority queue of the plurality of pending I/O operation queues;
responsive to said selecting, inserting the I/O operation into the first queue; and
performing I/O op

Assignees

• Emc Ip Holding Co Llc

Inventors

• Jung Jaeyoo
• Martin Owen
• Zhu Sichao
• Nuthakki Krishna Deepak
• Randolph Benjamin A

Classifications

• G06F13/1642 Primary

  with request queuing · CPC title

• G06F9/4818

  Priority circuits therefor · CPC title