Method and apparatus for prefetching data

• US 9,323,680 B1
• Filed: 09/28/2007
• Issued: 04/26/2016
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas US IP Holdings LLC
• Inventors: Salli, Tommi, Hobbs, Craig W., Van Rietschote, Hans
• Primary Examiner(s): Chea, Philip
• Assistant Examiner(s): Ma, Wing
• Application Number:
  US11/864,716
• Time in Patent Office: 3,133 Days
• Field of Search: 709/219, 709/231
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 2212/6028 Prefetching based on hints or prefetch instructions
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 65/61 for supporting one-way streaming services, e.g. Internet radio
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/752 adapting media to network capabilities
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04N 21/23406 involving management of server-side video buffer

Abstract

A method and apparatus for pre-fetching data to be streamed from a data storage to a user computer comprising the steps of determining information regarding a file type of a data file, establishing pre-fetch parameters in response to the information, accessing the data file and pre-fetching data blocks from the data file in accordance with the pre-fetch parameters is described.

Claims

1. A method for pre-fetching data, the method comprising:

ascertaining, using a computer, information regarding a data file, wherein the ascertaining

comprises

accessing a download speed of a network connection, a bit rate, a file size of the data file, and a length of play, and

computing a number of data blocks of the data file to buffer, wherein the computing is performed, at least in part, by multiplying the download speed with the length of play to calculate an intermediate result, and subtracting the intermediate result from the file size, and

the number of data blocks is greater than zero;

providing, using the computer, the information to an application programming interface (API);

in response to receiving the information, using the API to establish a first set of pre-fetch parameters, wherein

the first set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the first set of pre-fetch parameters is established in accordance with a first pre-fetch technique, and

the first pre-fetch technique is chosen from a plurality of pre-fetch techniques,

attempting to pre-fetch one or more of a plurality of data blocks via a network from the data file using the computer in accordance with the first set of pre-fetch parameters, wherein

the data file comprises the plurality of data blocks;

determining whether the attempting is successful;

in response to a determination that the attempting was unsuccessful, establishing a second set of pre-fetch parameters

wherein

the second set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the second set of pre-fetch parameters is not identical to the first set of pre-fetch parameters,

the second set of pre-fetch parameters is established in accordance with a second pre-fetch technique, and

the second pre-fetch technique is chosen from the plurality of pre-fetch techniques using the API; and

pre-fetching, using the computer, one or more of the plurality of data blocks from the data file, wherein

the pre-fetching is performed in accordance with either the first set of pre-fetch parameters or the second set of pre-fetch parameters, and

the pre-fetching is performed via the network;

accessing the data file using the computer, wherein

the data file is stored on a storage device, and

the storage device is communicatively coupled to the computer via a network; and

buffering the one or more pre-fetched data blocks, wherein the buffering comprises storing the one or more pre-fetched data blocks in a memory on the computer.

2. The method of claim 1, wherein the ascertaining the information regarding the data file further comprises

determining second information regarding a file type of the data file,

in response to a determination of the file type, determining one or more pointers of the data file, wherein

each of the one or more pointers points to one or more of the plurality of data blocks.

3. The method of claim 2, wherein

the ascertaining the information further comprises analyzing at least one of a content or a metadata of the data file, and

the pre-fetching the one or more data blocks in accordance with the first set of pre-fetch parameters comprises

accessing one or more respective data blocks of the one or more data blocks pointed to by each of the one or more pointers.

4. The method of claim 3, wherein the step of ascertaining the information further comprises determining a read access pattern for the file type.

5. The method of claim 1, wherein the step of ascertaining the information further comprises examining a usage pattern for the data file.

13. The method of claim 1, further comprising recording the failure of the first set of pre-fetch parameters such that subsequent accesses of the data file can be performed using an alternate set of pre-fetch parameters chosen in accordance with an alternate pre-fetch technique chosen from the plurality of pre-fetch techniques other than the first pre-fetch technique.

14. The method of claim 1, further comprising in response to the establishing of the first set of pre-fetch parameters, associating the first set of pre-fetch parameters with a file type of the data file;

and

in response to the establishing of the second set of pre-fetch parameters, disassociating the first set of pre-fetch parameters with the file type, and associating the second set of pre-fetch parameters with the file type.

15. The method of claim 14, further comprising:

determining, using the computer, other information regarding an other data file;

providing, using the computer, the other information to the application programming interface;

determining whether the other data file is of the file type; and

in response to a determination that the other data file is of the file type, establishing the second set of pre-fetch parameters using the application programming interface, wherein

the second set of pre-fetch parameters is established in accordance with the first pre-fetch technique.

16. The method of claim 1, further comprising playing the data file on the computer, wherein the playing comprises displaying a plurality of the pre-fetched data blocks;

retaining in the buffer, after the playing, a subset of the pre-fetched data blocks, wherein the subset is sufficient to scroll back a predetermined amount of time during the playing; and

discarding, after the playing, one or more of the pre-fetched data blocks that are not among the subset.

6. An apparatus for pre-fetching data, comprising:

a storage device comprising a data file, wherein

the data file comprises a plurality of data blocks;

a file system used by an application for accessing the data file via a network;

an application programming interface (API) for

receiving, via the network, information describing the data file, wherein the information comprises a download speed of a network connection, a bit rate, a file size of the data file, and a length of play, and

the information is used to compute a number of data blocks of the data file to buffer, wherein

the number is computed, at least in part, by multiplying the download speed with the length of play to calculate an intermediate result, and subtracting the intermediate result from the file size, and

the number is greater than zero;

in response to the receiving of the information, establishing a first set of pre-fetch parameters,

wherein

the first set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the first set of pre-fetch parameters is chosen in accordance with a first pre-fetch technique, and

the first pre-fetch technique is chosen from a plurality of pre-fetch techniques;

attempting to pre-fetch at least one of the plurality of data blocks via the network, wherein

the attempting comprises attempting to pre-fetch the at least one of the plurality of data blocks using the first set of pre-fetch parameters;

determining whether the attempting is successful;

in response to a determination that the attempting was unsuccessful, establishing a second set of pre-fetch parameters, wherein

the second set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the second set of pre-fetch parameters is not identical to the first set of pre-fetch parameters,

the second set of pre-fetch parameters is chosen in accordance with a second pre-fetch technique, and

the second pre-fetch technique is chosen from the plurality of pre-fetch techniques using the API;

a pre-fetching module, implemented by a processor, coupled to the file system for

pre-fetching, using the network, one or more of the plurality of data blocks from the data file in accordance with either the first set of pre-fetch parameters or the second set of pre-fetch parameters; and

a buffer for storing the one or more pre-fetched data blocks, wherein the application accesses the one or more pre-fetched data blocks from the buffer.

7. The apparatus of claim 6, wherein the pre-fetching module is further for

determining second information regarding a file type of the data file, and in response to a determination of the file type,

determining one or more pointers of the data file, wherein

each of the one or more pointers points to one or more respective data blocks of the plurality of data blocks.

8. The apparatus of claim 6, wherein the pre-fetching module processes instructions from the application for pre-fetching the data file through the API.

9. The apparatus of claim 7, wherein the pre-fetching module is further for analyzing at least one of a content or a metadata of the data file, and is configured to perform the pre-fetching of the data blocks in accordance with the second set of pre-fetch parameters by accessing one or more respective data blocks of the plurality of data blocks pointed to by each of the one or more pointers.

10. The apparatus of claim 6, wherein the pre-fetching module examines a usage pattern for the data file.

11. A system for pre-fetching data, comprising:

a user computer comprising;

an application for

requesting a data file stored on a storage device, wherein the data file comprises a plurality of data blocks, and the storage device is communicatively coupled to the user computer via a network,

determining information regarding the data file, wherein the information comprises a download speed of a network connection, a bit rate, file size of the data file, and a length of play,

computing a number of data blocks of the data file to buffer, wherein

the computing is performed, at least in part, by multiplying the download speed with the length of play to calculate an intermediate result, and subtracting the intermediate result from the file size, and

the number of data blocks is greater than zero;

an application programming interface (API) for

establishing a first set of pre-fetch parameters, wherein the first set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the first set of pre-fetch parameters is established in accordance with a first pre-fetch technique, and

the first pre-fetch technique is chosen from a plurality of pre-fetch techniques,

attempting to pre-fetch one or more of the plurality of data blocks from the data file,

using the user computer in accordance with the first set of pre-fetch parameters,

determining whether the attempting is successful,

in response to a determination that the attempting was unsuccessful,

establishing a second set of pre-fetch parameters, wherein the second set of pre-fetch parameters comprises at least two of alphabetical order, numerical order, an order according to a play list, and an order following instructions from the API,

the second set of pre-fetch parameters is not identical to the first set of pre-fetch parameters,

the second set of pre-fetch parameters is established in accordance with a second pre-fetch technique, and

the second pre-fetch technique is chosen from the plurality of pre-fetch techniques using the API;

a storage device for transmitting the data file to the user computer comprising;

a file system used by the application for accessing the data file;

a pre-fetching module, implemented by a processor, coupled to the file system for

pre-fetching at least one of the plurality of data blocks from the data file in accordance with either the first set of pre-fetch parameters or the second set of pre-fetch parameters; and

a buffer for storing the one or more pre-fetched data blocks, wherein the application is configured to access the one or more pre-fetched data blocks from the buffer.

12. The system of claim 11, wherein the application is a multimedia application for executing multimedia files.