Concurrent data recall in a hierarchical storage environment using plural queues

• US 7,343,446 B2
• Filed: 03/16/2005
• Issued: 03/11/2008
• Est. Priority Date: 02/15/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pudipeddi, Ravisankar, Kalach, Ran
• Primary Examiner(s): Breene; John
• Assistant Examiner(s): EHICHIOYA, IRETE FRED
• Application Number:
  US11/083,273
• Publication Number:
  US 20050165820A1
• Time in Patent Office: 1,091 Days
• Field of Search: 707/1, 707/8, 707/10, 707/204, 710/6, 711/111, 711/112, 711/154, 711/162, 711/168
• US Class Current: 711/112
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A technique for recalling data objects stored on media. A queue is created for each medium on which data objects are located, where each request to recall a data object is placed on the queue corresponding to the medium on which the data object is located. A queue is “active” when its corresponding medium is mounted and being used for recall; otherwise the queue is “non-active.” A thread is created for each active queue, where the thread retrieves from a medium the requested items on the active queue. When plural drives are available for mounting and reading media, plural queues may be active concurrently, so that the plural queues'"'"' respective threads may recall items from the plural media in parallel. Preferably, the requests on each queue are organized in an order such that the offset locations of the requested items form two monotonically increasing sequences.

Claims

1. A computer-readable storage medium encoded with computer-executable instructions to perform a method of recalling data objects stored on a plurality of media, the method comprising:

receiving a plurality of requests to recall data objects, each data object being located on a particular one of said plurality of media;

creating a plurality of queues, wherein each one of said queues corresponds to one of said media;

placing said requests on the created queues, wherein each request is placed on the queue corresponding to the medium on which the requested data object is located and with respect to an order, wherein the order of the requests on the queue is determined by respective offsets into said medium at which the corresponding data objects are located;

activating a first of said queues, said first queue being associated with a first of said plurality of media; and

retrieving, from said first medium, the data objects requested on the first queue.

2. The computer-readable storage medium of claim 1, wherein each queued request indicates the offset from a predetermined location on a medium at which the requested data object is located, and wherein said placing act comprises:

organizing the requests on each queue in a first and a second sequence, each sequence comprising a set of requests whose offsets are monotonically increasing within the respective sequence.

3. The computer-readable storage medium of claim 1, wherein the method further comprises:

activating a second of said queues, said second queue being associated with a second of said plurality of media, the second medium being different from said first medium; and

retrieving, from said second medium, the data objects requested on the second queue, the retrieval occurring at least in part concurrently with the retrieval of data objects from the first medium.

4. The computer-readable storage medium of claim 1, wherein each of said queues comprises a linked list of requests.

5. The computer-readable storage medium of claim 1, wherein the method further comprises querying a database to determine the locations of the requested data objects.

6. The computer-readable storage medium of claim 5, wherein each location provided by said database comprises a media identifier and an offset into the corresponding medium.

7. The computer-readable storage medium of claim 1, wherein creating a plurality of queues comprises timestamping each of the created queues, and wherein the act of activating a first of said plurality of queues comprises selecting a queue to be activated based on the timestamps of the respective queues.

8. The computer-readable storage medium of claim 1, the method being performed in a multi-threaded environment wherein plural threads execute concurrently, the method further comprising:

acquiring a lock prior to performing an action selected from a group consisting of;

placing a request on a queue; and

changing a queue from a non-active state to an active state;

said lock being acquirable by only one of said threads at a given time; and

releasing said lock subsequent to performing an action in said group.

9. The computer-readable storage medium of claim 1, wherein the method is performed in a computing environment comprising a hard disk, the method farther comprising:

determining that said data objects are not located on said hard disk.

10. The computer-readable storage medium of claim 1, wherein each of said media is capable of being mounted on any one of a plurality of drives, and wherein each medium corresponds to a particular one of the queues regardless of which drive the medium is mounted on.

11. A computer-readable storage medium encoded with computer-executable instructions to perform a method of scheduling requests to recall data objects from a medium, said medium being mounted on a drive, said drive having a reading head, the method comprising:

receiving a new request to recall a data object from said medium, said data object being located at a first offset along said medium;

identifying a queue comprising a plurality of requests to recall data from said medium, said requests having an order, each of said requests corresponding to a particular data object stored on said medium and indicating an offset into said medium at which the corresponding data object is located, said requests forming first and second sequences, said first sequence preceding said second sequence in said queue with respect to said order, wherein the offsets of the requests within said first sequence are a maximally monotonically increasing series;

determining a location of said reading head along said medium;

determining that the location of said reading head is beyond said first offset;

inserting said new request into said queue into a position that, with respect to said order, is subsequent to said first sequence.

12. The computer-readable storage medium of claim 11, wherein the offsets of the requests within said second sequence are a maximally monotonically increasing series.

13. The computer-readable storage medium of claim 12, wherein the position in said second sequence in which said new request is inserted is based on said first offset, such that the monotonically increasing nature of said second sequence is preserved following the insertion.

14. The computer-readable storage medium of claim 11, wherein the method further comprises:

selecting, from among a plurality of queues, a particular queue into which to insert said new request, wherein each one of said plurality of queues corresponds to a different medium, the selection being based on the medium on which the data object is located.

15. The computer-readable storage medium of claim 11, wherein said queue is identified from among a plurality of queues, and wherein each one of said plurality of queues has a timestamp indicating its creation time.

16. A system for retrieving data objects from a plurality of media comprising:

a queuing module which creates a plurality of queues corresponding to said plurality of media, there being one queue for each one of said plurality of media, said queuing module receiving requests to retrieve data objects from said plurality of media and queuing each of said requests on the queue corresponding to the medium on which the requested data object is located, said queuing module generating and storing, for each queue, a timestamp indicating a time at which the queue corresponding to the timestamp is created;

an activation module which selects queues for activation and activates the selected queues; and

a retrieval module which retrieves the data objects on one of the selected queues from the corresponding medium in an order in which the data objects are located on the queue.

17. The system of claim 16, further comprising:

a hard disk;

a file system which manages files on said hard disk, which stores information indicating which of said files have been migrated to said media, and which issues a request to said queuing module for requested files that have been migrated to said media.

18. The system of claim 16, wherein each requested data object is located at an offset into the medium on which the data object is located, and wherein said queuing module includes logic which maintains the requests on each of said plurality of queues in first and second sequences, the offsets of the data objects requested in each of said first and second sequences comprising a maximally monotonically increasing series.

19. The system of claim 16, wherein each of said media is capable of being mounted on any one of a plurality of drives, and wherein each medium corresponds to a particular one of the queues regardless of which drive the medium is mounted on.

20. The system of claim 16, wherein each of the queues corresponds to a particular one of the plurality of media, wherein each of the media is capable of being mounted on any one of a plurality of drives, and wherein each medium corresponds to a particular one of the queues regardless of which drive the medium is mounted on.