Method and system for dynamically prefetching information via a server hierarchy

• US 6,085,193 A
• Filed: 09/29/1997
• Issued: 07/04/2000
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Malkin, Peter Kenneth, Yu, Philip Shi-lung
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/939,277
• Time in Patent Office: 1,009 Days
• Field of Search: 707/3, 707/10, 707/200, 707/104, 707/202, 707/204, 395/200.3, 364/281.5, 364/282.1, 364/282.4, 364/200.3, 364/2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for prefetching data for clients associated with a proxy server hierarchy and an enhanced content server data transfer to the clients. The method for prefetching data identifies data access patterns and prefetches select information based on a dynamic interpretation of the data access patterns. The content server or proxy server identifies data access reference patterns of clients associated with the content server or the proxy server hierarchy. The data access patterns are preferably stored in a statistics table. The content server generates prefetch hint information based on inputs from the statistics table. The prefetch hint information annotates requested information or objects requested by the clients. The prefetch hint information optimally is updated as the requested information passes through the proxy server hierarchy. The prefetch hint information annotates the requested information requested by the clients. The ultimate decision to prefetch select information for the clients is made based on the prefetch hint information and prefetch hint values. The prefetch hint value is calculated based on local node-specific factors, such as storage constraints and access time.

Claims

1. A processing system for enhancing a flow of data from servers to clients along a network, the processing system comprising:

proxy servers associated with the network;

a content server associated with the network;

clients configured for communicating with one or more of said proxy servers;

a statistics table being stored in at least one of said proxy servers, the statistics table storing parent object identifiers and associated child object identifiers, the statistics table containing first counts of parent objects, the first counts representing the frequency in which parent objects are referenced by the clients, the statistics table containing second counts of child objects, the second counts representing the frequency in which the corresponding child objects are referenced after select ones of said parent objects are referenced; and

generating means for generating a prefetch hint information list by accepting inputs of the first counts and the corresponding second counts to derive the prefetch hint information list, said generating means including;

calculating means for calculating a ratio of the second count to the first count for each of said parent object identifiers;

comparing means for comparing the ratio to a hint threshold, the comparing means grouping or associating child objects and associated parent objects on the prefetch hint information list if the ratio exceeded the hint threshold; and

prefetching means for prefetching child objects based on the prefetch hint information and parent objects actually requested by the clients, the prefetching means comprises a first prefetch handler being stored in at least one of said proxy servers;

the prefetching means including computing means for computing a prefetch value, and evaluating means for evaluating the prefetch value computed by the computing means;

said computing means computing a prefetch value for each child object identifier on the prefetch hint information list;

said evaluating means evaluating the prefetch values of multiple child objects and prioritizing the caching of child objects associated with the highest prefetch values on the prefetch hint information list, the first prefetch handler managing available space in a prefetch cache associated with one of said proxy servers.

2. The processing system of claim 1 wherein one of said proxy servers has a prefetch cache, and wherein the prefetching means prefetches child objects and stores the child objects in the prefetch cache based on a priority scheme, the priority scheme storing objects with a highest prefetch value first until available memory of the prefetch cache is filled, the prefetch value based upon an individual or aggregate reference probability to the child objects by one or more clients.

3. The processing system according to claim 1 wherein each of said proxy servers has a first processor, a first memory, and a first storage means for storing data;

the first memory having at least a logical separation between a first main cache and a first prefetch cache;

the content server having a second processor, a second memory, and a second storage means for storing data;

at least one of the clients having a third processor, a third memory, and a third storage means for storing data, the third memory having at least a logical separation between a second main cache and a second prefetch cache, the prefetch handling means storing child objects in the first prefetch cache or the second prefetch cache.

4. The processing system according to claim 1 further comprising:

statistics updating means for updating the statistics table based upon a child object actually requested;

the statistics updating means first searching for an identity of a referring one of said parent objects, the referring one, or referrer object, being referenced prior to the child object actually requested, the child object actually requested having its corresponding second count updated in the statistics table.

5. A processing system for enhancing a flow of data from servers to clients along a network, the processing system comprising:

proxy servers associated with the network;

a content server associated with the network;

clients configured for communicating with one or more of said proxy servers;

a statistics table being stored in at least one of said proxy servers, the statistics table storing parent object identifiers and associated child object identifiers, the statistics table containing first counts of parent objects, the first counts representing the frequency in which parent objects are referenced by the clients, the statistics table containing second counts of child objects, the second counts representing the frequency in which the corresponding child objects are referenced after select ones of said parent objects are referenced; and

generating means for generating a prefetch hint information list by accepting inputs of the first counts and the corresponding second counts to derive the prefetch hint information list, said generating means including;

calculating means for calculating a ratio of the second count to the first count for each of said parent object identifiers;

comparing means for comparing the ratio to a hint threshold, the comparing means grouping or associating child objects and associated parent objects on the prefetch hint information list if the ratio exceeded the hint threshold; and

prefetching means for prefetching child objects based on the prefetch hint information and parent objects actually requested by the clients, the prefetching means comprises a first prefetch handler being stored in at least one of said proxy serves and a second prefetch handler being stored in at least one of said clients, respectively;

the prefetching means including computing means for computing a prefetch value, and evaluating means for evaluating the prefetch value computed by the computing means;

said computing means computing a prefetch value for each child object identifier on the prefetch hint information list and prioritizing the caching of child objects with the highest prefetch values on the prefetch hint information list, the prefetch handling means managing available space in the prefetch cache.

6. The processing system of claim 5 wherein one of said proxy servers has a prefetch cache, and wherein the prefetching means prefetches child objects and stores the child objects in the prefetch cache based on a priority scheme, the priority scheme storing objects with a highest prefetch value first until available memory of the prefetch cache is filled, the prefetch value based upon an individual or aggregate reference probability to the child objects by one or more clients.

7. The processing system according to claim 5 wherein each of said proxy servers has a first processor, a first memory, and a first storage means for storing data;

the first memory having at least a logical separation between a first main cache and a first prefetch cache;

the content server having a second processor, a second memory, and a second storage means for storing data;

at least one of the clients having a third processor, a third memory, and a third storage means for storing data, the third memory having at least a logical separation between a second main cache and a second prefetch cache, the prefetch handling means storing child objects in the first prefetch cache or the second prefetch cache.

8. The processing system according to claim 5 further comprising:

statistics updating means for updating the statistics table based upon a child object actually requested;

the statistics updating means first searching for an identity of a referring one of said parent objects, the referring one, or referrer object, being referenced prior to the child object actually requested, the child object actually requested having its corresponding second count updated in the statistics table.

9. A processing system for enhancing a flow of data from servers to clients along a network, the processing system comprising:

proxy servers associated with the network;

a content server associated with the network;

clients configured for communicating with one or more of said proxy servers;

a statistics table being stored in at least one of said proxy servers, the statistics table storing parent object identifiers and associated child object identifiers, the statistics table containing first counts of parent objects, the first counts representing the frequency in which parent objects are referenced by the clients, the statistics table containing second counts of child objects, the second counts representing the frequency in which the corresponding child objects are referenced after select ones of said parent objects are referenced; and

generating means for generating a prefetch hint information list by accepting inputs of the first counts and the corresponding second counts to derive the prefetch hint information list, said generating means including;

calculating means for calculating a ratio of the second count to the first count for each of said parent object identifiers;

comparing means for comparing the ratio to a hint threshold, the comparing means grouping or associating child objects and associated parent objects on the prefetch hint information list if the ratio exceeded the hint threshold; and

prefetching means for prefetching child objects based on the prefetch hint information and parent objects actually requested by the clients, and

prefetch updating means for updating the prefetch hint information list;

the prefetch updating means comparing the first counts to first local threshold counts and second local threshold counts, the first local threshold counts based on statistics from one server, the second local threshold counts based on statistics from another server, said prefetch updating means invoking the generating means for each of the child object identifiers for which the first counts exceeds both the first local threshold counts and the second local threshold counts;

the prefetch updating means keeping the original prefetch hint information list if the first counts do not exceed the first local threshold counts.

10. The processing system of claim 9 further comprising:

statistics updating means for updating the statistics table;

a proxy object handler being stored in one of said proxy servers, the proxy object handler invoking a prefetch hint information list update routine, the proxy object handler returning a requested object to a lower level proxy server if the lower level proxy server requested the requested object, the proxy object hander returning the requested object and invoking the statistics updating means if the requested object is not a prefetch object;

a prefetch cache manager for managing a prefetch cache associated with one of said proxy servers, the proxy object handler invoking the prefetch cache manager if the lower level server did not request the requested object;

a proxy object request handler being stored one of said proxy servers, the proxy object request handler retuning objects to a requesting one of said clients and marking the object as deletable from the prefetch cache if objects are in the prefetch cache and if the object was requested pursuant to a prefetch request;

the proxy object request handler sending an object request to another server if the requested object is not in a main cache or the prefetch cache, the proxy object request handler communicating with the statistics updating means if the requested object is not associated with the prefetch request and if the requested object is located in the prefetch cache or the main cache.

11. The processing system according to claim 9 further comprising:

statistics updating means for updating the statistics table;

a prefetch referenced message handler being stored in one of said proxy servers, the prefetch referenced message handler invoking the statistics updating means, the prefetch referenced message handler forwards a prefetch referenced message after invoking a cache manager routine if a requested object is located in the prefetch cache.

12. The processing system of claim 9 wherein one of said proxy servers has a prefetch cache, and wherein the prefetching means prefetches child objects and stores the child objects in the prefetch cache based on a priority scheme, the priority scheme storing objects with a highest prefetch value first until available memory of the prefetch cache is filled, the prefetch value based upon an individual or aggregate reference probability to the child objects by one or more clients.

13. The processing system according to claim 9 wherein each of said proxy servers has a first processor, a first memory, and a first storage means for storing data;

the first memory having at least a logical separation between a first main cache and a first prefetch cache;

the content server having a second processor, a second memory, and a second storage means for storing data;

at least one of the clients having a third processor, a third memory, and a third storage means for storing data, the third memory having at least a logical separation between a second main cache and a second prefetch cache, the prefetch handling means storing child objects in the first prefetch cache or the second prefetch cache.

14. The processing system according to claim 9 further comprising:

statistics updating means for updating the statistics table based upon a child object actually requested;

the statistics updating means first searching for an identity of a referring one of said parent objects, the referring one, or referrer object, being referenced prior to the child object actually requested, the child object actually requested having its corresponding second count updated in the statistics table.

15. A processing system for enhancing a flow of data from servers to clients along a network, the processing system comprising:

proxy servers associated with the network;

a content server associated with the network;

clients configured for communicating with one or more of said proxy servers in order to request one object from another object, the one and another object coupled together by one of a plurality of logical links prior to providing said request;

a statistics table being stored in the content server and at least one of said proxy servers, the statistics table storing parent object identifiers and associated child object identifiers, the statistics table containing first counts of parent objects, the first counts representing the frequency in which parent objects are requested by one of said logical links by the clients, the statistics table containing second counts of child objects, the second counts representing the frequency in which the corresponding child objects are proximately, temporally referenced after select ones of said parent objects are referenced;

generating means accepting inputs of first counts, second counts, child object identifiers, and parent object identifiers from the statistics table, the generating means including evaluating means for evaluating the access relationship between parent objects and their associated child objects, the evaluating means placing child object identifiers on a prefetch hint information list if the child objects are referenced with adequate frequencies proximately and subsequently prior to references by the clients to corresponding parent objects, said generating means including;

calculating means for calculating ratios of the second counts to the first counts for each of said parent object identifiers, and

comparing means for individually comparing the ratios to a hint threshold, the comparing means grouping or associating child objects and associated parent objects on the prefetch hint information list for parent objects that exceed the hint threshold; and

prefetching means for prefetching child objects via one of said logical links based on the prefetch hint information and parent objects actually requested by the clients.

16. The system according to claim 15 wherein the generating means further comprises calculating means for calculating the adequate frequencies based on the ratio of child accesses to corresponding parent accesses.

17. The system according to claim 15 wherein the prefetching means further comprises assigning means for assigning storage priorities to child objects identified on the prefetch hint information list and selective storage means for storing select ones of the child objects in accordance with the storage priorities.

18. The system according to claim 15 wherein the assigning means assigns storage priorities based on an estimated access probability that a child object on the prefetch hint information list will be accessed by particular ones of the clients and an access cost of the child object based on requisite storage size for storing select ones of the child objects.