Processing storage-related I/O requests using binary tree data structures

• US 7,730,222 B2
• Filed: 08/24/2004
• Issued: 06/01/2010
• Est. Priority Date: 08/24/2004
• Status: Expired due to Fees

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating System
• Inventors: Passerini, Ron
• Primary Examiner(s): Tsai; Henry W. H.
• Assistant Examiner(s): Sun; Michael
• Application Number:
  US10/924,582
• Publication Number:
  US 20060047902A1
• Time in Patent Office: 2,107 Days
• Field of Search: 710/5
• US Class Current: 710/5
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The disclosed technology can be used to develop systems and perform methods that receive and process I/O requests directed to at least a part of a logical unit of storage. The I/O requests can be associated with different times corresponding to when such I/O requests were received. Nodes that include non-overlapping address ranges associated with the logical unit of storage can be formed in response to receiving the I/O requests and such nodes can be subsequently organized into a tree data structure. The tree data structure can serve as a basis for determining address overlap, for example to enable processing a first operation associated with a first one of the I/O requests in accordance with the first I/O request'"'"'s receipt time, while one or more other operations associated with a different I/O request may be processed irrespective of that different I/O request'"'"'s receipt time. This can be useful in a system in system operations are improved by easy access to information about whether pending I/O requests are directed to overlapping units of storage.

Claims

1. A system for processing I/O requests, the system comprising:

a logical unit of storage to receive a plurality of I/O requests directed to at least a part of the logical unit of storage; and

a plurality of nodes arranged in a tree data structure, each node in the plurality of nodes being associated with a non-overlapping address range in the logical unit of storage, such that the tree data structure facilitates sequential processing of one or more of the plurality of I/O requests directed to the logical unit of storage based on an order in which the one or more I/O requests directed to the logical unit of storage were received, the plurality of I/O requests processed through the plurality of nodes forwarded to the associated non-overlapping address ranges in the logical unit of storage, wherein at least some of the nodes include pointers to operation sequences associated with corresponding I/O requests.

2. The system of claim 1, wherein the tree data structure is a binary tree data structure.

3. The system of claim 1, wherein at least one of the non-overlapping address ranges is associated with address ranges specified by at least two of the I/O requests.

4. The system of claim 1, wherein at least one of the non-overlapping address ranges is associated with an address range specified by one of the I/O requests.

5. The system of claim 1, wherein at least one of the nodes is removed from the tree data structure in response to completing operation sequences associated therewith.

6. The system of claim 1, wherein the tree data structure is expandable to include a new node, in response to receiving a new I/O request associated with a new address range that does not overlap the address ranges associated with other nodes in the tree data structure.

7. The system of claim 1, wherein at least one of the nodes in the tree data structure is split into at least two other nodes in response to receiving a new I/O request associated with a new address range that at least partially overlaps at least one of the address ranges associated with at least one node in the tree data structure.

8. A method of processing I/O requests, the method comprising:

receiving a plurality of I/O requests directed to particular address ranges in a logical unit of storage, the address ranges of at least some of the I/O requests at least partly overlapping;

forming a plurality of nodes associated with the received I/O requests, at least some of the nodes associated with non-overlapping address ranges in the logical unit of storage, wherein at least some of the nodes include pointers to operation sequences associated with corresponding I/O requests;

organizing the nodes into a tree data structure;

processing the received I/O requests based on the tree data structure; and

forwarding the received I/O requests to the associated address ranges in the logical unit of storage after processing.

9. The method of claim 8, wherein the I/O requests are further processed based on an order in which the I/O requests were received.

10. The method of claim 8, wherein the tree data structure is a binary tree data structure.

11. The method of claim 8, further comprising;

processing a first operation in a selected one of the operation sequences in accordance with an order in which the I/O requests were received; and

processing remaining operations in the selected operation sequence without regard to the order in which the I/O requests were received.

12. The method of claim 8, further comprising:

removing at least one of the nodes from the tree data structure in response to completing operation sequences associated with corresponding I/O requests.

13. The method of claim 8, further comprising:

receiving a new I/O request associated with a new address range that does not overlap the address ranges associated with other nodes in the tree data structure;

forming a new node associated with the new address range; and

expanding the tree data structure to include the new node.

14. The method of claim 8, further comprising:

receiving a new I/O request associated with a new address range that at least partially overlaps at least one of the address ranges associated with at least one node in the tree data structure;

splitting the at least one node in the tree data structure into at least two other nodes, the at least two other nodes including updated address ranges that do not overlap with the address ranges of other nodes in the tree data structure; and

expanding the tree data structure to include the at least two other nodes.

15. A method of processing I/O requests, the method comprising:

receiving a plurality of I/O requests directed to at least a part of a logical unit of storage, the I/O requests being associated with times at which such requests were received, wherein each of the receipt times of the I/O requests differ;

forming a plurality of nodes associated with the received I/O requests, at least some of the nodes associated with non-overlapping address ranges in the logical unit of storage, wherein at least some of the nodes include pointers to operation sequences associated with corresponding I/O requests;

organizing the nodes into a tree data structure;

based on the tree data structure, processing at least a first operation associated with a first one of the received I/O requests in accordance with the first received I/O request'"'"'s receipt time and processing at least another operation associated with a different one of the received I/O requests irrespective of the different received I/O request'"'"'s receipt time; and

forwarding the received I/O requests to the associated address ranges in the logical unit of storage after processing.

16. A method of processing I/O requests, the method comprising:

receiving a plurality of I/O requests directed to at least a part of a logical unit of storage;

forming a plurality of nodes associated with the received I/O requests;

organizing the nodes into a binary tree data structure, at least some of the nodes associated with non-overlapping address ranges in the logical unit of storage and pointers to received I/O requests associated with the non-overlapping address ranges wherein at least some of the nodes further include pointers to operations within operation sequences associated with at least some of the received I/O requests;

processing the received I/O requests based on the binary tree data structure; and

forwarding the received I/O requests to the associated address ranges in the logical unit of storage after processing.

17. The method of claim 16, wherein the operations and operation sequences are directed at data contained within at least one of the non-overlapping address ranges.