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

• US 20060047902A1
• Filed: 08/24/2004
• Published: 03/02/2006
• Est. Priority Date: 08/24/2004
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Passerini, Ron
• Granted Patent: US 7,730,222 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• 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 plurality of I/O requests directed to at least a part of a logical unit of storage; and

a plurality of nodes arranged in a tree data structure, the nodes each being associated with non-overlapping address ranges relative to each other in the logical unit of storage, such that the tree data structure facilitates sequential processing of I/O requests directed to the same units of storage based on an order in which I/O requests directed to the same units of storage were received.

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 some of the nodes include pointers to operation sequences associated with corresponding I/O requests.

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

7. 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.

8. 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.

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

receiving a plurality of I/O requests directed to particular address ranges of 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 including non-overlapping address ranges associated with the at least partly overlapping address ranges of the I/O requests;

organizing the nodes into a tree data structure; and

processing the I/O requests based on the tree data structure.

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

11. The method of claim 9, wherein the tree data structure is a binary tree data structure.

12. The method of claim 9, wherein at least some of the nodes include pointers to operation sequences associated with corresponding I/O requests.

13. The method of claim 12, 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.

14. The method of claim 12, 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.

15. The method of claim 9, 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.

16. The method of claim 9, 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.

17. 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 including non-overlapping address ranges associated with the logical unit of storage;

organizing the nodes into a tree data structure; and

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

18. 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 including non-overlapping address ranges associated with the logical unit of storage and pointers to I/O requests associated with the non-overlapping address ranges; and

processing the I/O requests based on the binary tree data structure.

19. The method of claim 18, 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.

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