Method and apparatus for sequential stream I/O processing

Patent metadata

Field	Value
Publication number	US-9684455-B2
Application number	US-201414456328-A
Country	US
Kind code	B2
Filing date	Aug 11, 2014
Priority date	Mar 4, 2013
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

A method for providing efficient processing for many concurrent streams of sequential I/O requests is provided. In response to receiving an I/O request, the method includes determining if the I/O request corresponds to an active stream. If the request corresponds to an active stream, then the method includes updating an existing active list entry of an active list corresponding to the active stream, and if the I/O request does not correspond to an active stream, then instead converting and configuring an inactive list entry of an inactive list into a new active list entry. The inactive list stores available but unallocated resources, and the active list stores allocated resources. The active list includes a head at one end of the active list and a tail at an opposite end. The active list head corresponds to a most recently used entry, and the tail corresponds to a least recently used entry.

First claim

We claim:

1. A method comprising:
in response to a storage controller receiving a host I/O request;
determining, by the storage controller, if the host I/O request corresponds to an active stream;
in response to the host I/O request corresponding to an active stream:
updating, by the storage controller, an existing active list entry corresponding to the active stream of an active list corresponding to one logically addressed storage volume; and
adjusting, by the storage controller, a move window corresponding to the existing active list entry, the move window being used to determine if stream window logical block address limits need to change; and

in response to the host I/O request not corresponding to an active stream:
converting, by the storage controller, an inactive list entry of an inactive list into a new active list entry of the active list; and
configuring the new active list entry,

the inactive list stores available but unallocated storage controller memory resources, the active list stores allocated storage controller memory resources and comprises an active list head at one end of the active list and an active list tail at an opposite end of the active list, the active list head corresponding to a most recently used active list entry and the active list tail corresponding to a least recently used active list entry.

2. The method of claim 1 , wherein determining if the host I/O request corresponds to an active stream comprises:
determining, by the storage controller, if the active list is empty;
in response to the active list is empty then the host I/O request does not correspond to an active stream; and
in response to the active list is not empty:
searching the active list entries beginning from the head of the active list;
identifying if an active list entry is within a stream window corresponding to the active list;
in response to an active list entry is within the stream window, the host I/O request corresponds to an active stream;
in response to an active list entry is not within the stream window, the host I/O request does not correspond to an active stream; and

repeating searching and identifying until either an active list entry within a stream window is identified or the entire active list is searched without identifying an active list entry within the stream window, wherein the stream window comprises an LBA range between a stream window upper LBA limit and a stream window lower LBA limit.

3. The method of claim 2 , wherein updating an existing active list entry of the active list corresponding to the active stream comprises:
removing, by the storage controller, the existing active list entry from the active list;
updating, by the storage controller, a time last hit corresponding to the existing active list entry, wherein the time last hit comprises a time stamp identifying when the host I/O request was received by the storage controller; and
placing, by the storage controller, the existing active list entry to the head of the active list.

4. The method of claim 3 , wherein the move window comprises an LBA range between a move window upper LBA limit and a move window lower LBA limit, wherein in response to the starting LBA of the host I/O request is outside the move window, the method further comprising:
adjusting, by the storage controller, the move window upper and lower LBA limits using a sequential stream window modifier in response to the starting LBA of the host I/O request is directly adjacent to the immediately previous I/O request to the same stream as the host I/O request; and
adjusting, by the storage controller, the move window upper and lower LBA limits using a semi-sequential stream window modifier in response to the starting LBA of the host I/O request is not directly adjacent to the immediately previous I/O request to the same stream as the host I/O request.

5. The method of claim 3 , wherein converting the inactive list entry of the inactive list into the new active list entry of the active list comprises:
determining, by the storage controller, if the inactive list is empty;
in response to determining the inactive list is empty then:
recycling, by the storage controller, one or more stale streams from the active list to the inactive list; and

in response to determining the inactive list is not empty then:
removing, by the storage controller, an inactive list entry from the inactive list.

6. The method of claim 5 , wherein recycling one or more stale streams from the active list to the inactive list comprises:
searching the active list entries beginning from the tail of the active list; and
determining if the difference between a current time and the time last hit is less than a stream recycle time for a current active list entry being searched;
in response to the difference between the current time and the time last hit is not less than the stream recycle time, then:
selecting a next most recent active list entry from the tail of the active list in response to there are more active list entries in the active list; and
repeating determining if the difference between the current time and the time last hit is less than the stream recycle time;

in response to the difference between the current time and the time last hit is less than the stream recycle time, then:
removing, by the storage controller, the current active list entry from the active list;
initializing the time last hit and the stream window for the current active list entry to zero; and
placing the current active list entry on the inactive list.

7. The method of claim 6 , further comprising:
maintaining, by the storage controller, an outstanding I/O count for each active list entry; and
for each active list entry:
incrementing, by the storage controller, the outstanding I/O count corresponding to the active list entry when the storage controller receives a host I/O request corresponding to the active list entry;
decrementing, by the storage controller, the outstanding I/O count corresponding to the active list entry in response to a host I/O request corresponding to the active list entry completing;
starting, by the storage controller, a burst timer corresponding to the active list entry when the outstanding I/O count transitions from one to zero; and
stopping, by the storage controller, the burst timer when the outstanding I/O count transitions from zero to one;
in response to stopping the burst timer:
storing the burst timer value in a time since last burst queue location identified by a time since last burst pointer; and
incrementing the time since last burst pointer to identify a next time since last burst queue location,

wherein the storage controller maintains a time since last burst queue and time since last burst pointer for each active list entry, wherein the time since last burst queues are circular queues with a predetermined number of locations.

8. The method of claim 7 , further comprising:
determining, by the storage controller, when a time since last burst queue is full,
wherein a time since last burst queue is full when each of the predetermined number of locations contains a nonzero time since last burst entry;
in response to a time since last burst queue is full:
calculating, by the storage controller, the stream recycle time based on an average of the time since last burst queue locations; and
saving, by the storage controller, the stream recycle time in a storage controller memory location.

9. The method of claim 8 , wherein the stream recycle time is a weighted average that comprises a greater weighting applied to more recent time since last burst values and a lesser weighting applied to less recent time since last burst values.

Assignees

• Dot Hill Systems Corp
• Seagate Technology Llc

Inventors

• Traut Zachary David
• Barrell Michael David

Classifications

• G06F12/0866

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F12/0862

  with prefetch · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/0659

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